#软考##计算机##程序员##中级软考#
校验码
码距两个编码中，A码变为B码所需要改变的位数。如10101和00110，第一、四、五位都不同，则码距为5。三种基本校验方式：奇偶校验码、循环冗余校验码、海明校验码。奇偶校验
奇校验：校验编码中是否有奇数个1。偶校验：校验编码中是否有偶数个1。循环冗余校验码CRC
CRC只能检错，不能纠错。一个能整除某个多项式的编码。将原始报文除以指定多项式，将所得余数作为校验位加在原始报文之后，再作为发送数据发给接收方。形式为：
←数据位→
←校验位→
1）特点
校验码由信息码产生校验码位数越长，校验能力越强2）校验方法
（1）先将多项式转为二进制表示，规则为：根据多项式幂指数看第n位有没有x的n-1次方，有则为1，无则为0。
例如多项式：x^4＋x^3＋x＋1，第1位x^0＝1，有；第2位x^1，有；第3位x^2，无；第4第5同理。则此多项式为11011。（2）在原始报文后面加上多项式最高幂指数个0（以上例则为4个0）。
（3）原始报文与多项式二进制数进行模2运算。
（4）将最后的余数作为校验码，与原始报文拼接，再发送出去。
（5）接收方将收到的数据与多项式二进制数进行模2运算，若余数为0，则校验正确，数据传输正确。
试题1（2022年上半年试题14）循环冗余校验码（Cyclic Redundancy Check，CRC）是数据通信领域中最常用的一种差错校验码，该校验方法中，使用多项式除法（模2除法）运算后的余数为校验字段。若数据信息为n位，则将其左移k位后，被长度为k＋1位的生成多项式相除，所得的k位余数即构成k个校验位，构成n＋k位编码。若数据信息为1100，生成多项式为X^3＋X＋1（即1011），则CRC编码是（）。
A.1100010
B.1011010
C.1100011
D.1011110
解：（1）题目已给二进制表示
（2）多项式最高幂指数为3，则原始报文后加3个0：1100000
（3）模2运算结果商为111，余数为10
（4）因为余数必须为k-1位，k=3。所以余数应为010，所以发送出去的报文为1100010。
海明校验码
1）性质
在数据位之间的确定位置插入K个校验位，通过扩大码距实现检错和纠错。
校验码位数：2^r - 1 >= n +k（n是信息码位数，k是校验码位数）。
2）生成过程
设信息位1011：
（1）由2^r - 1 >= n +k得K＝3，校验码为3位，占位是1，2，4位。
7
6
5
4
3
2
1
1
0
1
1
？
？
？
（2）将信息位拆分成二进制表示。即
7＝4＋2＋1
6 = 4+2
5 = 4+1
3 = 2+1
展开的二进制表示：第7位的信息位由第4、2、1位的校验码共同校验，其它同理。
（3）找出每个校验位有关联的信息位，进行异或求值。如校验位4关联的信息位是7、6、5，异式得0；校验位2同理，得0；校验位1同理，得1。
（4）最终发送的海明码为1010101。
3）检错
（1）接收到海明码后，将每一位校验位与其关联的信息位进行异或。如上例则为第4位校验位与
第7、6、5位信息位进行异或。
7
6
5
4
3
2
1
i4
i3
i2
i1
r2
r1
r0
r2异或i4异或i3异或i2→0
r1异或i4异或i3异或i1→0
r0异或i4异或i2异或i1→0
（2）如果是偶校验则为0，奇校验则为1。
4）纠错
假设上例接收出错，为1011101，并且是偶校验，则纠错过程为：
（1）
r2异或i4异或i3异或i2 = 1异或1异或0异或1 = 1
r1异或i4异或i3异或i1 = 0异或1异或0异或1 = 0
r0异或i4异或i2异或i1 = 1异或1异或1异或1 = 0
（2）将检错结果排列为二进制：100，这个100就是指出错的位置，即第4位。
（3）纠错方法就是将出错位取反。
以上知识点来源于我看完《软件设计师教程》第五版的相关知识点做的汇总，我，后续将会持续追更笔记。望各位软考顺利上岸~
图片版：
