Thuật toán Forney

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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ã BCHmã 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[sửa | sửa mã nguồ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 [2] định nghĩa như sau:

\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à X1−1,..., Xν−1. Chúng là nghịch đảo của các vị trí lỗi 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 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 \alpha^{(c + 0)\,i_1} + e_2 \alpha^{(c + 0)\,i_2} + \cdots \,
s_1 = e_1 \alpha^{(c + 1)\,i_1} + e_2 \alpha^{(c + 1)\,i_2} + \cdots \,
 \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]

\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]

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]

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:

e_j = - \frac{\Omega(X_j^{-1})}{\Lambda'(X_j^{-1})}

Đạo hàm hình thức[sửa | sửa mã nguồn]

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]

\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[sửa | sửa mã nguồn]

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

\Gamma(x) = \prod (1- x \, \alpha^{j_i})

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

\Psi(x) = \Lambda(x) \, \Gamma(x)

Xem thêm[sửa | sửa mã nguồn]

Tài liệu tham khảo[sửa | sửa mã nguồn]

  1. ^ Forney 1965
  2. ^ Gill 2010, tr. 24
  3. ^ a ă â Gill 2010, tr. 47
  4. ^ Gill 2010, tr. 48