奇校验海明码,海明校验码 异或纠错

海明码奇偶校验的基础问题~~求助！！！

1．校验原理：在数据中加入几个校验位（奇偶校验位），将数据代码的码距比较均匀地拉大，并把数据的每个二进制位分配在几个奇偶校验位组中。当某一位出错时，就会引起有关若干校验位的值发生变化，在不但可以发现出错，还能找出哪一位出错，为进一步自动纠错提供依据。2．编码规则：设对N位数据用K位校验位校验，则其海明码为：HmHm-1....H2H1其中最高位位号m，最低位位号为1。（1）校验位与数据位之和m（m=K+N）；（2）每个校验位Pi分配在海明码的2i-1位置上；（3）海明码中除校验位，其它为数据位。被校验数据从低到高顺序分配到海明码中；（4）海码的每一位码Hi由多个校验位校验，且被校验的每一位位号要等于校验它的个校验位的位号之和；（5）在增大合法码的码距时，使码距均匀地增大，保证检错平均。3．发现两位错、纠正一位错的海明码为表示N位数据、K位校验位中某一位出错以及无错，共有N+k+1种情况，另考虑到要发现两位同时出错，则应满足2K-1≥N+K+1按此关系计算所得K与N对应值如教材所示。例如，对N=8（一字节数据D8D7D6D5D4D3D2D1），需校验位K应为5，海明码为H13H12....H2H1其中5个校验位P5、P4、P3、P2、P1分别为H13、H8、H4、H2、H1，其余为数据位，即海码H13H12....H2H1为： P5D8D7D6D5P4D4D3D2P3D1P2P1根据“被校验位的海码位号==校验位号之和”关系，校验位Pi校验所有位号中带有i的海码位（方法同奇偶校验）：S1=P1⊕D1⊕D2⊕D4⊕D5⊕D7S2=P2⊕D1⊕D3⊕D4⊕D6⊕D7S3=P3⊕D2⊕D3⊕D4⊕D8S4=P4⊕D5⊕D6⊕D7⊕D8在上述关系中D4和D7分别由三个校验位校验，其余均只被两位校验，为此用P5对D1、D2、D3、D5、D6、D8再进行校验：若采用奇校验，则S1 S2 S3 S4 S5应为11111；若采用偶校验，则S1 S2 S3 S4 S5应为00000。现假设采用偶校验，则有：P1=D1⊕D2⊕D4⊕D5⊕D7P2=D1⊕D3⊕D4⊕D6⊕D7P3=D2⊕D3⊕D4⊕D8P4=D5⊕D6⊕D7⊕D8P5=D1⊕D2⊕D3⊕D5⊕D6⊕D8生成海明码，就是计算上述五个校验位；而校验过程就是计算前面所述的S1 S2 S3 S4 S5，它们反映了13 位海明码出错情况。当采用偶校验时，有教材所示判无错或发生一、二位出错及出错位号的结论。4．发现一位错、纠正一位错的海明码对N位数据位、K位校验位，要发现一位错、纠正一位错，则应满足2K≥N+K+1例如K=4，则N≤24-4-1=11，即最多只能校验11位数据。若对一字节（N=8）数据编码，则也需校验位4位，其海明码H12....H2H1为：D8D7D6D5P4D4D3D2P3D1P2P1校验关系式为：S1=P1⊕D1⊕D2⊕D4⊕D5⊕D7S2=P2⊕D1⊕D3⊕D4⊕D6⊕D7S3=P3⊕D2⊕D3⊕D4⊕D8S4=P4⊕D5⊕D6⊕D7⊕D8若假设采用偶校验，则有：P1=D1⊕D2⊕D4⊕D5⊕D7P2=D1⊕D3⊕D4⊕D6⊕D7P3=D2⊕D3⊕D4⊕D8P4=D5⊕D6⊕D7⊕D8举例：数据10101010采用偶校验方法可计算出4个校验位P4P3P2P1=0100，则求出数据10101010的海码为101001011000，把8位数据和4位校验位组成的海码一起存储、传送处理，当再次使用时，计算S1 S2 S3 S4，判是否均为0，若某一组S值不为0，则说明该组S所对应的位有错产生。如S4S3=11，则这两个S组中公有的一位出错---D8错。可通过对该位数据进行取反而得到纠正。

设被校验数据是二进制数1010，求其海明编码

用奇校验来确定其对应的汉明码为10100011101。

欲传送的二进制代码为1001101，有效信息位数为n=7位，则汉明校验的校验位为k位，则：2^k =n+k+1，k=4，进行奇校验设校验位为C1C2C3C4，汉明码为C1C2B7C3B6B5B4C4B3B2B1，

C1=1⊕B7⊕B6⊕B4⊕B3⊕B1=1⊕1⊕0⊕1⊕1⊕1=1

C2=1⊕B7⊕B5⊕B4⊕B2⊕B1=1⊕1⊕0⊕1⊕0⊕1=0

C3=1⊕B6⊕B5⊕B4=1⊕0⊕0⊕1=0

C4=1⊕B3⊕B2⊕B1=1⊕1⊕0⊕1=1

故传送的汉明码为10100011101。

什么是海明码呀？通俗一点，但又能深刻一点！谢谢了！！！

海明码其实也不难，相对于寄偶检验码 它不仅可以检验出错误，还能修正错误！但只能是检验、修正一位错误！说一大堆理论是没什么意思，下面将通过一个例子，尽可能的用最通俗易懂的方式进行讲解！最后大家会发现海明码很神奇！！

假设要传送的数据为：1011 0011

校验流程如下：

一：确定校验位并插入到有效数据位中。

相比奇偶校验只插入一个检验码，海明码需要插入多个检验码，插入的位数与有效数据位数相关，公式如下

公式：2^r-rk+1,其中r就是要插入检验码的个数,取满足条件的最小整数，k是有效数据位数。因为我们要传送的数据是：1011 0011，显然k=8,推出r=4。也就说我们要将4个校验位插入到有效数据中，怎么插入呢？按照如下规则：

插入位置固定为2^N（N：0，1,2,3,4，5……）处，因为r=4，即只需要取4个有{2^0,2^1,2^2,2^3},对应位置即是1,2,4,8，当然了，如果r=5,那么插入位置为：1,2,4,8，16.同类可以推出其他情况，不再啰嗦。（之所以选择这样的位置插入，是为了有效的分组，保证后面的校验分组能有效的错开，不会互相干扰，这句话不需要理解，到后面就能体会！）

通过分析得到待传送的数据为：xx1x 011x 0011,4位校验位+8为有效数据位。

二、确定校验位的数值。

显然X只能取0,1，下面确定x的值：

由一可知待传送数据为：xx1x 011x 0011。

规则：以X的位置为长度，依次从待传送数据中取X个数，然后跳过X个数，再取X个数，直到待传送数据串尾,得到一个子串，然后统计子串中1的个数，如果为奇数，则x=0,为偶数，x=1(当然，反过来也行，其实这就是奇偶校验的规则，想了解奇偶校验可以参见我以前的回答的，这里不了解也行)

第1个X：位置为1，从第1个位置开始依次取1个数据，并跳过1个数据再取，直到串尾得到一个子串：

{x 1 0 1 0 1}，这个串可记为第1个校验组, 因为1的个数是3个为奇数，故x=0.

第2个X：位置为2，故从第2个位置开始依次取2个数据，并跳过2个数据再取，直到串尾得到一个子串：

{x1 ?11 ?01} ，记为第2个校验组,因为1的个数为4是偶数，故x=1.

第3个X：位置是4，故从第4个位置开始依次取4个数据，并跳过4个数据再取，直到串尾得到一个子串：

{x011 ? ? 1}，记为第3个校验组，因为1的个数为3是奇数，故x=0.

第4个X：位置是8，故从第8个位置开始依次取8个数据，并跳过8个数据再取，直到串尾得到一个子串：

{x0011 }，记为第4个校验组，……，X=1。

故得到最终的待传送的数据串为：0110?0111?0011。

这里其实就可以看到了，为什么X的位置要取2^N,这样才能保证各个校验位不会相互干扰。

经过以上一、二步骤就完整了海明码的构造过程，下面讲解校验过程：

三、根据步骤二中的构造规则，取出各校验组

发送的数据串为：0110?0111?0011。

假设接受到的数据串为：0110?0111?1011（注意和传送数据串相比，第9为出现了错误！）

规则：以X的位置为长度，依次从待传送数据中取X个数，然后跳过X个数，再取X个数，直到待传送数据串尾,得到一个子串，然后统计子串中1的个数，如果为奇数，则x=0,为偶数，x=1(规则必须和步骤二中一样)

根据二中制定的规则再次取出各个校验组。

第1个校验组：从第1个位置开始依次取1个数据，并跳过1个数据再取，直到串尾得到一个子串：{0 1 0 1 1 1}。

第2个校验组：从第2个位置开始依次取2个数据，并跳过2个数据再取，直到串尾得到一个子串：{11 ?11 ?01}

第3个校验组：从第4个位置开始依次取4个数据，并跳过4个数据再取，直到串尾得到一个子串：{0011 ? ?1}

第4个校验组：从第8个位置开始依次取8个数据，并跳过8个数据再取，直到串尾得到一个子串：{11011}.

四、根据步骤二的构造规则，确定存在错误的校验组，并通过错误校验组的交集，最终确定出错的位置。

由步骤三得到4个校验组：

1：{0 1 0 1 1 1}。 ?对应位置为{1 3 5 7 9 11}

2：{11 ?11 ?01}。?对应位置为{2 3 6 7 10 11}

3：{0011 ? ?1} ?。对应位置为{4567 ? ?12}

4：{11011}。 ??对应位置为{8 9 10 11 12}

因为我们的构造规则是：统计子串中1的个数，如果为奇数，则x=0,为偶数，x=1。

所以正确的校验组中1的个数绝对是奇数！（好好琢磨，很容易就想通了，如果我们的规则是为奇数，则x=1,为偶数，x=0。那么正确的校验组中1的个数绝对是偶数），所以如果校验组1的个数不是奇数，那么这个校验组就存在问题。因而可以判断第1个和第4个校验组出现问题了。

确定了第1个和第4个校验组出现问题后，找到这两个校验组的交集即第9个位置和第11个位置是它们交集，即共同校验的位置。于是判断出现问题的位置要么就是第9个位置，要么就是第11个位置！因为在第2个校验组中有第11个位置，故第11个位置绝对没有出错，因为就可以判断是第9个位置出现错误！

到这里，应该懂了吧？但是不是觉得找出错位置有点麻烦啊？下面就给出一个具体的实现方法，理解了上面的描述，再了解下面实现的方法，立马就能确定出错误的位置：

首先：我们对各个校验组求异或。

第一个校验组：{0 1 0 1 1 1} 异或的结果为：0

第二个校验组：{11 ?11 ?01}异或的结果为：1

第三个校验组：{0011 ? ?1}?异或的结果为：1

第四个校验组：{11011}异或的结果为：0

接着：倒置拼接异或结果，得到：0110，

最后：按位取反的到：1001,。

大家有没有惊奇的发现1001的十进制数就是9，这不就是出错的位置吗？这是巧合吗？

不急再看一个例子：

传送的数据串为： ?0110?0111?0011（还是我们开始的那个串）

接受到的数据串为：0110?1111?0011（和正确数据串相比，第5个位置出错了）

第一个校验组：{0 1 1 1 0 1} 异或的结果为：0

第二个校验组：{11 ?11 ?01}异或的结果为：1

第三个校验组：{0111 ? ?1}?异或的结果为：0

第四个校验组：{10011}异或的结果为：1

倒置拼接：1010 ?反转为：0101 ?对应十进制数为5！

也就是说方法是真确的！！不用怀疑！！这也就是海明码的奇妙之处！

再来看看一个例子：

传送的数据串为： ?0110?0111?0011（还是我们开始的那个串）

接受到的数据串为：0110?0110?0011（和正确数据串相比，第8个位置校验位出错了）

显然这是校验位出错了，那么能不能校验出来呢？

第一个校验组：{0 1 0 1 0 1} 异或的结果为：1

第二个校验组：{11 ?11 ?01}异或的结果为：1

第三个校验组：{0011 ? ?1}?异或的结果为：1

第四个校验组：{00011}异或的结果为：0

倒置反转结果为1000 正好是8，所以也没问题。

下面我们来说下规则：（其实就是说异或与奇偶的关系，想拓展的就可以看看）

上面的例子中，我们规定： 统计子串中1的个数，如果为奇数，则x=0,为偶数，x=1。如果是按这样的规定，那么校验组中1的个数必定是奇数，正是因为如此，所以校验组中如果1的个数不是奇数那么肯定出现了错误！而如果一个串中1的个数是奇数，那么串异或的结果一定为1，其实这个规则对应的就是奇校验！反之，如果为奇数，则x=1,为偶数，x=0，那么对应的就是偶校验！

故得到以下结论：

如果采用奇检验构造海明码，那么出错校验组中的1的个数必为偶数，即异或的结果必定为0！

如果采用奇检验构造海明码，那么出错的位置是校验组异或结果倒置拼接并反转的十进制数

如果采用偶检验构造海明码，那么出错校验组中的1的个数必为奇数，即异或的结果必定为1！

如果采用偶检验构造海明码，那么出错位置是校验组异或结果直接倒置拼接的十进制数！

关于偶检验构造海明码这里就不再详细展开，如果你能用偶检验的方法在把上面的例子都做一遍，那么海明码你就已经完全弄懂了！试试吧！

关于奇偶检验码 建议还是看看，因为海明码是基于奇偶校验的改进！而且奇偶校验更简单！

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

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

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码的编码与校验纠错

欲传送的二进制代码为1010，用奇校验来确定其对应的汉明码

用奇校验来确定其对应的汉明码为10100011101。

欲传送的二进制代码为1001101，有效信息位数为n=7位，则汉明校验的校验位为k位，则：2^k =n+k+1，k=4，进行奇校验设校验位为C1C2C3C4，汉明码为C1C2B7C3B6B5B4C4B3B2B1，

C1=1_B7_B6_B4_B3_B1=1_1_0_1_1_1=1

C2=1_B7_B5_B4_B2_B1=1_1_0_1_0_1=0

C3=1_B6_B5_B4=1_0_0_1=0

C4=1_B3_B2_B1=1_1_0_1=1

故传送的汉明码为10100011101。

扩展资料

奇偶校验位是最简单的错误检测码。

奇偶校验位有两种类型：偶校验位与奇校验位。如果一组给定数据位中1的个数是奇数，那么偶校验位就置为1，从而使得总的1的个数是偶数；如果给定一组数据位中1的个数是偶数，那么奇校验位就置为1，使得总的1的个数是奇数。

如果是采用奇校验，在传送每一个字节的时候另外附加一位作为校验位，校验位在数据位后面，当实际数据中“1”的个数为偶数的时候，这个校验位就是“1”，否则这个校验位就是“0”，这样就可以保证传送数据满足奇校验的要求。

在接收方收到数据时，将按照奇校验的要求检测数据中“1”的个数，如果是奇数，表示传送正确，否则表示传送错误。

校验码可以用来实现可靠传输吗

校验码主要是为了解决计算机各部件进行数据传输和交换，确保传送过程的正确无误，一是为了提高硬件电路的可靠性，二是提高代码的校验能力。通常会用校验码来检查传送的数据是否正确。

校验码编码分为两类：合法编码、错误编码。合理的设计错误编码和编码规则，可以在数据传输的时候发现某种错误是就会变成错误编码，从而达到检验错误的目的。

码距：指的是一个编码系统中任意两个合法编码之间至少有多少个二进制位不同。

常用的三种校验码：奇偶校验码、海明码、循环冗余校验码。

2、校验码分类

3.1 奇偶校验码（Parity Code）

奇偶校验码特点如下：

无论数据位多少位，校验位只有一位

数据位和校验位一共所含的1个数为奇数，称为奇校验

数据位和校验位一共所含的1个数为偶数，称为偶校验

原理：在数据传输前，我们会求一次校验位，传输后，会求一次校验位，那么，在奇偶校验中，我们通过比较这两个校验位是否相同，一般是采用异或的方式，若结果为1，则说明有奇数个错误，结果为0，则说明正确或者偶数个错误。

常见的奇偶校验码 ：水平奇偶校验码、垂直奇偶校验码、水平垂直奇偶校验码。

3.2 海明码（Hamming Code）

设数据位是n位，校验位是k位，则n和k满足以下关系：

2^k-1=n+k

k 常取满足该关系的最小值。

选择题公式，可以记住

3个原则

海明码只能检测出2位错，纠1位错

海明码默认进行偶校验(除非特殊说明使用奇校验)。

海明码是一串由0和1组成的序列(除01外没有其他的值)

3.3 循环冗余校验码 CRC

循环冗余校验码广泛应用于数据通信领域和磁介质的存储系统中，它利用生成多项式为k个数据位产生r个校验位来进行编码，其编码长度为k+r。CRC的代码格式如下：

循环冗余校验码有两部分组成：数据为、校验位。若数据位占k位，则校验位占n-k位。n为CRC码的字长。检验码越长校验能力就会越强。在CRC编码是，采用的是模2运算，模2运算加减运算的规则是按位运算，不发生借位和进位。