Kỹ thuật sửa lỗi Reed–Solomon

Định nghĩa ban đầu (truyền điểm)

Cách định nghĩa đầu tiên của mã Reed-Solomon là mã hóa k ký hiệu bằng cách xem chúng như hệ số của một đa thức p(x) bậc k-1 trên một trường hữu hạn kích thước N, và tính giá trị của đa thức đó tại n>k điểm. Tính giá trị của một đa thức bậc k-1 tại hơn k điểm tạo ra một hệ phương trình nhiều phương trình hơn số ẩn số, đo đó cho phép tìm lại k hệ số từ n giá trị thông qua nội suy. n có thể nhận mọi giá trị không quá N.
Giả sử (x₁, x₂,..., xₙ) là một danh sách gồm n phần tử khác nhau của trường F. Bộ mã C được tạo từ các dãy n phần tử nhận được từ việc tính giá trị một đa thức bậc nhỏ hơn k bất kì trên trường F tại các giá trị xᵢ.
trong đó F[x] là vành đa thức trên F, và k, n được chọn sao cho 1≤ k ≤ n ≤ N.
Giả sử α là một phần tử sinh của nhóm nhân của F. Dãy (x₁, x₂,..., xₙ) với n=N có thể được chọn là
.
Khi loại bỏ 0 khỏi dãy trên, do αᴺ⁻¹ = 1, với mọi đa thức p(x), đa thức p(αx) cũng là một đa thức cùng bậc, và mã của nó chính là mã của p(x) xoay trái một vị trí. Do đó mã Reed-Solomon có thể được xem là một mã vòng.

Định nghĩa cổ điển dưới dạng mã BCH

Mỗi ký hiệu mã có thể được xem là một hệ số của đa thức tích s(x) bằng tích của đa thức nguồn p(x) với một đa thức sinh g(x) bậc t=N-k-1. Giả sử  là một phần tử sinh của nhóm nhân trong trường hữu hạn đã cho. Đa thức sinh g(x) được định nghĩa là đa thức có  là nghiệm.
Người gửi gửi đi N-1 hệ số của s(x)=p(x)g(x) và người nhận chia đa thức nhận được cho đa thức g(x) để xác định xem mã nhận được có lỗi hay không. Nếu phần dư khác không thì mã nhận được có lỗi. Đặt r(x) là đa thức dư của phép chia trên. Người nhận có thể tính giá trị của r(x) tại các nghiệm của g(x) và xây dựng một hệ phương trình để tìm ra các lỗi.
Mã Reed-Solomon là một trường hợp đặc biệt của một lớp rộng hơn, gọi là mã BCH. Thuật toán Berlekamp-Massey được thiết kế để giải mã cho mã BCH, và do đó cũng dùng được cho mã Reed-Solomon. Có thể thấy mã Reed-Solomon là một trường hợp đặc biệt của mã BCH dễ dàng hơn trong một định nghĩa khác của mã Reed-Solomon sau đây.
Cho trước một trường F kích thước q. Giả sử n = q-1 và α là một phần tử sinh của nhóm nhân của F. Cũng giả sử được cho trước 1≤ k ≤ n. Mã Reed-Solomon với các tham số trên có chứa mã tự  khi và chỉ khi  là nghiệm của đa thức
Với định nghĩa này, rõ ràng mã Reed-Solomon là một mã đa thức, và cụ thể hơn là một mã BCH. Đa thức sinh g(x) là đa thức nhỏ nhất với nghiệm α, α²,..., αⁿ⁻ᵏ, và các mã tự chính là các đa thức chia hết cho g(x).

Tính chất

Mã Reed-Solomon là một mã [n, k, n-k+1]. Cụ thể hơn, nó là một mã tuyến tính độ dài n (trên trường F) với k chiều, và khoảng cách Hamming nhỏ nhất là n-k+1. Mã Reed-Solomon là tối ưu theo nghĩa khoảng cách nhỏ nhất là lớn nhất có thể cho mọi mã tuyến tính kích thước (n, k); đây gọi là giới hạn Singleton. Những mã đạt tới giới hạn Singleton gọi là mã khoảng cách cực đại.

Thuật toán lý thuyết

Reed & Solomon (1960) mô tả một thuật toán giải mã để tìm ra đa thức phù hợp nhất. Thuật toán cho mã RS  kiểm tra tất cả mọi bộ  ký hiệu trong số  ký hiệu nhận được. Nói chung, để có thể giải mã thì cần nhận được ít nhất  ký hiệu đúng, và đây cũng chính là số ký hiệu cần thiết để nội suy ra đa thức thông điệp. Thuật toán giải mã thử nội suy mọi bộ  ký hiệu và so sánh giá trị của đa thức thu được ở các vị trí khác với giá trị nhận được. Đa thức nào cho giá trị đúng ở nhiều vị trí nhất chính là đa thức thông điệp. Tuy nhiên số tập hợp con gồm  ký hiệu là rất lớn nên thuật toán này không có giá trị thực tiễn. Số tập hợp con là , quá lớn với ngay cả những mã khá nhỏ. Để sửa 3 lỗi của mã , thuật toán phải kiểm tra 359 tỉ tập hợp con.

Tìm định vị lỗi từ đa thức định vị lỗi

Từ các hệ số Λᵢ tìm được ở bước trên, ta thu được đa thức định vị lỗi. Có thể tìm các nghiệm của đa thức định vị lỗi bằng các thử tất cả mọi giá trị có thể. Có thể tính các định vị lỗi (và do đó các vị trí lỗi) từ các nghiệm. Tìm kiếm Chien là một thuật toán hiệu quả cho bước này.

Tính giá trị lỗi

Sau khi đã tìm ra các vị trí lỗi, có thể tìm ra các giá trị lỗi và sửa chúng. Có thể giải hệ phương trình ở trên để tính Yₖ, hoặc dùng thuật toán Forney.