3.3.2 纠错编码
## 3.3.2 纠错编码
最常见的纠错编码是海明码。其基本原理是在原始信息位中插入若干检验位，构成具有检错与纠错能力的海明码。每个检验位对应一个校验组（通常采用偶校验），用于校验海明码中的若干信息位。通过将每个信息位分配到多个检验组中，当某一位出错时，会引发其所属的多个检验组同时出现校验错误，从而不仅能检测出错误，还能确定错误位置，实现单比特纠错。
下面以信息位1010为例，详细介绍海明码的构造与纠错过程。
### （1）确定海明码的总位数
设信息位有 $n$ 位，检验位有 $k$ 位。 $k$ 个检验位可表示 $2^{k}$ 种状态：信息位和检验位共有 $n + k$ 种单比特出错的位置，此外还需1种表示无错状态。因此，$n$ 与 $k$ 需满足
$$
2^{k} \geqslant n + k + 1
$$
本例中 $n = 4$，尝试 $k = 3$：$2^{3} \geqslant 4 + 3 + 1$ 成立。故取 $k = 3$，海明码共 $n + k = 7$ 位。记信息位为 $D_{4}D_{3}D_{2}D_{1} = 1010$，检验位为 $P_{3}P_{2}P_{1}$，海明码位号从右至左依次为 $H_{7}H_{6}H_{5}H_{4}H_{3}H_{2}H_{1}$。
### （2）确定检验位的分布
规定：检验位 $P_{1}$ 放在海明位号为 $2^{t - 1}$ 的位置上，其余各位放置信息位，因此：
$P_{1}$ 的海明码位号为 $2^{t - 1} = 2^{0} = 1$，即 $H_{1}$ 为 $P_{1}$。
$P_{2}$ 的海明码位号为 $2^{t - 1} = 2^{1} = 2$，即 $H_{2}$ 为 $P_{2}$。
$P_{3}$ 的海明码位号为 $2^{t - 1} = 2^{2} = 4$，即 $H_{4}$ 为 $P_{3}$。
将信息位按原顺序放在剩余位置，得到海明码的分布如下：
$$
H_{7} \quad H_{6} \quad H_{5} \quad H_{4} \quad H_{3} \quad H_{2} \quad H_{1}
$$
$$
D_{4} \quad D_{3} \quad D_{2} \quad P_{3} \quad D_{1} \quad P_{2} \quad P_{1}
$$
### （3）分组以形成检验关系
每个信息位由多个检验位共同校验，需满足条件：信息位所在位号 = 其所参与的所有检验
<!-- page: 71 -->
第3章 数据链路层
位位号之和。另外，检验位不需要再被检验。分组形成的检验关系如下。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
（4）检验位取值
检验位 $P_{1}$ 的值为其对应校验组中所有位（含信息位）求异或（偶校验结果）。
根据（3）中的分组有
$$
\begin{array}{l}
P_{1} \text{校验 } D_{1}, D_{2}, D_{4} \rightarrow P_{1} = D_{1} \oplus D_{2} \oplus D_{4} = 0 \oplus 1 \oplus 1 = 0 \\
P_{2} \text{校验 } D_{1}, D_{3}, D_{4} \rightarrow P_{2} = D_{1} \oplus D_{3} \oplus D_{4} = 0 \oplus 0 \oplus 1 = 1 \\
P_{3} \text{校验 } D_{2}, D_{3}, D_{4} \rightarrow P_{3} = D_{2} \oplus D_{3} \oplus D_{4} = 1 \oplus 0 \oplus 1 = 0 \\
\end{array}
$$
因此，1010 对应的海明码为 1010010（下划线为检验位，其余为信息位）。
（5）海明码的检验原理
每个检验组分别利用检验位和参与形成该检验位的信息位进行奇偶检验检查，构成 $k$ 个检验方程：
$$
\begin{array}{l}
S_{1} = P_{1} \oplus D_{1} \oplus D_{2} \oplus D_{4} \\
S_{2} = P_{2} \oplus D_{1} \oplus D_{3} \oplus D_{4} \\
S_{3} = P_{3} \oplus D_{2} \oplus D_{3} \oplus D_{4} \\
\end{array}
$$
若 $S_{3}S_{2}S_{1}$ 的值为“000”，表示无错误；否则表示出错，且这个数就是错误位的位号，如 $S_{3}S_{2}S_{1} = 001$，表示第 1 位出错，即 $H_{1}$ 出错，直接将其取反即可达到纠错的目的。
海明码的优势在于：通过少量冗余检验位，可实现单比特错误的自动定位与纠正。
3.3.3 本节习题精选
一、单项选择题
01. 下列有关数据链路层差错控制的叙述中，错误的是（ ）。
A. 数据链路层只能提供差错检测，而不提供对差错的纠正
B. 奇偶检验码只能检测出错误而无法对其进行修正，也无法检测出双位错误
C. CRC 检验码可以检测出所有的单比特错误
D. 海明码可以纠正一位差错
02. 下列关于奇偶检验码特征的描述中，正确的是（ ）。
A. 只能检查出奇数个比特的错误
B. 能检查出任意比特的错误
C. 比 CRC 检验更可靠
D. 只能检查出偶数个比特的错误
03. 字符 S 的 ASCII 编码从低到高依次为 1100101，采用奇检验，在下述收到的传输后字符中，错误（ ）不能检测。
A. 11000011
B. 11001010
C. 11001100
D. 11010011
04. 为纠正 2 比特错误，编码的码距至少应为（ ）。
A. 2
B. 3
C. 4
D. 5
05. 对于 10 位要传输的数据，若采用海明码检验，则需要增加的冗余信息位数是（ ）。
A. 3
B. 4
C. 5
D. 6
06. 下列关于循环冗余检验的说法中，错误的是（ ）。
<!-- page: 72 -->
2027年计算机网络考研复习指导
A. 带 $r$ 个检验位的多项式编码可以检测到所有长度小于或等于 $r$ 的突发性错误
B. 通信双方可以无须商定就直接使用多项式编码
C. CRC 检验可以使用硬件来完成
D. 有一些特殊的多项式，因为有很好的特性，而成了国际标准
07. 要发送的数据是 1101 0110 11，采用 CRC 检验，生成多项式是 10011，那么最终发送的数据应是（ ）。
A. 1101 0110 1110 10
B. 1101 0110 1101 10
C. 1101 0110 1111 10
D. 1111 0011 0111 00
08.【2023统考真题】若甲向乙发送数据时采用CRC检验，生成多项式为 $G(X) = X^4 + X + 1$（$G = 10011$），则乙方接收到比特串（ ）时，可以断定其在传输过程中未发生错误。
A. 10111 0000
B. 10111 0100
C. 10111 1000
D. 10111 1100
09.【2025统考真题】某差错编码的编码集为{1001 1010, 0101 1100, 1111 0000, 0000 1111}，该差错编码的检错和纠错能力是（ ）。
A. 不超过 2 位错的 $100\%$ 检错、不超过 1 位错的纠错
B. 不超过 2 位错的 $100\%$ 检错、不超过 2 位错的纠错
C. 不超过 3 位错的 $100\%$ 检错、不超过 1 位错的纠错
D. 不超过 3 位错的 $100\%$ 检错、不超过 2 位错的纠错
## 二、综合应用题
01. 在数据传输过程中，若接收方收到的比特序列为10110011010，收发双方采用的生成多项式为 $G(x) = x^4 + x^3 + 1$，则该比特序列在传输中是否出错？若未出错，则发送数据的比特序列和CRC检验码的比特序列分别是什么？
## 3.3.4 答案与解析
## 一、单项选择题
01. A
链路层的差错控制有两种基本策略：检错编码和纠错编码。常见的纠错编码有海明码，它可以纠正一位差错。CRC检验编码可以检测出所有的单比特错误（记住该结论即可）。
02. A
奇偶检验的原理是通过增加冗余位来使得码字中“1”的个数保持为奇数或偶数的编码方法，它只能检查出奇数个比特的错误。
03. D
既然采用奇检验，那么传输的数据中 1 的个数若是偶数则可检测出错误，若 1 的个数是奇数则检测不出错误。
04. D
要纠正 $d$ 位错误，编码的码距需满足 $2d + 1$。当 $d = 2$ 时，所需码距为 $2 \times 2 + 1 = 5$。
05. B
在 $k$ 比特信息位上附加 $r$ 比特冗余信息，构成 $k + r$ 比特的码字，必须满足 $2^r \geqslant k + r + 1$。若 $k$ 的取值小于或等于11且大于4，则 $r = 4$。
06. B
在使用多项式编码时，发送方和接收方必须预先商定一个生成多项式。发送方按照模 2 除法，得到检验码，在发送数据时将该检验码加到数据后面。接收方收到数据后，也需要根据该生成多
<!-- page: 73 -->
第3章 数据链路层
61
项式来验证数据的正确性。选项 A 是正确结论，了解即可，无须掌握证明过程。
## 07. C
假设一个帧有 $m$ 位，其对应的多项式为 $G(x)$，则计算冗余码的步骤如下：
① 加 0。假设 $G(x)$ 的阶为 $r$，在帧的低位端加上 $r$ 个 0。
② 模 2 除。利用模 2 除法，用 $G(x)$ 对应的数据串除①中计算出的数据串，得到的余数即为冗余码（共 $r$ 位，前面的 0 不可省略）。
多项式以 2 为模运算。按照模 2 运算规则，加法不进位，减法不借位，它刚好是异或操作。乘除法类似于二进制运算，只是在做加减法时按模 2 规则进行。
## 08. D
观察选项：除后 4 位外，前 5 位都为 10111，可知发送方发送的数据部分为 10111，列式求得余数部分为 1100，因此发送方发送的帧串为 10111 1100。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 09. C
首先计算该编码集的码距：对四个码字两两比较，任意两个码字的码距至少为 4，故该编码集的码距 $d_{\min} = 4$。根据差错控制理论，若编码集的码距为 $d$，则可检测不超过 $d - 1$ 位错误，能纠正不超过 $\lfloor (d - 1) / 2 \rfloor$ 位错误。因此该编码集最多能检测 3 位错误、纠正 1 位错误。
## 二、综合应用题
### 01. 【解答】
根据题意，生成多项式 $G(x)$ 对应的比特序列为 11001。进行如下的二进制模 2 除法，被除数为 10110011010，除数为 11001：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
所得余数为 0，因此该比特序列在传输过程中未出现差错。发送数据的比特序列是 1011001，CRC 检验码的比特序列是 1010。注，CRC 检验码的位数等于生成多项式 $G(x)$ 的最高次幂。
## 3.4 流量控制与可靠传输机制
在数据链路层中，流量控制机制和可靠传输机制是紧密交织的。
### 3.4.1 流量控制与滑动窗口机制
流量控制是指由接收方控制发送方的发送速率，确保接收方有足够的缓存空间来接收每一个
<!-- page: 74 -->
2027年计算机网络考研复习指导
帧。常见的流量控制方法有两种：停止-等待协议和滑动窗口协议。数据链路层和传输层均具备流量控制的功能，且都采用了滑动窗口的思想，但二者存在明显区别，主要体现在以下两方面。
1）数据链路层控制的是相邻节点之间的流量，而传输层控制的是端到端的流量。
2）数据链路层的控制手段是：当接收方无法接收时，不返回确认帧；而传输层的控制手段是：接收方在确认报文段中携带窗口字段值，动态调整发送方的发送窗口大小。
## 1. 停止-等待流量控制基本原理
停止-等待流量控制是一种最简单的流量控制方法。发送方每次仅允许发送一个帧，接收方每成功接收一个帧后，需返回一个确认帧，表示可以接收下一帧；发送方只有收到确认帧后，才能发送后续帧。若未收到确认帧，发送方将一直等待。由于发送方在发送完一个帧后必须等待确认，因此信道利用率较低，传输效率不高。
## 2. 滑动窗口流量控制基本原理
滑动窗口流量控制是一种更高效的流量控制方法。在任意时刻，发送方维持一组连续的、允许发送的帧序号，称为发送窗口；接收方也维持一组连续的、允许接收的帧序号，称为接收窗口。发送窗口的大小决定了在未收到对方确认的情况下，发送方最多还能发送多少帧以及哪些帧。接收窗口则用于控制接收方可以接收哪些帧，超出窗口范围的帧将被丢弃。
图3.9展示了发送窗口的工作原理，图3.10展示了接收窗口（ $W_{\mathrm{R}} = 1$ ）的工作原理。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.9 发送窗口的工作原理：(a)允许发送 $0\sim 4$ 号共5个帧；(b)允许发送 $1\sim 4$ 号共4个帧；(c)不允许发送任何帧；(d)允许发送 $5\sim 7$ 号共3个帧 发送方每收到一个按序到达的确认帧，就将发送窗口向前滑动一个位置，从而允许发送一个新的帧。当窗口内所有帧均已发送但尚未收到确认时，发送方暂停发送。 接收方每收到一个序号落在接收窗口内的帧，便接收该帧，随后将接收窗口向前滑动一个位置，并返回确认。若收到的帧序号落在接收窗口之外，则一律丢弃。 滑动窗口具有以下重要特性： 1）发送窗口的滑动依赖于确认信息：仅当发送方收到对某帧的确认后，其发送窗口才能向前滑动。而接收方仅在成功接收期望帧后，才会发送确认并滑动其接收窗口。 <!-- page: 75 --> 第3章 数据链路层
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.10 接收窗口的工作原理
## 导言出处
$\succ$ 滑动窗口协议的窗口机制（2019，2025）
2）从滑动窗口的角度看，停止-等待协议与后面将要介绍的后退 $N$ 帧协议和选择重传协议的主要区别在于发送窗口和接收窗口的大小：
停止-等待协议：发送窗口 $W_{\mathrm{T}} = 1$ ，接收窗口 $W_{\mathrm{R}} = 1$ 。
后退 $N$ 帧协议：发送窗口 $W_{\mathrm{T}} > 1$ ，接收窗口 $W_{\mathrm{R}} = 1$ 。
选择重传协议：发送窗口 $W_{\mathrm{T}} > 1$ ，接收窗口 $W_{\mathrm{R}} > 1$ 。
若采用 $n$ （ $n \geqslant 2$ ）比特对帧编号，则后两种滑动窗口协议还需满足 $W_{\mathrm{T}} + W_{\mathrm{R}} \leqslant 2^{n}$ 。
3）当接收窗口大小为1时，只有收到该帧后才允许接收下一帧，因此可保证帧的有序接收。
4）在数据链路层的滑动窗口协议中，窗口大小在传输过程中是固定的（与传输层不同）。
## 3.4.2 可靠传输机制
可靠传输是指发送方发出的数据能够被接收方正确且完整地接收，为实现这一目标，通常采用确认（ACK）和超时重传两种机制。
1）确认：接收方每成功接收到一个数据帧，就向发送方返回一个确认帧，表明该数据帧已被正确接收。
2）超时重传：发送方在发送一个数据帧后启动一个计时器，若在规定时间内未收到对应的确认帧，则认为该帧可能丢失或出错，从而自动重传该帧，直至成功收到确认为止。
结合这两种机制的可靠传输协议称为自动重传请求（Automatic Repeat reQuest，ARQ），它意味着：重传由发送方自主触发，无须接收方显式请求重传。在ARQ协议中，数据帧和确认帧都必须编号，以便发送方和接收方能够准确识别确认帧对应的是哪个数据帧，以及判断哪些帧尚未被确认，从而决定是否需要重传。ARQ协议主要包括三种类型：停止-等待（Stop-and-Wait）协议、后退 $N$ 帧（Go-Back- $N$ ）协议和选择重传（Selective Repeat）协议。这三种协议的基本原理不仅适用于数据链路层，也可应用于更高层的可靠传输设计。
在实际网络中，是否在数据链路层提供可靠传输服务取决于链路特性：有线网络的误码率较低，为降低开销，一般不要求数据链路层提供可靠传输服务；即使出现少量误码，也可由上层（如传输层）通过端到端机制处理。无线网络的链路易受干扰，误码率较高，因此要求数据链路层必须向上层提供可靠传输服务，以避免大量错误帧传递至上层，提升整体效率。
<!-- page: 76 -->
2027年计算机网络考研复习指导
1. 单帧滑动窗口与停止-等待协议（S-W）
在停止-等待协议中，发送方每次只能发送一个数据帧，只有在收到接收方对该帧的确认帧后，才能发送下一个帧。从滑动窗口的角度看，该协议的发送窗口和接收窗口大小均为1。
在实际传输过程中，可能出现以下两类差错：
1）数据帧出错或丢失。接收方检测到数据帧存在差错时，直接丢弃该帧；数据帧在传输途中丢失时，接收方不会收到任何信息。为应对这两种情况，发送方需要配备一个计时器。每发送完一个数据帧，发送方即启动该计时器；计时器超时仍未收到对应的确认帧时，认为该帧可能已丢失或出错，于是自动重传该帧。该过程重复进行，直至该帧被正确接收并返回确认帧为止。
2）确认帧出错或丢失。即使接收方已成功收到正确的数据帧，若其返回的确认帧在传输中出错或丢失，则发送方仍将因未收到确认而触发超时重传。这时，接收方会再次收到一个重复的数据帧。为避免重复处理，接收方会丢弃该重复帧，并重新发送对应的确认帧。
停止-等待协议每次仅发送一帧并等待确认，因此只需确保相邻发送的帧具有不同的序号即可区分新帧与重传帧。因此，仅需1比特序号空间就已足够：数据帧交替使用序号0和1，对应的确认帧分别记为ACK0和ACK1。若接收方连续收到相同序号的数据帧，则说明发送方进行了超时重传；若发送方连续收到相同序号的确认帧，则说明接收方收到了重复帧且重发了确认帧。
此外，为支持超时重传和重复帧识别，发送方和接收方均需设置帧缓冲区。发送方发送数据帧后，必须在发送缓存中保留该帧的副本，以便需要时重传；仅在收到对应的确认帧后，方可清除该副本。接收方也需记录最近成功接收的帧序号，以判断新到的帧是否是重复的帧。
停止-等待协议的信道利用率很低。为提高传输效率，后续发展出了连续ARQ协议（后退 $N$ 帧协议和选择重传协议），允许发送方连续发送多个数据帧，而无须逐帧等待确认。
2. 多帧滑动窗口与后退 $N$ 帧协议（GBN）
**考点击注** GBN 协议的工作原理（2009）
在后退 $N$ 帧协议中，发送方可在未收到确认帧的情况下，连续发送多个序号落在发送窗口内的数据帧。后退 $N$ 帧的含义是：若某个已发送的数据帧因超时未收到确认而被判定为丢失或出错，则发送方不仅需要重传该帧，还需重传其后所有已发送但未被确认的帧。这一机制的前提是：接收方仅按序接收数据帧，任何失序到达的帧都将被丢弃。
**考点击注** GBN 协议的累积确认机制（2017）
如图3.11所示，发送方向接收方连续发送数据帧，发送完0号帧后，可继续发送1号、2号等后续帧。其通常仅为最早未确认的帧维护一个超时计时器，当该帧被确认后，计时器移至下一个未确认帧。由于连续发送了多个帧，确认帧必须明确指示所确认的帧序号。为降低开销，GBN协议采用累积确认机制：接收方无须对每个正确接收的帧立即返回确认，而可在连续收到多个正确帧后，仅对其中序号最大的帧发送一个确认。具体而言， $\mathrm{ACK}n$ 表示接收方已正确收到 $n$ 号帧及之前的所有帧，下一次期望接收的是 $n + 1$ 号帧（若序号回绕，则可能是0号帧）。
由于接收方仅按序接收帧，当某帧出错或丢失时，其后所有正确到达的帧即使无误，也会被丢弃。例如，在图3.11中，尽管在出错的2号帧之后又收到了6个正确的数据帧，接收方仍必须将它们全部丢弃。此外，为了防止确认帧丢失，接收方可以重复发送最近一次的确认帧（如ACK1），促使发送方尽快感知当前的接收状态。2号帧的计时器超时后，发送方将从该帧开始，重传窗口内所有未被确认的帧（2号及之后的帧）。
<!-- page: 77 -->
第3章 数据链路层
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
骨质组区 GBN协议的超时重传机制（2017）
图3.11 GBN协议的工作原理：对出错数据帧的处理
骨质组区 GBN协议的滑动窗口机制（2012、2015、2017）
若采用 $n$ 比特对帧编号，则发送窗口 $W_{\mathrm{T}}$ 应满足 $1 < W_{\mathrm{T}} \leqslant 2^{n} - 1$ 。若 $W_{\mathrm{T}} > 2^{n} - 1$ ，而这可能导致接收方无法区分新发送的帧与因序号回绕而重复出现的旧帧（参见章末的疑难点1）。
GBN协议的接收窗口大小固定为 $W_{\mathrm{R}} = 1$ ，这保证了帧的严格按序接收。
不难看出，GBN协议一方面通过连续发送多个帧显著提高了信道利用率；另一方面，在发生差错时却必须重传大量已正确到达的帧（仅因这些帧前面有一帧出错），从而造成带宽浪费。因此，当信道误码率较高时，GBN协议的性能可能反而不如停止-等待协议。