计算机系统分析师考试时间（备考高级系统分析师-计算机系统知识-校验码）

继续肝？昨晚整到凌晨2点，今天随缘了，整到哪里算哪里！

说好的思维导图呢，不会鸽大家的，等我这章全部搞完之后，再做补充吧，希望小伙伴们耐心等待！

本次讲的内容就是校验码：

1. 奇偶校验码
2. 循环冗余校验码CRC
3. 海明码

什么是校验码，有什么作用呢？

简单说计算机处理的数据基本都是0101，傻傻的只认零跟壹，起源的话就是电路中表示高低两个电压比较容易一些，没有第三个状态，然后结合二进制，使用零跟壹是最方便的，当然感兴趣的小伙伴可以去查下二进制的来历，看看历史上伟大的科学家们是为了解决什么问题而提出来的，看看也挺有意思的！应该也会给你自己很大收获！

校验码你可以理解为，传输数据的时候01，会发生错误，为了检验传输的数据是否正确，又增加的校验位，这一套操作就形成了校验码。

1.奇偶校验码

码距：就单个编码A:00而言，其码距为1,因为其只需要改变一位就变成另一个编码。在两个编码中，从A码到B码转换所需要改变的位数称为码距，如A:00要转换为B:11,码距为2.一般来说，码距越大，越利于纠错和检错。

奇偶校验码：在编码中增加1位校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变为2。例如：

奇校验：编码中，含有奇数个1，发送给接收方，接收方收到后，会计算收到的编码有多少个1,如果是奇数个，则无误，是偶数个，则有误。

偶校验同理，只是编码中有偶数个1，由上述，奇偶校验只能检1位错，并且无法纠错。

了解下码距的概念。

例如：

问：00变成01，需要改变几位？答：1位，那它的码距就是1

问：00变为11，需要改变几位？答：2位，那它的码距就是2

结合上边的图片看下概念，估计就更清晰了。

奇偶校验码，看下概念，很好理解，增加一位校验位，看下1的个数，偶数个就是偶校验，奇数个就是奇校验。校验位一般都是加在最后一位，好像也可以加在最前边。

例如：

发送方，发送1100数据，采用奇校验的话，校验码就是11001（最后一位 1），发送方再发送1110数据，采用奇校验的话，校验码就是11100（最后一位 0）

同理偶校验也是这个意思。

了解了之后就知道奇偶校验码问题多多，只能校验1位，是原罪。

2.循环冗余校验CRC

英文名：Cyclic Redundancy Check，方便记忆CRC

嵌入式开发应用蛮多的，用java开发应用的，基本没用到过，但是这个校验思路，可以借鉴学习下，考试也会考的，计算循环冗余校验码。

CRC只能检错，不能纠错。使用CRC编码，需要先约定一个生成多项式G(x)。生成多项式的最高位和最低位必须是1。假设原始信息有m位，则对应多项式M(x)。生成校验码思想就是在原始信息位后追加若干校验位，使得追加的信息能被G(x)整除。接收方接收到带校验位的信息，然后用G(x)整除。余数为0，则没有错误；反之则发生错误。

例：假设原始信息串为10110，CRC的生成多项式为G(x)=x^4 x 1,求CRC校验码。

（1)在原始信息位后面添0，假设生成多项式的阶为r，则在原始信息位后添加r个0，本题中，G(x)阶为4，则在原始信息串后加4个0,得到的新串为101100000，作为被除数。

（2)由多项式得到除数，多项中x的幂指数存在的位置1，不存在的位置0。本题中，x的幂指数为0,1,4的变量都存在，而幂指数为2,3的不存在，因此得到串10011。

（3)生成CRC校验码，将前两步得出的被除数和除数进行模2除法运算（即不进位也不借位的除法运算）。

主要是关注图中例题，也就是计算步骤：

1.知道多项式，一般题目会给出来，然后找到除数跟被除数，假设给定的生成多项式G(x)=x^4 x 1,上述传递的原始数据是10110，下边上灵魂画师的图画，请欣赏

被除数为：10110 0000

除数为：10011

余数如下图为：1111，模2除法运算不进位也不借位（0/0=0,1/0=1,0/1=1,1/1=0），最终CRC校验码就是：原始数据 余数=10110 1111

这两个数据开始相除！

得到余数1111。

注意：余数不足r，则余数左边用若干个0补齐。如求得余数为11，r=4，则补两个0得到0011。

（4)生成最终发送信息串，将余数添加到原始信息后。上例中，原始信息为10110,添加余数1111后，结果为101101111.发送方将此数据发送给接收方。

（5)接收方进行校验。接收方的CRC校验过程与生成过程类似，接收方接收了带校验和的帧后，用多项式G(x)来除。余数为0,则表示信息无错；否则要求发送方进行重传。

注意：收发信息双方需使用相同的生成多项式。

思考个问题，用多项式G(x)来除？补上余数之后，来除余数肯定为0，有没有这种可能，原始数据变化了之后 余数，恰好除出来余数还是0，这样校验不就不准确了！这个问题我也查查，小伙伴们知道的也可以留言给我。

上个考题大伙做一下吧，看看会怎么考查你

真题来喽：

1.循环冗余校验码（Cyclic Redundancy Check,CRC)是数据通信领域中最常用的一种差错校验码，该校验方法中，使用多项式除法（模2除法）运算后的余数为校验字段。若数据信息为n位，则将其左移k位后，被长度为k 1位的生成多项式相除，所得的k位余数即构成k个校验位，构成n k位编码。若数据信息为1100,生成多项式为x3 X 1(即1011)，则CRC编码是（）。

A.1100010 B.1011010 C.1100011 D.1011110

答案暂时不肝了下班回去上灵魂画师的巨作！大伙估计自己就做出来了，不需要答案了，在座的都是天才！

这个题干的前半句话，都是用来介绍什么是CRC编码，只有最后一句话有用！

3.海明码

海明码利用奇偶性来校验和纠错，它能纠错，高级了一步，估计有比它更高级，可以去搜搜。

还有一个特点就是，它的校验位是在2的n次方上，例如校验位是第1,2,4,8,16,32,64..........位等等（比前边的奇偶校验跟CRC校验位放到末尾不同，它放在2的n次方位上），目前就64位系统，姑且只写到64位吧，估计考试也不会超出64位！

海明码稍微复杂一点吧，我觉得做题的话，得画表格，不然容易懵圈，没关系，学习不就是这样么，一遍不行两遍，两遍不行三遍，只要懂了原理就可以了，不需要你去深究它，主要是为了对付考试，当然感兴趣的同学可以研究下。

1.表格做题法，画出三行“位数”，“信息位”，“校验位”

例题：求1011的海明码？

答：

R2，R1，R0这几个校验位，最终是用异或操作，相同的为0，不相同的为1（0异或0=0,1异或1=0，1异或0=1，原则就是，同0非1）上边是偶校验，校验位最终=001，如果是奇校验就取反=110

最终结果1010101（偶校验），1011110（奇校验）

海明码的考题：

1.海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于某监被校位的数据当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误。对于32位的数据，至少需要加（）个校验位才能构成海明码。

以10位数据为例，其海明码表示为D9D8D7D6D5D4P4D3D2D1P3D0P2P1中，其中D(Osis9)表示数据位，Pj(1sjs4)表示校验位，数据位D9由P4、P3和P2进行校验（从右至左D9的位序为14,即等于8 4 2,因此用第8位的P4、第4位的P3和第2位的P2校验），数据位D5由（）进行校验

A.3 B.4 C.5 D.6

A.P4P1 B.P4P2 C.P4P3P1 D.P3P2P1

这个题第二问有点意思，不过他把过程给你讲了，咱们上边只讲了怎么求校验位，没讲数据位是由哪几个校验位校验的，这个也要会，不过题目中给出来了！D9的位序是14，等于8 4 2，因此是第8位的P4，第4位的P3和第2位的P2校验的，这句话是重点，不写出来你也要回，那么D5是那几位校验的呢？D5的位序是10，10=8 2，明显是第8位的P4跟第2位的P2校验的，所有答案就是P4P2

感谢大伙点赞 关注的支持，是我持续学习更新的动力，关注公众号：Coding-9527，跟大伙一起学习，成长，进步！

,