对循环冗余校验码CRC的理解

模2加法

1+1=0, 0+1=1, 1+0=1, 0+0=0

模2减法

1-1=0, 0-1=1, 1-0=1, 0-0=0

相当于二进制中的逻辑异或运算。也就是比较后两者对应位相同则结果为“0”,不同则结果为“1”.

模2除法

基于模2减法.

模2乘法

基于模2加法

模运算举例

crc-1

CRC校验码的位数

余数的位数一定要是比除数位数只能少一位,哪怕前面位是0,甚至是全为0(附带好整除时)

余数 是指 CRC校验码
除数 是指 生成多项式转成的二进制位
生成多项式位数 = CRC校验码位数 + 1

将多项式转成二进制位

G(X)= X4 + X3 + 1可以知道,它一共是5位(总位数等于最高位的幂次加1,即4+1=5),然后根据多项式各项的含义(多项式只列出二进制值为1的位,也就是这个二进制的第4位、第3位、第0位的二进制均为1,其它位均为0)很快就可得到它的二进制比特串为11001。

g(x)= x16 + x15 + x2 +1 对应二进制比特串为:11000000000000101
g(x)= x16 + x15 + x5 +1 对应二进制比特串为:11000000000100001

按照国际上通行的标准, 多项式转成二进制位后最高位和最低位必须均为“1”.

生成多项式

用于在接收端进行校验时,对接收的帧进行除法运算的除数,通常是以多项方式表示.

CRC校验码

所选定的除数二进制位数(假设为k位),然后在要发送的数据帧(假设为m位)后面加上k-1位“0”,然后以这个加了k-1个“0“的新帧(一共是m+k-1位)以“模2除法”方式除以上面这个除数,所得到的余数(也是二进制的比特串)就是该帧的CRC校验码.

接收端处理

将校验码(上面的余数)附加在原数据帧(就是m位的帧)后面,构建一个新帧发送到接收端;最后在接收端再把这个新帧以“模2除法”方式除以前面选择的除数(上面的生成多项式转成的二进制位),如果没有余数,则表明该帧在传输过程中没出错,否则出现了差错。

举个例子

发送端要发送的 m 位二进制数据为 10110011, 一共8位.选择的生成多项式为 G(x) = X4 + X3 + 1, 将G(x) 转成二进制位:11001, 一共5位,那么将 4 位 0000 附加到 m位二进制数据 后为: 101100110000, 现在 被除数是 101100110000, 除数是 11001, 得到的余数为 0100, 最后将 m 位二进制数据 加上 余数 0100 得到 101100110100 发送给接收端.

crc-2

练习1

  • 信息字段代码为: 1011001, 对应 m(x)=x6+x4+x3+1(第6,4,3,0位为1,其他位为0);
  • 假设生成多项式为:g(x)=x4+x3+1;则对应g(x)的代码为: 11001(第4,3,0位为1,其他位均为0)
  • 将信息字段后追加 4个零得到 10110010000(生成多项式一共5位所以要加4个零)
  • 将 10110010000 除以 11001 得到余数 1010,也就是说 CRC校验码为 1010
  • 最后的发送数据: 10110011010 (也就是原始数据加上CRC校验码)

练习2

  • 已知信息位为 1100,
  • 生成多项式G(x) = x3+x+1, 对应的二进制位为 1011
  • 信息位加上3个零为 1100000
  • 1100000 除以 1011 得到的 CRC校验码为 010
  • 最后发送的信息为 1100010

参考

Buy me a cup of coffee