计算机网络之差错控制中的 CRC（循环冗余校验码）

1 概述

1.1 简介

• CRC：Cyclic Redundancy Check（循环冗余校验）是计算机网络中常用的一种差错控制编码方法，用于检测数据传输或存储过程中可能出现的错误。

1.2 特点

特点	描述
检错能力强	能 检错，但不能 纠错
计算效率高	可用硬件快速实现
广泛应用	以太网（CRC-32）、磁盘存储、无线通信等

1.3 基本原则

CRC 基于 多项式除法原理：

1. 发送方和接收方预先商定一个生成多项式 G(x)
2. 发送方在 原始数据后 附加CRC校验码，使整个数据能被 G(x) 整除
3. 接收方用同样的 G(x) 去除接收到的数据，若 余数为 0 则认为数据正确

2 实现步骤

假设数据信息为 1100，生成多项式为 G(x) = X³ + X + 1，问：CRC校验码 和 CRC编码 分别是多少？

CRC 编码 = CRC 校验码 + CRC 数据

序号	步骤	描述
1	获取【校验码】位数 N	对应生成多项式的 最高次方 的数值，如示例 N = 3
2	获取【新数据】D	新数据 = 原始数据 + 0…0（M 个 0）， 如示例 D = 1100 000
3	提取生成多项式的【系数】C	$G(x)=X^3+X+1$ $=1\ast X^3+0\ast X^2+1\ast X^1+1\ast X^0$ C = 1 0 1 1
4	模 2 除法，取余数，得校验码	D 除以 C，进行 模2除法（异或运算：相同为 0，不同为 1），取余数。 余数 就是 CRC 校验码，余数的位数 = N，若余数位不够校验位数，前面补 0

3 例题

【例题1】 在采用CRC校验时，若生成多项式为 $G（X）=X^5+X^2+X+1$，传输数据为1011110010101时，生成的帧检验序列为（） 。
A.10101
B.01101
C.00000
D.11100

参考答案：C
① 获取【校验码】位数 N。G(X) 的最高次方为 5，则 N= 5，都满足题意
② 获取【新数据】D。D = 1011110010101 00000
③ 提取生成多项式的【系数】C。C = 100111
④ 步骤 ② 的结果 除以 步骤③ 的结果，取余数。101111 001010 100000 / 101111，余数位

【例题2】以下关于采用一位奇校验方法的叙述中，正确的是( )。
A.若所有奇数位出错，则可以检测出该错误但无法纠正错误
B.若所有偶数位出错，则可以检测出该错误并加以纠正
C.若有奇数个数据位出错，则可以检测出该错误但无法纠正错误
D.若有偶数个数据位出错，则可以检测出该错误并加以纠正

参考答案：C

【例题3】CRC是链路层常用的检错码，若生成多项式为 $X^5+X^3+1$，传输数据10101110，得到的CRC校验码是（ ）。
A.01000
B.01001
C.1001
D.1000

参考答案：A
① 获取【校验码】位数 N。最高项是5，N = 5，排除 C，D
② 获取【新数据】D。D = 1010111000000
③ 提取生成多项式的【系数】C。C = 101001
④ 步骤 ② 除以 步骤 ③（异或运算，余数位不够，前面补 0）。得到 A