汉明码编码原理介绍

1、汉明码编码原理介绍汉明码是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用于内存（RAM）。其SECDED版本另外加入一检测比特，可以侦测两个或以下同时发生的比特错误，并能够更正单一比特的错误。 1940年，汉明于贝尔实验室工作，运用贝尔模型电脑，输入端依靠打孔卡，这不免有些读取错误。在平日，特殊代码将发现错误并闪灯，使得操作者能够纠正这个错误。在周末和下班期间，在没有操作者的情况下，机器只会简单地转移到下一个工作，汉明在周末工作，他对于不可靠的读卡机发生错误后，

2、总是必须重新开始方案变得愈来愈沮丧。在接下来的几年中，他为了解决调试的问题，开发了功能日益强大的调试算法。在1950年，他发表了今日所称的汉明码。现在汉明码有着广泛的应用。 人们在汉明码出现之前使用过多种检查错误的编码方式，但是没有一个可以在和汉明码在相同空间消耗的情况下，得到相等的效果。 汉明码原理介绍：奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式。如果在传输的过程中，有奇数个位发生了改变，那么这个错误将被检测出来（注意奇偶位本身也可能改变）。一般来说，如果数据中包含有奇数个1的话，则将奇偶位设定为1；反之，如果数据中有偶数个1的话，则将奇偶位设定为0。换

3、句话说，原始数据和奇偶位组成的新数据中，将总共包含偶数个1. 奇偶校验并不总是有效，如果数据中有偶数个位发生变化，则奇偶位仍将是正确的，因此不能检测出错误。而且，即使奇偶校验检测出了错误，它也不能指出哪一位出现了错误，从而难以进行更正。数据必须整体丢弃并且重新传输。在一个噪音较大的媒介中，成功传输数据可能需要很长时间甚至不可能完成。虽然奇偶校验的效果不佳，但是由于他只需要一位额外的空间开销，因此这是开销最小的检测方式。并且，如果知道了发生错误的位，奇偶校验还可以恢复数据。如果一条信息中包含更多用于纠错的位，且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果，那么我们就可以找出出错位了。

4、在一个7位的信息中，单个数据位出错有7种可能，因此3个错误控制位就足以确定是否出错及哪一位出错了。 汉明编码方案通用算法下列通用算法可以为任意位数字产生一个可以纠错一位的汉明码。 一、1开始给数字的数据位（从左向右）标上序号, 1，2，3，4，5. 二、将这些数据位的位置序号转换为二进制，1, 10, 11, 100, 101,等。 三、数据位的位置序号中所有为二的幂次方的位（编号1，2，4，8，等，即数据位位置序号的二进制表示中只有一个1）是校验位 四、有其它位置的数据位（数据位位置序号的二进制表示中至少2个是1）是数据位 五、每一位的数据包含在特定的两个或两个以上的校验位中，这些校验位取决

5、于这些数据位的位置数值的二进制表示 1.校验位1覆盖了所有数据位位置序号的二进制表示倒数第一位是1的数据：1（校验位自身，这里都是二进制，下同），11，101，111，1001，等 2.校验位2覆盖了所有数据位位置序号的二进制表示倒数第二位是1的数据：10（校验位自身），11，110，111，1010，1011，等 3.校验位4覆盖了所有数据位位置序号的二进制表示倒数第三位是1的数据：100（校验位自身），101，110，111，1100，1101，1110，1111，等 4.校验位8覆盖了所有数据位位置序号的二进制表示倒数第四位是1的数据：1000（校验位自身），1001，1010，1011

6、，1100，1101，1110，1111，等 5.简而言之，所有校验位覆盖了数据位置和该校验位位置的二进制与的值不为0的数。 采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些，但在实践中并没有区别。从编码形式上，我们可以发现汉明码是一个校验很严谨的编码方式。在这个例子中，通过对4个数据位的3个位的3次组合检测来达到具体码位的校验与修正目的(不过只允许一个位出错，两个出错就无法检查出来了，这从下面的纠错例子中就能体现出来)。在校验时则把每个汉明码与各自对应的数据位值相加，如果结果为偶数(纠错代码为0)就是正确，如果为奇数(纠错代码为1)则说明当前汉明码所对应的三个数据位中有错误，此

7、时再通过其他两个汉明码各自的运算来确定具体是哪个位出了问题。·1234567891011121314151617181920编码后数据位置p1p2d1p4d2d3d4p8d5d6d7d8d9d10d11p16d12d13d14d15奇偶校验位覆盖率p1XXXXXXXXXXp2XXXXXXXXXXp4XXXXXXXXXp8XXXXXXXXp16XXXXX观察上表可发现一个比较直观的规律：第i个检验位是第2i-1位，从该位开始，检验2i-1位，跳过2i-1位依次类推。例如上表中第3个检验位p4从第23-1=4位开始，检验4、5、6、7共4位，然后跳过8、9、10、11共4位，再检验12、

8、13、14、15共4位在数学方面，汉明码是一种二元线性码。对于每一个整数m>2，存在一个编码，带有m个奇偶校验位2m- m-1个数据位。例子对11000010进行汉明编码，求编码后的码字。1.列出表格，从左往右（或从右往左）填入数字，但2的次方的位置不填。位置1234567891011121314数据110000102.把数据行有1的列的位置写为二进制。位置1234567891011121314数据11000010二进制0011010110113.收集所有二进制数字，求异或。4.把1101依次填入表格中2的次方的位置（低位在左）。位置1234567891011121314数据110000

9、10二进制001101011011校验10115.所以编码后的码字是101110010010。以数据码1101为例再次码的编码原理，此时D8=1、D4=1、D2=0、D1=1，在P1编码时，先将D8、D4、D1的二进制码相加，结果为奇数3，汉明码对奇数结果编码为1，偶数结果为0，因此P1值为1，D8+D2+D1=2，为偶数，那么P2值为0，D4+D2+D1=2，为偶数，P3值为0。这样，参照上文的位置表，汉明码处理的结果就是1010101。在这个4位数据码的例子中，我们可以发现每个汉明码都是以三个数据码为基准进行编码的。下面就是它们的对应表: 编码用的数据码 P1 （D8、D4、D1） P2

10、（D8、D2、D1） P3 （D4、D2、D1）从编码形式上，我们可以发现汉明码是一个校验很严谨的编码方式。在这个例子中，通过对4个数据位的3个位的3次组合检测来达到具体码位的校验与修正目的(不过只允许一个位出错，两个出错就无法检查出来了，这从下面的纠错例子中就能体现出来)。在校验时则把每个汉明码与各自对应的数据位值相加，如果结果为偶数(纠错代码为0)就是正确，如果为奇数(纠错代码为1)则说明当前汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算来确定具体是哪个位出了问题。1950年，汉明介绍了(7,4)代码。其编码由4数据比特到7位，增加三个奇偶校验码。汉明(7,4)可以检

11、测并纠正单比特错误，且也能检测双比特错误。带附加奇偶校验码的汉明码（SECDED），汉明(8,4)码：汉明(7,4)码可以很容易地编码为一个(8,4)码汉明距离：在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如： 1011101与1001001之间的汉明距离是2。 2143896与2233796之间的汉明距离是3。 "toned"与"roses"之间的汉明距离是3。 汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个

12、数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。Hamming码编译码器的设计Hamming码编译码器的设计首先构造最佳奇权码的校验矩阵即H矩阵，最佳奇权码的H矩阵应满足：(1)每列含有奇数个1，且无相同列；(2)总的1的个数少，所以校验位、伴随式生成表达式中的半加项数少，从而生成逻辑所需的半加器少，可以节约器材、降低成本和提高可靠性。(3)每行中1的个数尽量相等或接近某个平均值，这种决定了生成逻辑及其级数的一致性，不仅译码速度快，同时线路匀称。译码时把数据再次编码所得到的新校验位与原校验位模二加，便得到伴随式S，由其可判别错误类型。（1)若S0，则认为没有错误；(2)若

13、S0，且S含有奇数个1，则认为产生了单位错；(3)若S0，且S含有偶数个1，则认为产生了两位错；其中的情况(2)中，根据错误图样可以确定错误位置，将其取反即可完成纠错因为对用户而言真正有用的是数据，校验位是无用的。为了节省时间和器材，只对数据纠错，而对校验位不进行纠错，纠错后的数据也不再写回存储器。void CHammingDlg:OnButtonEncode() UpdateData(true);int i;char str="00000000000"for (i=0;i<7;i+)if(m_inputi='0')input6-i=0;elseinp

14、ut6-i=1;encodeout2=input0;encodeout4=input1;encodeout5=input2;encodeout6=input3;encodeout8=input4;encodeout9=input5;encodeout10=input6;encodeout0=input0input1input3input4input6;encodeout1=input0input2input3input5input6;encodeout3=input1input2input3;encodeout7=input4input5input6;for (i=0;i<11;i+)i

15、f(encodeouti=0)str10-i='0'elsestr10-i='1'm_encodeout=str;UpdateData(false); void CHammingDlg:OnButtonNoise() srand(unsigned)time(NULL); m_noisebit=rand()%11;encodeoutm_noisebit-1=encodeoutm_noisebit-11;UpdateData(false);void CHammingDlg:OnButtonDecode() int output7;int N,check4;char

16、str="0000000"N=0;int i;output0=encodeout2;output1=encodeout4;output2=encodeout5;output3=encodeout6;output4=encodeout8;output5=encodeout9;output6=encodeout10;check0=encodeout2encodeout4encodeout6encodeout8encodeout10;check1=encodeout2encodeout5encodeout6encodeout9encodeout10;check2=encodeout4encodeout5encodeout6;check3=encodeout8encodeout9encodeout10;check0!=encodeout0?N=N+1:N=N;check1!=encodeout1?N=N+2:N=N;check2!=encodeout3?N=N+4:N=N;check3!=encodeout7?N=N+8:N=N;encodeoutN-1=encod