实验四 纠错码编译码

《实验四 纠错码编译码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四纠错码编译码一、实验原理编译码原理和方法：（一）汉明码编译码编码汉明码的编码就是如何根据信息位数k，求出纠正一个错误的监督矩阵H，然后根据H求出信息位所对应的码字。构造汉明码监督矩阵H的方法很多，这里仅介绍一种。1)根据已知的信息位数k，从汉明不等式中求出校验位数m=n-k；2)在每个码字C：(C1，C2，⋯，Cn)中，用Cn，Cn-1，Cn-2作为监督位，剩下的位作为信息位；3)用二进制数字表示2m-1列，得到2m-1列和m行监督矩阵H；4)用3步的H形成HCT=0，从而得出m个监督方程；5)将已知的信息代入方程组，然后求出满足上述方程组的监督位c(i=0，1，⋯，m一1)。

2、例如，用以上方法，很容易求出[7，4，3]汉明码的监督矩阵：由H得到G1000111G=IkQ=010011000101010001011译码当收到一个接收码字R后，可用监督矩阵H来检验R是否满足监督方程，即HRT＝0T是否成立。若关系式成立，则认为R是一个码字，否则判为码字在传输中发生了错误。因此，HRT的值是否为0是检验码字出错与否的依据。把S＝RHT或ST＝HRT，称为接收码字R的伴随式(或监督子，或校验子)。设发送码字C＝(cn－1，cn－2，…，c0)，信道的错误图样为E＝(en－1，en－2，…，e0)式中：若ei＝0，表示第i位无错，若ei＝1，则表示第i位有错，i＝n

3、－1，n－2，…，0。那么，接收码字R为R＝(rn－1，rn－2，…，r0)＝C＋E=(cn－1＋en－1，cn－2+en－2，…，c0＋e0)将接收字用监督矩阵进行检验，即求接收码字的伴随式：ST＝HRT＝H(C＋E)T＝HCT＋HET由于HCT＝0T，所以：ST＝HET将H＝(h1，h2，…，hn)（hi表示H的列，i＝1，2，…，n）代入式(5―35)得：ST＝h1en－1＋h2en－2＋…+hne0 由上面分析得到如下结论：(1)伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定。(2)伴随式是错误的判别式：若S＝0，则判没有出错，接收

4、字是一个码字，若S≠0，则判有错。7(3)不同的错误图样具有不同的伴随式，它们是一一对应的，二元码伴随式是H阵中与错误码元对应列之和。任意n重码字的伴随式取决于它在标准阵列中所在陪集的陪集首；标准阵列的陪集首和伴随式也是一一对应的，因而码的可纠错误图样和伴随式是一一对应的。应用此对应关系可以构成比标准阵列简单得多的译码表，从而得到(n，k)线性码的一般译码步骤：（1）计算接收码字R的伴随式ST＝HRT。（2）根据伴随式和错误图样一一对应的关系，利用伴随式译码表，由伴随式译出R的错误图样E。（3）将接收码字减错误图样，得发送码字的估值。上述译码法称为伴随式译码法或查表译码法。

5、这种查表译码法具有最小的译码延迟和最小的译码错误概率。（一）循环码编译码编码设M＝(mk－1，mk－2，…，m0)为任一信息组，G(x)为该(n，k)循环码的生成矩阵，则相应的码多项式为任意(n，k)循环码的生成多项式g(x)一定整除1＋xn。反过来若g(x)是一个n—k次多项式并且还整除(1＋xn)，那么g(x)一定是某个循环码的生成多项式。设信息组为M＝(mk－1，mk－2，…，m0)，则相应的码多项式为C(x)＝MG(x)＝(mk－1xk－1＋mk－2xk－2＋…＋m0)g(x)式中C(x)的次数≤n-1，M(x)是2k个信息多项式的表示式，所以C(x)即为相应2k个

6、码多项式的表示式。因此g(x)生成一个(n，k)线性码。又因为C(x)是n-k次多项式g(x)的倍式，所以g(x)生成一个(n，k)循环码。循环码的主要优点之一是其编码过程很容易用移位寄存器来实现。由于生成多项式g(x)和监督多项式h(x)都可以惟一地确定循环码，因此编码方法既可基于g(x)又可基于h(x)。下面仅给出一种基于生成多项式的具体编码方案。一个系统码形式的(n，k)循环码的编码步骤如下：　　(1)用xn－k乘以信息多项式M(x)；　　(2)用g(x)除以xn-kM(x)得到余式b(x)；　　(3)作码字b(x)＋xn-kM(x)多项式。以上三步均可用一个除法电路完

7、成。该电路是一个带反馈的根据生成多项式g(x)＝1＋g1x+…＋gn－k－1xn－k－1+xn－k作出的(n-k)级线性移位寄存器,如图5―5所示。图2―1n–k移位寄存器编码电路7译码线性码的译码根据接收码字多项式的伴随式和可纠的错误图样间的一一对应关系，由伴随式得到错误图样。因为循环码是线性码的一个特殊子类，且由于循环码的循环特性，致使它的译码更加简单易行。循环码的译码包括三个步骤：计算接收多项式的伴随式，求伴随式对应的错误图样，用错误图样纠错。1.