一文搞定校验码(奇偶校验,海明,CRC 码) | 您所在的位置:网站首页 › 为什么奇偶校验码只能检测奇数位 › 一文搞定校验码(奇偶校验,海明,CRC 码) |
目录效验码计算码距方法奇偶校验码校验原理奇偶校验异或法制总结海明校验码海明校验码的分布规律海明码纠错以及定位实现原理海明码完善总结循环冗余校验码(CRC)模2除算法拓展检错与纠错纠错概述特点总结
效验码
校验码:指能够发现或能够自动纠正错误的数据编码,也称检错纠错编码。 实现原理:通过加一冗余码,来检验或纠错编码 码字 : 由若干位代码组成的一个字 码距:将两个码字逐位进行对比,具有不同的位的个数称为两个码字间的距离,一种编码方案可能有若干个合法码字,各合法码字间的最小距离称为“码距。也称海明距离。 计算码距方法计算0100和1111 直接观察法:可以看出,有3个数位值不同,所以码距为3. 异或计算法:0100⊕1111=1011 ,结果为1011,里面有几个1就代表有多少个数位值不同,即码距是多少,这里码距是3。 若码距=2,有检错能力;若码距≥3,可能还会纠错能力 奇偶校验码![]() 奇数个一相异或 为 1 偶数个零相同或 为 1 总结 上述奇偶校验码不能发现偶数位错误,能发现奇数位错误,但是不能定位。 海明校验码一种多重奇偶校验码。 实现原理:在有效信息位中加入几个校验位形成海明码,并把海明码的每一个二进制位分配到几个奇偶校验组中。当某一位出错后,就会引起有关的几个校验位的值发生变化。 特点:可以发现错误,定位错误位置,自动纠正错误。 可以检测双比特错误,但只能纠正单比特错误。
![]() S1=P1⨁D1⨁D2⨁D4 S2=P2⨁D1⨁D3⨁D4 S3=P3⨁D2⨁D3⨁D4 若S1S2S3=000,则说明无错,否则说明出错。这个数的值就是出错的位置,如S1S2S3=001,表示第1位出错,即H1出错,直接将该位取反就可以达到纠错的目的。
首先,发送端和接受端会有一个生成多项式G(x)约定,生成多项式G(x)的最高次幂为R。任意一个二进制数码都可用一个系数为0或1的多项式与之对应。比如:二进制数码 1101 对应的G(x)=1*X3+1*X2+0*X1+1*X0= X3+X2+1 确定生成多项式即为除数 在发送端,将要传送的K位二进制信息码左移R位,将它与生成多项式G(x)所对应的的二进制数码进行模2除法,产生余数,生成一个R位检验码,并附在信息码后,构成一个新的二进制码(CRC)码,共K+R位。
用于求 CRC 码
1、被除数最高位 为 1,上 1 否则 上 0 2、两者进行异或运算,一直得到校验位(一定比被除数少 1 位) 求得: 101001 的 CRC 码为 101001 001 拓展模2运算:分为模2加、模2减、模2乘、模2除,不考虑进位和借位。 检错与纠错注意: 余数与出错位的规律,并不是简单的余数的二进制转十进制,因为有三位对应二的三次方即为八除去正确的 000 ,即为七个一循环。 纠错概述但是实际一般运用于检错 特点理论上可以证明循环冗余校验码的检错能力有以下特点: 1)可检测出所有奇数个错误; 2)可检测出所有双比特的错误; 3)可检测出所有小于等于校验位长度的连续错误; 总结 |
CopyRight 2018-2019 实验室设备网 版权所有 |