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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Mã Reed–Solomon
Đặt theo tên Irving S. ReedGustave Solomon
Phân loại
Cấp bậc Mã khối tuyến tính
Mã đa thức
Mã vòng
Mã BCH
Mã Reed–Solomon
Tham số
Chiều dài khối n = q − 1
Chiều dài thông điệp k
Khoảng cách nk + 1
Kích thước bảng chữ cái q = pm  (p nguyên tố)
Kí hiệu Mã [n, k, nk + 1]q
Thuật toán
Giải mã Berlekamp–Massey
Euclid
.
Tính chất
Mã khoảng cách cực đại

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. ReedGustave 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 BerlekampJames 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 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ư DVBATSC, và trong ứng dụng cho máy tính như hệ thống RAID 6.

Mô tả[sửa | sửa mã nguồn]

Định nghĩa ban đầu (truyền điểm)[sửa | sửa mã nguồn]

Cách định nghĩa đầu tiên của mã Reed-Solomon[1] 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) < k \}

trong đó F[x]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[sửa | sửa mã nguồn]

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[2][3].

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

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

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

Thuật toán lý thuyết[sửa | sửa mã nguồn]

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

Peterson (1960) đư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).[4]

Giải mã hội chứng[sửa | sửa mã nguồn]

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).[5]

s(x) = \sum_{i = 0}^{n-1}  c_i x^i
g(x) = \prod_{j=1}^{n-k} (x - \alpha^j),

trong đó α là một căn nguyên thủy của đơn 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 ở ν 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 ν, các vị trí ik, và giá trị lỗi ở các vị trí đó.

Định nghĩa các hội chứng Sj 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[sửa | sửa mã nguồn]

Định nghĩa định vị lỗi Xkgiá 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 − k ≥ 2ν phương trình trên 2ν ẩ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[sửa | sửa mã nguồn]

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. Welch 1997, tr. 10 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 ν

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

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

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

Thuật toán Berlekamp–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–Massey. Trong ví dụ dưới đây, C(x) được dùng để biểu diễn Λ(x).

Ví dụ[sửa | sửa mã nguồn]

Xét mã Reed–Solomon định nghĩa trên GF(929) với α = 3t = 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à p(x) = 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 α.

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.

n Sn+1 d C B b m
0 732 732 197 x + 1 1 732 1
1 637 846 173 x + 1 1 732 2
2 762 412 634 x2 + 173 x + 1 173 x + 1 412 1
3 925 576 329 x2 + 821 x + 1 173 x + 1 412 2

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−3x2 = 562 = 3−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ừ e1x3e2x4 từ đa thức nhận được r để tìm ra mã tự ban đầu s.

Ghi chú[sửa | sửa mã nguồn]

  1. ^ Reed, Irving S.; Solomon, Gustave (1960). “Polynomial Codes over Certain Finite Fields”. Journal of the Society for Industrial and Applied Mathematics (SIAM) 8 (2): 300–304. doi:10.1137/0108018. 
  2. ^ Berlekamp, Elwyn R. (1984) [1968]. Algebraic Coding Theory. Laguna Hills, CA: Aegean Park Press. ISBN 0894120638.  Đã bỏ qua tham số không rõ |ed= (trợ giúp)
  3. ^ Massey, J. L. (1969), “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory, IT-15 (1): 122–127 
  4. ^ Welch 1997, tr. 10
  5. ^ Welch (1997, tr. 5)

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