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

Mã Reed–Solomon
Đặt theo tên	Irving S. Reed và Gustave 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
Chiều dài khối	n = q − 1
Chiều dài thông điệp	k
Khoảng cách	n − k + 1
Kích thước bảng chữ cái	q = pm  (p nguyên tố)
Thuật toán
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. 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ử (x₁, x₂,..., x_n) 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_i.

$C=\{(f(x_{1}),f(x_{2}),\ldots ,f(x_{n}))|f\in F[x],deg(f)<k\}$

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_n) 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 α, α²,..., α^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 = αⁱ, 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ó f_i=p(αⁱ) 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 (f₀, f₁,..., f_n-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 v_i=0 với i=k,..., n-1,
• khi và chỉ khi q(αⁱ)=0 với i=1,..., n-k
• khi và chỉ khi (f₀, f₁,..., f_n-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

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

Bài chi tiết: Thuật toán Peterson–Gorenstein–Zierler

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).

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 đó α 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 đó e_i là hệ số của lũy thừa bậc i của x. Hệ số e_i 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 i_k 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í i_k, và giá trị lỗi ở các vị trí đó.

Định nghĩa các hội chứng S_j như sau

${\begin{aligned}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{aligned}}$

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 X_k và giá trị lỗi Y_k 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 X_k và có thể khó giải. Tuy nhiên nếu đã biết X_k 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 Y_k 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 X_k.

Đ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. (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-xX_{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{aligned}&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{aligned}}$

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

${\begin{aligned}&\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{aligned}}$

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 Y_k, hoặc dùng thuật toán Forney.

Thuật toán Berlekamp–Massey

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ụ

Xét mã Reed–Solomon định nghĩa trên GF(929) với α = 3 và t = 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}+809x^{3}+723x^{2}+568x+522$

Nếu đa thức thông điệp là p(x) = 3 x² + 2 x + 1, thì mã tự nhận giá trị sau.

$s_{r}(x)=p(x)\,x^{t}\mod g(x)=547x^{3}+738x^{2}+442x+455$

$s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+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)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+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à x₁ = 757 = 3⁻³ và x₂ = 562 = 3⁻⁴, ứ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}=546x+732\,$

$\Lambda '(x)=658x+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ừ e₁x³ và e₂x⁴ từ đa thức nhận được r để tìm ra mã tự ban đầu s.

Tham khảo

• Cipra, Barry A. (1993), “The Ubiquitous Reed–Solomon Codes”, SIAM News, 26 (1)
• Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy
• Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory, Laguna Hills, CA: Aegean Park Press, ISBN 0-89412-063-8
• Forney, Jr., G. (1965), “On Decoding BCH Codes”, IEEE Transactions on Information Theory, 11 (4): 549–557, doi:10.1109/TIT.1965.1053825
• Gill, John (2010), EE387 Bài giảng thứ 7, tài liệu thứ 28 (PDF), Stanford University, Bản gốc (PDF) lưu trữ ngày 30 tháng 6 năm 2014, truy cập ngày 24 tháng 3 năm 2012
• Hong, Jonathan; Vetterli, Martin (tháng 8 năm 1995), “Simple Algorithms for BCH Decoding”, IEEE Transactions on Communications, 43 (8): 2324–2333Quản lý CS1: ngày tháng và năm (liên kết)
• Koetter, Ralf (2005), Reed–Solomon Codes, Bài giảng 6.451 tại MIT (Video), Bản gốc lưu trữ ngày 13 tháng 3 năm 2013, truy cập ngày 24 tháng 3 năm 2012
• Lin, Shu; Costello, Jr., Daniel J. (1983), Error Control Coding: Fundamentals and Applications, New Jersey, NJ: Prentice-Hall, ISBN 0-13-283796-X
• MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company
• Massey, J. L. (1969), “Shift-register synthesis and BCH decoding” (PDF), IEEE Transactions on Information Theory, IT-15 (1): 122–127
• Peterson, Wesley W. (1960), “Encoding and Error Correction Procedures for the Bose-Chaudhuri Codes”, IRE Transactions on Information Theory, Institute of Radio Engineers, IT-6: 459–470
• Reed, Irving S.; Chen, Xuemin (1999), Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers
• 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
• Welch, L. R. (1997), The Original View of Reed–Solomon Codes (PDF), Bài giảng, Bản gốc (PDF) lưu trữ ngày 2 tháng 7 năm 2010, truy cập ngày 24 tháng 3 năm 2012