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

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

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

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

校验码

  • 码距
  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位。

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

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

图片版:

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

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

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

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

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/70936.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信