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.^[1]

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ị s₀, s₁,... 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 ^[2] định nghĩa như sau:

${\displaystyle \Lambda (x)=\prod _{i=1}^{\nu }(1-x\,X_{i})=1+\sum _{i=1}^{\nu }\lambda _{i}\,x^{i}}$

Các nghiệm của Λ(x) là X₁⁻¹,..., X_ν⁻¹. Chúng là nghịch đảo của các vị trí lỗi ${\displaystyle X_{j}=\alpha ^{i_{j}}}$.

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 ${\displaystyle e_{j}}$ luôn có thể được tính bằng cách giải hệ phương trình tuyến tính

${\displaystyle s_{0}=e_{1}\alpha ^{(c+0)\,i_{1}}+e_{2}\alpha ^{(c+0)\,i_{2}}+\cdots \,}$

${\displaystyle s_{1}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \,}$

${\displaystyle \cdots \,}$

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^[3]

${\displaystyle \Omega (x)=S(x)\,\Lambda (x){\pmod {x^{2t}}}\,}$

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

${\displaystyle S(x)=s_{0}x^{0}+s_{1}x^{1}+s_{2}x^{2}+\cdots +s_{c+2t-1}x^{2t-1}.}$

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

${\displaystyle e_{j}=-{\frac {X_{j}^{1-c}\,\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}\,}$

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

${\displaystyle e_{j}=-{\frac {\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}}$

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

Bài chi tiết: Đạ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):^[3]

${\displaystyle \Lambda '(x)=\sum _{i=1}^{\nu }i\,\cdot \,\lambda _{i}\,x^{i-1}}$

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à

${\displaystyle \Gamma (x)=\prod (1-x\,\alpha ^{j_{i}})}$

Trong đó vị trí xóa được biểu diễn bởi j_i. Á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

${\displaystyle \Psi (x)=\Lambda (x)\,\Gamma (x)}$

Xem thêm

• Mã BCH
• Kỹ thuật sửa lỗi Reed–Solomon

Tham khảo

1. Forney 1965Lỗi harv: không có mục tiêu: CITEREFForney1965 (trợ giúp)
2. Gill 2010, tr. 24
3. ^ Gill 2010, tr. 47
4. Gill 2010, tr. 48

• Forney, Jr., G. (1965), “On Decoding BCH Codes”, IEEE Transactions on Information Theory, 11 (4): 549–557, doi:10.1109/TIT.1965.1053825, ISSN 0018-9448
• Gill, John (2010), EE387 Notes #7, Handout #28 (PDF), Stanford University, tr. 42–45, Bản gốc (PDF) lưu trữ ngày 30 tháng 6 năm 2014, truy cập ngày 18 tháng 4 năm 2012 Đã định rõ hơn một tham số trong |accessdate= và |access-date= (trợ giúp)
• Sách của W. Wesley Peterson