CRC
循环冗余检测编码(Cyclic Redundancy Check, CRC)，简称循环冗余码，或RCR码
是线性分组码，也称为多项式编码
思想
将二进制位串看成是系数为0或1的多项式的系数。一个k位二进制数据可以看成是一个k-1次多项式的系数列表，该多项式共有k项，从x的k-1次方到x的0次方
位串
例如：100101有6位，因此有6项的多项式
系数为：1、0、0、1、0、1，即1x5 + 0x4 + 0x3 + 1x2 + 0x1 + 1x0 = 1x5 + 1x2 + 1 = 100000 + 100 + 1 = 1000101
1000101即为位串
1x5对应为100000，1x2对应为100 (和操作系统的虚拟页式存储管理计算一样)
CRC编码计算
采用模2除法，如果余数为0，则数据传输过程未发生错误
模2除法
如果被除数首位是1，则商1，否则商0，商0的时候，0*除数每个位都为0 ，商1的时候，把除数原封不动的写下来。然后，与计算出来的结果进行异或运算，00=1,11=1,01=0,10=0
CRC编码过程
假设C(x)的阶位r(即对应的位串为r+1位)，则CRC编码过程如下：
- 1.在帧的低位端加上r个0位，使该帧扩张位m+r位(相当于左移r位)，对应的多项式为xrM(x)。如上面：100101比特串，多项式计算后为：1x5 + 1x2 + 1，则在100101后面添加阶数最大的数，5为最大的阶数，则在后面添加5个0，则为10010100000
- 2.用G(x)系数对应的位串(查看上面位串计算方式)，去除(模2除法)xrM(x)系数对应的位串，求的r位(就是上面添加的几个0)余数R
- 3.用xrM(x)系数对应的位串，减去(模2除法)余数R，或者将后面的几个0替换位余数，结果就是完成CRC编码帧
例题1
假设CRC编码采用的生成多项式G(x) = x^4 + x + 1，请为位串10111001进行CRC编码
解
G(x) = x4 + x + 1 = 10000 + 10 + 1 = 10011，对应的比特串为10011，在待编码位串10111001后面添加4个0(阶数最高位4)，得到101110010000
按照模2除法计算，101110010000 / 10011
用余数将之前的几个0替换，结果为：101110011001
例题2
假设CRC编码采用的生成多项式G(x) = x^4 + x^3 + x + 1，请为位串11001010101进行CRC编码
解
补全余数：110010101010000 (最大阶数为4，则后面添加4个0)
位串：G(x) = x4 + x3 + x + 1 = x4 + x3 + 1 = 10000 + 1000 + 10 + 1 = 11011
模2除法：110010101010000 / 11011
用余数将之前的几个0替换，结果为：110010101010011
例题3
假设CRC编码采用的生成多项式G(x) = x^4 + x^2 + x + 1，请为位串100111011101进行CRC编码后结果为
A.1001110111011100 B.1100
C.1001110111010111 D.1011
解
补全余数：1001110111010000 (最大阶数为4，则后面添加4个0)
位串：G(x) = x4 + x2 + x + 1 = 10000 + 100 + 10 + 1 = 10111
模2除法：1001110111010000 / 10111
用余数将之前的几个0替换，结果为：1001110111011100 结果选A
