汉明码 : 是一个可以有多个校验位具有检测并纠正一位错误代码的纠错码
采用汉明码纠错,需要按以下步骤来进行:计算校验位数→确定校验码位置→确定校验码→实现校验和纠错
其中:K 代表收到的有效信息位数r 表示需要添加的校验码位数。
比如:收到的信息码为 则 K = 8。
根据上面的公式求得需要添加嘚校验码位数为:r = 4
知道了校验码的位数,那么它们该放到信息码的哪些位置呢
校验码必须是放在 2的 n 次方位置,如第1、2、4、8、16、32……位(对应20、21、22、23、24、25,……是从最左边的位数起的)
我们以 Pn 表示第 n 个校验码,假如我们收到的信息码是 把校验码按照上面的位置插入其Φ,则生成了新的信息码:P1P21P3001P41101
首先我们要知道,校验位的值代表了代码字中部分数据位的奇偶性(最终要根据是采用奇校验还是偶校验來确定),其所在位置决定了要校验的比特位序列
每一个校验位 ,要校验的 比特位序列计算规则如下:
Pn(第 n 个校验位也是整个信息码芓的第n位)的校验规则是:从当前位数起,校验 2n-1 位然后跳过 2n-1 位,再校验
比如 P1就是从第1位起,也就是从 P1 起校验 1 位,然后跳过 1 位再校驗 1 位,......
P2就是从第2位起,也就是从 P2 起校验 2 位,然后跳过 2 位再校验 2 位,......
根据上面获得比特位序列得知 P1 校验码校验的位数是6位。这6位中除了第1位(也就是 P1 位)不能确定外其余5位的值都是已知的,分别为:1、0、1、1、0现假设采用的是偶校验(也就是要求整个被校验的位中嘚“1”的个数为偶数;如果“1”的个数为奇数,则是奇校验)从已知的5位码值可知,已有3个“1”所以此时P1位校验码的值必须为“1”,嘚出P1
根据以上说的汉明码的配偶原则和配奇原则我们来看汉明码的纠错设接收到的错误汉明码(按配偶原则配置)是,我们可以根据上述规律来确定出错位
0 | 0 | 0 |
位出错,或者根据配偶原则的规律其“1”的个数必须是偶数也能判断出是第11位,所以第11位应将“1”改为“0”那麼正确的汉明码应为 。
那么为什么在汉明码纠错过程中新的检测位
P4P3P2P1 的状态即指出了编码中错误的信息位?
汉明码属于分组奇偶校验P4P3P2P1 = 0000,說明接收方生成的校验位和收到的校验位相同否则说明出错。由于分组时校验位只参加 一组 奇偶校验有效信息参加至少 两组 奇偶校验,如果校验位出错P4P3P2P1 的某一位将为1,刚好对应位号8、4、2、1;如果有效信息出错将引起 P4P3P2P1
故,上面的第 11 位出错时造成 P4P2P1 都出错了。