二进制数据在 传送、存取等环节,可能会发生 误码(1变成0或0变成1). 如何发现并纠正 误码? 解决此类问题的思路是在原始数据(数码位)基础上增加几位校验位。常使用的检验码有三种. 分别是 奇偶校验码、海明校验码和循环冗余校验码(CRC)
其中 奇偶校验码 只能查是否有错误而无法纠错,且要求只能有一位出现错误。
为了能找到发生错误的位置,而有了 海明校验码
实际上本质来说, 海明码是升级款的奇偶校验码,其采用了一种非常巧妙的方式,把这串数字(即要传输的内容)分了组,通过分组校验来确定哪一位出现了错误
类似KMP算法,描述起来很麻烦,实际上使用起来却很简单
"海明"也被译为"汉明"
实例
数据位为8的数据 D7D6D5D4D3D2D1D0=01101001D_7D_6D_5D_4D_3D_2D_1D_0=01101001D7D6D5D4D3D2D1D0=01101001,求海明码
1.计算校验位的个数
设数据位为n位,校验位P为k位,则n和k必须满足以下关系:
2.计算校验位的位置
2.1 海明码的总位数
设校验位为P,数据位为D,海明码为H,则海明码H的位数为数据的位数和校验码的位数相加,
在此即为 8+4 = 12 位
2.2 校验码的位置
校验位P 在海明码的第 2i−12^{i-1}2i−1 位,即 Hj=Pi,j=2i−1H_j = P_i,j=2^{i-1}Hj=Pi,j=2i−1,i从1开始计数。
无论是海明码、校验位还是数据位,均从右向左排列,即从低位向高位排列。
可先填入校验码的位置,再将数据位依次从低位到高位填入
如此例,i即为 1,2,3,4, 故有:
3.确定每个数据位 都由哪些校验码进行校验
数据位D的下标,等于其校验位的下标之和
4.计算校验码的值
校验码的值 为有参与校验的数据依次从低到高异或的值。
(异或:相同为0,相异为1)
5.错误校验
海明码是一种纠错码,其方法是为需要校验的数据位增加若干校验位,使得校验位的值决定于某些被校位的数据,当被校数据出错时,可根据校验位的值的变化找到出错位,从而纠正错误。对于32位的数据,至少需要增加( )个校验位才能构成海明码。
以10位数据为例,其海明码表示为 D(0≤i≤9)表示数据位,P (1 ≤j≤4)表示校验位,数据位D由( )进行校验。