1. 引言

前序博客有：

• LDC——Locally Decodable Code

Reed-Solomon Codes为基于block的纠错码，在数字通信和存储中有大量应用，在如下系统中用于纠错：

• 存储设备（包括磁带、光盘、DVD、条形码等）
• 无线或移动通信（包括手机、微波连接等）
• 卫星通信
• 数字电视/DVB
• 高速调制解调器，如ADSL、xDSL等

典型的系统如下图所示：

Reed-Solomon encoder（编码器） 接收一块数字数据并添加额外的“冗余”位。数据在传输或存储过程中出现错误的原因有多种（如噪声或干扰，CD上的划痕等等）。
Reed-Solomon decoder（解码器） 会处理每个块，并试图纠正错误，恢复原始数据。

能纠正的错误类型和错误数量具体取决于Reed-Solomon码的特性。

2. Reed-Solomon码的特性

Reed-Solomon码为BCH码的子集，属于linear block码。

Reed-Solomon码定义为：
$RS(n,k)$ with $s$-bit symbols。

也就意味着：

• Reed-Solomon 编码器接收$k$个data symbols，每个symbol对应有 $s$ bits，然后添加parity symbols，最终获得长度为$n$的symbol codeword。parity symbol的个数为$n-k$个，每个parity symbol对应有 $s$ bits。
• Reed-Solomon 解码器可纠正codeword中最多$t$个symbol错误，其中$2t=n-k$。

对Reed-Solomon进行编解码所需的算力，与每个codeword内的parity symbols数量相关。更大的$t$值以为这可纠正更多的错误，但是相比于 小$t$ 需要更多的算力。

已知symbol size为$s$，则Reed-Solomon码的最大codeword length $n$为$n=2^s-1$。如对于8-bit symbol（$s=8$），其code最大长度为$255$ bytes。

以下为典型的Reed-Solomon codeword（又名Systematic码，因为数据部分保持不变，仅附加了parity symbols）：

比如，流行的Reed-Solomon码$RS(255,223)$ with 8-bit symbols，每个codeword包含了255 code word bytes，其中223 bytes为数据，32 bytes为parity，有：
$n=255,k=223,s=8$
$25=32,t=16$

解码器可纠正code word中的任意16个symbol error，即codeword中的任意位置的最多16 bytes错误可被自动纠正。

2.1 缩短Reed-Solomon码

理论上Reed-Solomon码长度是可缩短的，通过在编码时将一定数量的data symbols设置为0，不传输这些为0的data symbols，然后在解码时重新插入为0的data symbols。
仍然以上面的$(255,223)$码为例，可将其缩短为$(200,168)$码，编码时的block内有168 data bytes，然后理论上增加55 zero bytes，创建出一个$(255,223)$ codeword，但是实际仅需传输168 data bytes和32 parity bytes。

2.2 Symbol Errors

若单个symbol内有一个bit出错或者所有bit都错了时，则均为一个symbol error。

仍然以$RS(255,223)$为例，其可纠正$16$个symbol errors，最差的情况是，有16 bit errors，每个bit错误发生在不同的symbol（byte），解码器纠正16 bit errors。最好的情况是，16个symbol内的所有bit都错了，此时解码器可纠正 $16\times 8$ bit errors。

Reed-Solomon码特别适于纠正burst errors（即所接收到的codeword内有a series of bits出错）。

2.3 解码

Reed-Solomon代数解码的过程中，可：

• 纠错
• 擦除：当已知错误symbol的位置时，可进行擦除。

解码器可最多纠正$t$个symbol错误，或最多擦除$2t$个错误symbol。在数字通信系统中，擦除信息通常由解调器提供，即解调器会对其收到的symbols中可能 包含错误的symbol 进行“标记”。

当对codeword解码时，有以下3种可能：

• 1）若$2s+r<2t$，即$s$个error，$t$个擦除，则总是可恢复出所传输的原始code word。
• 2）解码器发现其无法恢复原始code word，并说明了该情况。
• 3）解码器，在无任何说明的情况下，进行了错误解码并恢复了错误的code word。

以上3种情况发生的概率取决于具体的Reed-Solomon码、error数量 以及 error分布情况。

2.4 coding gain编码增益

使用Reed-Solomon码的优势在于，解码后数据内包含错误的概率，通常远低于，未使用Reed-Solomon码的错误发生概率。通常将其称为coding gain。

如：
数字通信系统中，设计的Bit Error Ration（BER）为$10^{-9}$，即所接收到的$10^9$个bits，最多仅能有$1$个bit出错。
可通过增加发射器的功率 或 添加Reed-Solomon码（或另一种 前向纠错码） 来实现。Reed-Solomon码可使得系统发射器以较低的输出功率实现目标BER。由于使用Reed-Solomon所节约的power，即称为coding gain。

3. Reed-Solomon码的编解码架构

Reed-Solomon编解码可在软件或特定用途硬件内实现。

3.1 关键概念

• 1）Finite（Galois） Field Arithmetic：
  Reed-Solomon码基于数学上名为Galois fields或Finite fields的特殊域。finite field内具有的属性为：field elements 经（加减乘除等）运算后的结果 仍在field域内。
  Reed-Solomon编码器或解码器需要执行这些运算操作，这些运算需要特殊的硬件或实现相应的软件函数。

• 2）Generator多项式：
  Reed-Solomon codeword采用特殊的多项式生成，所有有效的codewords都可整除该generator polynomial。
  generator多项式的通用形式为：
  $$g(x)=(x-{\alpha }^0)(x-{\alpha }^1)\cdots (x-{\alpha }^{2t-1})$$
  codeword的构建方式为：
  $$c(x)=g(x)\cdot i(x)$$
  其中$g(x)$为generator多项式，$i(x)$为information block（即上面提到的data symbol），$c(x)$为一个有效codeword，$\alpha$为field F域内的一个primitive element（generator）。

所谓generator，是指$[{\alpha }^0,{\alpha }^1,{\alpha }^2,\cdots ,{\alpha }^{|F|-2}]$为不同的非零值，即generator $\alpha$的幂乘生成了field F内的所有非零元素。$|F|$为field size，即不同元素的总数。

• 待编码的数据长度$k$满足$1\le k<|F|$。
• 在数据之后附加的纠错码长度$m=2t$满足$1\le m<|F|-k$。
• 编码后的长度$n=k+m$满足$2\le n<|F|$。

3.2 Reed-Solomon编码架构——Systematic编码器

基于$m$和$\alpha$的generator多项式定义为：
$$g(x)=\prod _{i=0}^{m-1}(x-{\alpha }^i)=(x-{\alpha }^0)(x-{\alpha }^1)\cdots (x-{\alpha }^{m-1})$$

原始消息为一系列$k$个值$(M_0,M_1,\cdots ,M_{k-1})$，简单地以这些原始消息值为系数构建message多项式：
$$M(x)=\sum _{i=0}^{k-1}{M}_i{x}^i=M_0{x}^0+M_1{x}^1+\cdots +M_{k-1}{x}^{k-1}$$

计算Reed-Solomon codeword的公式为：
$$s(x)=M(x)x^m-[(M(x)x^m)\mathrm{mod}g(x)]$$
其中$[(M(x)x^m)\mathrm{mod}g(x)]$多项式具有的degree小于等于$m-1$，因此不会与$M(x)x^m$项的结果相互影响。总的$s(x)$的degree小于等于$n-1$。

将$s(x)$展开为：
$$s(x)=\sum _{i=0}^{n-1}{s}_i{x}^i=s_0{x}^0+s_1{x}^1+\cdots s_{n-1}{x}^{n-1}$$
最终发送的RS码为$n$个值$(s_0,s_1,s_2,\cdots ,s_{n-1})$。

3.3 Reed-Solomon解码架构——Peterson-Gorenstein-Zierler解码器

假设收到的codeword为$(r_0,r_1,\cdots ,r_{n-1})$，可将received codeword多项式定义为：
$$r(x)=\sum _{i=0}^{n-1}{r}_i{x}^i=r_0{x}^0+r_1{x}^1+\cdots +r_{n-1}{x}^{n-1}$$

作为接收方，并不知道实际发送的值为$(s_0,s_1,s_2,\cdots ,s_{n-1})$，但会定义error值，令$e_0=r_0-s_0,e_1=r_1-s_1,\cdots ,e_{n-1}=r_{n-1}-s_{n-1}$，从而直接定义error多项式为：
$$e(x)=r(x)-s(x)=\sum _{i=0}^{n-1}{e}_i{x}^i=e_0{x}^0+e_1{x}^1+\cdots +e_{n-1}{x}^{n-1}$$

Reed-Solomon解码架构为：

其中：

• $r(x)$：为received codeword
• $S_i$：为Syndromes
• $L(x)$：Error locator polynomial
• $X_i$：Error locations
• $Y_i$：Error magnitudes
• $c(x)$：Recovered code word
• $\nu$：number of errors

以上架构图中：

• 1）Syndrome Calculation（计算Syndromes）：
  与parity calculation的计算类似，仅取决于errors（而不取决于所传输的code word），Reed-Solomon中有$m=2t$个syndromes。syndromes可通过向$r(x)$提交 generator多项式$g(x)$的 $m=2t$ 个根来计算。
  对于$0\le i<m$，计算$m$个syndrome值的方法为——evaluating the received codeword多项式$r(x)$ at various powers of the generator：
  $$S_i=r({\alpha }^i)=s({\alpha }^i)+e({\alpha }^i)=0+e({\alpha }^i)=e({\alpha }^i)=e_0{\alpha }^{0i}+e_1{\alpha }^{1i}+\cdots +e_{n-1}{\alpha }^{(n-1)i}$$
  其中对于$0\le i<m$，有$s({\alpha }^i)=0$。由此可看出，syndromes值仅依赖于添加到sent codeword上的errors，与sent codeword无关，与原始消息也无关。
  若所有的syndrome值均为0，则该codeword是正确的，即无需做任何处理，工作至此完成。
  所有 $m$ 个syndrome方程式为：
  { S 0 = e 0 α 0 × 0 + e 1 α 1 × 0 + ⋯ + e n − 1 α ( n − 1 ) × 0 S 1 = e 0 α 0 × 1 + e 1 α 1 × 1 + ⋯ + e n − 1 α ( n − 1 ) × 1 ⋯ S m − 1 = e 0 α 0 × ( m − 1 ) + e 1 α 1 × ( m − 1 ) + ⋯ + e n − 1 α ( n − 1 ) × ( m − 1 ) \left\{

  S0=e0α0×0+e1α1×0+⋯+en−1α(n−1)×0S1=e0α0×1+e1α1×1+⋯+en−1α(n−1)×1⋯Sm−1=e0α0×(m−1)+e1α1×(m−1)+⋯+en−1α(n−1)×(m−1)" role="presentation" style="position: relative;">S0=e0α0×0+e1α1×0+⋯+en−1α(n−1)×0S1=e0α0×1+e1α1×1+⋯+en−1α(n−1)×1⋯Sm−1=e0α0×(m−1)+e1α1×(m−1)+⋯+en−1α(n−1)×(m−1)$$\begin{array}{c}{S}_0=e_0{\alpha }^{0\times 0}+e_1{\alpha }^{1\times 0}+\cdots +e_{n-1}{\alpha }^{(n-1)\times 0}\\ S_1=e_0{\alpha }^{0\times 1}+e_1{\alpha }^{1\times 1}+\cdots +e_{n-1}{\alpha }^{(n-1)\times 1}\\ \cdots \\ S_{m-1}=e_0{\alpha }^{0\times (m-1)}+e_1{\alpha }^{1\times (m-1)}+\cdots +e_{n-1}{\alpha }^{(n-1)\times (m-1)}\end{array}$$
  \right. ⎩ ⎨ ⎧​S0​=e0​α0×0+e1​α1×0+⋯+en−1​α(n−1)×0S1​=e0​α0×1+e1​α1×1+⋯+en−1​α(n−1)×1⋯Sm−1​=e0​α0×(m−1)+e1​α1×(m−1)+⋯+en−1​α(n−1)×(m−1)​
  以矩阵表示syndrome方程组为：
  [ α 0 × 0 α 0 × 1 ⋯ α ( n − 1 ) × 0 α 0 × 1 α 0 × 1 ⋯ α ( n − 1 ) × 1 ⋮ ⋮ ⋱ ⋮ α 0 × ( m − 1 ) α 0 × ( m − 1 ) ⋯ α ( n − 1 ) × ( m − 1 ) ] [ e 0 e 1 ⋮ e n − 1 ] = [ S 0 S 1 ⋮ S m − 1 ]
  [α0×0α0×1⋯α(n−1)×0α0×1α0×1⋯α(n−1)×1⋮⋮⋱⋮α0×(m−1)α0×(m−1)⋯α(n−1)×(m−1)]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢⎢α0×0α0×1⋮α0×(m−1)α0×1α0×1⋮α0×(m−1)⋯⋯⋱⋯α(n−1)×0α(n−1)×1⋮α(n−1)×(m−1)⎤⎦⎥⎥⎥⎥⎥$$\left[\begin{array}{cccc}{\alpha }^{0\times 0}& {\alpha }^{0\times 1}& \cdots & {\alpha }^{(n-1)\times 0}\\ {\alpha }^{0\times 1}& {\alpha }^{0\times 1}& \cdots & {\alpha }^{(n-1)\times 1}\\ ⋮& ⋮& \ddots & ⋮\\ {\alpha }^{0\times (m-1)}& {\alpha }^{0\times (m-1)}& \cdots & {\alpha }^{(n-1)\times (m-1)}\end{array}\right]$$
  [e0e1⋮en−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢e0e1⋮en−1⎤⎦⎥⎥⎥⎥$$\left[\begin{array}{c}{e}_0\\ e_1\\ ⋮\\ e_{n-1}\end{array}\right]$$
  =
  [S0S1⋮Sm−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢S0S1⋮Sm−1⎤⎦⎥⎥⎥⎥$$\left[\begin{array}{c}{S}_0\\ S_1\\ ⋮\\ S_{m-1}\end{array}\right]$$
  ⎣ ⎡​α0×0α0×1⋮α0×(m−1)​α0×1α0×1⋮α0×(m−1)​⋯⋯⋱⋯​α(n−1)×0α(n−1)×1⋮α(n−1)×(m−1)​⎦ ⎤​⎣ ⎡​e0​e1​⋮en−1​​⎦ ⎤​=⎣ ⎡​S0​S1​⋮Sm−1​​⎦ ⎤​

• 2）寻找Symbol Error Locations：
  寻找Symbol Error Locations的过程，包含了，对包含t个未知变量simultaneous多项式的求解。有多种快速算法可实现该求解。这些算法利用了Reed-Solomon码的特殊结构，可大幅减少所需的算力。
  求解算法中通常包含2步：

  • 2.1）找到一个error locator多项式：可使用Berlekamp-Massey算法或Euclid算法。实际Euclid算法使用更广，因其更易于实现。但是Berlekamp-Massey算法的效率会更高。
  • 2.2）找到该多项式的根：通过Chien search算法实现。

  以$\nu$来表示试图找到的errors个数，要求$1\le \nu \le \lfloor m/2\rfloor$。除非有时空限制，否则最好将$\nu$设置为尽可能大，以可纠正尽可能多的错误。
  假设我们已知这$\nu$个error位置为$I_0,I_1,\cdots ,I_{\nu -1}$，为$n$个received codeword值的orderless set of unique indexes，因此，每个元素均满足$0\le I_i<n$。注意，此处有：indexes $I_i$处的error值可能为非零，但是除$e_{I_0},e_{I_1},\cdots ,e_{I_{\nu -1}}$之外的其它indexes处的error值必须为0。
  对于$0\le i<\nu$，基于error location indexes $I_i$，引入新变量：
  $X_i={\alpha }^{I_i}$
  $Y_i=e_{I_i}$
  由于所有其它indexes的$e_i$值均为0，因此可将syndrome方程式组重写为：
  [ X 0 0 X 1 0 ⋯ X ν − 1 0 X 0 1 X 1 1 ⋯ X ν − 1 1 ⋮ ⋮ ⋱ ⋮ X 0 m − 1 X 1 m − 1 ⋯ X ν − 1 m − 1 ] [ Y 0 Y 1 ⋮ Y ν − 1 ] = [ S 0 S 1 ⋮ S m − 1 ]

  [X00X10⋯Xν−10X01X11⋯Xν−11⋮⋮⋱⋮X0m−1X1m−1⋯Xν−1m−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢⎢⎢X00X10⋮Xm−10X01X11⋮Xm−11⋯⋯⋱⋯X0ν−1X1ν−1⋮Xm−1ν−1⎤⎦⎥⎥⎥⎥⎥⎥$$\left[\begin{array}{cccc}{X}_0^0& X_1^0& \cdots & X_{\nu -1}^0\\ X_0^1& X_1^1& \cdots & X_{\nu -1}^1\\ ⋮& ⋮& \ddots & ⋮\\ X_0^{m-1}& X_1^{m-1}& \cdots & X_{\nu -1}^{m-1}\end{array}\right]$$
  [Y0Y1⋮Yν−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢Y0Y1⋮Yν−1⎤⎦⎥⎥⎥⎥$$\left[\begin{array}{c}{Y}_0\\ Y_1\\ ⋮\\ Y_{\nu -1}\end{array}\right]$$
  =
  [S0S1⋮Sm−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢S0S1⋮Sm−1⎤⎦⎥⎥⎥⎥$$\left[\begin{array}{c}{S}_0\\ S_1\\ ⋮\\ S_{m-1}\end{array}\right]$$
  ⎣ ⎡​X00​X01​⋮X0m−1​​X10​X11​⋮X1m−1​​⋯⋯⋱⋯​Xν−10​Xν−11​⋮Xν−1m−1​​⎦ ⎤​⎣ ⎡​Y0​Y1​⋮Yν−1​​⎦ ⎤​=⎣ ⎡​S0​S1​⋮Sm−1​​⎦ ⎤​
  此时，对$X_i,Y_i$值仍是位置的，但是，接下来有个聪明的multi-step方法来知晓具体的$X_i,Y_i$值。
  基于未知的$X_i$变量，定义error locator多项式为：
  $$\Lambda (x)=\prod _{i=0}^{\nu -1}(1-X_{i}x)=1+{\Lambda }_{1}x+{\Lambda }_{2}x+\cdots +{\Lambda }_{\nu }{x}^{\nu }$$
  error locator多项式系数为$(1,{\Lambda }_1,{\Lambda }_2,\cdots ,{\Lambda }_{\nu })$。
  对于任意的$0\le i<\nu$，有：
  $$0=\Lambda (X_i^{-1})=1+{\Lambda }_1{X}_i^{-1}+{\Lambda }_2{X}_i^{-2}+\cdots +{\Lambda }_{\nu }{X}_i^{-\nu }$$
  以上等式为0是因为$(1-X_i{X}_i^{-1})=1-1=0$。
  对于$0\le i<\nu$，取任意的$j\in \mathbb{Z}$，在以上等式左右两边都乘以$Y_i{X}_i^{j+\nu }$，有：
  $$Y_i{X}_i^{j+\nu }0=Y_i{X}_i^{j+\nu }\Lambda (X_i^{-1})=Y_i{X}_i^{j+\nu }(1+{\Lambda }_1{X}_i^{-1}+{\Lambda }_2{X}_i^{-2}+\cdots +{\Lambda }_{\nu }{X}_i^{-\nu })$$
  $$0=Y_i{X}_i^{j+\nu }\Lambda (X_i^{-1})=Y_i{X}_i^{j+\nu }+{\Lambda }_1{Y}_i{X}_i^{j+\nu -1}+{\Lambda }_2{Y}_i{X}_i^{j+\nu -2}+\cdots +{\Lambda }_{\nu }{Y}_i{X}_i^j$$
  对所有的$0\le i<\nu$方程式求和，有：
  $$0=\sum _{i=0}^{\nu -1}{Y}_i{X}_i^{j+\nu }\Lambda (X_i^{-1})=(\sum _{i=0}^{\nu -1}{Y}_i{X}_i^{j+\nu })+{\Lambda }_1(\sum _{i=0}^{\nu -1}{Y}_i{X}_i^{j+\nu -1})+{\Lambda }_2(\sum _{i=0}^{\nu -1}{Y}_i{X}_i^{j+\nu -2})+\cdots +{\Lambda }_{\nu }(\sum _{i=0}^{\nu -1}{Y}_i{X}_i^j)=S_{j+\nu }+{\Lambda }_1{S}_{j+\nu -1}+{\Lambda }_2{S}_{j+\nu -2}+\cdots +{\Lambda }_{\nu }{S}_j$$
  将以上等式左右项重组，对于$0\le j<\nu$，均有：
  $${\Lambda }_{\nu }{S}_j+{\Lambda }_{\nu -1}{S}_{j+1}+\cdots +{\Lambda }_1{S}_{j+\nu -1}=-S_{j+\nu }$$
  对于所有的$0\le j<\nu$，可获得$\nu$个线性等式：
  { Λ ν S 0 + Λ ν − 1 S 1 + ⋯ + Λ 1 S ν − 1 = − S ν Λ ν S 1 + Λ ν − 1 S 2 + ⋯ + Λ 1 S ν = − S ν + 1 ⋯ Λ ν S ν − 1 + Λ ν − 1 S ν + ⋯ + Λ 1 S 2 ν − 2 = − S 2 ν − 1 \left\{
  ΛνS0+Λν−1S1+⋯+Λ1Sν−1=−SνΛνS1+Λν−1S2+⋯+Λ1Sν=−Sν+1⋯ΛνSν−1+Λν−1Sν+⋯+Λ1S2ν−2=−S2ν−1" role="presentation" style="position: relative;">ΛνS0+Λν−1S1+⋯+Λ1Sν−1=−SνΛνS1+Λν−1S2+⋯+Λ1Sν=−Sν+1⋯ΛνSν−1+Λν−1Sν+⋯+Λ1S2ν−2=−S2ν−1$$\begin{array}{c}{\mathrm{\Lambda }}_{\nu }{S}_0+{\mathrm{\Lambda }}_{\nu -1}{S}_1+\cdots +{\mathrm{\Lambda }}_1{S}_{\nu -1}=-S_{\nu }\\ {\mathrm{\Lambda }}_{\nu }{S}_1+{\mathrm{\Lambda }}_{\nu -1}{S}_2+\cdots +{\mathrm{\Lambda }}_1{S}_{\nu }=-S_{\nu +1}\\ \cdots \\ {\mathrm{\Lambda }}_{\nu }{S}_{\nu -1}+{\mathrm{\Lambda }}_{\nu -1}{S}_{\nu }+\cdots +{\mathrm{\Lambda }}_1{S}_{2\nu -2}=-S_{2\nu -1}\end{array}$$
  \right. ⎩ ⎨ ⎧​Λν​S0​+Λν−1​S1​+⋯+Λ1​Sν−1​=−Sν​Λν​S1​+Λν−1​S2​+⋯+Λ1​Sν​=−Sν+1​⋯Λν​Sν−1​+Λν−1​Sν​+⋯+Λ1​S2ν−2​=−S2ν−1​​
  以矩阵形式表示为：
  [ S 0 S 1 ⋯ S ν − 1 S 1 S 2 ⋯ S ν ⋮ ⋮ ⋱ ⋮ S ν − 1 S ν ⋯ S 2 ν − 2 ] [ Λ ν Λ ν − 1 ⋮ Λ 1 ] = [ − S ν − S ν + 1 ⋮ − S 2 ν − 1 ]
  [S0S1⋯Sν−1S1S2⋯Sν⋮⋮⋱⋮Sν−1Sν⋯S2ν−2]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢⎢S0S1⋮Sν−1S1S2⋮Sν⋯⋯⋱⋯Sν−1Sν⋮S2ν−2⎤⎦⎥⎥⎥⎥⎥$$\left[\begin{array}{cccc}{S}_0& S_1& \cdots & S_{\nu -1}\\ S_1& S_2& \cdots & S_{\nu }\\ ⋮& ⋮& \ddots & ⋮\\ S_{\nu -1}& S_{\nu }& \cdots & S_{2\nu -2}\end{array}\right]$$
  [ΛνΛν−1⋮Λ1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢ΛνΛν−1⋮Λ1⎤⎦⎥⎥⎥⎥$$\left[\begin{array}{c}{\mathrm{\Lambda }}_{\nu }\\ {\mathrm{\Lambda }}_{\nu -1}\\ ⋮\\ {\mathrm{\Lambda }}_1\end{array}\right]$$
  =
  [−Sν−Sν+1⋮−S2ν−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢−Sν−Sν+1⋮−S2ν−1⎤⎦⎥⎥⎥⎥$$\left[\begin{array}{c}-S_{\nu }\\ -S_{\nu +1}\\ ⋮\\ -S_{2\nu -1}\end{array}\right]$$
  ⎣ ⎡​S0​S1​⋮Sν−1​​S1​S2​⋮Sν​​⋯⋯⋱⋯​Sν−1​Sν​⋮S2ν−2​​⎦ ⎤​⎣ ⎡​Λν​Λν−1​⋮Λ1​​⎦ ⎤​=⎣ ⎡​−Sν​−Sν+1​⋮−S2ν−1​​⎦ ⎤​
  以上由$\nu +1$个方程式组成，若以上线性方程式是consistent的，根据Gauss-Jordan消减法，可获得系数${\Lambda }_1,{\Lambda }_2,\cdots ,{\Lambda }_{\nu }$，从而获得了error locator多项式$\Lambda (x)$，对所有的$0\le i<n$，取$x={\alpha }^{-i}$，检查$\Lambda ({\alpha }^{-1})=0$是否成立。

• 3）寻找Symbol Error Values：仍然包含了，对包含t个未知变量simultaneous多项式的求解。广泛使用的快速算法为Forney算法。
  此时，已知了所有的error location indexes $I_0,I_1,\cdots ,I_{\nu -1}$，以及对于$0\le i<\nu$，已知所有的$X_i={\alpha }^{I_i}$值。

  • 3.1）由于已知了$X_i$值和$S_i$值，可求解之前方程式：
    [ X 0 0 X 1 0 ⋯ X ν − 1 0 X 0 1 X 1 1 ⋯ X ν − 1 1 ⋮ ⋮ ⋱ ⋮ X 0 m − 1 X 1 m − 1 ⋯ X ν − 1 m − 1 ] [ Y 0 Y 1 ⋮ Y ν − 1 ] = [ S 0 S 1 ⋮ S m − 1 ]
    [X00X10⋯Xν−10X01X11⋯Xν−11⋮⋮⋱⋮X0m−1X1m−1⋯Xν−1m−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢⎢⎢X00X10⋮Xm−10X01X11⋮Xm−11⋯⋯⋱⋯X0ν−1X1ν−1⋮Xm−1ν−1⎤⎦⎥⎥⎥⎥⎥⎥$$\left[\begin{array}{cccc}{X}_0^0& X_1^0& \cdots & X_{\nu -1}^0\\ X_0^1& X_1^1& \cdots & X_{\nu -1}^1\\ ⋮& ⋮& \ddots & ⋮\\ X_0^{m-1}& X_1^{m-1}& \cdots & X_{\nu -1}^{m-1}\end{array}\right]$$
    [Y0Y1⋮Yν−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢Y0Y1⋮Yν−1⎤⎦⎥⎥⎥⎥$$\left[\begin{array}{c}{Y}_0\\ Y_1\\ ⋮\\ Y_{\nu -1}\end{array}\right]$$
    =
    [S0S1⋮Sm−1]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢S0S1⋮Sm−1⎤⎦⎥⎥⎥⎥$$\left[\begin{array}{c}{S}_0\\ S_1\\ ⋮\\ S_{m-1}\end{array}\right]$$
    ⎣ ⎡​X00​X01​⋮X0m−1​​X10​X11​⋮X1m−1​​⋯⋯⋱⋯​Xν−10​Xν−11​⋮Xν−1m−1​​⎦ ⎤​⎣ ⎡​Y0​Y1​⋮Yν−1​​⎦ ⎤​=⎣ ⎡​S0​S1​⋮Sm−1​​⎦ ⎤​
    的解$Y_i=e_{I_i}$。
  • 3.2）由于已知了error locations $I_i$ 和 error values $Y_i$，可试图fix the received codeword。
    定义repaired codeword多项式为：
    $$r^{\prime }(x)=r_0^{\prime }{x}^0+r_1^{\prime }{x}_1+\cdots +r_{n-1}^{\prime }{x}^{n-1}$$
    其中，对于$0\le i<\nu$，系数$r_{I_i}^{\prime }=r_{I_i}-Y_i=r_{I_i}-e_{I_i}$，而对于任意的$0\le i<n$且不满足$0\le i<\nu$的$i$值，有$r_i^{\prime }=r_i$。由此，the repaired codeword多项式$r^{\prime }(x)$具有all-zero syndrom values。
    该解码codeword是基于received codeword的最佳猜想。

Reed-Solomon解码者试图识别并纠正最多$t$个errors或$2t$个erasures。

3.4 时间复杂度

以上编码器为短而简介的，其时间复杂度为$\Theta (mk)$，已不太可能在简洁性或速度上有显著改进。

假设最大纠错能力为$\nu =\lfloor \rfloor$，以上解码器的时间复杂度为$\Theta (m^3+mk)$。其中的三次方runtime并不理想，可借助其它算法改进到二次方。Berlekamp-Massey算法find error locator多项式的时间复杂度为$\Theta (m^2)$，且Forney算法find error values的时间复杂度也为$\Theta (m^2)$。

4. Reed-Solomon编解码器实现

4.1 Reed-Solomon编解码器硬件实现

目前有一些商业硬件实现了Reed-Solomon编解码功能，很多采用了“off-the-shelf”集成电路来对Reed-Solomon码进行编解码。这些IC支持一定数量的可编程性（如$RS(255,k)$，其中$t=1$~16个symbols）。
当前的趋势是VHDL或Verilog设计（logic cores 或 intellectual property cores）。相比于标准IC，主要优势有：

• 1）logic core可与其他VHDL或Verilog元素集成
• 2）可与FPGA（Field Programmable Gate Array）或ASIC（Application Specific Integrated Circuit）合成

这种“System on Chip”设计，支持将多个模块合并在单一IC内。取决于生产规模，相比于标准IC，logic cores可大幅降低系统开销，设计者可避免潜在的“周期性购买”Reed-Solomon IC。

4.2 Reed-Solomon编解码器软件实现

编码的速度要快于解码，所需的算力也更少。

相关软件代码实现见：
Reed-Solomon error-correcting code decoder

RS纠错码Java实现为：

/* 
 * Reed-Solomon error-correcting code decoder (Java)
 * 
 * Copyright (c) 2017 Project Nayuki
 * All rights reserved. Contact Nayuki for licensing.
 * https://www.nayuki.io/page/reed-solomon-error-correcting-code-decoder
 */

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Objects;


/**
 * Performs Reed-Solomon encoding and decoding. This object can encode a message into a codeword.
 * The codeword can have some values modified by external code. Then this object can try
 * to decode the codeword, and under some circumstances can reproduce the original message.
 * 
This class is immutable and thread-safe, but the argument arrays passed into methods are not thread-safe.
 */
public final class ReedSolomon<E> {
	
	/*---- Fields ----*/
	
	/** The number of values in each message. Always at least 1. */
	public final int messageLen;
	
	/** The number of error correction values to expand the message by. Always at least 1. */
	public final int eccLen;
	
	/** The number of values in each codeword, equal to messageLen + eccLen. Always at least 2. */
	public final int codewordLen;
	
	
	// The field for message and codeword values, and for performing arithmetic operations on values. Not null.
	private final Field<E> f;
	
	// An element of the field whose powers generate all the non-zero elements of the field. Not null.
	private final E generator;
	
	// The class object for the actual type parameter E, which is used in newArray(). Not null.
	private Class<E> elementType;
	
	
	
	/*---- Constructor ----*/
	
	/**
	 * Constructs a Reed-Solomon encoder-decoder with the specified field, lengths, and other parameters.
	 * 
Note: The class argument is used like this:
	 * {@code ReedSolomon rs = new ReedSolomon<>(f, gen, Integer.class, msgLen, eccLen);}
	 * @param f the field for all values and operations (not {@code null})
	 * @param gen a generator of the field {@code f} (not {@code null})
	 * @param elemType the class object for the type parameter {@code E} (not {@code null})
	 * @param msgLen the length of message arrays, which must be positive
	 * @param eccLen the number of values to expand each message by, which must be positive
	 * @throws NullPointerException if any of the object arguments is null
	 * @throws IllegalArgumentException if msgLen ≤ 0, eccLen ≤ 0, or mlgLen + eccLen > Integer.MAX_VALUE
	 */
	public ReedSolomon(Field<E> f, E gen, Class<E> elemType, int msgLen, int eccLen) {
		// Check arguments
		Objects.requireNonNull(f);
		Objects.requireNonNull(gen);
		Objects.requireNonNull(elemType);
		if (msgLen <= 0 || eccLen <= 0 || Integer.MAX_VALUE - msgLen < eccLen)
			throw new IllegalArgumentException("Invalid message or ECC length");
		
		// Assign fields
		this.f = f;
		this.generator = gen;
		this.elementType = elemType;
		this.messageLen = msgLen;
		this.eccLen = eccLen;
		this.codewordLen = msgLen + eccLen;
	}
	
	
	
	/*---- Encoder methods ----*/
	
	/**
	 * Returns a new array representing the codeword produced by encoding the specified message.
	 * If the message has the correct length and all its values are
	 * valid in the field, then this method is guaranteed to succeed.
	 * @param message the message to encode, whose length must equal {@code this.messageLen}
	 * @return a new array representing the codeword values
	 * @throws NullPointerException if the message array or any of its elements are {@code null}
	 * @throws IllegalArgumentException if the message array has the wrong length
	 */
	public E[] encode(E[] message) {
		// Check arguments
		Objects.requireNonNull(message);
		if (message.length != messageLen)
			throw new IllegalArgumentException("Invalid message length");
		
		// Make the generator polynomial (this doesn't depend on the message)
		E[] genPoly = makeGeneratorPolynomial();
		
		// Compute the remainder ((message(x) * x^eccLen) mod genPoly(x)) by performing polynomial division.
		// Process message bytes (polynomial coefficients) from the highest monomial power to the lowest power
		E[] eccPoly = newArray(eccLen);
		Arrays.fill(eccPoly, f.zero());
		for (int i = messageLen - 1; i >= 0; i--) {
			E factor = f.add(message[i], eccPoly[eccLen - 1]);
			System.arraycopy(eccPoly, 0, eccPoly, 1, eccLen - 1);
			eccPoly[0] = f.zero();
			for (int j = 0; j < eccLen; j++)
				eccPoly[j] = f.subtract(eccPoly[j], f.multiply(genPoly[j], factor));
		}
		
		// Negate the remainder
		for (int i = 0; i < eccPoly.length; i++)
			eccPoly[i] = f.negate(eccPoly[i]);
		
		// Concatenate the message and ECC polynomials
		E[] result = newArray(codewordLen);
		System.arraycopy(eccPoly, 0, result, 0, eccLen);
		System.arraycopy(message, 0, result, eccLen, messageLen);
		return result;
	}
	
	
	// Computes the generator polynomial by multiplying powers of the generator value:
	// genPoly(x) = (x - gen^0) * (x - gen^1) * ... * (x - gen^(eccLen-1)).
	// The resulting array of coefficients is in little endian, i.e. from lowest to highest power, except
	// that the very highest power (the coefficient for the x^eccLen term) is omitted because it's always 1.
	// The result of this method can be pre-computed because it doesn't depend on the message to be encoded.
	private E[] makeGeneratorPolynomial() {
		// Start with the polynomial of 1*x^0, which is the multiplicative identity
		E[] result = newArray(eccLen);
		Arrays.fill(result, f.zero());
		result[0] = f.one();
		
		E genPow = f.one();
		for (int i = 0; i < eccLen; i++) {
			// At this point, genPow == generator^i.
			// Multiply the current genPoly by (x - generator^i)
			for (int j = eccLen - 1; j >= 0; j--) {
				result[j] = f.multiply(f.negate(genPow), result[j]);
				if (j >= 1)
					result[j] = f.add(result[j - 1], result[j]);
			}
			genPow = f.multiply(generator, genPow);
		}
		return result;
	}
	
	
	
	/*---- Decoder methods ----*/
	
	/**
	 * Attempts to decode the specified codeword with the maximum error-correcting
	 * capability allowed, returning either a best-guess message or {@code null}.
	 * 
If the number of erroneous values in the codeword is less than or equal to floor(eccLen / 2),
	 * then decoding is guaranteed to succeed. Otherwise an explicit failure ({@code null} answer)
	 * is most likely, but wrong answer and right answer are also possible too.
	 * @param codeword the codeword to decode, whose length must equal {@code this.codewordLen}
	 * @return a new array representing the decoded message, or {@code null} to indicate failure
	 * @throws NullPointerException if the codeword is {@code null}
	 * @throws IllegalArgumentException if the codeword array has the wrong length
	 */
	public E[] decode(E[] codeword) {
		return decode(codeword, eccLen / 2);
	}
	
	
	/**
	 * Attempts to decode the specified codeword with the specified level of
	 * error-correcting capability, returning either a best-guess message or {@code null}.
	 * 
If the number of erroneous values in the codeword is less than or equal to numErrorsToCorrect,
	 * then decoding is guaranteed to succeed. Otherwise an explicit failure ({@code null} answer)
	 * is most likely, but wrong answer and right answer are also possible too.
	 * @param codeword the codeword to decode, whose length must equal {@code this.codewordLen}
	 * @param numErrorsToCorrect the number of errors in the codeword to try to fix,
	 * which must be between 0 to floor(eccLen / 2), inclusive
	 * @return a new array representing the decoded message, or {@code null} to indicate failure
	 * @throws NullPointerException if the codeword is {@code null}
	 * @throws IllegalArgumentException if the codeword array has the wrong length,
	 * or numErrorsToCorrect is out of range
	 */
	public E[] decode(E[] codeword, int numErrorsToCorrect) {
		// Check arguments
		Objects.requireNonNull(codeword);
		if (codeword.length != codewordLen)
			throw new IllegalArgumentException("Invalid codeword length");
		if (numErrorsToCorrect < 0 || numErrorsToCorrect > eccLen / 2)
			throw new IllegalArgumentException("Number of errors to correct is out of range");
		
		// Calculate and check syndromes
		E[] syndromes = calculateSyndromes(codeword);
		if (!areAllZero(syndromes)) {
			// At this point, we know the codeword must have some errors
			if (numErrorsToCorrect == 0)
				return null;  // Only detect but not fix errors
			
			// Try to solve for the error locator polynomial
			E[] errLocPoly = calculateErrorLocatorPolynomial(syndromes, numErrorsToCorrect);
			if (errLocPoly == null)
				return null;
			
			// Try to find the codeword indexes where errors might have occurred
			int[] errLocs = findErrorLocations(errLocPoly, numErrorsToCorrect);
			if (errLocs == null || errLocs.length == 0)
				return null;
			
			// Try to find the error values at these indexes
			E[] errVals = calculateErrorValues(errLocs, syndromes);
			if (errVals == null)
				return null;
			
			// Perform repairs to the codeword with the information just derived
			E[] newCodeword = fixErrors(codeword, errLocs, errVals);
			
			// Final sanity check by recomputing syndromes
			E[] newSyndromes = calculateSyndromes(newCodeword);
			if (!areAllZero(newSyndromes))
				throw new AssertionError();
			codeword = newCodeword;
		}
		
		// At this point, all syndromes are zero.
		// Extract the message part of the codeword
		return Arrays.copyOfRange(codeword, eccLen, codeword.length);
	}
	
	
	// Returns a new array representing the sequence of syndrome values for the given codeword.
	// To summarize the math, syndrome[i] = codeword(generator^i).
	private E[] calculateSyndromes(E[] codeword) {
		// Check arguments
		Objects.requireNonNull(codeword);
		if (codeword.length != codewordLen)
			throw new IllegalArgumentException();
		
		// Evaluate the codeword polynomial at generator powers
		E[] result = newArray(eccLen);
		E genPow = f.one();
		for (int i = 0; i < result.length; i++) {
			result[i] = evaluatePolynomial(codeword, genPow);
			genPow = f.multiply(generator, genPow);
		}
		return result;
	}
	
	
	// Returns a new array representing the coefficients of the error locator polynomial
	// in little endian, or null if the syndrome values imply too many errors to handle.
	private E[] calculateErrorLocatorPolynomial(E[] syndromes, int numErrorsToCorrect) {
		// Check arguments
		Objects.requireNonNull(syndromes);
		if (syndromes.length != eccLen || numErrorsToCorrect <= 0 || numErrorsToCorrect > syndromes.length / 2)
			throw new IllegalArgumentException();
		
		// Copy syndrome values into augmented matrix
		Matrix<E> matrix = new Matrix<>(numErrorsToCorrect, numErrorsToCorrect + 1, f);
		for (int r = 0; r < matrix.rowCount(); r++) {
			for (int c = 0; c < matrix.columnCount(); c++) {
				E val = syndromes[r + c];
				if (c == matrix.columnCount() - 1)
					val = f.negate(val);
				matrix.set(r, c, val);
			}
		}
		
		// Solve the system of linear equations
		matrix.reducedRowEchelonForm();
		
		// Create result vector filled with zeros. Note that columns without a pivot
		// will yield variables that stay at the default value of zero
		E[] result = newArray(numErrorsToCorrect + 1);
		Arrays.fill(result, f.zero());
		result[0] = f.one();  // Constant term is always 1, regardless of the matrix
		
		// Find the column of the pivot in each row, and set the
		// appropriate output variable's value based on the column index
		outer:
		for (int r = 0, c = 0; r < matrix.rowCount(); r++) {
			// Advance the column index until a pivot is found, but handle specially if
			// the rightmost column is identified as a pivot or if no column is a pivot
			while (true) {
				if (c == matrix.columnCount())
					break outer;
				else if (f.equals(matrix.get(r, c), f.zero()))
					c++;
				else if (c == matrix.columnCount() - 1)
					return null;  // Linear system is inconsistent
				else
					break;
			}
			
			// Copy the value in the rightmost column to the result vector
			result[numErrorsToCorrect - c] = matrix.get(r, numErrorsToCorrect);
		}
		return result;
	}
	
	
	// Returns a new array that represents indexes into the codeword array where the value
	// might be erroneous, or null if it is discovered that the decoding process is impossible.
	// This method tries to find roots of the error locator polynomial by brute force.
	private int[] findErrorLocations(E[] errLocPoly, int maxSolutions) {
		// Check arguments
		Objects.requireNonNull(errLocPoly);
		if (maxSolutions <= 0 || maxSolutions > codewordLen)
			throw new IllegalArgumentException();
		
		// Create temporary buffer for roots found
		int[] indexesFound = new int[maxSolutions];
		int numFound = 0;
		
		// Evaluate errLocPoly(generator^-i) for 0 <= i < codewordLen
		E genRec = f.reciprocal(generator);
		E genRecPow = f.one();
		for (int i = 0; i < codewordLen; i++) {
			// At this point, genRecPow == generator^-i
			E polyVal = evaluatePolynomial(errLocPoly, genRecPow);
			if (f.equals(polyVal, f.zero())) {
				if (numFound >= indexesFound.length)
					return null;  // Too many solutions
				indexesFound[numFound] = i;
				numFound++;
			}
			genRecPow = f.multiply(genRec, genRecPow);
		}
		return Arrays.copyOf(indexesFound, numFound);
	}
	
	
	// Returns a new array representing the error values/magnitudes at the given error locations,
	// or null if the information given is inconsistent (thus decoding is impossible).
	// If the result of this method is not null, then after fixing the codeword it is guaranteed
	// to have all zero syndromes (but it could be the wrong answer, unequal to the original message).
	private E[] calculateErrorValues(int[] errLocs, E[] syndromes) {
		// Check arguments
		Objects.requireNonNull(errLocs);
		Objects.requireNonNull(syndromes);
		if (syndromes.length != eccLen)
			throw new IllegalArgumentException();
		
		// Calculate and copy values into matrix
		Matrix<E> matrix = new Matrix<>(syndromes.length, errLocs.length + 1, f);
		for (int c = 0; c < matrix.columnCount() - 1; c++) {
			E genPow = pow(generator, errLocs[c]);
			E genPowPow = f.one();
			for (int r = 0; r < matrix.rowCount(); r++) {
				matrix.set(r, c, genPowPow);
				genPowPow = f.multiply(genPow, genPowPow);
			}
		}
		for (int r = 0; r < matrix.rowCount(); r++)
			matrix.set(r, matrix.columnCount() - 1, syndromes[r]);
		
		// Solve matrix and check basic consistency
		matrix.reducedRowEchelonForm();
		if (!f.equals(matrix.get(matrix.columnCount() - 1, matrix.columnCount() - 1), f.zero()))
			return null;  // System of linear equations is inconsistent
		
		// Check that the top left side equals an identity matrix,
		// and extract the rightmost column as result vector
		E[] result = newArray(errLocs.length);
		for (int i = 0; i < result.length; i++) {
			if (!f.equals(matrix.get(i, i), f.one()))
				return null;  // Linear system is under-determined; no unique solution
			result[i] = matrix.get(i, matrix.columnCount() - 1);
		}
		return result;
	}
	
	
	// Returns a new codeword representing the given codeword with the given errors subtracted.
	// Always succeeds, as long as the array values are well-formed.
	private E[] fixErrors(E[] codeword, int[] errLocs, E[] errVals) {
		// Check arguments
		Objects.requireNonNull(codeword);
		Objects.requireNonNull(errLocs);
		Objects.requireNonNull(errVals);
		if (codeword.length != codewordLen || errLocs.length != errVals.length)
			throw new IllegalArgumentException();
		
		// Clone the codeword and change values at specific indexes
		E[] result = codeword.clone();
		for (int i = 0; i < errLocs.length; i++)
			result[errLocs[i]] = f.subtract(result[errLocs[i]], errVals[i]);
		return result;
	}
	
	
	
	/*---- Simple utility methods ----*/
	
	// Returns a new array of the given length with E as the actual element type.
	// This method exists so that unchecked generic operations are confined in one place here.
	@SuppressWarnings("unchecked")
	private E[] newArray(int len) {
		if (len < 0)
			throw new NegativeArraySizeException();
		return (E[])Array.newInstance(elementType, len);
	}
	
	
	// Returns the value of the given polynomial at the given point. The polynomial is represented
	// in little endian. In other words, this method evaluates result = polynomial(point)
	// = polynomial[0]*point^0 + polynomial[1]*point^1 + ... + ponylomial[len-1]*point^(len-1).
	private E evaluatePolynomial(E[] polynomial, E point) {
		Objects.requireNonNull(polynomial);
		Objects.requireNonNull(point);
		
		// Horner's method
		E result = f.zero();
		for (int i = polynomial.length - 1; i >= 0; i--) {
			result = f.multiply(point, result);
			result = f.add(polynomial[i], result);
		}
		return result;
	}
	
	
	// Tests whether all elements of the given array are equal to the field's zero element.
	private boolean areAllZero(E[] array) {
		Objects.requireNonNull(array);
		for (E val : array) {
			if (!f.equals(val, f.zero()))
				return false;
		}
		return true;
	}
	
	
	// Returns the given field element raised to the given power. The power must be non-negative.
	private E pow(E base, int exp) {
		Objects.requireNonNull(base);
		if (exp < 0)
			throw new UnsupportedOperationException();
		E result = f.one();
		for (int i = 0; i < exp; i++)
			result = f.multiply(base, result);
		return result;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440

相应的demo为：

/* 
 * Reed-Solomon error-correcting code decoder demo (Java)
 * 
 * Copyright (c) 2019 Project Nayuki
 * All rights reserved. Contact Nayuki for licensing.
 * https://www.nayuki.io/page/reed-solomon-error-correcting-code-decoder
 */

import java.util.Arrays;
import java.util.Random;


public final class ReedSolomonDemo {
	
	// Runs a bunch of demos and tests, printing information to standard error.
	public static void main(String[] args) {
		showBinaryExample();
		showPrimeExample();
		testCorrectness();
	}
	
	
	// Shows an example of encoding a binary message, and decoding a codeword containing errors.
	private static void showBinaryExample() {
		// Configurable parameters
		BinaryField field = new BinaryField(0x11D);
		Integer generator = 0x02;
		int msgLen = 8;
		int eccLen = 5;
		ReedSolomon<Integer> rs = new ReedSolomon<>(field, generator, Integer.class, msgLen, eccLen);
		
		// Generate random message
		Integer[] message = new Integer[msgLen];
		for (int i = 0; i < message.length; i++)
			message[i] = rand.nextInt(field.size);
		System.err.println("Original message: " + Arrays.toString(message));
		
		// Encode message to produce codeword
		Integer[] codeword = rs.encode(message);
		System.err.println("Encoded codeword: " + Arrays.toString(codeword));
		
		// Perturb some values in the codeword
		double probability = (double)(eccLen / 2) / (msgLen + eccLen);
		int perturbed = 0;
		for (int i = 0; i < codeword.length; i++) {
			if (rand.nextDouble() < probability) {
				codeword[i] = field.add(codeword[i], rand.nextInt(field.size - 1) + 1);
				perturbed++;
			}
		}
		System.err.println("Number of values perturbed: " + perturbed);
		System.err.println("Perturbed codeword: " + Arrays.toString(codeword));
		
		// Try to decode the codeword
		Integer[] decoded = rs.decode(codeword);
		System.err.println("Decoded message: " + (decoded != null ? Arrays.toString(decoded) : "Failure"));
		System.err.println();
	}
	
	
	// Shows an example of encoding a prime message, and decoding a codeword containing errors.
	private static void showPrimeExample() {
		// Configurable parameters
		PrimeField field = new PrimeField(97);
		Integer generator = 5;
		int msgLen = 9;
		int eccLen = 4;
		ReedSolomon<Integer> rs = new ReedSolomon<>(field, generator, Integer.class, msgLen, eccLen);
		
		// Generate random message
		Integer[] message = new Integer[msgLen];
		for (int i = 0; i < message.length; i++)
			message[i] = rand.nextInt(field.modulus);
		System.err.println("Original message: " + Arrays.toString(message));
		
		// Encode message to produce codeword
		Integer[] codeword = rs.encode(message);
		System.err.println("Encoded codeword: " + Arrays.toString(codeword));
		
		// Perturb some values in the codeword
		double probability = (double)(eccLen / 2) / (msgLen + eccLen);
		int perturbed = 0;
		for (int i = 0; i < codeword.length; i++) {
			if (rand.nextDouble() < probability) {
				codeword[i] = field.add(codeword[i], rand.nextInt(field.modulus - 1) + 1);
				perturbed++;
			}
		}
		System.err.println("Number of values perturbed: " + perturbed);
		System.err.println("Perturbed codeword: " + Arrays.toString(codeword));
		
		// Try to decode the codeword
		Integer[] decoded = rs.decode(codeword);
		System.err.println("Decoded message: " + (decoded != null ? Arrays.toString(decoded) : "Failure"));
		System.err.println();
	}
	
	
	// Tests the Reed-Solomon encoding and decoding logic under many parameters with many repetitions.
	// This prints the results of each test round, and loops infinitely unless
	// stopped by an exception (which should not happen if correctly designed).
	// - Whenever numErrors <= floor(eccLen / 2), the decoding will always succeed,
	//   otherwise the implementation is faulty.
	// - Whenever numErrors > floor(eccLen / 2), failures and wrong answers are perfectly normal,
	//   and success is generally not expected (but still possible).
	private static void testCorrectness() {
		// Field parameters
		BinaryField field = new BinaryField(0x11D);
		Integer generator = 0x02;
		
		// Run forever unless an exception is thrown or unexpected behavior is encountered
		int testDuration = 3000;  // In milliseconds
		while (true) {
			// Choose random Reed-Solomon parameters
			int msgLen = rand.nextInt(field.size) + 1;
			int eccLen = rand.nextInt(field.size) + 1;
			int codewordLen = msgLen + eccLen;
			if (codewordLen > field.size - 1)
				continue;
			int numErrors = rand.nextInt(codewordLen + 1);
			ReedSolomon<Integer> rs = new ReedSolomon<>(field, generator, Integer.class, msgLen, eccLen);
			
			// Do as many trials as possible in a fixed amount of time
			long numSuccess = 0;
			long numWrong   = 0;
			long numFailure = 0;
			long startTime = System.currentTimeMillis();
			while (System.currentTimeMillis() - startTime < testDuration) {
				
				// Generate random message
				Integer[] message = new Integer[msgLen];
				for (int i = 0; i < message.length; i++)
					message[i] = rand.nextInt(field.size);
				
				// Encode message to codeword
				Integer[] codeword = rs.encode(message);
				
				// Perturb values in the codeword
				int[] indexes = new int[codewordLen];
				for (int i = 0; i < indexes.length; i++)
					indexes[i] = i;
				for (int i = 0; i < numErrors; i++) {
					// Partial Durstenfeld shuffle
					int j = rand.nextInt(indexes.length - i) + i;
					int temp = indexes[i];
					indexes[i] = indexes[j];
					indexes[j] = temp;
					// Actual perturbation
					codeword[indexes[i]] ^= rand.nextInt(field.size - 1) + 1;
				}
				
				// Try to decode the codeword, and evaluate result
				Integer[] decoded = rs.decode(codeword);
				if (Arrays.equals(decoded, message))
					numSuccess++;
				else if (numErrors <= eccLen / 2)
					throw new AssertionError("Decoding should have succeeded");
				else if (decoded != null)
					numWrong++;
				else
					numFailure++;
			}
			
			// Print parameters and statistics for this round
			System.err.printf("msgLen=%d, eccLen=%d, codewordLen=%d, numErrors=%d;  numTrials=%d, numSuccess=%d, numWrong=%d, numFailure=%d%n",
				msgLen, eccLen, codewordLen, numErrors, numSuccess + numWrong + numFailure, numSuccess, numWrong, numFailure);
		}
	}
	
	
	private static final Random rand = new Random();
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

参考资料

[1] Reed-Solomon Codes （An introduction to Reed-Solomon codes: principles, architecture and implementation）
[2] Error Correction Coding
[3] Reed-Solomon error-correcting code decoder