前置知识
结合律
模二除法的余数满足结合律：两数的余数异或等于两数异或后的余数
$$
(M(x) % G(x)) \oplus (N(x) % G(x)) = (M(x) \oplus N(x)) % G(x)
$$
例如，已知发送方发送数据1100010，生成多项式G(x)=1011，1100010 mod 1011=000.
正确的情况
如果收到1100010，拿它除以生成多项式，1100010 mod 1011=000，余数为0说明数据传输正确。
错误的情况
假设最低位出错了，收到的数据是0100010
$$
\begin{equation}
\begin{aligned}
0100010 &= 1100010 \oplus 1000000 \
0101000 mod 1101 &= (1100010 mod 1011) \oplus (1000000 mod 1011) \
&= 000 \oplus 101 \
&= 101
\end{aligned}
\end{equation}
$$
所以如果接收方收到0100010，得到余数101表示错误在最高位。
CRC编码的非0余数具有循环特性
将余数左移一位除以生成多项式，将得到下一个余数，继续重复在新余数的基础上左移一位除以生成多项式，余数最后能循环为最开始的余数。
举个例子，假设正确的数据为1100010，G(x)=1011
比如最低位出错，收到的数据为1100011，余数为001，001左移一位得0010，再除以G(x)得010，这就是倒数第二位出错得到的余数。
一直重复这个过程，当余数为101，即最高位出错时我们修改最高位得到正确的值，继续操作直到余数回到001，说明出错位已经回到原来的位置，而且我们已经纠错过出错位了，所以得到了正确的数据。
| 说明 | 校验码现在的值 | 运算 | 余数 |
|---|---|---|---|
| 发现出错， 开始纠错 | 1100011 | 1101011与G(x)做模二除 | 001 |
| 001补0=0010 | 1000111 | 0010与G(x)做模二除 | 010 |
| 010补0=0100 | 0001111 | 0100与G(x)做模二除 | 100 |
| 100补0=1000 | 0011110 | 1000与G(x)做模二除 | 011 |
| 011补0=0110 | 0111100 | 0110与G(x)做模二除 | 110 |
| 110补0=1100 | 1111000 | 1100与G(x)做模二除 | 111 |
| 111补0=1110 | 1110001 | 1110与G(x)做模二除 | 101 |
| 101补0=1010 | 1100011 | 1010与G(x)做模二除 | 001 |
这时我们发现余数回到了最开始的001，原本出错的位又回到了原来的位置。
纠错过程
一边对余数补0进行模二除，同时让被检测的校验码循环左移，当余数为101时，出错位也移到最高位（这一点我们之前在结合律的例子中算过了）。通过异或运算纠正后继续循环左移和执行余数模二除法，直到回到原来的余数，修改后的出错位回原位。 这样循环移位的方法的好处是，不需对每一位提供纠正电路，只需在最高位添加纠正电路，对于位数很长的数据效率很高。
| 说明 | 校验码现在的值 | 运算 | 余数 |
|---|---|---|---|
| 发现出错， 开始纠错 | 1100011 | 1101011与G(x)做模二除 | 001 |
| 001补0=0010 | 1000111 | 0010与G(x)做模二除 | 010 |
| 010补0=0100 | 0001111 | 0100与G(x)做模二除 | 100 |
| 100补0=1000 | 0011110 | 1000与G(x)做模二除 | 011 |
| 011补0=0110 | 0111100 | 0110与G(x)做模二除 | 110 |
| 110补0=1100 | 1111000 | 1100与G(x)做模二除 | 111 |
| 111补0=1110,此时余数101，我们将最高位异或1，得到0110001 | 1110001 | 1110与G(x)做模二除 | 101 |
| 101补0=1010，0110001循环左移 | 1100010 | 1010与G(x)做模二除 | 001 |
在倒数第二行，余数为101，说明出错位已经移到了最高位，我们将最高位异或1
$$1110001\oplus 1000000=0110001$$
得到0110001，这样就纠正了出错位。
继续循环直到余数回到001，也就是最后一行，说明出错位已经回到原来的位置，而且我们已经纠错过出错位了，所以得到了正确的数据1100010。
为什么不查表？(个人理解)
把每个位出错得到的余数写一张表，收到数据算出余数比对，不就知道哪位出错了，修改对应位就好了？
这样是挺快的，但是当位数很多时，表很大，而且要对每一位提供纠错电路，这样开销就大了。