3.3.1_2 检错编码（循环冗余校验码）
这小节中我们要学习循环冗余校验码，英文缩写叫CRC码。这个小节中，我们首先会介绍CRC 码的基本思想，然后介绍如何构造，如何使用也就是如何检错和纠错。
首先来看一下这种校验码的基本思想。我们从大家熟悉的十进制出发，假设现在你要给另一个人传送882这样的一个十进制数据。为了防止传送数据的过程中，某一个数据位发生错误，你可以和你的另一个小伙伴约定一个除数，比如说是7，882÷7 刚好是除的尽的，最后我们算得的余数应该是等于0。当数据的接收方接收到数据的时候就可以用它接收到的这个数据和你们约定的除数进行一个除法操作，检查一下余数是否为零？如果余数不等于零，是不是就可以确定数据传输的过程中肯定是发生了错误，比如说对方收到的其实是883，也就是最后一个数发生了错误，那883÷7，最后可以算得余数等于1不等于0，这就说明肯定是发生了错误，需要重新传送，再比如说第二个数据位发生了错误，由8变成了5，那么除以七得到的余数是等于5，同样这种情况也可以确定我们的数据传输肯定出现了问题，这是大家熟悉的十进制除法。我们通过约定一个除数，然后在接收到数据之后，与这个除数进行相除的操作检查余数是否发生了改变。用这样的方式就可以检测出数据传送的错误。
这个小节中，我们要学习的循环冗余校验码和我们刚才说到的十进制除法的例子，其实是类似的思想。数据的发送方和接收方会先约定一个除数，当然了，我们处理的是计算机里边的数据，所以这个除数肯定是一个二进制的除数，然后我们会想办法在K个原始的信息位后面加上R个校验位，我们需要确保拼接上R个校验位之后，一整串的数据和我们刚才约定的除数进行相除的操作，余数要等于0。接下来，数据的接收方接收到这K+R位的数据之后，需要用二进制除法来检查余数是否等于零。如果余数不等于0，就说明有一些二进制位出现了错误，这种情况下我们就可以进行重传，或者某些时候也可以进行单比特位的纠错，这个我们一会儿再展开。
总之这就是循环冗余校验码的一个思想和大家熟悉的十进制除法，其实是有某些联系的。刚才我们说过，构建循环冗余校验码，需要有两个关键的要素，一个是除数，一个是被除数。
一般来说题目里会用生成多项式的方式给出除数。注意观察这个生成多项式，我们可以把它写成1乘以x的三次方，加上1乘以x的二次方，加上0乘以x 的一次方，再加上1乘以x的零次方，由于这个生成多项式里边所有的这些项，它的系数要么为一，要么为零。因此我们可以把这个生成多项式，转换成对应的二进制数，像这个G(x)，我们可以转换成1101,就是和这些系数都是分别对应的，所以给出的生成多项式，其实就是指明了我们的除数是多少。接下来给出了K位的这个信息码，这些信息我们会把它放到高位的部分，接下来我们需要确定校验位的位数R应该等于多少。
确定的方法是这样的R应该是等于它给出的生成多项式的最高次幂。像这个式子当中最高次幂是 x 的三次方，所以我们最终会拼接上三位的校验位。现在大家先不要纠结为什么校验位的位数等于三，我们先往后看会更容易理解。由于信息码有六位，然后刚才我们推出校验位有三位，所以最终我们生成的CRC校验码总共应该是6+3=9 位，另外之前我们说过这个生成多项式，它对应了一串二进制码，总共是四个比特。还记不记得之前说的思路，我们会在这六位的信息位后面加上三个校验位，并且我们需要保证我们添加了这三位校验位之后，我们的校验码除以这个除数，余数要等于0。因此，接下来我们需要确定的是我们添加的这三位校验位应该是多少才能保证余数为零？做法是这样的：
我们会把信息码左移R位，也就是左移三位，这是计算机硬件的处理方式，但我们手动做题的话，其实很简单。就是在这六个信息位后面补上R个，也就是补上三个零。接下来我们会用1101这个数和除数进行相除的操作。这个除法运算会让我们得到三位，也就是R位的余数。不过这个地方我们
需要进行的是模2除的运算，和我们普通的除法，是有一些区别的。
来看一下这种特殊的除法模2除是怎么进行的？首先，由于除数有四位，所以我们会取被除数的高四位，与它先商一次。模2除里边取商的方式比较特别，我们只看当前的最高位。如果它是1，那么我们就商1，1乘以1101等于1101，我们把它填到下面，接下来我们会对后三位进行模2减的运算。
其实，模2减的效果和模2加是相同的，模2加其实就是异或运算，所以事实上我们就是对后边的三位进行了异或运算，先来看0和1异或等于1，1和0异或等于1，0和1异或同样等于1，因此后边三位进行模2减或者说分别进行异或得到的结果是111。那接下来有点类似于十进制的除法，我们把被除数的后面一位补到刚才得到的这个余数的低位，接下来我们要确定下一位的商，和之前一样，我们只看最高位，如果最高位为1的话，那我们就商1，同样的1乘以1101得到1101。接下来我们需要对后面的三位进行一次模2减的运算，1和1进行模2减，就相当于它们俩进行了一次异或等于0，1和0异或等于1，0和1异或等于1。所以这一次模2减得到的是011。接下来再补一位，凑足四位，现在由于高位为零，所以接下来我们应该商零。0乘以1101应该是等于四个0，所以我们在下边写上四个0，接下来同样的我们需要把后三位进行模2减，或者说异或的运算得到三个1，现在由于高位是1，所以下一个商我们应该商1得到1101，后三位进行模2减得到011，再补一个0，现在由于高位是
0，所以我们需要商0，因此接下来需要减0000，后三位进行模2减得到110。最后还剩一位，我们再把它补上去，由于此时高位为1，所以我们要商1，和1101的后三位进行模2减得到的结果是001，001就是我们刚才的这一串代码和1101进行模2除得到的一个余数。用模2除的规则最终得到的余数位数应该只比除数少一位。我们用这些操作得到的余数就是我们的校验位，所以最终我们得到的CRC校验码就应该是前六个信息位再拼上最后的校验位001，这就是校验位的一个确定方式。用这种方式确定的校验码和1101进行模2除得到的余数一定是000。
现在我们已经有了校验码，我们就可以把这一整串的信息进行传输发送，接收方接收到数据之后就需要进行检错和纠错。注意发送方和接收方提前已经约定好了这个生成多项式，或者说约定好了除数1101。、
那么，当接收方接收到数据之后，就可以用接收到的这一串信息和刚才约定好的这个除数进行模2除的运算，如果最终得到的余数是000，那么就代表没有出错。来试一下进行模2除，由于高位是1，所以商一1得1101，然后三位进行模2减应该是111。补一个零，接下来商1，1101后三位进行模2减，应该是011。接下来再补一个1，由于最高位是0，所以商0，然后是四个零，后三位进行模2减等于111，接下来补一个零，现在由于最高位是1，所以商1，那么1101和它进行相减，就应该是011，再补一个零。接下来商0，进行模2减，应该是等于110，最后再补一个1，然后商1，那么1101再减掉1101，最终得到的余数就应该是000。如果要类比十进制的除法，就相当于刚好除的尽没有余数，这种情况下就表示没有出错。
再看另一种情况，如果说倒数第二位出现了错误，那么和1101进行模2除余数应该是等于010。好为了让大家熟悉摩尔除运算，我们还是啊动手来算一遍呃，第一位是一，那么
我们商一幺幺零幺。后三位摩尔减等于幺幺幺补一个零，接下来商一幺幺零幺后三位进行摩尔减等于零幺幺。接下来补一个1，由于最高位是0，所以我们商零四个零。后三位相减等于幺幺幺再补一个零。好，接下来商一幺幺零幺后，三位摩尔减等于零幺幺。再补一个。一接下来商零那么四个零。进行摩尔减等于三个一，最后再补一个一。接下来，商一等于幺幺零幺那么后三位进行摩尔减等于零一。幺零。所以倒数第二位，也就是 c2 这一位，如果发生了错误的话，那么我们最终得到的余数应该是零幺零。这里大家会发现一个巧合，我们得到的这个余数，如果把它翻译成2进制的话，刚好就是二，而出错的位置刚好也是C2 这个位置，但是其实这个余数和出错位置之间并没有必然的联系。所以这个地方我把它划了一条横线，这句话既对也不对。
为什么这么说呢？这地方我把原始的这串儿数据各个位置进行了一个改变，如果出错位在第一位的话，和这个生成多项式进行模2除得到的余数是001，如果出错的位置是第二位，就是刚才那个例子，那得到余数是010，如果出错的位置是第三位，得到的余数是100，如果把100翻译成二进制的话，应该是等于4。所以余数的值和出错位置之间，其实并不是二进制到十进制一转换这么简单，但是余数和出错位置确实又有对应关系。细心的同学会发现这儿的余数只有三个比特的信息，而三个比特的信息总共只能表示二的三次方，也就是八种状态。如果余数等于三个零，那么表示这个数据的传输是正确的，接下来出错位为一、二、三、四、五、六、七，这七种状况，分别会对应不同的余数，这七种余数再加上000是不是已经把三个比特能够表示的信息都表示了。所以我们再看如果第八位出错的话，余数又会等于001，然后如果是第九位出错的话，余数又等于010，也就相当于这个余数又从头来了一遍，第一个是001，第二个是010，所以上一页 PPT 中余数等于010就可以确定是第二位出错了吗？这个结论显然是站不住脚的，因为如果第九位出错，也有可能会导致余数变为010，因此刚才那句话我们画了一条横线，表示它并不严谨并不正确。既然如此，是不是意味着循环冗余校验码只有检错的能力。而没有纠错的能力，也就是无法确定出错的位置在哪呢。这种理解也不全对，像刚才这个例子当中，由于我们信息位加校验位总共有九个位，而校验码只有三位的信息，三位的信息最多只能表示八种状态，无法完全的标注出这九个位置到底是哪一个位置发生了错误。所以并不是循环冗余校验码，没有纠错的能力，而是这个例子当中，信息位太长了。
所以我们再看另一个例子，如果信息位只有四位，然后生成多项式，和之前是一样的1101。首先我们在信息位后边补三个零，然后用这一整串对1101进行模2除运算，得到余数011，所以最终得到CRC码就应该是这四个信息位在拼接上011这三个校验位。接下来如果这串数据传输过程中没有任何一位发生错误，显然余数应该是等于0。而如果第一位发生错误，那余数是001，如果是第二位发生错误，余数是010，第三位是100，然后第四位，第五位。细心的同学会发现余数和出错位置之间的这个对应关系与上一个例子当中并没有发生任何改变，上个例子当中余数为001同样出错位是1，010同样出错位是2，然后100同样出错位是3，后续的也是一样的。所以这也就意味着，只要我们确定了一个生成多项式，无论我们的信息位如何变化，最终，这个余数的值和出错位置之间，肯定都是一种固定不变的对应关系。而如果数据的位数并没有超过余数所能表示的这个范围，那么，余数和出错位之间就是一一对应的关系。在这个例子当中，如果余数等于010，那我们就可以确定出错位，一定是第二位。于是，我们只需要纠正第二位就可以了。所以循环融于校验码，其实是有纠错功能的，只不过信息位的位数不能太多。
到底要多少个信息位才不算多呢？我们有R个校验位，就意味着最终我们会得到R位的余数，而这么多位的余数可以表示二的R次方这么多种状态，其中有一种状态也就是余数为000，这种状态是对应正确的状态，剩下的2R-1这么多种状态，需要分别对应上K+R这么多位，每一个位出现错误的那种情况，需要进行一个一一的对应，所以如果能够满足二的二次方大于等于K+R+1，那么CRC校验码就拥有可以纠正一位错误的能力。不过在实际应用当中CRC码这种方式通常用于计算机网络的数据传输，通常会把几千个比特的信息位，加上几个校验位。所以在实际使用当中，这种校验码通常只会用来检错，而不会用于纠错。只不过大家也需要知道，它实际上是有纠错能力的，理论上这种校验码它可以检测出所有的奇数个的错误。同时可以检测出所有的双比特错误。另外，它可以检测出小于等于校验位长度，也就是小于等于R位的连续的错误，这是这种校验码的一个检错能力。这一页的知识大家能有一个简要的了解就可以。
这个小节当中我们学习了循环冗余校验码，又叫CRC码。考试中一般会给大家一个生成多项式，然后给出确定的K个信息位。大家需要通过这两个初始条件得到R位的余数，也就是R位的校验码，然后和 K的信息位进行一个拼接，得到最终的一个校验码。当接收方接收到数据之后，需要和这个生成多项式进行一个模2除的运算来检查余数是否为零，如果余数为零，那么说明没有错误。如果余数非零，就说明有错误。
这小节最后我们也探讨了CRC码的一个检错和纠错能力，有不少教材会说CRC码没有纠错能力，但是这种理解是错误的，只要信息位的位数和校验位的位数足够合理，不超过某一种特定的范围界限，那么CRC码就可以纠正单比特的错误。因为我们得到的余数和出错位置之间是有一一对应的关系的，这种对应关系只要我们确定了生成多项式，其实就很好确定。
以上就是这个小节的全部内容，最后再给大家分享一个有意思的东西来解释一下为什么这种校验码叫做循环冗余校验码，我们刚才说过，如果出错位是在第一个位置，那么得到的余数是001.现在我们尝试着001的后面给它添一个0，然后对这个生成多项式进行模2除的运算，生成多项式是1101，进行摩尔除那么应该商0，等于4个0。后三位进行模2减应该是010，有没有发现这就是出错位为第二个位置的时候的余数。继续再来末尾补一个0，然后由于首位是0，因此我们需要商0，进行模2减，等于100和出错位置为3的这个余数是相同的。再添一个零，接下来我们应该商1等于1101，后三位模2减等于101，和出错位4是一样的，那么刚才这种方法，大家继续往下算的话，会发现我们得到的三位余数永远都是001，然后一路一直变到110，110再回到001，如此循环往复。所以为什么这种校验码叫循环冗余校验码，就是这个原因。刚才我们说的这些例子当中出错位为八的时候，余数又回到了001，为第九位的时候回到了010，也就是第二个位置，那如果信息位更多一些，比如说有十位的话，那么接下来一个余数肯定是100是这样的一个规律。当然，这个地方讲的这些东西很有意思，不过不是我们考试的重点，大家随便一听，乐呵乐呵就行。