海明码校验码例题,海明码校验码纠错

超级无敌简单易懂的海明码的校验和纠错原理与实现

最近和朋友的聊天涉及到了海明码纠错，先来康康海明纠错码到底是什么

Hamming Code，电信领域的一种线性调试码，由于编码简单，广泛应用于内存（RAM）。

若海明码长为n，信息位数为k，则需要插入r个监督位校验码。如果想要r个校验码能构成r个关系式来指示出错码的n个可能位置，则需要

即为

比如说我们有8位二进制数需要编码，那么应该有

海明码的校验码都在2的整数次幂处，也就是第1、2、4....等位

注意这不是数组索引，没有第0位数。

如果用pn表示第n个校验码

dk表示第k个数据

所以我们的8位二进制数编码结果应该是

校验位1 的校验规则是从当前位数起，校验一位，跳过一位，再校验一位，再跳过一位.......也就是说校验了所有数据位位置序号的二进制表示的最后一位是1的数据，即 0001，0011，0101，0111，1001，1011

同理，第k个校验位的校验规则是从当前位开始连续校验 位然后跳过 位......也就是说，第k位校验位应该校验数据位位置序号的二进制表示的倒数第k位是1的数据

其实就是二进制数的第k位表示

那到底咋算嘞？

之前学过奇校验和偶校验，可以排上用场了

奇校验是要求整个被校验的位中“1”的个数为奇数，偶校验则是要求整个被校验的位中“1”的个数为偶数

我们用偶校验来试算一下。

比如我们输入的数据是10111011

插入后应该是

计算p1， 第0001，0011，0101，0111，1001，1011位中除了p1本身共有4个1，所有p1为0可以使“1”的总数为0

同理p2为0

p3为1

p4为1

所得数据为

比起普通的奇校验偶校验而言，海明码非常强大的一点就在于它不仅可以实现校验，还能实现1bit的纠错。

依然以我们的偶校验为例

可以看出来的是，所有的校验码位都不会被其他校验码影响，仅由自己校验自己，这就保证了如果我们的某位校验码出错的话不会影响其他校验码的校验结果，我们可以轻易的找到这个出错的校验码。

所以说，我们的四个校验组计算出来如果只有一个校验组的结果是错误的，那么说明是该位校验码出错，取反即可。

再来看看数据位。

因为每个数据都被校验了2-3次，所以出错的校验组数肯定大于1

如果是两个校验组出错的话，有d1、d2、d3、d5、d6、d8，每个数据位都和校验组的组合形式一一对应，因此我们知道哪两个校验组出错就知道了哪一位出错。

如果是三个校验组出错的话同理也可以找出是哪一位。

本来应该用FPGA写verilog的，不过我现在电脑里就只能写python

就用python做了一个hamming码的编码与校验纠错

已知有效信息位为01101110,求海明码的生成和校验过程?

将K位检测位记作Ci(i=1,2,4,8...)分别安插在n+k位代码编号的第1,2,4,8,16...位上.

01101110(n=8)根据2的k次方大于等于n+k+1,可求出配置成海明码需增添检测位k=4,

原码01101110记作B8,B7,B6,B5,B4,B3,B2,B1.

则原码同检测位的位置安排如下：

二进制序号：1 2 3 4 5 6 7 8 9 10 11 12

名称 C1 C2 B8 C4 B7 B6 B5 C8 B4 B3 B2 B1

如果按配偶原则来配置海明码,则

C1应使1,3,5,7,9,11位中的“1”的个数为偶数；

C2应使2,3,6,7,10,11位中的“1”的个数为偶数；

C4应使4,5,6,7,12位中的“1”的个数为偶数；

C8应使8,9,10,11,12位中的“1”的个数为偶数；

故C1应为3位⊕5位⊕7位⊕9位⊕11位,即C1=B8⊕B7⊕B5⊕B4⊕B2

故C2应为3位⊕6位⊕7位⊕10位⊕11位,即C2=B8⊕B6⊕B5⊕B3⊕B2

故C4应为5位⊕6位⊕7位⊕12位,即C4=B7⊕B6⊕B5⊕B1

故C8应为9位⊕10位⊕11位⊕12位,即C8=B4⊕B3⊕B2⊕B1

即,

C1=B8⊕B7⊕B5⊕B4⊕B2=0⊕1⊕0⊕1⊕1=1

C2=B8⊕B6⊕B5⊕B3⊕B2=0⊕1⊕0⊕1⊕1=1

C4=B7⊕B6⊕B5⊕B1=1⊕1⊕0⊕0=0

C8=B4⊕B3⊕B2⊕B1=1⊕1⊕1⊕0=1

故01101110的海明校验码为C1 C2 B8 C4 B7 B6 B5 C8 B4 B3 B2 B1=110011011110

求教海明码

再学学哦

1.海明码的概念

海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式：

2^r=n+1 或 2^r=k+r+1

海明码的编码效率为：

R=k/(k+r)

式中 k为信息位位数

r为增加冗余位位数

2.海明码的原理

在数据中间加入几个校验码，将玛距均匀拉大，将数据的每个二进制位分配在几个奇偶校验组里，当某一位出错，会引起几个校验位的值发生变化。

海明不等式：

校验码个数为K，2的K次幂个信息，1个信息用来指出“没有错误”，其余2K-1个指出错误发生在那一位，但也可能是校验位错误，故有N=2的K次-1-K能被校验。

海明码的编码规则：

1.每个校验位Ri被分配在海明码的第2的i次的位置上，

2.海明玛的每一位（Hi)是由多个/1个校验值进行校验的，被校验玛的

位置玛是所有校验这位的校验位位置玛之和。

一个例题：

4个数据位d0,d1,d2,d3, 3个校验位r0,r1,r2，对应的位置为：

d3 d2 d1 r2 d0 r1 r0 ======b7 b6 b5 b4 b3 b2 b1

校验位的取值，就是他所能校验的数据位的异或

b1为b3,b5,b7的异或，b2为b3,b6,b7 b4为b5,b6,b7

海明玛传送到接受方后，将上三式的右边（b1,b2,b4)的逻辑表达式分别

异或上左边的值就得到了校验方程，如果上题采用偶校验

G1=b1 b3 b5 b7的异或

G2=b2 b3 b6 b7的异或

G3=b4 b5 b6 b7的异或

若G1G2G3为001是第四位错

若为011是第六位错

3.海明码的生成与接收

特注：以下的+均代表异或

方法一：

1)海明码的生成。

例1.已知：信息码为："0010"。海明码的监督关系式为：

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

求：海明码码字。

解：1)由监督关系式知冗余码为a2a1a0。

2)冗余码与信息码合成的海明码是："0010a2a1a0"。

设S2=S1=S0=0,由监督关系式得：

异或运算：

a2=a4+a5+a6=1

a1=a3+a5+a6=0

a0=a3+a4+a6=1

因此，海明码码字为："0010101"

2)海明码的接收。

例2.已知：海明码的监督关系式为：

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

接收码字为："0011101"(n=7)

求：发送端的信息码。

解：1)由海明码的监督关系式计算得S2S1S0=011。

2)由监督关系式可构造出下面错码位置关系表：

S2S1S0

000

001

010

100

011

101

110

111

错码位置

无错

a0

a1

a2

a3

a4

a5

a6

3)由S2S1S0=011查表得知错码位置是a3。

4)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1"

5)把冗余码a2a1a0删除得发送端的信息码："0010"

方法二：(不用查表，方便编程)

1)海明码的生成（顺序生成法）。

例3.已知：信息码为：" 1 1 0 0 1 1 0 0 " (k=8)

求：海明码码字。

解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码

码字:" A B 1 C 1 0 0 D 1 1 0 0 "

码位: 1 2 3 4 5 6 7 8 9 10 11 12

其中A,B,C,D分别插于2的k次方位(k=0,1,2,3)。码位分别为1,2,4,8。

2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)

A-1,3,5,7,9,11；

B-2,3,6,7,10,11；

C-4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)

D-8,9,10,11,12。

3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：

A=∑(0,1,1,0,1,0)=1

B=∑(0,1,0,0,1,0)=0

C=∑(0,1,0,0,0) =1

D=∑(0,1,1,0,0) =0

4)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0"

2)海明码的接收。

例4.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=8)

求：发送端的信息码。

解：1)设错误累加器(err)初值=0

2)求出冗余码的偶校验和，并按码位累加到err中：

A=∑(1,0,1,0,1,0)=1 err=err+20=1

B=∑(0,0,0,0,1,0)=1 err=err+21=3

C=∑(1,1,0,0,0) =0 err=err+0 =3

D=∑(0,1,1,0,0) =0 err=err+0 =3

由err≠0可知接收码字有错，

3)码字的错误位置就是错误累加器(err)的值3。

4)纠错--对码字的第3位值取反得正确码字：

"1 0 1 1 1 0 0 0 1 1 0 0"

5)把位于2的k次方位的冗余码删除得信息码："1 1 0 0 1 1 0 0"

如何求解海明码？

1)海明码的生成。 例1.已知：信息码为："0010"。海明码的监督关系式为： S2=a2+a4+a5+a6 S1=a1+a3+a5+a6 S0=a0+a3+a4+a6 求：海明码码字。 解：1)由监督关系式知冗余码为a2a1a0。 2)冗余码与信息码合成的海明码是："0010a2a1a0"。 设S2=S1=S0=0,由监督关系式得： 异或运算： a2=a4+a5+a6=1 a1=a3+a5+a6=0 a0=a3+a4+a6=1 因此，海明码码字为："0010101" 对以上这道题目的第二问的疑问： 冗余码与信息码合成的海明码是："0010a2a1a0"。为什么a2a1a0直接加在信息码后面，而不是按照1,2,4,8位的顺序加在信息码后面【例如：001(a2)0(a1)(a0)=0011001】 2)海明码的接收。 例2.已知：海明码的监督关系式为： S2=a2+a4+a5+a6 S1=a1+a3+a5+a6 S0=a0+a3+a4+a6 接收码字为："0011101"(n=7) 求：发送端的信息码。 解：1)由海明码的监督关系式计算得S2S1S0=011。 2)由监督关系式可构造出下面错码位置关系表： S2S1S0 000 001 010 100 011 101 110 111 错码位置 无错 a0 a1 a2 a3 a4 a5 a6 3)由S2S1S0=011查表得知错码位置是a3。 4)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1" 5)把冗余码a2a1a0删除得发送端的信息码："0010" 方法二：(不用查表，方便编程) 1)海明码的生成（顺序生成法）。 例3.已知：信息码为：" 1 1 0 0 1 1 0 0 " (k=4代表冗余位数，即校验码位数) 求：海明码码字。 解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码 码字:" A B 1 C 1 0 0 D 1 1 0 0 " 码位: 1 2 3 4 5 6 7 8 9 10 11 12 其中A,B,C,D分别插于2的k次方位(k=0,1,2,3)。码位分别为1,2,4,8。 2)冗余码A,B,C,D的线性码位是：(相当于监督关系式) 监督关系式的推导： D C B A 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 根据上面表格得到 A B C D 需要说明的是公式中参与计算的是表格中出现"1"的那个位 右边是数据位的二进制数,公式中的"+"表示异或 故此有如下表达式： A-1,3,5,7,9,11；(这里的1 3 5 7 9 11均为A那一列出现1的位) B-2,3,6,7,10,11； C-4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4) D-8,9,10,11,12。 3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)： A=∑(0,1,1,0,1,0)=1 B=∑(0,1,0,0,1,0)=0 C=∑(0,1,0,0,0) =1 D=∑(0,1,1,0,0) =0 4)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0" 2)海明码的接收。 例4.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=4代表冗余位数，即校验码位数) 求：发送端的信息码。 解：1)设错误累加器(err)初值=0 2)求出冗余码的偶校验和，并按码位累加到err中： A=∑(1,0,1,0,1,0)=1 err=err+2^0=1 B=∑(0,0,0,0,1,0)=1 err=err+2^1=3 C=∑(1,1,0,0,0) =0 err=err+0 =3 D=∑(0,1,1,0,0) =0 err=err+0 =3 由err≠0可知接收码字有错， 3)码字的错误位置就是错误累加器(err)的值3。 4)纠错--对码字的第3位值取反得正确码字： "1 0 1 1 1 0 0 0 1 1 0 0" 5)把位于2的k次方位的冗余码删除得信息码："1 1 0 0 1 1 0 0"