海明码是一种可以纠正一位差错的编码,它是利用校验字段来检测数据中是否包含错误的一种方式。
海明码编码方法
计算校验为个数
校验码个数需要满足公式:
2^K ≥ N + K
其中K为校验码的个数,N为数据的个数
例如需要编码的数据为0011 1001,则需要K需要至少等于4才能满足条件
重排编码位置
根据编码K的大小,将当前编码位放置到2^K的位置上
取数据位为D0, D1, DK.....
取编码位为P0, P1, PK.....
重排前位置为 D7, D6, D5, D4, D3, D2, D1, D0
重排后位置为 D7, D6, D5, D4, P3, D3, D2, D1, P2, D0, P1, P0
计算编码值
对于P0,从P0开始每间隔2^0=1位,取1个值进行异或
P0 = D0 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6
对于P1,从P1开始每间隔2^1=2位,取2个值进行异或
P1 = D0 ⊕ D2 ⊕ D3 ⊕ D5 ⊕ D6
对于P2,从P2开始每间隔2^2=4位,取4个值进行异或
P2 = D1 ⊕ D2 ⊕ D3 ⊕ D7
对于P3,从P3开始每间隔2^3=8位,取8个值进行异或
P3 = D4 ⊕ D5 ⊕ D6 ⊕ D7
将计算完的P值放入到编码后的对应位置即可得到最终的编码
海明码解码方法
海明码解码跟海明码编码方式刚好相反
下面以0011 0110 1111为例
先获取海明码编码位数的大小
通过 2^K ≥ 12 得出K的大小至少为4,所以海明码编码位数的大小为4
获取编码位置的值
通过PK = 2^K获取具体的编码值
P0 = 1
P2 = 1
P3 = 1
P4 = 0
通过D重新计算P值
计算中可以通过1的个数来快速进行异或,偶数个1为0,奇数个1为1
P0 = D0 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6 = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 = 1
P1 = D0 ⊕ D2 ⊕ D3 ⊕ D5 ⊕ D6 = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 = 0
P2 = D1 ⊕ D2 ⊕ D3 ⊕ D7 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0
P3 = D4 ⊕ D5 ⊕ D6 ⊕ D7 = 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
判断错误位
当P值出现和原始P值不同时,则表明在该位上对应的D出现了错误
其中P0, P3无错误,所以D0, D1, D3, D4, D5, D6, D7无错误
P1, P2 有错误,推出D2错误
网友评论