检错纠错码

理论

在数据传输时，考虑到各种因素的印象，可能会出现部分数据出错，此时需要使用一些编码方法，使得接受方可以检测出错误，让发送方重新传输；或者让接受方直接纠正错误。随着传输速度不断提高，误码率上升，重新传输的概率提高，通常就会引入纠错码，一般叫做 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 \ge k+r \]

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

\[ 2^r \ge k+r+1 \]

例如当 \(r=3\) 时，\(k \le 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 \le q\) 且 \(q\) 是素数。

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

\[ p_x(a) = \sum_{i=1}^k x_ia^{i-1} \bmod q \]

\[ C(x) = (p_x(a_1), \ldots, 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)\)

实践

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

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

参考文档

• Error correction code

评论