(四)软件设计师考试之三种常考校验码(附带图片版)

#软考##计算机##程序员##中级软考#

校验码

• 码距

1. 两个编码中，A码变为B码所需要改变的位数。
2. 如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（2017年上半年试题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位。

（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位信息位进行异或。

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）纠错方法就是将出错位取反。

以上知识点来源于我看完《软件设计师教程》第五版的相关知识点做的汇总，关注我，后续将会持续追更笔记。望各位软考顺利上岸~

图片版：