【计算机组成原理】CRC码

CRC码(Syclic redundancy check)

基本思想

发送和接收方约定一个除数。

K个信息位+R个校验位作为被除数。保证除法没有余数。

若余数非0说明出错，则进行重传或纠错。

如何构造

1、确定K，R以及生成多项式对应的二进制

设生成多项式为：X^3+X2+1，信息码为101001，求对应的CRC码。

信息位长度K=信息码长度=6，R生成多项式的最高次幂=3。校验码长度等于=6+3=9

生成多项式对应的二进制为1101

2、信息码左移R位，低位补0

101001——>101001000

3、相除

对移位后的信息码，用生成多项式进行模2除法，产生余数。

模二除：最高位是1就商1、模二减和异或想同。得到K位余数

101001000模二除1101 = 001

对应的CRC码：101001001

4、检错和纠错

发送：101001001 代表：C₉C₈C₇C₆C₅C₄C₃C₂C₁

接收：101001001

接收方用1101进行除法，余数为000，没有出错。

若接收：101001011，余数为 010，代表出错

对于确定的生成多项式，出错位与余数是相对应得。

若2^R >= K + R + 1，则CRC码可以纠正一个错误。

1、可检测奇数错误

2、可检测双bit得错误

3、可检测小于等于校验位长度的连续错误