循环冗余校验码（Cyclic Redundancy Check, CRC）的根本思维是 发送方和接管方约定一个除数，被除数是由信息位 (n) 和校验位 (k) 组成，最终除法的余数要等于 0
原理
假如数据为 10101011，生成多项式为 10011，求 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 没判断出错位了。
| 承受 | 余数 | 出错位 |
|---|---|---|
| 101001001 | 000 | |
| 101001000 | 001 | 1 |
| 101001011 | 010 | 2 |
| 101001101 | 011 | 3 |
| 101000001 | 100 | 4 |
| 101011001 | 101 | 5 |
| 101101001 | 110 | 6 |
| 100001001 | 111 | 7 |
| 111001001 | 001 | 8 |
| 001001001 | 010 | 9 |
所以要使 CRC 码有纠错能力，必须满足：2^k >= n + k + 1
n + k示意谬误的状态的数量1示意的正确的状态
不过在理论的利用，CRC 码只用于检错，比方 几千个 bit+ 几个校验位
总结
- 确定 CRC 码位数
- 移位，低位补
0 - 模 2 除求余数，余数是校验位
- CRC 码 = 信息位 + 校验位
如果要有纠错能力，须要满足：2^k >= n + k + 1