循环冗余校验码原理（CRC码）计算机计算机组成计算机基础

循环冗余校验码（Cyclic Redundancy Check, CRC）的基本思想是发送方和接收方约定一个除数，被除数是由信息位(n)和校验位(k)组成，最终除法的余数要等于 0
原理假设数据为 10101011，生成多项式为 10011，求 CRC 码？
【循环冗余校验码原理（CRC码）】多项式就是双方约定的除数 10011

最高位次幂为 4
CRC 码位数由信息位和校验位组成：8 + 4 = 12

由于 CRC 码是 12 位，目前数据为 10101011 只有 8 位，需要左移 4 位（低位补 0），得到 101010110000。
对移位后的数据进行模2除，产生余数：

被除数最高位为 1 商 1，为 0 商 0
剩余位数进行异或运算
最终余数的位数应该比除数的位数少一位

模2除用竖式计算，算出最后的余数为 1010

101010110000/10011
- 10101/10011 = 1 ... 0110
- 01100/10011 = 0 ... 1100
- 11001/10011 = 1 ... 1010
- 10101/10011 = 1 ... 0110
- 01100/10011 = 0 ... 1100
- 11000/10011 = 1 ... 1011
- 10110/10011 = 1 ... 0101
- 01010/10011 = 0 ... 1010

余数 1010 就是 CRC 码的校验位，加上信息位组合成最终的 CRC 码： 101010111010
用 101010111010 与 10011 相除，最终的余数一定是 0000
检错和纠错发送的 CRC 码记为：C12C11C10C9C8C7C6C5C4C3C2C1

C12	C11	C10	C9	C8	C7	C6	C5	C4	C3	C2	C1
1	0	1	0	1	0	1	1	1	0	1	0

一位出错(纠错)

	C12	C11	C10	C9	C8	C7	C6	C5	C4	C3	C2	C1
	1	0	1	0	1	0	1	1	1	0	1	0
C4出错	1	0	1	0	1	0	1	1	0	0	1	0

把 101010110010代入模2除，得到余数 0100，对应十进制 4，也就是说 C4 处出错了
一位出错(不能纠错)
上面的例子，校验位是 4 位，可以表示 16 种状态，实际的 CRC 码只有 12 位，所以有纠错能力。
如果校验位是 3 位，可以表示 8 种状态，实际的 CRC 码有 9 位，这种情况下就没办法实现纠错了。
假如说现在求得的余数是 010 转换为十进制是 2，能否说明第 2 位出错了呢？
看下面表，010 对应的出错位是 2 和 9，也就是说当第二位或者第九位出错了，余数是一样的，这就导致了我们根据 010 没判断出错位了。