跳转至

错误检测和纠正

物理信道在数据传输的过程中发生错误不可避免，因此必须有处理传输错误的方法。主要有两种基本的策略，都在发送的数据中加入冗余信息。

一种策略是包含足够多的冗余信息，以便接收方能够推断出被发送的数据的正确形式。这种策略使用一种纠错码，被称为前向纠错（FEC）。

另一种策略是包含恰好足够的冗余信息，使得接收方能够推断出是否发生了错误，但是不知道正确形式，此时接收方可以请求重传。这种策略使用检错码。

纠错码

主要有下面四种纠错码：

  • 海明码；
  • 二进制卷积码；
  • 里德-所罗门码；
  • 低密度奇偶校验码。

以上所有编码都将冗余信息加入到待发送的信息中。考虑这样的模型：一帧由 \(m\) 个数据位（消息）和 \(r\) 个冗余位（校验位）组成，数据块的总长度为 \(n = m + r\) 位码字，描述为 \((m, n)\) 码。我们定义码率为码字中的数据位占比，用 \(m / n\) 表示。

所有的 \(n\) 位码字可以构成一个集合，称为编码集，集合的总码字数位 \(2^n\)，其中有 \(2^m\) 个有效码字，\(2^n - 2^m\) 个无效码字。若一个有效码字由于差错变成一个无效码字，就能判断出有错；若一个有效码字错成了另一个有效码字，则错误就检测不出来了。

海明距离

定义两个码字中不同位的个数为海明距离。要计算两个码字的海明距离，可以对他们做异或运算，然后计算结果中 1 的个数：

\[ \begin{aligned} &10001001 \\ &10110001 \\ \hline &00111000 \end{aligned} \]

这样就能确定 10001001 和 10110001 的海明距离为 3，编码集的海明距离为其中海明距离最小的两个有效码字的海明距离，编码集的检错与纠错的能力取决于海明距离。

有关检错和纠错的两个重要结论

  • 如果要检测出 \(d\) 个比特错误，则编码集的海明距离至少应为 \(d+1\)；
  • 如果要纠正 \(d\) 个比特错误，则编码集的海明距离至少应为 \(2d+1\)。

Example

考虑一个实例：编码集中有四个有效码字

\[ \begin{aligned} 000000，000111，111000，111111 \end{aligned} \]

海明距离为 \(3\)，则可检测 \(3-1 = 2\) 个比特错，可纠正 \((3-1)/2 = 1\) 个比特错：如果确定只会发生 \(1\) 比特的错误，则只需要找到离接收信息最近的正确信息即为原信息。

校验位数下界

考虑下面的问题：

设计一种编码，它有 \(m\) 个信息位和 \(r\) 个校验位，当 \(r\) 满足什么条件时，能纠正所有单比特错？

根据定义，码字长度 \(n=m+r\)，其中有效码字有 \(2^m\) 个。对于 \(2^m\) 条合法消息，任何一条消息都对应 \(n\) 个距离为 \(1\) 的非法码字。这些非法码字可以这样构成：将该消息对应的合法码字的 \(n\) 个位逐个取反。

因此，每 \(2^m\) 条合法消息需要 \(n + 1\) 个位模式标识它们。由于总共只有 \(2^n\) 个位模式，所以必须有 \((n + 1)2^m \leqslant 2^n\)，化简一下得：

\[ (m + r + 1) \leqslant 2^r \]

即为给定 \(m\) 情况下纠正单比特错的校验位下界。

海明码

海明在 1950 年提出一种编码来纠正单比特错的编码。该编码是将码字内的位从左到右依次编号，编号为 \(2^k (k \geqslant 0)\) 的位是校验位，其余为信息位。

每个校验位的取值应使得包括自己在内的一些集合服从规定的奇偶性。集合的选取规则为：对编号为 \(k\) 的信息位来说，\(k\) 可以分解成 \(2\) 的幂的和，如编号为 \(11 = 1 + 2 + 8\)，即第 \(11\) 位由 \(1, 2, 8\) 校验位校验，它同时属于 \(1, 2, 8\) 所在的集合。

发送方计算海明码

假设发送端要发送字母 \(A\)，其 ASCII 码为 \(1000001\)，考虑用海明码对其进行编码。根据校验位数下界

\[ (7 + r + 1) \geqslant 2^r \implies r \geqslant 4 \]

因此至少需要 4 个校验位，也就是 11 位海明码。按照海明码编码规则，考虑如下编码：

\[ h_1h_2h_3h_4h_5h_6h_7h_8h_9h_{10}h_{11} = p_1p_2 1 p_4 0 0 0 p_8 0 0 1 \]

其中 \(p_i, i = 1, 2, 4, 8\) 表示校验位。下面根据规则确定决定校验位取值的集合，例如 \(3 = 1 + 2\)，因此 \(h_3\) 应该同时包含于决定 \(p_1\) 和 \(p_2\) 的集合中，以此类推，我们有

\[ \begin{aligned} &k_1 = \{ p_1, h_3, h_5, h_7, h_9, h_{11} \} = p_1 1 0 0 0 1\\ &k_2 = \{ p_2, h_3, h_6, h_7, h_{10}, h_{11} \} = p_2 1 0 0 0 1\\ &k_4 = \{ p_4, h_5, h_6, h_7 \} = p_4 0 0 0 \\ &k_8 = \{ p_8, h_9, h_{10}, h_{11} \} = p_8 001 \end{aligned} \]

其中 \(k_i, i = 1, 2, 4, 8\) 表示决定 \(p_i\) 取值的集合。若采用偶校验，则可以推出 \((p_1, p_2, p_3, p_4) = (0, 0, 0, 1)\)，得到最终的海明码为 \(00100001001\)。

接收方收到信息后，重新计算海明码，将不符合奇偶校验的位数下标相加即可得到出错的位置。

接收方纠错

发送方采用前面例子得到的海明码，交由物理层发送。假设接收方得到的编码为 \(0010\textcolor{red}{1}001001\)，则根据规则计算各个集合的奇偶校验：

\[ \begin{aligned} &k_1 = \{ p_1, h_3, h_5, h_7, h_9, h_{11} \} = \textcolor{red}{0 1 1 0 0 1}\\ &k_2 = \{ p_2, h_3, h_6, h_7, h_{10}, h_{11} \} = 0 1 0 0 0 1\\ &k_4 = \{ p_4, h_5, h_6, h_7 \} = \textcolor{red}{0 1 0 0} \\ &k_8 = \{ p_8, h_9, h_{10}, h_{11} \} = 1001 \end{aligned} \]

显然 \(p_1\) 和 \(p_4\) 不符合，将其下标相加 \(1 + 4 = 5\)，得知 \(h_5\) 出错，取反得到 \(00100001001\) 即为正确信息。

本文关于纠错码只介绍上述两种，更多的可自行查阅资料。

检错码

纠错码被广泛应用于无线链路，然而对于光线或铜线这种出错率较低的链路，检错重传通常更加有效。本文考虑下面三种检错方法：

  • 奇偶校验
  • 校验和
  • 循环冗余校验码

奇偶校验

一种基本的检错方式是奇偶校验，在数据后面增加一个奇偶校验位（parity bit）的编码，奇偶校验位的选取原则是使码字内的 1 的数目为偶数（偶校验）或奇数（奇校验）。

\[\begin{aligned} 10110101 \to \begin{cases} 10110101\textcolor{red}{1} & \text{偶校验} \\ 10110101\textcolor{red}{0} & \text{奇校验} \end{cases} \end{aligned}\]

这种编码的海明距离为 2，可检测单比特错误。

交错奇偶校验

交错奇偶校验是一种改进的奇偶校验，用于检测数据块中的突发性错误。考虑将 \(k\) 个 \(n\) 比特的数据组成的数据块组织成一个矩阵：

\[ \begin{aligned} \left(\begin{array}{cccc} d_{11} & d_{12} & \cdots & d_{1n} \\ d_{21} & d_{22} & \cdots & d_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ d_{k1} & d_{k2} & \cdots & d_{kn} \end{array}\right) \end{aligned} \]

对每一列分别进行奇偶校验，生成列校验位：

\[ \begin{aligned} \left(\begin{array}{cccc} d_{11} & d_{12} & \cdots & d_{1n}\\ d_{21} & d_{22} & \cdots & d_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ d_{k1} & d_{k2} & \cdots & d_{kn}\\ \hline p_{1} & p_{2} & \cdots & p_{n} \end{array}\right) \end{aligned} \]

其中 $p_{j} $ 是第 \(j\) 列的奇偶校验位。

接收方收到数据后，重新计算行校验位和列校验位，通过比对接收到的奇偶校验和重新加酸的结果可以检测出是否发生错误。

校验和

校验和是一种简单的检错码，通过对数据块中的所有字节进行二进制求和，并将结果附加到数据块的末尾来实现。接收方对接收到的数据块进行相同的求和操作，并检查结果是否与附加的校验和匹配。

假设有一个数据块 10110101 11001010 11110000，计算校验和如下：

\[ \begin{aligned} &10110101 \\ &11001010 \\ \hline &01111111 \\ &11110000 \\ \hline &01101111 \end{aligned} \]

将校验和 01101111 附加到数据块末尾，得到 10110101 11001010 11110000 01101111。接收方收到数据后，进行相同的求和操作，若结果为 00000000，则说明数据无误，否则说明数据出错。

校验和方法可以检测单比特错误和某些多比特错误，但不能纠正错误。

循环冗余校验

CRC（Cyclic Redundancy Code，循环冗余码，也叫多项式编码）是一种高性能的检错编码。其基本思想是将位串中每一位二进制数看成是一个一元多项式的系数，则一个 \(k\) 位帧可表示成一个阶数为 \(k-1\) 的从 \(x^{k-1}\) 到 \(x^0\) 的 \(k\) 次多项式，如 \(110001\) 表示成 \(x^5 + x^4 + 1\) 为一个 \(5\) 阶多项式。

CRC 编码过程

  1. 设发送方发送 \(m\) 位长的帧多项式为 \(M(x)\)，双方需共同选择一个生成多项式 \(G(x)\)，其阶数为 \(r\)，且必须满足 \(m > r + 1\)。
  2. 将待发送的消息多项式 \(M(x)\) 左移 \(r\) 位，得到 \(M(x) \cdot x^r\)。
  3. 用 \(M(x) \cdot x^r\) 按模 2 除法除以 \(G(x)\)，得到余数 \(R(x)\)。
  4. 按模 2 减法将余数 \(R(x)\) 从多项式 \(M(x)\) 中减去，得到编码后的多项式 \(T(x)\)。

Note

多项式以 2 为模运算，其加减法及除法中的减法都同于异或操作，只有被除数和除数等长时才作减法。

CRC 解码过程

接收方收到编码后的消息后，进行以下步骤：

  1. 用接收到的消息除以生成多项式 \(G(x)\)。
  2. 如果余数为 0，则说明数据无误；否则说明数据出错。

CRC 编码示例

假设生成多项式 \(G(x) = x^3 + x + 1\)，对应的二进制表示为 \(1011\)。待发送的消息为 \(1101\)，对应的多项式为 \(M(x) = x^3 + x^2 + 1\)。

  1. 将消息多项式左移 3 位，得到 \(M(x) \cdot x^3 = 1101000\)。
  2. 用 \(1101000\) 除以 \(1011\)，得到余数 \(1010\)。
  3. 将余数 \(1010\) 从 \(x^r M(x)\) 中减去，得到编码后的消息 \(T(x) = 1100010\)。

接收方收到 \(T(x)\) 后，用 \(T(x)\) 除以 \(1011\)，如果余数为 0，则说明数据无误，否则说明数据出错。

CRC 能检验出所有长度小于等于 \(r\) 的错误。