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.

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à

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ử $\backslash 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ó $\backslash alpha,\; \backslash alpha^2,\; \backslash ldots,\; \backslash alpha^t$ 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ự $(f\_0,\; f$1, \ldots, f{n-1}) khi và chỉ khi $\backslash alpha,\; \backslash alpha^2,\; \backslash ldots,\; \backslash alpha^\{n-k\}$ 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 α, α²,..., α^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ử

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\; =\; \backslash frac\{1\}\{n\}\; q(\backslash 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

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à $\backslash textstyle\; \backslash binom\{n\}\{k\}\; =\; \{n!\; \backslash 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)\; =\; \backslash sum\_\{i\; =\; 0\}^\{n-1\}\; c$i x^i :$g(x)\; =\; \backslash 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(\backslash alpha^i)\; =\; 0,\; \backslash \; i=1,2,\backslash 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)\; =\; \backslash 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)\; =\; \backslash 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 :$\backslash 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 X_k và giá trị lỗi Y_k như sau: :$X\_k\; =\; \backslash alpha^\{i\_k\},\; \backslash \; 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.

:2^1 & \cdots & X\nu^1 \ X_1^2 & X2^2 & \cdots & X\nu^2 \ \vdots & \vdots && \vdots \ X_1^{n-k} & X2^{n-k} & \cdots & X\nu^{n-k} \ \end{bmatrix} \begin{bmatrix} Y_1 \ Y2 \ \vdots \ Y\nu \end{bmatrix}

\begin{bmatrix} S_1 \ S2 \ \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. 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

:$\backslash Lambda(x)\; =\; \backslash prod\_\{k=1\}^\backslash nu\; (1\; -\; x\; X\_k)\; =\; 1\; +\; \backslash Lambda\_1\; x^1\; +\; \backslash 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\}$: :$\backslash Lambda(X\_k^\{-1\})\; =\; 0$

:$\backslash Lambda(X\_k^\{-1\})\; =\; 1\; +\; \backslash Lambda\_1\; X\_k^\{-1\}\; +\; \backslash Lambda\_2\; X$k^{-2} + \cdots + \Lambda\nu X_k^{-\nu} = 0

Nhân cả hai vế với $Y\_k\; X\_k^\{j+\backslash nu\}$ và giá trị nhận được vẫn là 0.

: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 Xk^{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 ν

:k^{j+\nu -2} + \cdots + \Lambda{\nu} Y_k Xk^{j}) = 0 \ & \sum{k=1}^\nu (Y_k X_k^{j+\nu}) + \Lambda1 \sum{k=1}^\nu (Y_k X_k^{j+\nu-1}) + \Lambda2 \sum{k=1}^\nu (Y_k Xk^{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\; +\; \backslash nu\}\; +\; \backslash 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} \Lambda1 = - 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:

:2 & \cdots & S{\nu} \ S_2 & S3 & \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:

:$\backslash Delta\; =\; S\_\{i\}\; +\; \backslash Lambda$1 \ S{i-1} + \cdots + \Lambdae \ 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 với và (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à , thì mã tự nhận giá trị sau. :$s\_r(x)\; =\; p(x)\; \backslash ,\; x^t\; \backslash mod\; g(x)\; =\; 547\; x^3\; +\; 738\; x^2\; +\; 442\; x\; +\; 455$ :$s(x)\; =\; p(x)\; \backslash ,\; 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\backslash cdot\; 3^6\; +\; 2\backslash cdot\; 3^5\; +\; 123\backslash cdot\; 3^4\; +\; 456\backslash cdot\; 3^3\; +\; 191\backslash cdot\; 3^2\; +\; 487\backslash cdot\; 3\; +\; 474\; =\; 732$ :$S\_2\; =\; r(3^2)\; =\; 637,\backslash ;S\_3\; =\; r(3^3)\; =\; 762,\backslash ;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à 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. :$\backslash Omega(x)\; =\; S(x)\; \backslash Lambda(x)\; \backslash mod\; x^4\; =\; 546\; x\; +\; 732\backslash ,$ :$\backslash Lambda\text{'}(x)\; =\; 658\; x\; +\; 821\backslash ,$ :$e\_1\; =\; -\backslash Omega(x\_1)/\backslash Lambda\text{'}(x\_1)\; =\; -649/54\; =\; 280\; \backslash times\; 843\; =\; 74\backslash ,$ :$e\_2\; =\; -\backslash Omega(x\_2)/\backslash Lambda\text{'}(x\_2)\; =\; 122\backslash ,$ Trừ e₁x³ và e₂x⁴ từ đa thức nhận được r để tìm ra mã tự ban đầu s.