计算机底层：循环冗余校验码CRC

信息位+校验位组成循环冗余校验码，也称CRC码。

循环冗余校验码的思想：

通过将信息进行除以某个规定的数，这个数是提前约定好的，并且两边都知道的数。

假设信息是882，约定了除数是7

那么为啥是7呢？计算机可以通过逆运算推出来，当找到可以令余数为0的数时，两边计算机就可以约定将这个数作为除数

如果得到余数为0，那么这个信息就是正确的，如果不是0，则是错误的：

以上是为了方便理解循环冗余校验码，但是并不是真正的循环冗余校验码的过程。切勿将以上认作是循环冗余校验码

但以上的十进制除法的方式，与循环冗余校验码还是很像的。

循环冗余校验码CRC：

用题目理解：p

与上面一样的是：会规定一个除数和被除数。

除数：

会通过生成多项式，来规定除数。起始除数是一串二进制码，那图中的生成多显示G(x)怎么是一个函数呢？

G(x)可以分解成如上图所示，这样就可以得到一串二进制:1101，而这就是真正的生成多项式。

那题目中生成多项式G(x)是如何的来的呢？

计算机想要得到生成多项式，首先需要确定需求，我们是要纠错呢？还是只需要查错呢？因为我们并不了解循环冗余校验码是如何差错或是纠错的，因此可以先看完整篇文章后，再看这里。

如果想要使校验码拥有纠错能力。那么需要设定知道信息位数K，和校验位数R。使得2^R≥K+R+1。这个公式的意思和海明校验码的意思一样：用2^R所能表示的状态数量，能够表示出错位置的数量。其中R的位数是生成多项式所确定位数的-1个位数。这里不太懂也可以看完整篇文章，再看这里。

学到后面其实还会发现，生成多项式表示的位数越多，校验强度其实越高，既然如此就极易消耗cpu和内存。因此计算机规定校验位数量时，会依据计算机的计算能力和存储能力进行判断。

以上内容下面会解释。

除数的作用：

1.用于得到校验位上的校验码。

2.用于对CRC校验码进行校验。

被除数：

被除数包括了两种：

1.信息位作为被除数，即题目中的：101001。信息位作为被除数，是为了得到校验位上的校验码。

2.信息位+校验位即CRC码作为被除数，是为了进行CRC校验码进行校验。

可以看到题目中的要求是得到CRC 码，就是得到校验位。

获取校验位：

想要得到校验位，需要有：1.信息位，2.生成多项式。

信息位是：101001

生成多项式是：1101

得到两个信息后，需要将除数(生成多项式)的位数-1，那么就是n=3(最高次幂)，得到的这个数，然后在信息位后添n=3加个0。即:101001000

然后进行除法运算:

得到的余数是n=3个位。

运算方法：模二除。

只看首位，是1就x1进去：

再对1后面的三位010与101进行异或，在得到的结果后面添加信息位的下一个位：

如果遇到第一位是0，那么就x0进去，得到了0000，再进行后三位的异或：

以此类推，最后会得到3bit位的余数，这3位的余数，就是我们添加到信息位后的校验位：

最后得到了CRC码：

到了这里，我们再说说生成多项式：

1.校验位数和生成多项式是有着关系的，生成多项式的最高次幂是校验位的位数。

2.生成多项式位数越多，在得到校验位的计算上，信息位后面需要补更多的0，位数变多了，计算量也就变大了，同时储存它们的空间也需要变大。

3.不及如此，生成多项式位数越多，除数也会变多。因为除数就是生成多项式。

CRC码的校验：

接收方收到发送方的CRC校验码时，需要对CRC校验码进行校验。

生成多项式是接收方和发送方一起规定的，因此都会知道这个生成多项式。

校验方式还是：模二除

还是将生成多项式作为除数，接收的CRC校验码作为被除数。

尝试未出错时的计算：

发现：最后的余数是000，说明信息未发生改变。

尝试发生改变时的计算：

发现：得到了010的余数，不为000说明发生了错误。

CRC码的纠错问题：

根据上图中余数是010，而出错位置也是010。那么余数真的表示出错位置吗？

算出每个出错位置，以及对应的余数，得到一个表格：

上图发现余数为001和010的位置有两处。显然在这里余数并不能表示出错位置。

图中用余数表示出错位置，余数只有3位，只有2^3=8种状态，其中000是其中的一种用来表示正确状态，其余7种表示错误状态。

所以我们知道，余数3位只能表示7种错误位置。也就是到图中第七位的错误为止。

我们会发现这里不能纠错的原因是：第八位和第九位的存在，导致只有3位的余数，不够表示错误位置。

那我们如果减少信息位，让CRC码只有7位，那么余数的7种状态就完全可以一一对应，使得拥有纠错的能力。

减少信息位例题：

信息位只有4位，生成多项式还是1101，得到的CRC码只有7位。

此时再看图：

该信息位置与余数一一对应，这样当我们知道余数时，就可以知道错误位置再哪了。

以上是减少信息位，显然现实中，减少信息位肯定是不可能的。发送的信息是人规定死的。机器不能减少。

因此机器会选择增多余数，这样余数增多，所能表示的位数就越多。虽然余数和校验位位数是一样的，但是校验位数的增多绝对赶不上余数表示错误位置的数量。

巩固记忆：生成多项式最高次幂，可以表示：1.计算校验位时，需要再信息位添加0的个数。2.校验位个数。3.进行校验所得到的余数。

生成多项式无论在获取校验码或是进行校验时，都作为除数。

比如：0100010余数有3bit，表示7种错误位置。刚好全部可以表示

01000101余数有4bit，可以表示2^4=16种状态，还有8种状态冗余

010001010余数有5bit,可以表示2^5=32种状态，还有23中状态冗余。

由此，我们就可以知道，余数越多纠错能力就越强。

回到生成多项式：

我们知道余数和生成多项式有关，进而说明了生成多项式越多位，就能够进行更多的纠错，所以文章开头说生成多项式的时候说：按需求而定，是想要纠错呢？还是单纯检错？

到此可以回看上面的生成多项式，这样你可以完全明白生成多项式这个东西

学完循环冗余校验码，更需要知道它的引用领域：

循环冗余校验码通常只会用在计算机网络当中，且在OSI七层模型架构中的数据链路层。

而且，一般不会用到它的纠错能力，只会用到检错能力。

知识回顾：

循环冗余校验码的由来(只是补充，不学也行)：

将余数作为被除数，生成多项式作为除数。

在余数后面补一个0，保证余数个数和生成多项式位数一样。

由此进行模二除的运算：

会发现：得到的余数010是CRC码第二位错误时的余数。继续往下：

发现余数又是下一个位置出错的余数。继续往下：

发现101又是下一个

当你继续算下去会发现会算到110，然后继续算时又会回到001，就这样一直往复，一直循环

因此就叫做：循环冗余校验码