✨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ị 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 định nghĩa như sau:

:$\backslash Lambda(x)\; =\; \backslash prod\_\{i=1\}^\backslash nu\; (1-\; x\; \backslash ,\; 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 $X\_j\; =\; \backslash 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 $e\_j$ luôn có thể được tính bằng cách giải hệ phương trình tuyến tính

:$s\_0\; =\; e\_1\; \backslash alpha^\{(c\; +\; 0)\backslash ,i\_1\}\; +\; e\_2\; \backslash alpha^\{(c\; +\; 0)\backslash ,i\_2\}\; +\; \backslash cdots\; \backslash ,$ :$s\_1\; =\; e\_1\; \backslash alpha^\{(c\; +\; 1)\backslash ,i\_1\}\; +\; e\_2\; \backslash alpha^\{(c\; +\; 1)\backslash ,i\_2\}\; +\; \backslash cdots\; \backslash ,$ :$\backslash cdots\; \backslash ,$

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

:$\backslash Omega(x)\; =\; S(x)\backslash ,\backslash Lambda(x)\; \backslash pmod\{x^\{2t\; \backslash ,$

Trong đó S(x) là một phần đa thức hội chứng: :$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:

:$e\_j\; =\; -\; \backslash frac\{X\_j^\{1-c\}\; \backslash ,\; \backslash Omega(X\_j^\{-1\})\}\{\backslash Lambda\text{'}(X\_j^\{-1\})\}\; \backslash ,$

Với mã BCH nghĩa hẹp, c = 1, nên biểu thức trên trở thành: :$e\_j\; =\; -\; \backslash frac\{\backslash Omega(X\_j^\{-1\})\}\{\backslash Lambda\text{'}(X\_j^\{-1\})\}$

Đạ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): :$\backslash Lambda\text{'}(x)\; =\; \backslash sum\_\{i=1\}^\{\backslash nu\}\; i\; \backslash ,\; \backslash cdot\; \backslash ,\; \backslash lambda\_i\; \backslash ,\; 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à :$\backslash Gamma(x)\; =\; \backslash prod\; (1-\; x\; \backslash ,\; \backslash 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 :$\backslash Psi(x)\; =\; \backslash Lambda(x)\; \backslash ,\; \backslash Gamma(x)$