在计算机运行时,为了保证二进制数据在传输时准确,通常采用校验码对传输的数据进行检测和纠错。 代码间距离是任意合法编码之间至少有多少个二进制位不同例如,与:个已编码比特1的“8 1 4 2”代码相对应的二进制分别为1000、0001、0100、0010 .即使任一已编码比特发生变化时因此,仅靠代码间隔是无法检测出传输内容的错误的。
一.奇偶校验码
在编码中增加一个奇偶校验位,使编码中的第一个数为奇数或偶数,代码间距离为2。 奇偶校验是指加上奇偶校验位使编码中的第一个个数为奇数,奇偶校验是指加上奇偶校验位使编码中的第一个个数为偶数。
例如,对于编码8,对应的原始字节流为00001000。 如果在开头附加奇偶校验位,则进行奇偶校验时字节流为0 00001000,
原代码0 00001000的编码正确,1个位传输错误0 00001010不满足1的个数为奇数,2个位传输错误0 00101010被正确编码,满足1的个数为奇数,3个位传输错误0 00001111不满足1
偶数检查时
原代码1 00001000的编码正确,任一个位传输错误1 00001010不满足1的个数为偶数,两个位传输错误1 00101010被正确地编码,满足1的个数为偶数,三个位传输错误1 00001111不满足1的个数为
因此,奇偶校验不能检测偶数个比特传输错误,也不能校正错误比特。
二.海明威
汉明码在数据中的特定位置插入k个奇偶校验位。 数据的位数是n。 那么,汉明码的总位数是n k
的插入个数满足2^k -1=n k
1 )插入的奇偶校验位pi=2^(I-1 )的位置,即汉明码的1、2、4、8、16、32 .位
2 )将汉明码bit的下标分别转换为二进制,将奇偶校验位对应的汉明码bit,的零置换为通配符进行分组。
例如,8位数据是4位奇偶校验位
通配符1 * * * *1* * *1* * *1* * * * 1汉明码h12 h10 H9 h8 H5 H3 h 1数据位D/奇偶校验位PD7D6D5D4D4D3D3D2D1P3D0P2P1分别为由于满足****1汉明码的下标所置换为的D6的满足***1*的汉明码的下标的组分别为H2、H3、H6、H7、H10、H11,所以对应的P2、D0、D2、D5、D11
4 ) Gi不是全0的情况下,对应的10进制表示汉明码所对应的下标错误。 相反可以纠正。
例如,1001001110序列,10比特
1 )需要插入4个奇偶校验位,汉明码总共14位。 汉明码对应的内容如下表所示
奇偶校验位零为通配符*1*****1***1***1****1汉明码h14 H13 h12 h10 h8 H5 H3 h1数据位D/奇偶校验位PD9D8 D7 D6 D5 D4 D4 P4 D4
2 )集团化
P1、D0、D1、D3、D4、D6、D8是一组;
P2、D0、D2、D3、D5、D6、D9是一组;
P3、D1、D2、D3、D7、D8、D9是一组;
P4、D4、D5、D6、D7、D8、D9是一组;
4 )求p值,偶校验//1001001110时
P1=d0D1D3D4D6D8=0101100=1
p2=d0
P3=D1
P4=D4 > D5 > D6 > D7 > D8,> d9=0>0>1<0>0>1=0
3 )对于实际收到的值,
G1=P1d0D1D3D4D6D8=1010110=0
G2=p2d0D2D3D5D6d9=0001011=1
G3=P3D1D2D3D7D8d9=0101001=1
G4=P4D4D5D6D7D8,d9=0001001=0
因此,相对应的G4-G3-G2-G1的值为0110真值6,可以认为在H6传输中发生了错误,即在D2中发生了错误,进行逆修正。