校验码
- 码距
- 两个编码中,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(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