汉明码编译码文档.docx

《汉明码编译码文档.docx》由会员分享，可在线阅读，更多相关《汉明码编译码文档.docx（11页珍藏版）》请在优知文库上搜索。

1、第一章绪论过失控制编码1.1 概述数字信号在传输过程中，由于受到干扰的影响，码元波形将变坏。接收端收到后可能发生错误判决。由于乘性干扰引起的码间串扰，可以采用均衡的方法来纠正。而加性干扰的影响那么需要用其他方法解决。在设计数字通信系统时，应该首先从合理选择调制制度,解调方法以及发送功率等方面考虑，使加性干扰缺乏以影响到误码率要求。在仍不能满足要求时，就要考虑采用过失控制措施了。从过失控制角度看，按加性干扰引起的错码分布规律不同，信道可以分为3类，即随机信道，突发信道和混合信道。在随机信道中，错码的出现是随机的，而且错码之间是统计独立的。在突发信道中，错码是成串集中出现的，而且在短促的时间段之间

2、存在较长的无错码区间。把既存在随机错码又存在突发错码的的信道称为混合信道。对于不同类型的信道，应该采用不同的过失控制技术。1.2 纠错编码原理我们把信息码分组，为每组信息码附加假设干监督码的编码称为分组码(blockcode).在分组码中，监督码元仅监督本码组中的信息码元。分组码一般用符号(n,k)表示，其中n是码组的总位数，又称为码组的长度(码长)，k是码组中信息码元的数目，n-k=r为码组中的监督码元的数目，或者称为监督位数目，分组码的结构如图2示，图中前k位为信息位，后面附加r个监督位。其中an到a为k个信息位，a-到a为r个监督位。Qn-I3n-23r-SLo图4分组码的结构在分组码中

3、，把码组中“1”的个数称为码组的重量，简称码重。把两个码组中对应位上数字不同的位数称为码组的距离，简称为码距，码距又称为汉明距离。我们把某种编码中各个码组之间距离的最小值称为最小码距(d。)。一种编码的最小距离的大小直接关系着这种编码的检错与纠错能力：(1)为检测e个错码，要求最小码距d。大于等于e+1;(2)为了纠正t个错码,要求最小码距d。大于等于2t+l；(3)为纠正t个错码同时检测e个错码,要求最小码距d。大于等于e+t+1St).1.3汉明码编码Hamming码中文称作汉明码。汉明码是由汉明于1950年提出的，具有纠正一位错误能力的线性分组码它的突出特点是：编译码电路简单，易于硬件实

4、现；用软件实现编译码算法时，软件效率高；而且性能比拟好.1汉明码的定义：假设一致监督矩阵H的列是由不全为O且互不相同的所有二进制m（m22的正整数）重组成，那么由此H矩阵得到的线性分组码称为3汉明码。汉明码的构造特点：1） .绐定一个m,我们由二进制In重组成线性分组码的监督矩阵H,由二进制m重来标定一个发生错误的位置。由此可知，二进制m重共有2种位组合，去掉一个全为O的位组合,那么余下共有2-1种位组合。故汉明码的最大码长2-1。2） .由上面分析，我们可以知道：m即是汉明码监督位的位数。故一个汉明码中，信息位的位数k=nm=2-l-m3） .汉明码的距离为3,因此可以纠正1位错误，检出2位

5、错误。汉明码编码的主要算法汉明码的编码就是如何根据信息位数k,求出纠正一个错误的监督矩阵H,然后根据H求出信息位所对应的码字。构造汉明码监督矩阵H的方法很多，这里仅介绍一种。1）根据的信息位数k,从汉明不等式中求出校验位数m=n-k；2）在每个码字C：（C1,C2,中，用4，心，c7作为监督位，剩下的位作为信息位；3）用二进制数字表示2门列，得到2门列和m行监督矩阵H；4）用3步的H形成HC=0,从而得出In个监督方程；5）将的信息代入方程组，然后求出满足上述方程组的监督位C（i=0,1,m-l）o例如，用以上方法，很容易求出7,4,3汉明码的监督矩阵：11101001101010101100

6、1及编码所对应的码字为C=OlloOl。1.4.主要应用领域1. 4.1钢丝绳张力检测系统随着现代通信技术和计算机技术的高速开展，无线数字通信的应用越来越广泛.钢丝绳张力检测系统将数字无线通信、测量和计算机技术结合在一起，其功能是将电梯、缆车或提升机钢丝绳张力检测信息转换成数字信号，通过无线方式传送给控制中心，由控制中心对原始数据进行处理、分析和计算，输出人们想耍的结果，做出相应的判断与控制。因此,钢丝绳张力的检测系统对使用钢丝绳的提升设备的平安运行起着至关重要的作用。数字存储系统随着PC机的日益普及，存储对象的日渐多元化，用户对存储需求不断升级，如何保证数据稳定、高速传输？RAlD（,Red

7、undantArrayofIndependentDisk”）独立冗余磁盘阵列解决了这个难题，并且成为目前存储的主流技术。RAID之所以实现数据高速、可靠的传输，一个关键的核心技术就是应用了一定的过失控制编码技术。在RAlD众多系列中最复杂的RAID2中就采用了汉明码（HammingCOde）过失控制编码技术”，它在数据存储及移动过程中进行过失控制，对传输过程中出现的过失自动进行纠正，保证了数据传输的平安可靠性。保密通信技术随着计算机网络的开展及应用的普及，特别是在军事指挥，情报系统，银行系统的应用，通信的可靠性及保密性要求越来越高，这就要求研制新的高可靠性及保密性通信技术。接收端不仅能从接收到

8、的信息中检测出传输过程中的错误而且能纠正之。针对IBM-PC微计算机之间通信过程中的纠错技术提出了一种在通信计算机之间不增加任何硬件设备的情况下，仅用编写一段纠错编码（发送端）和纠错译码（接收端）的软件方法到达计算机通信纠错和保密的目的，即利用汉明码编码实现检错、纠错的具体方案，这样做的优点是：在保持一定功能和相应速度的前提下，采用软件方法，不仅可以提高通信过程的可靠性，而且还可以提高通信系统本身的可靠性。第二章（7,4）汉明码的编码原理2. 1根本构造对于码组长度为n、信息码元为k位、监督码元为r=nk位的分组码，常记作（n,k）码，如果满足2-12n,那么有可能构造出纠正一位或一位以上错误

9、的线性码。下面我们通过（7,4）汉明码的例子来说明如何具体构造这种码。设分组码（n,k）中,k=4,为能纠正一位误码,要求23。现取r=3,那么n=k+r=7我们用02出2退出56表示这7个码元，用Si、S2、S,表示由三个监督方程式计算得到的校正子，并假设三位Si、S2、S3校正子码组与误码位置的对应关系如表1所示。S1S2S3错码位置S1S2S3错码位置OOlao101alOlOa110100a2111a6Oila3OOO无错码表1校正子和错码位置关系由表可知,当误码位置在a?、a4as26时，校正子Si=I;否那么SI=Oo因此有S】=aea.1a2,同理有S2=a6a$3a1和S3=a

10、6a.3a。在编码时26、asa、a3为信息码元，a2.%、a。为监督码元。那么监督码元可由以下监督方程唯一确定a6a5Sa1a2=0-a6a5a3a=0Oa6aa3a0=0L_也即a2=a6a5Saa0a6a1a3由上面方程可得到表2所示的16个许用码组。在接收端收到每个码组后，计算出$、S2、S3,如果不全为0,那么表示存在错误，可以由表1确定错误位置并予以纠正。举个例子,假设收到码组为0000011,可算出S1S2S3=Oll,由表1可知在a3上有一误码。通过观察可以看出，上述(7,4)码的最小码距为(Ln=3,纠正一个误码或检测两个误码。如果超出纠错能力那么反而会因“乱纠”出现新的误码

11、.信息位监督位信息位监督位d6d54d33233(32&134)00000001000IllOOOlOll1001100OOlO1011010OlOOOll110IOllOOlOlOO1101100OOlOlOl101IlOlOlOOllOOllIllO100Olll000IlllIll表2(7,4)汉明码的许用码组2.2监督矩阵上面有提到过，线性码是指信息位和监督位满足一组线性代数方程的码，式()就是这样的例子，现在将它改写成1*ae1*a51*a10*a31*a?O*a1O*ao-Ol*a61*a5O*a11*a30*a2l*aO*ao-O()1*afi0*a51*a11*a30*a2O*

12、a11*ao-O()我们可以将式O表示成如下的矩阵形式11010101011001a0式O还可以简记为H*=O或*H=OO其中IIIOIO0、*、H=1101010A=aa5a4a3a2aao0=0001011001上角“T”表示将矩阵转置。例如HT是H的转置，即HT的第一行为H的第一列，第二行为第二列。我们将H称为监督矩阵（Paritycheckmatrix）.只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。由O和（1.1.5）都可以看出，H的行数就是监督关系式的数目r,H的每一行中的“1”的位置表示相应码元之间存在的监督关系。式（1.1.4）中的H矩阵可以分为两局部。IlIOC

13、oO、H=IIoloIO=Pl（）1011001式中：P汕*k阶矩阵；L必*r阶单位方阵。2.3生成矩阵由代数理论可知，H矩阵的的各行应该是线性无关的，否那么将得不到r个线性无关的监督关系式，从而也得不到r个独立的监督位。假设一矩阵可以写成PL的矩阵形式，那么其各行一定是线性无关的。因为容易验证L的各行是线性无关的，故PL的各行也是线性无关的。类似于O那样，（1.1.2）可以改写成IOll或者其中，Q为一个k*r阶矩阵，它为P的转置，即Q-Pt式O表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。我们将Q的左边加上一个k*k阶单位方阵，就构成一个矩阵G1010111、G=IQ=01

14、00110()00101010001011V.JG称为生成矩阵(generatormatrix),因为由它可产生整个码组，即有第三章(7,4)汉明码编码的设计3.1 (7,4)汉明码的编码思路(7,4)汉明码的编码就是将输入的四位信息码编成七位的汉明码，即参加三位监督位。根据式()A=a6a5ala3-G可知，信息码与生成矩阵G的乘积就是编好以后的(7,4)汉明码，而生成矩阵G又是的，由式(1.1.9)得IllA1 1 0Jr000G=010000101010001011I所以，可以得出如下方程组a6=a6at=at3333O112-3-*3s-*-313116*a$+8311o-3a+113

15、根据式()就可以编出编码程序了。3.2 (7,4)汉明码的编码程序设计根据(7,4)汉明码的编码原理，首先画出程序设计的流程图:图6编码流程图输入信息码a3a2aa0,输出(7,4)汉明码bebsbhbzbh。首先，输入信息码a3a2a,即使用以下语句：port(a:instdlogic_vector(3downto0);然后，根据式()，就可以得到监督位与信息码之间的对应关系，使用异或运算，即:b(6)=a(3);b(5)=a(2);b(4)=a(l);b(3)=a(0);b(2)=a(3)xora(2)xora(l);b(l)=a(3)xora(2)xora(0);b(0)-a(3)xora(l)xora(0);