计算机组成原理CRC基础

CRC

【感谢美好的教程】

异或

==相同为0 不同为1==

• 1+1=0 1+0=1 0+0=0 0+1=1
• 其实就是相加后==模2==

多项式(polynomial)

诸如$1x^6+0x^5+1x^4+0x^3+1x^2+1x^1+0*x^0$的一长串式子是CRC的==生成多项式==

使用的==目的是==避免计算过程中发生进位

一般使用简写的$x^6+x^4+x^2+x+1$的形式，可以从右到左的方式补写出多项式

此时CRC的==除数==就是生成多项式的各项系数（简式要自行补足）10101111

处理

首先在被除数==尾端加0==，个数是==多项式的阶==数，在上面的例子中，最高阶是6，因此要补6个0

假设数据串为1101011011，那么应该补到1101011011 000000

计算

对齐

首先将数据串的第一个1与除数左对齐，然后进行异或操作

1101011 011 000000
1010111↓
------------------
0111100 011 000000

未处理的数据直接搬下来，作为新的被除数，依然记得需要与新的被除数进行==对齐==

01111000 11000000
X1010111↓
------------------
 0101111 11000000

这么重复操作，直到所有的数据都被处理

01011111 1000000
X1010111↓
----------------
 0001000 1000000
 
0001000100 0000
XXX1010111↓
---------------
   0110011 0000

01100110 000
X1010111↓
---------------
 0110001 000

01100010 00
X1010111↓
---------------
 011010100

01101010 0
X1010111↓
---------------
 01111010

01111010
X1010111
---------------
 0101101
 
# 因为位数已经不够，处理完毕

此时得到的结果从==第一位==1开始到结束，就是CRC校验和，这里是101101，他的长度为==被除数长度-1==

==注意==：如果最后的位数非常少（如0000011）需要补0，此时校验和为000011

组装

这时我们有:

• 数据串：1101011011
• CRC除数：1010111
• 校验和：111011

在整个数据串后附上校验和，就是带上CRC校验的数据：1101011011 111011

小测试

• 数据: 1101011011
• 多项式:$x^4+x+1$

# 开始吧
# 提取CRC除数为 10011
# 因为最高阶为4，补4个0，为1101011011 0000

11010 11011 0000
10011↓
----------------
010011 1011 0000
X10011↓
----------------
 0000010110 000
     X10011
     -----------
      00101000
       X10011
       ---------
        001110
        --------
          1110
# 因为除数长度为5，因此取4位余数，结果为1110
# 附带到数据上，就是 1101011011 1110