hammin(汉明)码编码规则.doc

计算机 汉明码 编码规则 若编成的海明码为Hm，Hm-1H2H1，则海明码的编码规律为：(1)校验位分布：在m位的海明码中，各校验位Pi分布在位号为2(i-1)的位置，即校验位的位置分别为1，2，4，8，其余为数据位；数据位按 原来的顺序关系排列。如有效信息码为D5D4D3D2D1，则编成的海明码为D5P4D4D3D2P3D1P2P1。(2)校验关系：校验关系指海明码的每一位Hi要有多个校验位校验，其关系是被校验位的位号为校验位的位号之和。如D1(位号为3)要由P2(位号为2) 与P1(位号为1)两个校验位校验，D2(位号为5)要由P3(位号为4)与P1两个校验位校验，D3(位号为6)要由P2与P3两个校验位校 验，D4(位号为7)要由P1，P2，P3三个校验位校验，。这样安排的目的是希望校验的结果能正确反映出出错位的位号。(3)在增大合法码的码距时，使所有码的码距尽量均匀增大，以保证对所有码的校验能力平衡提高。汉明距离在一个码组集合中，任意两个码字之间对应位上码元取值不同的位的数目定义为这两个码字之间的汉明距离。即d(x,y)=xiyi，这里i=0,1,.n-1，x,y都是n位的编码，表示异或例如，(00)与(01)的距离是1，(110)和(101)的距离是2。在一个码组集合中，任意两个编码之间汉明距离的最小值称为这个码组的最小汉明距离。最小汉明距离越大，码组越具有抗干扰能力。下面我们用d表示码组的最小汉明距离。1。当码组用于检测错误时，设可检测e个位的错误，则d = e + 1设 有两个距离为d的码字A和B，如果A出现了e个错误，则A变成了以A为圆心，e位半径的球体表面的码字。为了能够准确地分辨出这些码字既不是A也不是B， 那么A误码后变成的球面上的点与B至少应该有一位距离（如果B在球面上或在球面内部则无法分辨出到底B是不是A的错误码），即A与B之间的最小距离d = e+1。2。若码组用于纠错，设可纠错t个位的错误，则d = 2t+1设 有码字A和B，如果A出现了t个错误，B也出现了t各错误，则A码变成以A为圆心，t为半径的球面上的码字；B码变成以B为圆心，t为半径的球面上的码 字。为了在出现t个错之后仍能分辨一个码字到底是属于A的错码还是属于B的错码，A,B为球心的两个球面应该不相交，即球心A，B之间距离应该大于2t， 所以d = 2t+1。3。如果码组用于纠正t个错，检测e个错，则d = e+t+1, 这里et这 种检错纠错方式结合的情况同上述两个情况类似。当码字出现t个或者小于t个错时，系统按照纠错方式工作。当码字出现超过t个错而小于等于e个错时，系统按 照检错方式工作；当A出现e个错，B出现t个错时，既要纠正B的错，又要发现A的错，则以A为球心，e为半径的球和以B为球心，t为半径的球应该不相交， 所以A,B之间的距离应该大于等于e+t+1，即d=e+t+1。汉明码汉明码是一种线性分组码。线性分组码是指将信息序列划分为长度为k的序列段，在每一段后面附加r位的监督码，且监督码和信息码之间构成线性关系，即它们之间可由线性方程组来联系。这样构成的抗干扰码称为线性分组码。设码长为n，信息位长度为k，监督位长度为r=n-k。如果需要纠正一位出错，因为长度为n的序列上每一位都可能出错，一共有n种情况，另外还有不出错的情况，所以我们必须用长度为r的监督码表示出n+1种情况。而长度为r的监督码一共可以表示2r种情况。因此2r = n + 1， 即r = log(n+1)我们以一个例子来说明汉明码。假设k=4，需要纠正一位错误，则 2r = n + 1 = k + r + 1 = 4 + r + 1解得 r = 3。我们取r=3，则码长为3+4=7。用a6,a5,.a0表示这7个码元。用S1,S2,S3表示三个监关系式中的校正子。我们作如下规定（这个规定是任意的）：S1 S2 S3 错码的位置0 0 1 a00 1 0 a11 0 0 a20 1 1 a31 0 1 a41 1 0 a51 1 1 a60 0 0 无错按照表中的规定可知，仅当一个错码位置在a2,a4,a5或a6时校正子S1为1，否则S1为0。这就意味着a2,a4,a5,a6四个码元构成偶校验关系：S1 = a6a5a4a2 (1)式同理，可以得到：S2 = a6a5a3a1 (2)式S1 = a6a4a3a0 (3)式在发送信号时，信息位a6,a5,a4,a3的值取决于输入信号，是随机的。监督为a2,a1,a0应该根据信息位的取值按照监督关系决定，即监督位的取值应该使上述(1)(2)(3)式中的S1,S2,S3为0，这表示初始情况下没有错码。即a6a5a4a2 = 0a6a5a3a1 = 0a6a4a3a0 = 0由上式进行移项运算，得到：a2 = a6a5a4a1 = a6a5a3a0 = a6a4a3已知信息位后，根据上式即可计算出a2,a1,a0三个监督位的值。接收端受到每个码组后，先按照(1)(3)式计算出S1,S2,S3，然后查表可知错码情况。例如，若接收到的码字为0000011，按照(1)(3)计算得到：S1 = 0, S2 = 1, S3 = 1查表可得在a3位有一个错码。这种编码方法的最小汉明距离为d=3，所以这种编码可以纠正一个错码或者检测两个错码。Reed-Muller码是差错控制编码技术的一种。 编辑本段差错控制编码理论的起源和发展1948年，Bell实验室的C.E.Shannon发表的通信的数学理论，是关于现代信息理论的奠基性论文，它的发表标志着信息与编码理论这一学科的创立。Shannon在该文中指出，任何一个通信信道都有确定的信道容量C，如果通信系统所要求的传输速率R小于C，则存在一种编码方法，当码长n充分大并应用最大似然译码（MLD，MaximumLikelihoodDecdoding）时，信息的错误概率可以达到任意小。从Shannon信道编码定理可知，随着分组码的码长n或卷积码的约束长度N的增加，系统可以取得更好的性能（即更大的保护能力或编码增益），而译码的最优算法是MLD，MLD算法的复杂性随n或N的增加呈指数增加，因此当n或N较大时，MLD在物理上是不可实现的。因此，构造物理可实现编码方案及寻找有效译码算法一直是信道编码理论与技术研究的中心任务。 Shannon指出了可以通过差错控制码在信息传输速率不大于信道容量的前提下实现可靠通信，但却没有给出具体实现差错控制编码的方法。20世纪40年代，R.Hamming和M.Golay提出了第一个实用的差错控制编码方案，使编码理论这个应用数学分支的发展得到了极大的推动。通常认为是R.Hamming提出了第一个差错控制码。当时他作为一个数学家受雇于贝尔实验室，主要从事弹性理论的研究。他发现计算机经常在计算过程中出现错误，而一旦有错误发生，程序就会停止运行。这个问题促使他编制了使计算机具有检测错误能力的程序，通过对输入数据编码，使计算机能够纠正这些错误并继续运行。Hamming所采用的方法就是将输入数据每4个比特分为一组，然后通过计算这些信息比特的线性组合来得到3个校验比特，然后将得到的7个比特送入计算机。计算机按照一定的原则读取这些码字，通过采用一定的算法，不仅能够检测到是否有错误发生，同时还可以找到发生单个比特错误的比特的位置，该码可以纠正7个比特中所发生的单个比特错误。这个编码方法就是分组码的基本思想，Hamming提出的编码方案后来被命名为汉明码。 虽然汉明码的思想是比较先进的，但是它也存在许多难以接受的缺点。首先，汉明码的编码效率比较低，它每4个比特编码就需要3个比特的冗余校验比特。另外，在一个码组中只能纠正单个的比特错误。M.Golay研究了汉明码的这些缺点，并提出了两个以他自己的名字命名的高性能码字：一个是二元Golay码，在这个码字中Golay将信息比特每12个分为一组，编码生成11个冗余校验比特。相应的译码算法可以纠正3个错误。另外一个是三元Golay码，它的操作对象是三元而非二元数字。三元Golay码将每6个三元符号分为一组，编码生成5个冗余校验三元符号。这样由11个三元符号组成的三元Golay码码字可以纠正2个错误。 汉明码和Golay码的基本原理相同。它们都是将q元符号按每k个分为一组然后通过编码得到n-k个q元符号作为冗余校验符号，最后由校验符号和信息符号组成有n个q元符号的码字符号。得到的码字可以纠正t个错误，编码码率为为k/n。这种类型的码字称为分组码，一般记为(q,n,k,t)码，二元分组码可以简记为(n,k,t)码或者(n,k)码。汉明码和Golay码都是线性的，任何两个码字经过模q的加操作之后，得到的码字仍旧是码集合中的一个码字。 在Golay码提出之后最主要的一类分组码就是Reed-Muller码。它是Muller在1954年提出的，此后Reed在Muller提出的分组码的基础上得到了一种新的分组码，称为Reed-Muller码，简记为RM码。在1969年到1977年之间，RM码在火星探测方面得到了极为广泛的应用。即使在今天，RM码也具有很大的研究价值，其快速的译码算法非常适合于光纤通信系统。汉明码用于数据传送，能检测所有一位和双位差错并纠正所有一位差错的二进制代码。当计算机存储或移动数据时，可能会产生数据位错误，这时可以利用汉明码来检测并纠错，简单的说，汉明码是一个错误校验码码集，由Bell实验室的R.W.Hamming发明，因此定名为汉明码。校验与其他的错误校验码类似，汉明码也利用了奇偶校验位的概念，通过在数据位后面增加一些比特，可以验证数据的有效性。利用一个以上的校验位，汉明码不仅可以验证数据是否有效，还能在数据出错的情况下指明错误位置。 编辑本段纠错在接受端通过纠错译码自动纠正传输中的差错来实现码纠错功能，称为前向纠错FEC。在数据链路中存在大量噪音时，FEC可以增加数据吞吐量。通过在传输码列中加入冗余位(也称纠错位)可以实现前向纠错。但这种方法比简单重传协议的成本要高。汉明码利用奇偶块机制降低了前向纠错的成本。 编辑本段校验方法进行奇偶校验的方法是先计算数据中1的个数，通过增加一个0或1(称为校验位)，使1的个数变为奇数(奇校验)或偶数(偶校验)。例如，数据1001总共是4个比特位，包括2个1，1的数目是偶数，因此，如果是偶校验，那么增加的校验位就是一个0，反之，增加一个1作为校验位。通过“异或”运算来实现偶校验，“同或”运算来实现奇校验。单个比特位的错误可以通过计算1的数目是否正确来检测出来，如果1的数目错误，说明有一个比特位出错，这表示数据在传输过程中受到噪音影响而出错。利用更多的校验位，汉明码可以检测两位码错，每一位的检错都通过数据中不同的位组合来计算出来。校验位的数目与传输数据的总位数有关，可以通过汉明规则进行计算： d+p+1=2的p次方 d表示传输数据位数目，p表示校验位数目。两部分合称汉明码字，通过将数据位与一个生成矩阵相乘，可以生成汉明码字。 2008-07-05 19:10 针对4位数据的汉明码编码示意图 汉明码是一个在原有数据中插入若干校验码来进行错误检查和纠正的编码技术。以典型的4位数据编码为例，汉明码将加入3个校验码，从而使实际传输的数据位达到7个（位），它们的位置如果把上图中的位置横过来就是： 数据位 1234567 代码 P1 P2 D8 P3 D4D2 D1 说明 第1个汉明码 第2个汉明码 第1个数据码 第3个汉明码 第2个数据码 第3个数据码 第4个数据码 注：Dx中的x是2的整数幂（下面的幂都是指整数幂）结果，多少幂取决于码位，D1是0次幂，D8是3次幂，想想二进制编码就知道了。另外，汉明码加插的位置也是有规律的。以四位数据为例，第一个汉明码是第一位，第二个是第二位，第三个是第四位，1、2、4都是2的整数幂结果，而这个幂次数是从0开始的整数。这样我们可以推断出来，汉明码的插入位置为1（20 (注：20表示2的0次幂)）、2（21）、4（22）、8（23）、16（24）、32（25） 编辑本段汉明码的编码原理现以数据码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 D8、D2、D1 P3 D4、D2、D1 从编码形式上，我们可以发现汉明码是一个校验很严谨的编码方式。在这个例子中，通过对4个数据位的3个位的3次组合检测来达到具体码位的校验与修正目的（不过只允许一个位出错，两个出错就无法检查出来了，这从下面的纠错例子中就能体现出来）。在校验时则把每个汉明码与各自对应的数据位值相加，如果结果为偶数（纠错代码为0）就是正确，如果为奇数（纠错代码为1）则说明当前汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算来确定具体是哪个位出了问题。 还是刚才的1101的例子，正确的编码应该是1010101，如果第三个数据位在传输途中因干扰而变成了1，就成了