1237134
Thuật toán Berlekamp–Massey
https://vi.wikipedia.org/wiki?curid=1237134
Title: Thuật toán Berlekamp–Massey
Thuật toán Berlekamp–Massey là một thuật toán tìm bộ ghi dịch hồi tiếp tuyến tính (LFSR) ngắn nhất sinh ra một dãy nhị phân cho trước. Thuật toán cũng tìm ra đa thức nhỏ nhất của một quan hệ truy toán tuyến tính trên một trường bất kì.
Elwyn Berlekamp phát minh ra thuật toán này để giải mã mã Bose–Chaudhuri–Hocquenghem (BCH). James Massey phát hiện ra ứng dụng của nó cho bộ ghi dịch hồi tiếp tuyến tính và đơn giản hóa thuật toán. Massey gọi thuật toán là Thuật toán Tổng hợp LFSR (Thuật toán Lặp Berlekamp) , nhưng ngày nay nó được gọi là thuật toán Berlekamp–Massey.
Mô tả thuật toán.
Thuật toán Berlekamp–Massey là một phương pháp giải hệ các phương trình tuyến tính mô tả trong thuật toán giải mã Peterson cho mã Reed–Solomon, có thể tóm tắt như sau:
Dưới đây, C(x) là một trường hợp nhất định của Λ(x). Đa thức định vị lỗi C(x) cho "L" lỗi được định nghĩa là:
hay viết ngược lại:
Mục tiêu của thuật toán là tìm bậc "L" nhỏ nhất và đa thức C(x) sao cho:
với mọi giá trị hội chứng S đã cho, "n" = "L" to ("N"-1).
Thuật toán hoạt động như sau. Khởi tạo C(x) bằng 1, "L" là giả định số lượng lỗi hiện tại, khởi tạo bằng 0. "N" là số giá trị hội chứng. "n" là biến lặp chính và là chỉ số của giá trị hội chứng từ 0 đến ("N"-1). B(x) lưu giá trị cũ cuối cùng của C(x) mỗi lần "L" thay đổi, và được khởi tạo bằng 1. "b" lưu giá trị cũ cuối cùng của độ sai lệch "d" (giải thích ở dưới) mỗi lần "L" thay đổi, và được khởi tạo bằng 1. "m" là số lần lặp từ lần cuối "L", B(x), và "b" thay đổi và được khởi tạo bằng 1.
Trong mỗi lần lặp, thuật toán tính một giá trị sai lệch "d". Ở lần lặp thứ "k" giá trị đó là: