差错控制

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

奇偶校验码

奇偶校验码（Parity Check Code）是一种 简单高效 的错误检测机制，广泛应用于数据传输和存储系统。它一定能发现 单比特错误，更一般地能检测任意奇数个比特错误，但会漏掉偶数个比特同时翻转的情况。其核心思想是添加一个 校验比特（parity bit），确保码字中“1”的总数符合特定奇偶规则。

奇偶校验码有两种常见的类型：奇校验 和 偶校验。

奇校验（Odd Parity）：
- 校验比特的值使数据（包括校验比特）中“1”的总数为奇数。
- 例如，若原始数据“1”的个数为偶数，校验比特设为 1；若为奇数，设为 0。
- 若接收端检测到“1”的总数为偶数，则说明传输中存在错误。
偶校验（Even Parity）：
- 校验比特确保数据中“1”的总数为偶数。
- 例如，若原始数据“1”的个数为奇数，校验比特设为 1；若为偶数，设为 0。
- 若接收端检测到“1”的总数为奇数，则表明数据出错。

奇偶校验码的 工作原理 如下：

发送端：根据奇校验或偶校验规则，计算原始数据中 “1” 的个数，设置校验比特，并将数据连同校验比特一起发送。
接收端：检查接收到的数据（包括校验比特）中 “1” 的总数是否符合预设规则。若不符合，说明发生了奇数个比特错误；若符合，也不能排除偶数个比特错误。

奇偶校验的工作原理是发送端计算数据中所有比特的总数，并根据所选的奇偶性规则设置校验比特的值。接收端在接收数据后再次计算所有比特的总数，包括校验比特，然后检查总数是否满足所选的奇偶性规则。如果总数不符合规则，接收端将检测到错误。

循环冗余码

循环冗余校验（CRC, Cyclic Redundancy Check）是一种常用的数据完整性校验方法，广泛应用于数据传输和存储系统中，用于检测数据在传输过程中是否发生了错误。其核心思想是将数据视为一个二进制多项式，并使用特定的 生成多项式 对其进行 模 2 除法，最终所得的余数即为 CRC 校验值。

校验流程

CRC 的基本校验过程包括以下几个步骤：

设待发送数据对应多项式为 $M(x)$ ，生成多项式为 $G(x)$ ，且 $G(x)$ 的最高次数为 $r$ （二进制表示共 $r+1$ 位）。发送端计算

R(x)=x^rM(x)\bmod G(x)

并发送码字

T(x)=x^rM(x)+R(x)

生成多项式 CRC 的关键是一个预先定义好的 生成多项式，通常用二进制数表示。该多项式必须在发送端和接收端之间事先达成一致。
计算校验码（发送端） 发送端将待发送的数据帧看作一个二进制多项式。若生成多项式二进制表示有 $k=r+1$ 位，就在数据末尾附加 $k-1$ 个 0，得到 扩展数据。将这组数据用 模 2 除法 除以生成多项式，得到的 $r$ 位余数即为 CRC 校验码。
附加并发送 将上述余数作为 CRC 校验码，附加在原始数据帧之后，组成完整的传输数据帧并发送。
校验（接收端） 接收端收到数据后，以相同方式使用 生成多项式 进行 模 2 除法。余数非零表示检测到差错；余数为零只表示数据在传输过程中 未检测到错误、校验通过，仍可能存在恰好能被 $G(x)$ 整除的错误模式。

发送方

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

G(x)=x^5+x^4+x^2+1

发送方计算 CRC 校验码的操作流程如下：

扩展数据：生成多项式是 6 位，因此我们在数据尾部补上 6-1 = 5 个零，得到扩展数据：101000110100000
模 2 除法计算 CRC（使用异或操作）：

              110101011
       ------------------
110101 | 101000110100000
         110101
         ------
          111011
          110101
          ------
            111010
            110101
            ------
              111110
              110101
              ------
                101100
                110101
                ------
                 110010
                 110101
                 ------
                   01110

最终余数为：01110，所以完整的数据帧为：1010001101 01110。

接收方

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

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

              110101011
       --------------------------------------
110101 | 101000110101110
         110101
         ------
          111011
          110101
          ------
            111010
            110101
            ------
              111110
              110101
              ------
                101111
                110101
                ------
                 110101
                 110101
                 ------
                      0

余数为 00000，表示本次 校验通过、未检测到差错；不能据此证明绝对没有差错。

下面的交互按“补零、异或相除、追加余数、接收端复验”推进本例；竖式保留作手算底稿。

过程流

CRC 码字怎样从模 2 除法得到

沿用数据 1010001101 与生成多项式 110101，逐步检查补 5 个零、按位异或相除、追加余数 01110 和接收端余数 00000。

确定补零数→首轮异或首轮异或→逐位下移逐位下移→形成发送码字形成发送码字→接收端复验接收端复验→理解边界

当前查看：确定补零数。生成多项式 110101 共 6 位、最高次数 r=5，因此在原数据末尾补 5 个零。

使用异或进行 CRC 计算

在 CRC 运算中，模 2 除法的“减法”实际上就是按位异或操作（XOR）。这是因为在二进制中，加法和减法在无进位的情况下是等价的。比如：

1 ⊕ 1 = 0（相当于 1 - 1 或 1 + 1（不进位））
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1

因此，CRC 的除法过程实际上是不断地将当前被除数高位与 生成多项式 对齐后进行异或操作，然后向右滑动继续处理，直到处理完所有位。

海明码

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

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

生成过程

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

步骤 1：确定校验位数量

假如数据为 1011，也就是 $k=4$ 位。根据海明码的原则，需要确定足够的校验位 $r$ ，使

2^r\ge k+r+1

对于 $k=4$ ，最小的 $r$ 为 3。

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

假设有 $k$ 位数据，需要添加 $r$ 位校验位，那么校验位的总数必须满足以下条件： $r$ 个校验位可产生 $2^r$ 种 syndrome，必须覆盖 $k+r$ 个单比特错误位置以及 1 种“无错误”状态。换句话说，所有数据位和校验位的总数加起来都要能由校验位模式唯一表示，其中加 1 是因为校验位模式全为零（即没有错误）的情况也必须被考虑在内。因此

2^r\ge 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 开始。上表为了符合通常书写顺序，按位置 7 到位置 1 展示；进行校验分组时仍以位置编号为准。

步骤 3：计算校验位

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

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

采用偶校验时，每个校验位负责所有“位置编号的对应二进制位为 1”的位置：

$p_1$ 检查位置 1、3、5、7（位置编号最低位为 1）：
$p_1=d_1\oplus d_2\oplus d_4=1\oplus0\oplus1=0$
$p_2$ 检查位置 2、3、6、7（位置编号中间位为 1）：
$p_2=d_1\oplus d_3\oplus d_4=1\oplus1\oplus1=1$
$p_3$ 检查位置 4、5、6、7（位置编号最高位为 1）：
$p_3=d_2\oplus d_3\oplus d_4=0\oplus1\oplus1=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 的 Hamming(7,4) 码若按 位置 1 到位置 7 书写，就是 0110011；若像上表一样按 位置 7 到位置 1 展示，则是 1100110。两种写法描述的是同一个码字，只是书写方向相反。任意一个比特发生错误时，都能由 syndrome 定位并纠正。

检测和纠错

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

假设码字按位置 1 到位置 7 的顺序发送。原码字 0110011 的位置 2 发生翻转后，接收码字变为 0010011。接收端对各校验组重新做偶校验，得到 syndrome 的三个分量：

\begin{aligned} s_1&=c_1\oplus c_3\oplus c_5\oplus c_7 =0\oplus1\oplus0\oplus1=0,\\ s_2&=c_2\oplus c_3\oplus c_6\oplus c_7 =0\oplus1\oplus1\oplus1=1,\\ s_3&=c_4\oplus c_5\oplus c_6\oplus c_7 =0\oplus0\oplus1\oplus1=0. \end{aligned}

将 syndrome 按高位到低位写成 $s_3s_2s_1$ ：

s_3s_2s_1=010_2=2

因此错误位于位置 2，也就是 $p_2$ 。注意：syndrome 的拼接顺序必须明确；若写成 $(s_1,s_2,s_3)$ ，视觉上虽然同为 010，但一般情形下不能据此直接把二进制值当作位置编号。

最后一步是 纠正错误：位置 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

把位置 2 的值从 0 翻转为 1，便恢复为正确码字：按位置 1 到 7 书写为 0110011，按位置 7 到 1 书写为 1100110。

下面的交互把数据位放置、三个校验位计算、错误翻转、syndrome 合成与纠错分成可逐步检查的状态；静态表格保留作位置对照。

过程流

Hamming(7,4) 从放位到 syndrome 纠错

以数据 1011 为例，逐步放置数据位和偶校验位，生成位置 1→7 的码字 0110011，再让位置 2 翻转并用 syndrome 010 定位。

确定校验位数→按位置放位按位置放位→计算偶校验位计算偶校验位→翻转位置 2翻转位置 2→合成 syndrome合成 syndrome→翻转纠错

当前查看：确定校验位数。k=4 时最小 r=3，因为 2³=8 能覆盖 7 个单错位置和 1 个无错状态。

海明距离

海明距离是指两个等长的比特序列（也称为码字）在对应位置上不相同的比特个数。它是衡量两个码字之间差异程度的重要指标，广泛应用于 编码理论 中，用于分析 错误检测 和 错误纠正 能力。

编码集

在通信或存储系统中，编码集是指用于表示信息的一组码字。每个码字通常是一个固定长度的比特串，通过引入冗余位，编码集可以在传输过程中检测或纠正一定数量的错误。

编码集的关键属性之一是其 最小海明距离（记作 $d_{\min}$ ）——即任意两个不同码字之间海明距离的最小值。它直接决定该编码集的容错能力：

检错能力：最多可以检测
$t_{\rm detect}=d_{\min}-1$
位错误。
纠错能力：最多可以纠正
$t_{\rm correct}=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor$
位错误。

最小海明距离越大，意味着码字之间越“分散”，在信道中被干扰后仍然能区分开来，因此检测和纠错能力更强。

举个实际例子，设有一个编码集，其中包含以下三个 4 位码字：

0000, 0110, 1011

我们计算这三组码字之间的海明距离：

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

因此，该编码集的最小海明距离为 $d_{\min}=2$ 。

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

检测 1 位错误，因为 $d_{\min}-1=1$ ；
不能纠错，因为 $\left\lfloor(d_{\min}-1)/2\right\rfloor=0$ 。

如果我们想要具备1 位纠错能力，最小海明距离至少要达到 3。

海明码示例

海明码（Hamming Code） 是一种经典的线性分组码。普通 Hamming(7,4) 的最小海明距离为 $d_{\min}=3$ 。这意味着：

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

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

若伴随式为全零，说明数据未被破坏；
若伴随式为非零，且对应某个位的错误模式，则可准确定位并纠正该位；
若发生 2 位错误，它已超出普通海明码的单错纠正能力。这里“最多检测 2 位错误”和“最多纠正 1 位错误”是分别讨论的理论能力；普通的单错纠正译码器可能把双比特错误误判为另一个位置的单比特错误并进行误纠。

若希望译码器能够同时可靠地区分“无错、单错、双错”，可在普通海明码之外增加一个全局奇偶校验位，形成扩展海明码，即常说的 SECDED（Single Error Correction, Double Error Detection，单错纠正、双错检测）。