1239190
Thuật toán Forney
https://vi.wikipedia.org/wiki?curid=1239190
Title: 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"0, "s"1... 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à "X"1−1..., "X""ν"−1. Chúng là nghịch đảo của các vị trí lỗi formula_2.
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 formula_3 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à