Thuật toán Forney

Trong lý thuyết mã hóa, thuật toán Forney là một thuật toán để tính các giá trị lỗi khi đã biết các vị trí lỗi. Nó là một bước trong việc giải mã mã BCH và mã Reed–Solomon (một lớp con của mã BCH). George David Forney, Jr. đã xây dựng thuật toán này.

Mô tả thuật toán

Có thể xem các từ mã của mã BCH là các đa thức. Theo định nghĩa, đa thức sinh có các nghiệm αc, αc+1,..., αc+d−2. Đặt t=(d-1)/2 là số lỗi cần sửa.

Từ thông điệp nhận được, có thể tính các giá trị s0, s1,... gọi là các giá trị hội chứng.
Việc giải mã sử dụng khái niệm đa thức định vị lỗi  định nghĩa như sau:

Các nghiệm của Λ(x) là X1−1,..., Xν−1. Chúng là nghịch đảo của các vị trí lỗi .

Khi đã biết các vị trí lỗi, bước tiếp theo là tính các giá trị lỗi ở các vị trí này. Các giá trị lỗi được dùng để sửa giá trị nhận được và thu được từ mã ban đầu.

Một cách tổng quát, các giá trị lỗi  luôn có thể được tính bằng cách giải hệ phương trình tuyến tính

Tuy nhiên, có thể tính nhanh hơn bằng cách sử dụng thuật toán Forney dựa trên nội suy Lagrange. Đầu tiên tính đa thức tính giá trị lỗi

Trong đó S(x) là một phần đa thức hội chứng:

Sau đó có thể tính các giá trị lỗi như sau:

Với mã BCH nghĩa hẹp, c = 1, nên biểu thức trên trở thành:

Đạo hàm hình thức

Λ'(x) là đạo hàm hình thức của đa thức định vị lỗi Λ(x):

Trong biểu thức trên, i là một số tự nhiên, và λi là một phần tử của trường hữu hạn. Toán tử · biểu diễn phép nhân thông thường (lặp đi lặp lại phép cộng trong trường hữu hạn) và không phải là phép nhân trong trường hữu hạn.

Xem chi tiết cách suy ra biểu thức trên cho giá trị lỗi ở nội suy Lagrange.

Lỗi xóa

Định nghĩa đa thức định vị xóa là

Trong đó vị trí xóa được biểu diễn bởi ji. Áp dụng thuật toán trên, thay Γ vào vị trí của Λ.

Nếu có cả lỗi thay đổi và lỗi xóa thì dùng đa thức định vị lỗi và xóa sau

Xem thêm
Mã BCH
Kỹ thuật sửa lỗi Reed–Solomon

Tham khảo

 Sách của W. Wesley Peterson

Phát hiện và sửa lỗi
Lý thuyết mã hóa