检错纠错码

理论

在数据传输时，考虑到各种因素的印象，可能会出现部分数据出错，此时需要使用一些编码方法，使得接受方可以检测出错误，让发送方重新传输；或者让接受方直接纠正错误。随着传输速度不断提高，误码率上升，重新传输的概率提高，通常就会引入纠错码，一般叫做 FEC（Forward Error Correction）。

核心思路是发送数据的时候，添加冗余，使得原始数据在编码以后，只有一部分合法值，其余的是非法的，且合法值之间保证有一个最小的编辑距离。编辑距离也叫 Hamming 距离，等于异或后二进制表示中 1 的个数。

在传输出错时，如果出错的位数在编辑距离之内，就一定会从合法值变为非法值，此时就可以检测出错误。更进一步，如果出错的位数比较小，距离非法值最近的合法值唯一，此时就可以纠正错误。

奇偶校验 Parity

奇偶校验对每 k 位数据，添加额外的 1 位，记录这 k 位数据中有奇数个 1 还是偶数个 1。奇偶校验编码后，合法值的编辑距离为 2，只能检测出 1 位的错误，无法纠正错误。

编码的效率是 $k / (k + 1)$ 。

UART 协议用的是奇偶校验。

参考：Parity bit

重复编码

重复编码的方法是，把输入的每个位重复 n 次，n 为奇数：例如 n 等于 3，那么 0 变成 000，1 变成 111，两个合法值的编辑距离是 3，此时可以检测出 1 位的错误，也可以纠正 1 位的错误。可以检测出 2 位的错误，但是无法和 1 位的错误区分开。解码的时候，按 n 位分组，每个分组内的 0 和 1 的数量哪个多，就认为原始值是哪个。

编码的效率是 $1 / n$ 。

参考：Repetition code

Hamming 码

Hamming 码的特点是，可以检测并纠正 1 位的错误。为了达到这一点，编辑距离需要保证至少是 3。如果不纠正错误的话，可以检测出 1 位或者 2 位的错误，但是无法区分是哪种情况。

此外如果给 Hamming 码加上额外的奇偶校验位，那么编辑距离至少是 4，就可以检测出 2 位的错误，但是不能纠正 2 位的错误。这种扩展 Hamming 码实现了 SECDED（Single Error Correction，Double Error Detection）。

假设传输的数据是 k 位，添加冗余的 r 位校验码，当出现 1 位错误的时候，为了纠正错误，需要知道错误的位置。错误的位置可能出现在 k+r 位的任意一个地方，那么这个错误的位置应该可以通过冗余的 r 位校验码推断出来，因此：

2^{r} \geq k + r

此外还有一个合法情况，也就是没有出错位置，因此：

2^{r} \geq k + r + 1

例如当 $r = 3$ 时， $k \leq 4$ ，此时如果取 $k = 4$ ，那就是每 4 位数据，添加 3 位的校验码，一共是 7 位。此时就称这个编码为 Hamming(7,4)。

重复编码在 n=3 时等价于 Hamming(3,1)。

编码的效率是 $k / (k + r)$ 。

ECC DRAM 对 64 位数据添加 8 位的冗余，可以采用扩展 Hamming 码来实现 SECDED。

参考：Hamming code

Reed-Soloman

Reed-Solomon 有三个参数：字母表大小 $q$ ，编码后的块大小 $n$ 和数据长度 $k$ ，要求 $k < n \leq q$ 且 $q$ 是素数。

Reed-Solomon 算法的过程是，对于 $k$ 个数据，每个数据范围都在 $[0, q - 1]$ 内，以这 $k$ 个数为系数得到一个多项式 $p$ 。取 $n$ 个点 $a_{1}, \dots a_{n}$ ，分别带入多项式，把结果对 $q$ 取余，就得到了 Reed Solomon 编码：

p_{x} (a) = \sum_{i = 1}^{k} x_{i} a^{i - 1} mod q

C (x) = (p_{x} (a_{1}), \dots, p_{x} (a_{n}))

由于任意两个不同的 $k$ 次多项式，最多只会有 $k - 1$ 个交点，所以 Reed Solomon 编码中，其余的 $n - (k - 1) = n - k + 1$ 个值都是不一样的，所以编辑距离就是 $n - k + 1$ 。

因此 Reed Solomon 可以纠正 $(n - k) / 2$ 个系数的错误。这使得 Reed Solomon 编码可以根据需要，设置不同的编辑距离，对应不同的检错和纠错能力。更进一步，如果错误会连续出现（erasure），由于传输的是多个值，对同一个值产生的多个位的错误和一个位的错误是一样的，因此连续错误的纠错能力更强。

除了上面这种把数据编码为多项式系数的方法，还可以用其他方式。例如把数据设定为多项式在 $k$ 个点上的取值，其余的点的值通过拉格朗日插值法计算得出。这样的好处是编码以后，数据会原样保留下来。

此外还可以预先设定一个多项式 $g (x)$ ，编码的时候，计算 $s (x) = p (x) g (x)$ ，然后传输 $s (x)$ 的 $n$ 个系数，这种方法叫做 BCH（Bose–Chaudhuri–Hocquenghem）。

实践中使用的时候，由于计算机传输时每个字节有 256 种取值，此时如果用素数 $q$ 来限制字母表大小，那就要求 $q$ 是比 256 大的素数，会有所浪费。因此，常用大小为 256 的 Galois Field 来替代素数域，上面多项式中的运算都替换为 Galois Field 中对应的运算，此时一个符号就是一个字节。例如 RS(255,223) 码（8 位符号）就是每 223 个字节分为一组，编码为 255 个字节的数据，可以纠正 16 个字节的错误。

如果希望缩减 $n$ ，可以填充一部分字节，例如 RS(200,168) 码，给数据填充 55 个零字节后，再按照 RS(255,223) 进行编码，得到 32 个校验字节，传输的时候，只传输 168+32 个字节，此时要求在 Reed Solomon 编码的时候，采用保留原始数据的方法。

参考：Reed-Solomon error correction

CRC

CRC 是把数据当成一个 GF(2) 多项式的系数，除以已知的多项式，得到的余数就是 CRC 的结果。CRC 主要是为了检测错误，但在特定条件下，也可以纠正错误，但 CRC 主要还是用来检测错误。此外，CRC 不要求数据长度固定。

小结

下面给出不同检错纠错码的对比：

	编辑距离	数据位数	冗余位数	总位数
奇偶校验	$2$	$n$	$1$	$n + 1$
重复编码	$n$	$1$	$n - 1$	$n$
Hamming 码	$3$	$2^{r} - r - 1$	r	$2^{r} - 1$
扩展 Hamming 码	$4$	$2^{r} - r - 1$	$r + 1$	$2^{r}$
Reed Solomon	$n - k + 1$	$k \log_{2} (q)$	$(n - k) \log_{2} (q)$	$n \log_{2} (q)$

实践

很多协议采用了检错纠错码来保证数据的可靠性，例如：

以太网 FCS（Frame Check Sequence）：4 字节的 CRC，保护一个 MTU 加头部大小的数据
IP（Internet Protocol）：2 字节的 Internet Checksum，保护一个 IP 头部的数据
PCIe TLP（Transaction Layer Packet）：4 字节的 CRC，保护一个 TLP 的数据
PCIe DLLP（Data Link Layer Packet）：2 或 4 字节的 CRC，保护一个 DLLP 的数据
CXL 68B FLIT：2 字节的 CRC，保护 64 字节的数据
CXL Standard 256B FLIT：8 字节的 CRC，6 字节的 FEC，保护 242 字节的数据
CXL Latency Optimized 256B FLIT：前半部分 6 字节的 CRC 保护 122 字节的数据，后半部分 6 字节的 CRC 保护 116 字节的数据；最后 6 字节的 FEC 保护完整的 FLIT

参考文档

Error correction code