纠错编码-海明码

#一.海明码 ###海明码只能发现双比特错误，纠正单比特错误 #二.工作原理 ###“动一发而牵全身”，因为海明码是一个多重校验码，也就是码字中的信息码位同时被多个校验码进行校验 #三.工作流程 ###1.确定校验码位数 海明不等式2^r>=k+r+1,r为冗余信息位，k为信息位 eg:要发送的数据为D=101101 则数据的位数k=6 满足的不等式最小r为4 也就是D=101101的海明码应该有6+4=10位，其中原始数据6位，校验码4位 ###2.确定校验码和数据的位置 还是上面的那个例子D=101101，假设这4位校验码分别为P1，P2,P3,P4,数据从左往右为D1,D2...D6 校验码必须是在2n次方位置，如第1、2、4、8、16、32,...位（对应2^0 2^1 2^2 2^3 2^4 2^5……，是从最左边的位数起的），这样一来就知道了信息码的分布位置，也就是非2n次方位置，如第3、5、6、7、9、10、11、12、13，...位（是从最左边的位数起的） 即  | | | | | | | | | |  -|-|-|-|-|-|-|-|-|-|- 数据位|1|2|3|4|5|6|7|8|9|10 代码|P1|P2|D1|P3|D2|D3|D4|P4|D5|D6 实际值| | |1| |0|1|1| |0|1 ###3.求出校验码的值 D=101101  | | | | | | | | | |  -|-|-|-|-|-|-|-|-|-|- 二进制|0001|0010|0011|0100|0101|0110|0111|1000|1001|1010 数据位|1|2|3|4|5|6|7|8|9|10 代码|P1|P2|D1|P3|D2|D3|D4|P4|D5|D6 实际值|0|0|1|0|0|1|1|1|0|1 可以看出P1对应的二进制第一位为1（看二进制是几位的话就看最后一个数据位是几位二进制格式）可以发现D1，D2，D4，D5对应的二进制第一位也是1，则P1代码校验的数据为D1,D2,D4,D5 令所有要校验的位异或=0（即同0异1） 1 0 1 0 P1⊕D1⊕D2⊕D4⊕D5⊕=0 可推出P1=0 1 0 0 同理P2对应的二进制第二位是1，则P2代码校验的数据为D1,D3,D4,D6 1 1 1 1 P2⊕D1⊕D3⊕D4⊕D6⊕=0 可推出P2=0 0 1 0 同理P3对应的二进制第三位是1，则P3代码校验的数据为D2,D3,D4 0 1 1 P3⊕D2⊕D3⊕D4=0 可推出P3=0 1 0 同理P4校验的数据为D5，D6 0 1 P3⊕D5⊕D6=0 可推出P4=0 1 具体的计算方法我参阅了http://www.cnblogs.com/scrutable/p/6052127.html，即 p1（第1个校验位，也是整个码字的第1位）的校验规则是：从当前位数起，校验1位，然后跳过1位，再校验1位，再跳过1位，....。这样就可得出p1校验码位可以校验的码字位包括：第1位（也就是p1本身）、第3位、第5位、第7位、第9位、第11位、第13位、第15位，...。然后根据所采用的是奇校验，还是偶校验，最终可以确定该校验位的值。 p2（第2个校验位，也是整个码字的第2位）的校验规则是：从当前位数起，连续校验2位，然后跳过2位，再连续校验2位，再跳过2位，……。这样就可得出p2校验码位可以校验的码字位包括：第2位（也就是p2本身）、第3位，第6位、第7位，第10位、第11位，第14位、第15位，...。同样根据所采用的是奇校验，还是偶校验，最终可以确定该校验位的值。 p3（第3个校验位，也是整个码字的第4位）的校验规则是：从当前位数起，连续校验4位，然后跳过4位，再连续校验4位，再跳过4位，……。这样就可得出p4校验码位可以校验的码字位包括：第4位（也就是p4本身）、第5位、第6位、第7位，第12位、第13位、第14位、第15位，第20位、第21位、第22位、第23位，...。同样根据所采用的是奇校验，还是偶校验，最终可以确定该校验位的值。 p4（第4个校验位，也是整个码字的第8位）的校验规则是：从当前位数起，连续校验8位，然后跳过8位，再连续校验8位，再跳过8位，……。这样就可得出p4校验码位可以校验的码字位包括：第8位（也就是p4本身）、第9位、第10位、第11位、第12位、第13位、第14位、第15位，第24位、第25位、第26位、第27位、第28位、第29位、第30位、第31位，...。同样根据所采用的是奇校验，还是偶校验，最终可以确定该校验位的值。 综上所诉101101的海明码为0010011101 ###4.检验并纠错 D=101101  | | | | | | | | | |  -|-|-|-|-|-|-|-|-|-|- 二进制|0001|0010|0011|0100|0101|0110|0111|1000|1001|1010 数据位|1|2|3|4|5|6|7|8|9|10 代码|P1|P2|D1|P3|D2|D3|D4|P4|D5|D6 实际值|0|0|1|0|0|1|1|1|0|1 故101101的海明码为0010011101 假设第五位出错，因此接收到的数据位为00101111101 对所有要校验的位异或运算 0 1 1 1 0 P1⊕D1⊕D2⊕D4⊕D5⊕=1 1 0 1 1 0 1 1 1 1 P2⊕D1⊕D3⊕D4⊕D6=0 1 0 1 0 0 1 1 1 P3⊕D2⊕D3⊕D4=1 1 0 1 1 0 1 P3⊕D5⊕D6=0=0 1 0 从P4往P1写可得到0101，即二进制序列为0101，恰好对应的二进制5，这样就找到了出错的位置，即出错位是第五位