软件设计师历年校验码真题软件设计师考试之三种常考校验码

导读#软考##计算机##程序员##中级软考#校验码码距两个编码中，A码变为B码所需要改变的位数。如10101和00110，第一、四、五位都不同，则码距为5。三种....

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

校验码

• 码距

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位。