差错控制

💡 低优先级

说实话本节细节极多但是考查频率很低，考的话一般是在选择题考一题，这一节的几个知识点说实话只能硬背了，大家可以根据自身精力决定要不要搏一搏这可能出现的两分。

奇偶校验码（Parity Check Code）是一种 简单高效 的错误检测机制，广泛应用于数据传输和存储系统中，用于发现传输过程中发生的错误。其核心思想是在原始数据后增加 1 位校验位（Parity Bit），使整个数据（原始数据 + 校验位）中 “1” 的总数满足预先规定的奇偶规则。

奇偶校验码分为 奇校验 和 偶校验 两种。

奇校验规则：数据（包括校验位）中 “1” 的总数为奇数。
偶校验规则：数据（包括校验位）中 “1” 的总数为偶数。

注意

为什么奇校验中，原始数据已有奇数个 “1” 时，校验位反而为 0？

需要注意的是，校验位本身并不表示奇偶性，它的作用是使 整个数据（原始数据 + 校验位） 满足规定的奇偶规则。

例如采用 奇校验：

若原始数据中已经有 奇数个 “1”，说明已经满足奇校验要求，因此校验位设置为 0，保持总数不变。
若原始数据中有 偶数个 “1”，则需要补一个 1，使总数变为奇数，因此校验位设置为 1。

偶校验的原理完全相同，只不过目标变成了使 “1” 的总数为偶数。

类型	数据中 “1” 个数	校验位	接收端判定
奇校验	偶数	1	若收到后 “1” 的总数不是奇数，则检测到错误。
奇校验	奇数	0	若收到后 “1” 的总数不是奇数，则检测到错误。
偶校验	奇数	1	若收到后 “1” 的总数不是偶数，则检测到错误。
偶校验	偶数	0	若收到后 “1” 的总数不是偶数，则检测到错误。

奇偶校验码的 工作过程 如下：

发送端：统计原始数据中 “1” 的个数，根据奇校验或偶校验规则计算校验位，并将校验位附加到原始数据后一起发送。
接收端：对接收到的数据（包括校验位）再次统计 “1” 的个数，检查是否满足预设的奇偶规则；若不满足，则说明传输过程中发生了错误。

需要注意的是，奇偶校验码只能 检测错误，不能 纠正错误，因为它无法确定出错比特的位置。此外，它能够检测 任意奇数个比特错误（例如 1 位、3 位、5 位错误），但 无法检测偶数个比特错误（例如 2 位、4 位错误）。

检错能力	是否支持
单比特错误检测	✔
任意奇数个比特错误检测	✔
偶数个比特错误检测	✘
错误定位	✘
错误纠正	✘

循环冗余码

CRC 校验码

循环冗余校验（CRC，Cyclic Redundancy Check）是一种常用的数据完整性校验方法，广泛应用于数据传输和存储系统中，用于检测数据在传输过程中是否发生了错误。

其 核心思想 是将数据视为一个二进制多项式，并使用预先约定好的 生成多项式 对其进行 模 2 除法，最终所得的余数就是 CRC 校验码。

模 2 除法

CRC 中最核心的运算就是 模 2 除法（Modulo-2 Division）。

它与我们熟悉的十进制长除法过程基本相同，不同之处在于，模 2 除法中的 减法运算被替换为了按位异或（XOR）运算，整个计算过程中 没有借位。

因此，模 2 除法可以简单理解为：

将生成多项式与当前被除数的最高位对齐。
若当前最高位为 1，则与生成多项式进行一次 按位异或。
若当前最高位为 0，则无需计算，直接向右移动一位。
重复上述过程，直到所有数据处理完成，最后剩余的几位就是 CRC 校验码。

由于整个过程中只涉及异或和移位运算，因此 CRC 十分适合使用硬件电路实现，计算效率很高。

校验流程

CRC 校验码的生成与校验过程如下：

确定生成多项式
发送端和接收端事先约定好同一个 生成多项式。
扩展原始数据
若生成多项式共有 k 位，则在原始数据末尾补 k−1 个 0，得到扩展数据。
计算 CRC 校验码
使用扩展数据对生成多项式进行 模 2 除法，所得余数就是 CRC 校验码。
发送数据
将 CRC 校验码附加到原始数据末尾，组成完整的数据帧并发送。
接收校验
接收端收到数据后，再次使用相同的生成多项式进行 模 2 除法。若余数为 0，则说明数据未检测到错误；否则说明数据在传输过程中发生了错误。

发送方

假设原始数据为：1010001101，选用的生成多项式为：110101，则对应的多项式形式为：

x^{5} + x^{4} + x^{2} + 1

发送方计算 CRC 校验码的过程如下：

扩展数据：生成多项式共有 6 位，因此在原始数据末尾补上 6 - 1 = 5 个 0，得到扩展数据：
```
101000110100000
```
进行模 2 除法：使用扩展数据对生成多项式进行 模 2 除法（实际计算过程中使用异或操作）。

最终得到余数：

因此，发送的数据帧为：

1010001101 01110

接收方

继续以上述例子进行说明，接收方收到的数据为：

101000110101110

接收方同样使用生成多项式 110101 进行 模 2 除法：

最终余数为：

说明数据在传输过程中 未检测到错误，因此 校验通过。

为什么接收方不需要重新补 0？

有人说，接收方也可以采用另一种等价的校验方式：

从接收帧中分离出原始数据和 CRC 校验码；
在原始数据后重新补上 (r) 个 0；
重新计算 CRC 余数；
将重新计算出的余数与接收到的 CRC 校验码进行比较。

即判断：

CRC (M^{'} (x)) = ? R^{'} (x)

其中， $M^{'} (x)$ 是接收到的数据部分， $R^{'} (x)$ 是接收到的 CRC 字段， $G (x)$ 是生成多项式。

这种方法在数学上与直接对完整接收帧进行模 2 除法是等价的。不过在一般的 CRC 原理讲解和硬件实现中，通常采用更直接的方式：

完整接收帧 mod G (x)

然后检查余数是否为全 0。

海明码

海明码考点

海明码（Hamming Code）是一种用于 错误检测 和纠正的编码方案，通常用于数据传输和存储系统中。它的主要目标是检测和纠正数据中的 单比特错误。

海明码的核心思想是在 数据位 之间插入一定数量的 校验位（也称为奇偶校验位），使得每个校验位都负责检查一组特定的位。校验位的数量取决于数据位的数量，并且它们的位置通常是 2 的幂次（即第 1 位、第 2 位、第 4 位……）。

生成过程

以一个实例说明海明码的 生成和纠正 过程：

步骤 1：确定校验位数量

假如我们的数据是 $1011$ ，也就是 $k = 4$ 位。根据海明码的原则，我们需要确定足够的校验位 $r$ 来满足以下条件：

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

对于 $k = 4$ （数据位），我们找到最小的 $r$ 为 3。

注意

对于 $k$ 位数据，应该有多少位校验位

假设我们有 $k$ 位数据，我们需要添加 $r$ 位校验位，那么校验位的总数必须满足以下条件：

所有数据位和校验位的总数加起来可以由校验位来表示。也就是说，每一位数据位和校验位在位模式中都有一个唯一的表示。这意味着 $2^{r}$ 必须至少等于 $k + r + 1$ ，其中加 $1$ 是因为校验位模式全为零（即没有错误）的情况也必须被考虑在内，即

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

步骤 2：放置校验位和数据位

首先将校验位（ $p$ ）插入到数据位中的适当位置。校验位下标是 2 的幂（ $1, 2, 4, 8, ...$ ）。

第 $1 (2^{0})$ 位：校验位 $p_{1}$
第 $2 (2^{1})$ 位：校验位 $p_{2}$
第 $4 (2^{2})$ 位：校验位 $p_{3}$

然后再放置剩余的 数据位 $d$ ：

第 $3$ 位：数据位 $d_{1}$
第 $5$ 位：数据位 $d_{2}$
第 $6$ 位：数据位 $d_{3}$
第 $7$ 位：数据位 $d_{4}$

位置	7	6	5	4	3	2	1
海明码	$d_{4}$	$d_{3}$	$d_{2}$	$p_{3}$	$d_{1}$	$p_{2}$	$p_{1}$
数据	1	1	0	-	1	-	-

注意

注意到上述我们提到的关于校验位和数据位的第 $n$ 位，下标是从 1 开始 而不是 0 开始的。

步骤 3：计算校验位

首先给出位置下标的二进制表示：

位置	7	6	5	4	3	2	1
二进制	111	110	101	100	011	010	001

$p_{1}$ 检查位置 $1$ 、 $3$ 、 $5$ 、 $7$ 的位（最低位为 1）。所以 $p_{1} = d_{1} \oplus d_{2} \oplus d_{4} = 1 \oplus 0 \oplus 1 = 0$ ，所以 $p_{1} = 0$ 。
$p_{2}$ 检查位置 $2$ 、 $3$ 、 $6$ 、 $7$ 的位（次低位为 1）。这些位的异或值为 $p_{2} = d_{1} \oplus d_{3} \oplus d_{4} = 1 \oplus 1 \oplus 1 = 1$ ，所以 $p_{2} = 1$ 。
$p_{3}$ 检查位置 $4$ 、 $5$ 、 $6$ 、 $7$ 的位（最高位为 1）。这些位的异或值为 $p_{3} = d_{2} \oplus d_{3} \oplus d_{4} = 0 \oplus 1 \oplus 1 = 0$ ，所以 $p_{3} = 0$ 。

步骤 4：生成海明码

位置	7	6	5	4	3	2	1
海明码	$d_{4}$	$d_{3}$	$d_{2}$	$p_{3}$	$d_{1}$	$p_{2}$	$p_{1}$
数据	1	1	0	0	1	1	0

所以， $1011$ 的 $(7, 4)$ 海明码是 0110011 。任何一位的单一错误都可以通过分析 校验位 来检测并纠正。

检测和纠错

还是以上文的例子来说明海明码检测和纠错的过程。

假设在传输过程中第二位出现了错误，接收的码变为 $0010011$ 。

首先，接收者现在要 重新计算校验位：

$p_{1}$ （位置 1）：检查二进制最低位为 1 的位置（1, 3, 5, 7），即 $p_{1}, d_{1}, d_{2}, d_{4}$
- $p_{1}^{'} = 0 \oplus 1 \oplus 0 \oplus 1 = 0$
- 接收到的 $p_{1} = 0$ ，所以 $p_{1}^{'} = p_{1}$ ，无错误
$p_{2}$ （位置 2）：检查二进制第二位为 1 的位置（2, 3, 6, 7），即 $p_{2}, d_{1}, d_{3}, d_{4}$
- $p_{2}^{'} = 0 \oplus 1 \oplus 1 \oplus 1 = 1$
- 接收到的 $p_{2} = 0$ ，所以 $p_{2}^{'} \neq = p_{2}$ ，有错误
$p_{3}$ （位置 4）：检查二进制第三位为 1 的位置（4, 5, 6, 7），即 $p_{3}, d_{2}, d_{3}, d_{4}$
- $p_{3}^{'} = 0 \oplus 0 \oplus 1 \oplus 1 = 0$
- 接收到的 $p_{3} = 0$ ，所以 $p_{3}^{'} = p_{3}$ ，无错误

可以看到有错误发生，接下来需要 生成错误模式：

(p_{1}^{'} \oplus p_{1}, p_{2}^{'} \oplus p_{2}, p_{3}^{'} \oplus p_{3}) = (0 \oplus 0, 1 \oplus 0, 0 \oplus 0) = (0, 1, 0)

错误模式为二进制 010，十进制值为 2，表示错误在位置 2（即 $p_{2}$ ）。

最后一步是 纠正错误：位置 2 的值 $p_{2}$ 从 0 翻转为 1，得到纠正后的码字：

位置	7	6	5	4	3	2	1
海明码	$d_{4}$	$d_{3}$	$d_{2}$	$p_{3}$	$d_{1}$	$p_{2}$	$p_{1}$
修改前	1	1	0	0	1	0	0
修改后	1	1	0	0	1	1	0

现在，海明码回到了正确的 0110011 状态。

海明距离

在数据传输或存储过程中，比特可能会受到噪声干扰，从 0 变成 1，或者从 1 变成 0，这种现象称为 比特翻转。

例如，发送端原本发送：101101，接收端实际收到：100111

对比两个比特序列可以发现，第 3 位和第 5 位发生了变化，因此一共发生了 2 位错误。

这种“两个等长比特序列在多少个位置上不同”的数量，就称为它们之间的 海明距离。

设两个长度相同的比特序列分别为：

x = x_{1} x_{2} \dots x_{n}, y = y_{1} y_{2} \dots y_{n}

则它们之间的海明距离记作：

d (x, y)

其值等于满足 $x_{i} \neq = y_{i}$ 的位置个数。

因此，如果发送码字为 $x$ ，接收序列为 $y$ ，并且：

d (x, y) = t

就说明传输过程中一共发生了 $t$ 位错误。

编码集

应用层产生的原始数据可以由 0 和 1 任意组合。对于长度为 $k$ 的原始信息，一共有 $2^{k}$ 种可能的比特串。

为了使数据具备检错或纠错能力，发送端会对原始信息进行差错控制编码，将每个长度为 $k$ 的 原始信息 转换为长度为 $n$ 的码字，通常有：

n > k

其中，多出的 $n - k$ 位用于承载校验信息，因此称为 冗余位。

编码过程可以表示为：

0, 1^{k} ⟶ C \subseteq 0, 1^{n}

其中， $C$ 表示编码规则能够产生的所有码字的集合，称为 编码集，也称为 码（code）。

全部可能的 $n$ 位比特串共有 $2^{n}$ 个，但编码规则通常只使用其中的 $2^{k}$ 个作为码字。其余 $2^{n} - 2^{k}$ 比特串仍然是正常的二进制序列，只是不属于当前编码集。

例如，假设用 2 位信息表示四种原始数据，并将其编码为 3 位码字：

00011011 ⟶ 000, ⟶ 011, ⟶ 101, ⟶ 110.

那么该编码集为：

C = 000, 011, 101, 110

在全部 $2^{3} = 8$ 个 3 位比特串中，只有这 4 个属于编码集。

接收端事先知道发送端只会发送编码集中的码字。因此，当接收到一个不属于编码集的比特串时，就可以判断数据在传输或存储过程中发生了错误。

最小海明距离

编码集 $C$ 的 最小海明距离 定义为任意两个 不同码字之间海明距离的最小值：

x, y \in C x \neq = y min d (x, y)

通常也将其简记为 $d$ 。

最小海明距离反映了编码集中距离最近的两个合法码字相隔多远。它直接决定编码集的容错能力：

最多可以检测的错误位数为：

d_{m i n} - 1

最多可以纠正的错误位数为：

t = ⌊ \frac{d _{m i n} - 1}{2} ⌋

检测和纠错位数是如何得到的

其原因可以从码字之间的距离进行理解。

假设两个合法码字 $x$ 和 $y$ 的距离为 $d_{m i n}$ 。要把 $x$ 经过比特翻转变成另一个合法码字 $y$ ，至少需要翻转 $d_{m i n}$ 位。因此，只要错误位数小于 $d_{m i n}$ ，错误后的序列就不可能成为另一个合法码字，接收端便能够判断数据发生了错误。

所以最多可以检测 $d_{m i n} - 1$ 位错误。

对于纠错，接收端通常采用 最近邻译码：将接收到的序列判定为与其海明距离最近的合法码字。

要保证接收序列仍然唯一地靠近原码字，原码字周围可纠正的范围不能与其他码字的可纠正范围重叠。因此需要满足：

2 t < d_{m i n}

由此得到：

t = ⌊ \frac{d _{m i n} - 1}{2} ⌋

最小海明距离越大，码字在整个比特空间中越“分散”，发生一定数量的比特翻转后，接收端越容易区分原始码字。

例如，设编码集为：0000, 0110, 1011

三组码字之间的海明距离分别为：

0000 与 0110 的海明距离为 2，第 2、3 位不同；
0000 与 1011 的海明距离为 3；
0110 与 1011 的海明距离为 3。

因此，该编码集的最小海明距离为：

d_{m i n} = 2

根据公式，该编码集最多可以：

检测 $d_{m i n} - 1 = 1$ 位错误；
纠正 $⌊ \frac{1}{2} ⌋ = 0$ 位错误。

也就是说，它能够发现单比特错误，但无法保证确定原始码字。

例如，接收到 0010，它与 0000 和 0110 的海明距离都为 (1)。因此，接收端虽然知道发生了错误，但无法判断原本发送的是哪个码字。

如果想要稳定地纠正 1 位错误，就必须使任意两个合法码字之间至少相隔 3 位，即：

d_{m i n} \geq 3

海明码示例

海明码（Hamming Code） 是一种经典的线性分组码，其最小海明距离为 $d = 3$ 。这意味着：

可以 检测最多 2 位错误。
可以 纠正 1 位错误。

接收端在解码过程中，会计算出一个称为 伴随式（syndrome） 的比特序列，用于判断是否发生了错误，以及错误的位置：

若伴随式为全零，说明数据未被破坏；
若伴随式为非零，且对应某个位的错误模式，则可准确定位并纠正该位；
若发生 2 位错误，伴随式可能不唯一，可检测但不可纠正，因为错误位置无法唯一确定。