Computer Science

WangMC Blog

循环冗余校验(CRC)

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

循环冗余校验码(CRC) 知识点+解题方法 完整整理（应试版，最全无遗漏）

一、CRC核心知识点（必背，填空/选择高频考点）

1. 基本概念

CRC（循环冗余校验码）是检错码（只能检错，不能纠错），属于差错控制编码，在计算机网络（数据链路层）、存储系统中广泛使用，检错能力极强，漏检率极低。

  • 核心思想：在发送端，将待发送的二进制数据序列（信息位），除以一个约定的二进制除数（生成多项式G(x)），得到的余数作为校验位，拼接在信息位后一起发送；

  • 接收端：将收到的完整码字，用同一个生成多项式G(x)做除法，若余数为0则无差错（大概率），余数非0则判定有差错。

  • 关键说明：CRC能检测出所有奇数个比特错误、所有双比特错误、所有长度≤生成多项式阶数的突发错误，是性价比最高的检错方式。

2. 核心术语（固定定义，必须记牢）

  1. 信息码/信息位：待发送的原始数据，记为 位，对应多项式

  2. 校验码/冗余位/CRC位：CRC计算得到的余数，记为 位，对应多项式

  3. 码字/编码后的代码：信息位+校验位，总长度 位，对应多项式

  4. 生成多项式：约定的除数，记为 ，是一个二进制数串，也是考点的核心已知条件；
    ✅ 重要性质：生成多项式 为 位二进制数 → 校验位一定是 位；
    ✅ 规范要求： 必须最高位和最低位都为1（无例外，题目给的G(x)都满足）。

  5. 模2运算：CRC的所有加减乘除，全部使用模2运算（核心！和普通算术运算唯一区别）

    • 模2加法 = 模2减法 = 按位异或：对应位相同为0，不同为1，无进位、无借位。
    • 模2除法：被除数、除数做模2减法（异或），商只记0/1，余数位数必须比除数少一位。

3. 生成多项式的两种写法（必考转换，无容错）

题目中生成多项式有多项式形式和二进制形式两种给出方式，必须能秒转换，例如：

  • → 最高次幂为3 → 二进制位数=3+1=4位 → 二进制：

  • $G(x)=x4+x2+x+1最高次幂位二进制：{10111}$

  • → 最高次幂3 →4位 → 二进制：
    ✅ 转换规则：多项式的幂次对应二进制位的位置（从0开始，右→左），有该幂次则写1，无则写0。

二、CRC的三大核心题型

前置通用结论：生成多项式 最高次幂为 → 校验位有 位 → 信息位要左移r位(末尾补r个0)

✅ 题型1：已知【信息位+生成多项式G(x)】，求CRC校验位 + 最终发送的码字（★★★）

解题万能步骤（死记，按顺序写）

  1. 确定生成多项式的二进制形式，得到 的位数 ，记录校验位位数 ；

  2. 信息位左移r位（等价于：信息位后面补r个0），得到移位后的信息位序列 ；

  3. 用移位后的信息位序列 做模2除法，除以 的二进制序列，得到余数R；
    ⚠️ 关键要求：余数的位数必须是 位！如果余数位数不足，高位补0补齐r位（比如r=3，余数是10→补0为010，余数是1→补0为001），这是最容易丢分的点！

  4. CRC校验位 = 最终的余数R；

  5. 最终发送的码字 = 原始信息位 + CRC校验位（拼接）。

例题示范（经典考题）

已知信息位为 101001，生成多项式 ，求CRC校验位和发送的码字。解：
① → 二进制=1011，最高次幂r=3 → 校验位3位，信息位左移3位；
② 信息位101001左移3位 → 101001000；
③ 模2除法：101001000 ÷ 1011，求余数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
          100101
        _________
1011 ) 101001000
        1011
        -----
          01110
          0000
          -----
          11100
          1011
          -----
           1010
           1011
           -----
             001  （余数）

④ 余数=001，刚好3位，无需补0 → CRC校验位=001；
⑤ 发送的码字 = 101001 + 001 = 101001001。

✅ 题型2：已知【接收的码字+生成多项式G(x)】，判断传输是否出错（★★）

解题万能步骤（死记，最简步骤）

  1. 确定生成多项式G(x)的二进制形式；

  2. 将接收的完整码字，做模2除法，除以G(x)的二进制序列，求余数；

  3. 判断规则：

    • 余数 = 0 → 传输无差错（CRC的检错逻辑，大概率正确）；
    • 余数 ≠ 0 → 传输有差错，需要重传。

例题示范

接收到的码字为101001001，生成多项式G(x)=x³+x+1，判断是否出错。解：用101001001 ÷ 1011，模2除法余数=0 → 无差错。补充：若接收到101001000，除法余数=110≠0 → 有差错。

✅ 题型3：已知【信息位+CRC校验位+生成多项式G(x)】，反推校验位是否正确 / 求余数（题型1的逆题，必考）

本质和题型2完全相同，解题步骤一致：将「信息位+校验位」拼接成完整码字，用G(x)模2除，余数为0则校验位正确，余数非0则错误。

三、CRC的关键补充知识点（易混点+易错点，避坑必备，选择题高频）

✔️ 易错点整理

模2运算≠算术运算：模2减法是异或，没有借位，模2除法商只记0/1，余数位数必须比除数少1位，这是CRC的根基，错了全错；

  1. 校验位的位数必须等于G(x)的最高次幂r：余数不足r位时，高位补0，不是低位补0！比如r=3，余数是1→001，余数是10→010；

  2. 信息位左移r位 = 信息位×2^r：本质是给校验位留出位置，不是随便补0；

  3. CRC是检错码，不是纠错码：能发现错误，但无法定位错误位置，更不能纠正错误，发现错误后只能要求重传（选择题必考考点）；

  4. 生成多项式的约束：G(x)必须最高位和最低位都是1，题目中不会给不符合的，但要知道这个性质。

✔️ 常考特性

  1. CRC能检测出所有奇数个比特位的错误；

  2. CRC能检测出所有长度≤r的突发错误（r是G(x)最高次幂）；

  3. CRC能检测出绝大多数长度>r的突发错误，漏检率极低；

  4. 发送的码字 ，满足 ，即码字能被生成多项式整除。