1.1.4 校验码

码距

两个合法编码对应位之间比较,有多少位编码不同,又称为海明距离。比如10101和00110就是(从高到低1,4,5位不同,码距为3)

计算海明距离的一种方法,就是对两个位串进行异或(xor)运算,并计算出异或运算结果中1的个数。例如110和011这两个位串,对它们进行异或运算,其结果是:

110011=101110 \bigoplus 011=101

异或结果中含有两个1,因此110和011之间的海明距离就等于2。

为了使一个系统能检查和纠正一个差错,码间最小距离必须至少是“3”。最小距离为3时,或能纠正一个错,或能检二个错,但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。

码距越大,纠错能力越强,但数据冗余也越大,即编码效率低了。

模二加法

这是一种二进制的运算,等同于“异或”运算。

规则是两个序列按位相加模二,即两个序列中对应位,相加,不进位,相同为0,不同为1。

奇偶校验码(Parity Codes)

是一种通过增加冗余位使得码字中"1"的个数恒为奇数或偶数的编码方法,它是一种检错码。在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。因为其利用的是编码中1的个数的奇偶性作为依据,所以不能发现偶数位错误。(错偶数个奇偶性不变)

海明码(Hamming Code)

贝尔实验室Richard Hamming设计,在特定位置插入k个校验码,通过扩大码距来检错纠错。

n位数k校验位,则必须符合:

2k1n+k2^k-1\geq n+k

Pk,Pk1,...p1校验位: P_k, P_{k-1},...p_1

Dn1,Dn2,...D0数据位:D_{n-1},D_{n-2},...D_0

Hn+k,Hn+k1,...H1海明码:H_{n+k},H_{n+k-1},...H_1

Hj=Pi,j=2i1则:H_j=P_i,j=2^{i-1} 数据从低到高占据剩下的位置

海明码中的任何一位都是由若干个校验位来校验的:被校验的海明位的下标==所有参与校验该位的校验位的下标之和,校验位由自身校验。

编码过程

对于8位数,要4个校验位。

  • 1.确定D与P位置
Hamming D&P
H(12) D(7)
H(11) D(6)
H(10) D(5)
H(9) D(4)
H(8) P(4)
H(7) D(3)
H(6) D(2)
H(5) D(1)
H(4) P(3)
H(3) D(0)
H(2) P(2)
H(1) P(1)
  • 2.确定校验关系
海明码 分布 海明码下标 校验位组
H(12) D(7) 12=4+8 P3,P4
H(11) D(6) 11=1+2+8 P1,P2,P4
H(10) D(5) 10=2+8 P2,P4
H(9) D(4) 9=1+8 P1,P4
H(8) P(4) 8 P4
H(7) D(3) 7=1+2+4 P1,P2,P3
H(6) D(2) 6=2+4 P2,P3
H(5) D(1) 5=1+4 P1,P3
H(4) P(3) 4 P3
H(3) D(0) 3=1+2 P1,P2
H(2) P(2) 2 P2
H(1) P(1) 1 P1

根据每个校验位参与校验得

P1=D0D1D3D4D6P_1=D_0 \bigoplus D_1 \bigoplus D_3 \bigoplus D_4 \bigoplus D_6

P2=D0D2D3D5D6P_2=D_0 \bigoplus D_2 \bigoplus D_3 \bigoplus D_5 \bigoplus D_6

P3=D1D2D3D7P_3=D_1 \bigoplus D_2 \bigoplus D_3 \bigoplus D_7

P4=D4D5D6D7P_4=D_4 \bigoplus D_5 \bigoplus D_6 \bigoplus D_7

若使用奇校验,将校验位的偶校验值取反即可

  • 3.检测错误

G1=P1D0D1D3D4D6G_1=P_1 \bigoplus D_0 \bigoplus D_1 \bigoplus D_3 \bigoplus D_4 \bigoplus D_6

G2=P2D0D2D3D5D6G_2=P_2 \bigoplus D_0 \bigoplus D_2 \bigoplus D_3 \bigoplus D_5 \bigoplus D_6

G3=P3D1D2D3D7G_3=P_3 \bigoplus D_1 \bigoplus D_2 \bigoplus D_3 \bigoplus D_7

G4=P4D4D5D6D7G_4=P_4 \bigoplus D_4 \bigoplus D_5 \bigoplus D_6 \bigoplus D_7

如果采用偶校验,G4G3G2G1全为0则无错(奇校验全为1),且其十进制值指出了错误位置,如1010说明H10(D5)出错了,将其取反即可纠正错误。

Author: sumshare
Link: http://blog.sumshare.cn/2021/02/28/hammingcode/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.