考研笔记

检错编码

差错控制分检错和纠错两路，数据链路层实际只用检错这一路：发现坏帧就丢，不修。 本节两种检错码里，奇偶检验码只有一条结论要记（只能查奇数个错），CRC 则要会手算——2023 年直接考过冗余码的计算。

机制

差错控制的两条路

实际的通信链路都不是理想的，比特在传输过程中可能产生差错，1 可能变成 0，0 也可能变成 1，这就是比特差错。比特差错是传输差错中的一种，本节只讨论比特差错。

通常利用编码技术进行差错控制，主要有两类：

  • 自动重传请求（Automatic Repeat reQuest，ARQ）：接收方检测到差错时，就设法通知发送方重发，直到收到正确的数据为止。
  • 前向纠错（Forward Error Correction，FEC）：接收方不但能发现差错，而且能确定错误的位置并加以纠正。

与之对应，差错控制又分为检错编码和纠错编码。ARQ 只需要检错编码，FEC 需要纠错编码（3.3.2）。

检错编码的共同思想：冗余

检错编码都采用冗余编码技术，核心思想是：在有效数据（信息位）被发送前，按某种关系附加一定的冗余位（检验位），构成一个符合某一规则的码字后发送。要发送的有效数据变化时，相应的冗余位也随之变化，使码字始终遵从不变的规则。接收方根据收到的码字是否仍符合原规则，来判断是否出错。

奇偶检验码

奇偶检验码是奇检验码和偶检验码的统称，是一种最基本的检错码。它由 位数据和 1 位检验位组成，检验位的取值（0 或 1）使整个检验码中”1”的个数为奇数或偶数：

  • 奇检验码：附加一个检验位后， 位码字中”1”的个数为奇数；
  • 偶检验码：附加一个检验位后， 位码字中”1”的个数为偶数。

例如 7 位数据 1001101（含 4 个 1）对应的奇检验码为 10011011，偶检验码为 10011010。

奇偶检验码只能检测奇数位的出错情况，但不知道是哪些位错了，也不能发现偶数位的出错情况。道理很直接：翻转偶数个位，“1 的个数”的奇偶性不变。

循环冗余码（CRC）

数据链路层广泛使用循环冗余码（Cyclic Redundancy Code，CRC）检错技术，基本思想是：

  1. 收发双方约定一个生成多项式 ，要求最低位必须为 1。 位位串可视为阶数为 的多项式的系数序列，例如多项式 表示位串 1101。
  2. 发送方基于待发送的数据和 计算出冗余码，把冗余码附加到数据后面一起发送。
  3. 接收方收到数据和冗余码后，通过 计算收到的数据和冗余码是否产生了差错。

设一个待传送的 位数据，CRC 运算产生一个 位的冗余码，称为**帧检验序列（FCS）**，形成的帧由 位组成。在数据后面增加 位冗余码虽然增大了传输开销，但可以进行差错检测，这种代价往往是值得的。这个带检验码的帧刚好能被预先确定的多项式 整除；接收方用相同的多项式去除收到的帧，若余数为 0，则认为无差错。

冗余码的计算（2023 年考过）只有两步：

  1. 加 0：设 的阶为 ，在数据后面加 个 0，相当于乘以 。
  2. 模 2 除：用 对应的二进制串去除第 1 步得到的数据串，得到的余数即为冗余码，共 位，前面的 0 不可省略。

模 2 运算规则是加法不进位、减法不借位，相当于对应位进行逻辑异或运算。

发送方的 FCS 生成和接收方的 CRC 检验都是由硬件实现的，处理很迅速，不会影响数据的传输。若传输过程中无差错，经 CRC 检验后得出的余数 肯定为 0；若出现误码，余数 仍为 0 的概率极低。因此通过 CRC 检错技术可以做到对帧的无差错接收，即”凡是接收方数据链路层接受的帧，都能以非常接近 1 的概率认为这些帧在传输过程中未产生差错”；而接收方丢弃的帧，虽然曾经收到，但最终因为有差错而被丢弃，即未被接受。

教材在这里专门加了一条注意：CRC 本身是具有纠错功能的，只是数据链路层仅使用了它的检错功能，检测到帧出错就直接丢弃，这是为了方便协议的实现，所以教材不介绍 CRC 的纠错功能。

计算模板：CRC 冗余码

  1. 由 写出除数：最高次为 ，除数有 位。 → 10011，。
  2. 被除数 = 数据后补 个 0。
  3. 逐位异或：当前最高位为 1 就异或除数（商上 1），为 0 就异或全 0（商上 0），然后左移一位接下一位。
  4. 余数写满 位，前导 0 保留。发送数据 = 原数据 + 余数。
  5. 验收：接收方用同一个除数去除收到的整串，余数为 0 才接受。

例（教材例）：（），（）。被除数 101001000，模 2 除得商 110101、余数 001，发送 101001 001，共 位。

          110101          ← 商（不用）
1101 ) 101001000
       1101
        1110
        1101
         0111
         0000
          1110
          1101
           0110
           0000
            1100
            1101
             001          ← 余数 = FCS，保留前导 0

例（2023 真题，王道 3.3.3 第 7 题）：（10011），乙方收到下列哪个比特串时可断定未发生错误？A. 10111 0000　B. 10111 0100　C. 10111 1000　D. 10111 1100

四个选项前 5 位都是 10111，所以数据部分就是 10111，只需算它的冗余码：被除数 101110000，模 2 除得余数 1100。正确的帧是 10111 1100，选 D。这类题不必把四个选项各除一遍，算一次冗余码对照即可。

边界

生成多项式必须事先商定，不能”无须商定就直接使用”。

错题复盘：CRC 的生成多项式必须由收发双方预先商定

王道 3.3.3 第 5 题：下列关于循环冗余检验的说法中，错误的是（A. 带 r 个检验位的多项式编码可以检测到所有长度小于或等于 r 的突发性错误　B. 通信双方可以无须商定就直接使用多项式编码　C. CRC 检验可以使用硬件来完成　D. 有一些特殊的多项式，因为其有很好的特性，而成了国际标准）。答案 B。

使用多项式编码时，发送方和接收方必须预先商定一个生成多项式：发送方按模 2 除法得到检验码，附加在数据后面发送；接收方收到数据后，也要用同一个生成多项式来验证数据的正确性。双方用的多项式不同，余数就毫无意义。

A 是正确结论，了解即可，无须掌握证明。它说明 CRC 对突发错误有很强的检测能力—— 位检验能抓住所有长度不超过 的突发错误。D 也正确，以太网 FCS 使用的就是标准化的 32 位 CRC（3.6.2）。

CRC 能检测出所有的单比特错误（王道 3.3.4 第 1 题”记住该结论即可”）；但它不能保证检出所有错误——出错后余数恰好仍为 0 的情况概率极低，但存在。“余数为 0”只能说明”未检出差错”。

CRC 检验码的位数等于生成多项式的最高次数，不是生成多项式对应位串的长度。 对应 5 位的 11001，冗余码是 4 位。

“数据链路层只能检错、不能纠错”是错的。 链路层的差错控制有检错编码和纠错编码两种基本策略，海明码可以纠正一位差错（王道 3.3.4 第 1 题）。只是实际的有线链路只用检错，这与”不能纠错”是两回事。

奇偶检验只能查奇数个错，所以判断”能不能检测”要数 1 的个数。 例如字符 S 的 ASCII 码 1100101 采用奇检验，收到 11010011 时其中 1 的个数为 5（奇数），奇检验通过，这个错误检测不出来（王道 3.3.3 第 3 题）。

对照速查

奇偶检验码CRC
冗余位数1 位 位（ 的最高次）
能检出奇数个比特错所有单比特错；所有长度 的突发错；其余以极高概率检出
能否定位否链路层不用其纠错功能
实现简单硬件，速度快
说法对错
生成多项式的最低位必须为 1✅
CRC 余数为 0 说明一定没有差错❌（只是极大概率无差错）
奇偶检验码能检测出双位错误❌
冗余码前面的 0 可以省略❌
以太网 FCS 使用 CRC-32✅

考点

  • 差错控制两类：ARQ（检错 + 重传）、FEC（纠错）
  • 奇偶检验：只能检测奇数位出错，不能定位
  • CRC：双方预先商定 ；数据后补 个 0，模 2 除，余数 位即 FCS（2023）
  • 接收方余数为 0 则接受；链路层对帧做到”无差错接受”，而不是”可靠传输”
  • CRC 能检出所有单比特错和长度 的突发错；链路层只用它的检错功能

链接

反向链接