模2除法（CRC冗余码计算）和二进制/十进制除法

复习网络，不小心碰到差错控制的CRC冗余码计算，随便算了一下，发现自己算的不对，于是发现了一串知识，总结如下。主要就是CRC中用到的模2运算和二进制/十进制除法有别，前者是特殊的除法，甚至根本不是除法，就是异或。

CRC循环冗余检验：余数为0就没出错；不能确定哪几个比特出错了

看来必然是要增加开销的，没有白吃的午餐，难怪名字叫做“冗余”呢



就是发送方先把冗余码的位置放n个0，然后把整个数据（k+n）位作为一个数字，除以（用的是模2除法，很重要！！不是常规除法）一个事先准备好的除数p（n+1位），除下来的余数R就是n位的，这n位余数就作为发送方的CRC循环冗余码。

到了收方，就拿收到的数字除以相同的除数P（大概是协议规定好的P），余数为0就代表没出错

对每一帧都要校验一下

也不是100%会检测正确，也有概率检测的结果不对，冗余码的位数越大，结果才能越准确，检测错误的概率才会小

二进制除法（和十进制除法其实一样！）

模2除法（不同于二进制除法！本质就是异或而已）

这篇博客点醒了我
一直看不明白CRC冗余码的计算过程，，花了一个多小时研究，之前以为上面的描述是说十进制除法，自己的例子和ppt的例子都推不通，看了很多网页，以为是二进制除法，结果发现二进制除法本质和十进制除法是一样的，得到的结果也是一样的。。。

后来终于明白了，CRC计算中说的除法，根本不是十进制或者二进制除法，而是模2除法，这是一种特殊的除法，基本也只在CRC冗余码的计算中才会用到，别的地方不用。

模2除法的重点是（只要掌握了这几个点，就可以打通模2除法的经脉了，不再彷徨疑惑）：

• 不考虑进位
• 等同于按位异或，虽然名字是除法，实际上根本和常规除法不是一回事，本质就是异或而已。比如商的判定不是根据余数和除数的大小来判定，而是根据余数的首位是0还是1，如果余数首位是0那就商1，如果余数首位是1那就商0。

为何余数首位是1，则商为是0呢？
因为其实商是余数首位和除数首位的异或，但是除数一直都不变且其首位一定是1啊，所以自然就是余数首位为1，商就是0咯

• 商的第一位由被除数决定：被除数的首位如果是1，则商的最高位就是1，否则是0。
• 计算过程中，如果余数的首位不是0，则不可以右移，即不能从被除数中再取一位下来，且这一位的商也就为0；只有余数首位是0，才可以再取一位下来，且这一位的商就是1。所以也可以说是根据是否可以右移来判断商是0还是1的，可以右移则商1。

可以看到异或运算在IT领域是多么重要

可以看到：

• 模2除法的每一位的计算是完全独立的，就是异或，根本没有什么进位借位的事儿
• 如果余数首位为1，则商为0，且再和除数异或一次，第二次的余数首位一定为0了，但是这一次只右移，并不得到商。所以上面的例子中做了8次异或运算，但是只有6位商，因为其中有两次的余数是1.
• 模2运算中除数和余数用的是异或；二进制和十进制除法中除数和余数用的是减法。

收方收到数据后：

余数是0，所以没出错，接收。