error detection and correction

Galois Field

Cyclic Redundancy Check

对于 RS 码的最小 hamming distance 为 $d_{\min}=n-d$

对于检错与纠错:

检查 $k$ 个错需要 hamming distance $k+1$ 的码, 因为有 $k+1$ 个错可能没错; 有 $r>k+1$ 个错等价于有 $(r\mod (k+1))$ 个错
纠正 $k$ 个错需要 hamming distance $2k+1$ 的码, 为了距离为 $k$ 的范围不重叠

因为 RS 是纠错码, 所以 $d_{\min} \geq 2k+1$

即 $n\geq d+2k+1$, 即要想从 $d+1$ 个原始数据中纠正最多 $k$ 个错, 需要至少 $d+2k+1$ 个数据

用于解码 Reed-Solomon

对于次数为 $d$ 的多项式 $P(x)$ ($d+1$ 个系数), 如果要纠正 $k$ 个错, 需要至少 $d+2k+1$ 个数据

假设我们接收到的系数为 $r_0 \cdots r_{d+2k}$

假设出错的所有下标集合为 $Z=\set{r_i \not=P(i)}$, 大小为 $|Z|\leq k$

构造一个多项式 $\displaystyle E(x)=\prod_{i\in Z}(x-i)$

则我们有恒等式 $P(x)\cdot E(x)=r_x \cdot E(x)$

同时如果 $|Z|=k$, 那么 $E(x)$ 可表示成 $x^k+e_{k-1}x^{k-1}+\cdots+e_0$

$P(x)\cdot E(x)$ 可表示成 $f_{d+k}x^{d+k} + \cdots +f_0$

那么将所有 $x=0,\cdots,d+2k$ 插入多项式恒等式，得到了 $d+2k+1$ 个未知量，$d+2k+1$ 个等式

未知量指 $f_{d+k}, \cdots ,f_0,e_{k-1},\cdots,e_0$

解线性方程得到所有的 $f_{d+k}, \cdots ,f_0,e_{k-1},\cdots,e_0$

输出多项式 $\frac{P(x)\cdot E(x)}{E(x)}$, 系数即为所求

取有限域 ($\mathbb{F}_7$) (模 7 计算), 设 $P(x)=2x+1$ 为原始信息多项式, 容错能力 $k=1$, 因此发送 $d+2k+1 = 1 + 2 + 1 = 4$ 个点

计算发送值: $$ \begin{array}{c|cccc} x & 0 & 1 & 2 & 3 \ \hline P(x) & 1 & 3 & 5 & 0 \end{array} $$

即发送序列: $(1,3,5,0)$.

假设第 3 个符号出错 (即 $r_2$ 变成 6):

接收到: $$ \tilde{r} = (1, 3, 6, 0) $$ 其中真实 $r_2=5$, 现在错误为 $6$.

我们要解 $Q(x)=P(x)E(x)$, 其中 $\deg P = 1, \deg E = 1, \Rightarrow \deg Q = 2$.

设: $$ E(x) = x + e_0,\quad Q(x) = q_2x^2 + q_1x + q_0 $$

等式: $$ Q(x_i) = \tilde{r}_i E(x_i) $$

对于 $x=0,1,2,3$, 得到 4 个方程.

$q_0 = e_0$

$q_2+q_1+q_0 = 3 + 3e_0$

$4q_2 + 2q_1 + q_0 = 5 + 6e_0$

$2q_2 + 3q_1 + q_0 = 0$

求解同余方程 ($\mod 7$), 我们得: $$ E(x)=x+5,\quad Q(x)=2x^2+4x+5. $$

做多项式除法 ($\mod 7$):

\[ P(x) = \frac{Q(x)}{E(x)}. \]

$2x^2 \div x = 2x$. 乘回: $2x(x+5)=2x^2+10x\equiv2x^2+3x$. 相减: $(2x^2+4x+5) - (2x^2+3x) = x+5$.
$(x+5) \div (x+5) = 1$. 相减得到 0.

所以 $P(x) = 2x + 1$