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

Trong lý thuyết mã hóa, mã Reed-Solomon (RS) là một mã vòng sửa lỗi tuyến tính phát minh bởi Irving S. Reed và Gustave Solomon. Bằng cách thêm vào t ký hiệu kiểm tra, mã RS có thể nhận ra không quá t ký hiệu lỗi và sửa không quá ⌊t/2⌋ ký hiệu lỗi. Dưới dạng mã xóa, nó có thể sửa không quá t ký hiệu bị xóa ở các vị trí đã biết, hoặc nhận dạng và sửa cả ký hiệu lỗi và ký hiệu bị xóa. Ngoài ra, mã RS còn hữu hiệu cho việc sửa nhiều bit lỗi liên tiếp, do một dãy b+1 bit bị lỗi liên tiếp chỉ có thể ảnh hưởng đến hai ký hiệu có kích thước b. Tham số t có thể được chọn tùy ý tùy theo người thiết kế mã trong một giới hạn khá rộng.

Trong mã hóa Reed-Solomon, các ký hiệu là các hệ số của một đa thức p(x) trên một trường hữu hạn. Ý tưởng ban đầu của mã RS là tạo ra n ký hiệu mã từ k ký hiệu nguồn bằng cách tính p(x) tại n>k điểm, truyền tải n giá trị này, và dùng kĩ thuật nội suy để xây dựng lại các ký hiệu nguồn. Thay vào đó, mã RS cũng có thể được xem là mã vòng BCH, trong đó các ký hiệu mã được xây dựng từ hệ số của đa thức tích của p(x) và một đa thức sinh. Cách nhìn này dẫn đến thuật toán giải mã hiệu quả do Elwyn Berlekamp và James Massey, được gọi là thuật toán giải mã Berlekamp-Massey.

Mã Reed-Solomon có rất nhiều ứng dụng quan trọng, từ liên lạc trong không gian tới đồ điện tử gia dụng. Chúng được sử dụng trong các thiết bị điện tử như CD, DVD, đĩa Blu-ray, trong Mã QR, trong công nghệ truyền dẫn dữ liệu như DSL, WiMAX, trong hệ thống phát thanh truyền hình như DVB và ATSC, và trong ứng dụng cho máy tính như hệ thống RAID 6.

Mô tả
Đị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ử (x1, x2,..., xn) 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ị xi.

C = \{(f(x_1), f(x_2), \ldots, f(x_n))|f\in F[x], deg(f)

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 (x1, x2,..., xn) với n=N có thể được chọn là
(0, \alpha^0, \alpha^1, \ldots, \alpha^{N-2}.

Khi loại bỏ 0 khỏi dãy trên, do αN−1 = 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ử \alpha 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ó \alpha, \alpha^2, \ldots, \alpha^t là nghiệm.

g(x)=(x-\alpha)(x-\alpha^2)\cdots(x-\alpha^t) = g_0 + g_1 x + \cdots+g_{t-1}x^{t-1}+x^t

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ự (f_0, f_1, \ldots, f_{n-1}) khi và chỉ khi \alpha, \alpha^2, \ldots, \alpha^{n-k} là nghiệm của đa thức
p(x) = f_0 + f_1 x + \cdots + f_{n-1}x^{n-1}

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 α, α2,..., αn-k, và các mã tự chính là các đa thức chia hết cho g(x).

Sự tương đương của hai định nghĩa
Thoạt nhìn, hai định nghĩa của mã Reed-Solomon là rất khác nhau.

Sự tương đương của hai định nghĩa có thể chứng minh bằng biến đổi Fourier rời rạc. Phép biến đổi này cho thấy sự đối ngẫu giữa hệ số của một đa thức và giá trị của nó. Tính đối ngẫu này có thể được tóm tắt như sau: giả sử p(x) và q(x) là hai đa thức bậc không quá n. Nếu các giá trị của p(x) là các hệ số của q(x) thì với một tỉ lệ và hoán vị thích hợp, các giá trị của q(x) chính là các hệ số của p(x). Cụ thể hơn, giả sử α là một căn bậc n nguyên thủy của đơn vị. Các giá trị được tính tại x = αi, với i=0, 1,..., n-1. Giả sử

p(x)=v_0 + v_1 x + v_2 x^2 + \cdots+v_{n-1}x^{n-1},

q(x)=f_0 + f_1 x + f_2 x^2 + \cdots+f_{n-1}x^{n-1}

và giả sử p(x) và q(x) được liên hệ bởi phép biến đổi Fourier rời rạc. Khi đó, với mọi i=0, 1,..., n-1, ta có fi=p(αi) và v_i = \frac{1}{n} q(\alpha^{n-i}).

Sử dụng các tính chất này ta nhận thấy (f0, f1,..., fn-1) là một mã tự của mã Reed-Solomon theo định nghĩa thứ nhất
khi và chỉ khi p(x) có bậc nhỏ hơn k
khi và chỉ khi vi=0 với i=k,..., n-1,
khi và chỉ khi q(αi)=0 với i=1,..., n-k
khi và chỉ khi (f0, f1,..., fn-1) là một mã tự của mã Reed-Solomon theo định nghĩa thứ hai.

Do đó, hai định nghĩa là tương đương.

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.

Các thuật toán giải mã
Thuật toán lý thuyết

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 (n,k) kiểm tra tất cả mọi bộ k ký hiệu trong số n ký hiệu nhận được. Nói chung, để có thể giải mã thì cần nhận được ít nhất k 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 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 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à \textstyle \binom{n}{k} = {n! \over (n-k)! k!}, quá lớn với ngay cả những mã khá nhỏ. Để sửa 3 lỗi của mã (255,249), thuật toán phải kiểm tra 359 tỉ tập hợp con.

Thuật toán giải mã Peterson

đưa ra một thuật toán giải mã hiệu quả dựa trên giải mã hội chứng. Berlekamp sau đó đã cải tiến thuật toán này (mô tả dưới đây).

Giải mã hội chứng

Có thể xem thông điệp gửi đi là các hệ số của một đa thức s(x) chia hết cho đa thức sinh g(x).
:s(x) = \sum_{i = 0}^{n-1} c_i x^i
:g(x) = \prod_{j=1}^{n-k} (x - \alpha^j),

trong đó &alpha; là một căn nguyên thủy của đơn vị.

Vì s(x) chia hết cho g(x), nên
:s(\alpha^i) = 0, \ i=1,2,\ldots,n-k

Đa thức truyền đi được cộng thêm một đa thức lỗi e(x) để tạo thành đa thức nhận được r(x).
:r(x) = s(x) + e(x)
:e(x) = \sum_{i=0}^{n-1} e_i x^i

Trong đó ei là hệ số của lũy thừa bậc i của x. Hệ số ei bằng không nếu không có lỗi ở vị trí i và khác không nếu có lỗi. Nếu có lỗi ở &nu; lũy thừa khác nhau ik của x, thì

:e(x) = \sum_{k=1}^\nu e_{i_k} x^{i_k}

Mục tiêu của thuật toán là tìm ra &nu;, các vị trí ik, và giá trị lỗi ở các vị trí đó.

Định nghĩa các hội chứng S'j như sau
:
\begin{align}
S_j &= r(\alpha^j) = s(\alpha^j) + e(\alpha^j) = 0 + e(\alpha^j) = e(\alpha^j), \ j=1,2,\ldots,n-k \\
&= \sum_{k=1}^{\nu} e_{i_k} \left(\alpha^{j} \right)^{i_k}
\end{align}

Lợi thế của việc xét các hội chứng là chúng chỉ phụ thuộc vào đa thức lỗi, không phụ thuộc thông điệp.

Định vị lỗi và giá trị lỗi

Định nghĩa định vị lỗi Xk và giá trị lỗi Yk như sau:
: X_k = \alpha^{i_k}, \ Y_k = e_{i_k}

Khi đó có thể viết các hội chứng bằng định vị lỗi và giá trị lỗi như sau:
: S_j = \sum_{k=1}^{\nu} Y_k X_k^{j}

Các hội chứng cho ta n&nbsp;&minus;&nbsp;k ≥ 2&nu; phương trình trên 2&nu; ẩn, nhưng các phương trình này không tuyến tính theo Xk và có thể khó giải. Tuy nhiên nếu đã biết Xk thì hệ các phương trình hội chứng là một hệ phương trình tuyến tính của các giá trị lỗi Yk và có thể giải dễ dàng.

:\begin{bmatrix}
X_1^1 & X_2^1 & \cdots & X_\nu^1 \\
X_1^2 & X_2^2 & \cdots & X_\nu^2 \\
\vdots & \vdots && \vdots \\
X_1^{n-k} & X_2^{n-k} & \cdots & X_\nu^{n-k} \\
\end{bmatrix}
\begin{bmatrix}
Y_1 \\ Y_2 \\ \vdots \\ Y_\nu
\end{bmatrix}
=
\begin{bmatrix}
S_1 \\ S_2 \\ \vdots \\ S_{n-k}
\end{bmatrix}

Vì vậy vấn đề chính là tìm ra Xk.

Đa thức định vị lỗi

Peterson tìm ra một quan hệ truy toán tuyến tính dẫn đến một hệ phương trình tuyến tính.
Nếu giải hệ này thì có thể tìm ra các định vị lỗi.

Định nghĩa đa thức vị trí lỗi Λ(x) như sau

:\Lambda(x) = \prod_{k=1}^\nu (1 - x X_k) = 1 + \Lambda_1 x^1 + \Lambda_2 x^2 + \cdots + \Lambda_\nu x^\nu

Các nghiệm của Λ(x) là các nghịch đảo của X_k^{-1}:
: \Lambda(X_k^{-1}) = 0

:\Lambda(X_k^{-1}) = 1 + \Lambda_1 X_k^{-1} + \Lambda_2 X_k^{-2} + \cdots + \Lambda_\nu X_k^{-\nu} = 0

Nhân cả hai vế với Y_k X_k^{j+\nu} và giá trị nhận được vẫn là 0.

:
\begin{align}
& Y_k X_k^{j+\nu} \Lambda(X_k^{-1}) = 0. \\
\text{N}\hat{\mbox{e}}\text{n } & Y_k X_k^{j+\nu} + \Lambda_1 Y_k X_k^{j+\nu} X_k^{-1} + \Lambda_2 Y_k X_k^{j+\nu} X_k^{-2} + \cdots + \Lambda_{\nu} Y_k X_k^{j+\nu} X_k^{-\nu} = 0, \\
\text{hay } & Y_k X_k^{j+\nu} + \Lambda_1 Y_k X_k^{j+\nu-1} + \Lambda_2 Y_k X_k^{j+\nu -2} + \cdots + \Lambda_{\nu} Y_k X_k^j = 0 \\
\end{align}

Cộng các đẳng thức trên cho k = 1 đến &nu;

:\begin{align}
& \sum_{k=1}^\nu (Y_k X_k^{j+\nu} + \Lambda_1 Y_k X_k^{j+\nu-1} + \Lambda_2 Y_k X_k^{j+\nu -2} + \cdots + \Lambda_{\nu} Y_k X_k^{j}) = 0 \\
& \sum_{k=1}^\nu (Y_k X_k^{j+\nu}) + \Lambda_1 \sum_{k=1}^\nu (Y_k X_k^{j+\nu-1}) + \Lambda_2 \sum_{k=1}^\nu (Y_k X_k^{j+\nu -2}) + \cdots + \Lambda_\nu \sum_{k=1}^\nu (Y_k X_k^j) = 0
\end{align}

Rút gọn đẳng thức trên, ta thu được

: S_{j + \nu} + \Lambda_1 S_{j+\nu-1} + \cdots + \Lambda_{\nu-1} S_{j+1} + \Lambda_{\nu} S_j = 0 \,

: S_j \Lambda_{\nu} + S_{j+1}\Lambda_{\nu-1} + \cdots + S_{j+\nu-1} \Lambda_1 = - S_{j + \nu} \

Đây là một hệ phương trình tuyến tính mà giải nó cho ta các hệ số Λi của đa thức định vị lỗi:

:\begin{bmatrix}
S_1 & S_2 & \cdots & S_{\nu} \\
S_2 & S_3 & \cdots & S_{\nu+1} \\
\vdots & \vdots && \vdots \\
S_{\nu} & S_{\nu+1} & \cdots & S_{2\nu-1}
\end{bmatrix}
\begin{bmatrix}
\Lambda_{\nu} \\ \Lambda_{\nu-1} \\ \vdots \\ \Lambda_1
\end{bmatrix}
=
\begin{bmatrix}
- S_{\nu+1} \\ - S_{\nu+2} \\ \vdots \\ - S_{\nu+\nu}
\end{bmatrix}

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

Từ các hệ số Λi 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 Yk, hoặc dùng thuật toán Forney.

Thuật toán Berlekamp&ndash;Massey
Thuật toán Berlekamp&ndash;Massey là một thuật toán lặp để tìm lỗi. Trong mỗi lần lặp, thuật toán tính một giá trị sai lệch dựa trên giá trị hiện thời của Λ(x) và số lượng lỗi giả định e:

: \Delta = S_{i} + \Lambda_1 \ S_{i-1} + \cdots + \Lambda_e \ S_{i-e}

sau đó điều chỉnh Λ(x) và e sao cho giá trị Δ bằng không. Xem mô tả chi tiết thủ tục lặp ở thuật toán Berlekamp&ndash;Massey. Trong ví dụ dưới đây, C(x) được dùng để biểu diễn Λ(x).

Ví dụ

Xét mã Reed&ndash;Solomon định nghĩa trên với 3}} và 4}} (mã này thường dùng cho mã vạch PDF417). Đa thức sinh là
:g(x) = (x-3)(x-3^2)(x-3^3)(x-3^4) = x^4+809 x^3+723 x^2+568 x+522
Nếu đa thức thông điệp là 3 x2 + 2 x + 1}}, thì mã tự nhận giá trị sau.
:s_r(x) = p(x) \, x^t \mod g(x) = 547 x^3 + 738 x^2 + 442 x + 455
:s(x) = p(x) \, x^t - s_r(x) = 3 x^6 + 2 x^5 + 1 x^4 + 382 x^3 + 191 x^2 + 487 x + 474
Lỗi trong quá trình truyền có thể khiến cho đa thức nhận được trở thành
:r(x) = s(x) + e(x) = 3 x^6 + 2 x^5 + 123 x^4 + 456 x^3 + 191 x^2 + 487 x + 474
Các hội chứng là các giá trị của r tại các lũy thừa của &alpha;.
:S_1 = r(3^1) = 3\cdot 3^6 + 2\cdot 3^5 + 123\cdot 3^4 + 456\cdot 3^3 + 191\cdot 3^2 + 487\cdot 3 + 474 = 732
:S_2 = r(3^2) = 637,\;S_3 = r(3^3) = 762,\;S_4 = r(3^4) = 925
Để sửa lỗi, dùng thuật toán Berlekamp–Massey để tính đa thức định vị lỗi.

Giá trị cuối cùng của C là đa thức định vị lỗi, Λ(x). Có thể tìm các nghiệm bằng cách thử mọi giá trị. Các nghiệm là x1 = 757 = 3&minus;3 và x2 = 562 = 3&minus;4, ứng với các vị trí lỗi. Để tìm ra giá trị lỗi, áp dụng thuật toán Forney.
:\Omega(x) = S(x) \Lambda(x) \mod x^4 = 546 x + 732\,
:\Lambda'(x) = 658 x + 821\,
:e_1 = -\Omega(x_1)/\Lambda'(x_1) = -649/54 = 280 \times 843 = 74\,
:e_2 = -\Omega(x_2)/\Lambda'(x_2) = 122\,
Trừ e1x3 và e2x4 từ đa thức nhận được r để tìm ra mã tự ban đầu s.

Ghi chú

Tham khảo

|first1=Shu
|last1=Lin
|first2=Daniel J.
|last2=Costello, Jr.
|title=Error Control Coding: Fundamentals and Applications
|location=New Jersey, NJ
|publisher=Prentice-Hall
|year=1983
|isbn=0-13-283796-X
}}