线性码及其应用幻灯片.ppt

线性码及其应用第1页，共37页，编辑于2022年，星期一定义2 码字X=x1x2xn的汉明重量是码字中非零码元的位数，用W(X)表示。例如：W(1001)=2,W(11010)=3由定义1和定义2知 D(X,Y)=W(X-Y)定义3 一组码字C包括若干码字C1,C2,Cn,所有这些码字相互间码距的最小的数值，称为该码组的最小码距d(简称码距d)。d=minD(Ci,Cj)=minW(Ci-Cj)i,j 1,2,N,i j 例如 C=(0111100,1011011,1101001)d=3说明：为尽量避免码字受到干扰而出错，总是希望码字间有尽可能大的距离，最小码距代表了一个码组中最不利的情况。从安全出发，往往选用最小码距来分析码的检错纠错能力。第2页，共37页，编辑于2022年，星期一第二节第二节 检错能力与纠错能力检错能力与纠错能力1、码距为1时，能保证码字的唯一性，但不能检错和纠错。2、码距为2时，能检查出一位错误，但无法纠错。3、码距为3时，能检查出一位或两位错误，并且还可纠正一位错误。例：设码长为3，取000、111作为码字，其余为禁用码字。如接收端收到001，它是禁用码字，知道出错，由于001与000相差一个码元，与111相差两个码元，根据最大似然译码原则将001译为000。最大似然译码原则：当Ci为若干个发送码字中的一个，R为接收码字，若条件概率P(R/Ci)为最大，则认为码字Ci就是发送码字。第3页，共37页，编辑于2022年，星期一结论：结论：（一）、要检出码字中任意e个码元错误，必须使最小码距d满足 d e+1（二）、要纠正码字中任意t个码元错误，必须使最小码距d满足 d 2t+1（三）、要纠正码字中任意t个码元错误，并同时发现e个错误（e t），则最小码距d满足 d t+e+1当码距d=2t+1时，码长为n的一个许用码字中可纠正的错误类型总数为：i=1tC(n,i)许用码字数Q i=0tC(n,i)2n第4页，共37页，编辑于2022年，星期一第三节第三节 寄偶监督码寄偶监督码寄偶监督码是最简单的一种检错码，是目前计算机系统用得最多的一种差错控制码。寄偶监督码的编码方式：是在n-1位信息元Cn-1,Cn-2,C1后面附加1位监督元C0，使得码字中“1”的数目保持为奇数或偶数。奇数监督，对应的监督方程为：Cn-1+Cn-2+C1+C0=1偶数监督，对应的监督方程为：Cn-1+Cn-2+C1+C0=0P169表5-1列出了用七位ASCII码表示的十个数字符号的寄偶校验位。第5页，共37页，编辑于2022年，星期一判别方法：接收端收到编好的寄偶监督码后，用与发送端相同的规则检查“1”的个数是否仍保持奇数或偶数，从而确定传输过程中是否有错误。特点：能发现一位码元或所有奇数位码元出错的情况。但不能纠正任何错误以及发现偶数位码元错误。简单寄偶码的效率高：=n-1n寄偶监督码的实现：1、硬件法：采用模二相加的异或电路。C1C2C3C4C5C6C7C0C0第6页，共37页，编辑于2022年，星期一2、软件法（见P170图5-6的流程图）为了改进差错控制性能，引入二维寄偶监督码（水平-垂直寄偶监督码、方阵码、纵横寄偶监督码）。就是在水平方向进行寄偶监督的同时，再按垂直方向进行一次寄偶监督。如P171图5-7，图5-8（二维水平-斜向寄偶监督码）。二维寄偶监督码特点：能检出每一行或每一列的两位或偶数位错误。可以用水平、垂直两个方向上的监督码元，来确定单个错误码元的位置，从而进行纠正。但它无法检出四个错误码元构成矩形（或平行四边形）四个顶点的错误图样，也无法检出双向成偶的错误图样。第7页，共37页，编辑于2022年，星期一第五节第五节 监督矩阵与生成矩阵监督矩阵与生成矩阵设有待编码的消息序列为M=m1m2mk,对应的信息元序列X1X2Xk。为了进行差错控制，我们按线性代数关系来添加监督码元序列Xk+1Xk+2Xn，则称此码长n，信息元数k的码字序列X1X2Xk|Xk+1Xk+2Xn为线性分组码。记为(n,k)，如果其最小码距为d，也可记为(n,k,d)或n,k,d。其中监督元数r=n-k。用线性的监督方程组来表示：a11X1+a12X2+a1kXk=Xk+1a21X1+a22X2+a2kXk=Xk+2ar1X1+ar2X2+arkXk=Xn式中加号均表示模二加第8页，共37页，编辑于2022年，星期一或a11X1+a12X2+a1kXk+Xk+1+0+0=0a21X1+a22X2+a2kXk+0+Xk+2+0=0ar1X1+ar2X2+arkXk+0+0+Xn=0若用矩阵表示，则a11 a12 a1k 1 0 0a21 a22 a2k 0 1 0ar1 ar2 ark 0 0 1 X1 X2 Xk Xk+1 Xk=0简写为 HXT=0TH：监督矩阵XT：行矩阵X=X1X2Xn的转置矩阵第9页，共37页，编辑于2022年，星期一例5-1 一个(7,3)码的信息元X1X2X3和监督元X4X5X6X7间的监督方程组为X1+X3+X4=0X1+X2+X3+X5=0X1+X2+X6=0X2+X3+X7=0求出对应信息元的监督元。解：列出各种信息元组合，依据监督方程组求出对应监督元 如下表所示。信息元监督元编成码字0000010100111001011101110000110101111010111000111001010000000000011101010011101110101001110101001111010011110100第10页，共37页，编辑于2022年，星期一还可以写出监督矩阵形式HX =10 1 1 0 0 0 1 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1TX1X2X3X4X5X6X7=0000第11页，共37页，编辑于2022年，星期一说明说明：1、编码中，往往在多种可能的码字排列中，选取少量 的许用码字。2、任意两个码字逐位模二加，可以得到另一个码字。这种特性叫做封闭性。它是线性码的重要特点。3、由封闭性知，两个码字的码距，就是另一个码字 的码重。所以，该组码字的最小码距就等于码字 中码的最小重量。4、监督矩阵H=A|Ir，A为rxk阶矩阵，Ir为r阶单位 阵，r=n-k，H起监督是否是码字的作用。5、在线性码组中，如果有一个码重为W的码字，则 在H中必有与之相应的W列相加等于0，固称此W 列线性相关。如果要求码组的最小码距为d,即要求 码字的最小码重为d，则H中至少有d列相加之和为 0，任意小于或等于d-1列线性无关。第12页，共37页，编辑于2022年，星期一例如：例题中0011101是码字，码重为4，它应该满足监督方程组。即HXT=10 1 1 0 0 0 1 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 10011101=1101+1000+0100+0001=0000第13页，共37页，编辑于2022年，星期一下面讨论一下监督矩阵H与生成矩阵G的关系。HXT=A|IrX1X2XkXk+1Xk+2Xn=0T或AX1X2Xk+IrXk+1Xk+2Xk=0T则Xk+1Xk+2Xn=-AX1X2Xk=-Amkm1m2令X1X2Xk=Ikmkm1m2第14页，共37页，编辑于2022年，星期一X1X2Xk=Ik-Am1m2mk两边取转置得X=MGX，M为行矩阵的形式；G=Ik|-AT称为生成矩阵。利用G可由M直接生成码X。以前面的例题为例，知道A，可求出-A T =11 1 00 1 1 11 1 0 1Ik=10 00 1 00 0 1设有信息元组m1m2m3=101则由X=MG求出对应码字1010011G=1 0 0 1 1 1 00 1 0 0 1 1 10 0 1 1 1 0 1可以观察G的三行分别是例5-1求出的第5，3，2个码字第15页，共37页，编辑于2022年，星期一这三个码字组成的G，能使求出的码字信息元在前，监督元在后，即构成的是系统码。如选其他三个码字组合成G，得出的码字信息元与监督元将是交错排列，即非系统码。由H=A|In-k,G=Ik|-A T则HG =A|In-k =A-A=0TIk-A由这个等式可知G的每一行都是一个码字。生成矩阵G和监督矩阵H的关系：一个(n,k)码字的监督矩阵H，正好是另一个(n,n-k)=(n,r)码字的生成矩阵G，反之亦然。我们称(n,n-k)码是(n,k)码的对偶码。可以用下面这个图反映G和H的关系（注意理解）第16页，共37页，编辑于2022年，星期一1 0 0 1 1 1 00 1 0 0 1 1 00 0 1 1 1 0 11 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 0 1 0 0 0 1krkr此处有H(7,4)=G(7,3)或H(7,3)=G(7,4)如H(7,4)=G(7,3)=1 0 0 1 1 1 00 1 0 0 1 1 00 0 1 1 1 0 1可以通过矩阵变换将上面矩阵化为典型监督矩阵形式第17页，共37页，编辑于2022年，星期一第六节第六节 伴随式与标准阵列伴随式与标准阵列设发送的码序列X=X1X2XiXn接收的码序列Y=Y1Y2YiYn两者的差别 E=Y-X=e1e2eien称为差错序列或错误图样用监督矩阵来校验接收到的码字时，有HY =H(X+E)=HX +HETTTT =HET(X是码字，HX =0)T令S =HY =HETTT则S=EHTS称为伴随式，或校验子，用它来检查接收码字中的错误。P182-184用例5-1的监督矩阵为例讨论了接收端可能遇到的几种错误情况，可以看出一种码的检错和纠错能力受码距的限制，超过此限度就会检不出错误，或者造成误判。注意S是一个r维的行矩阵第18页，共37页，编辑于2022年，星期一标准阵列问题：标准阵列问题：设有一个(n,k)线性码，它共有2 个码字C0,C1,C2,C -1。将它排列成下表所示形式。其中零码矢C0放在第一列，它的下面放置各种错误图样。当监督元有n-k个时，在C0下放有2 -1个错误图样。在C0以后各码字C1,C2,C2 -1的同一列下，各放置一些元素，这些元素为该列码字与相应行的错误图样模二相加而成。我们称同一行的这些元素为陪集，C0下面那些错误图样称为陪集首。每一行对应着唯一的一个伴随式。如果将标准阵列预先存储在接收端，则当接收到某个错误码字序列时，可以按照相应的陪集位于哪一列，而依据最大似然法则将其译成该列之首的那个码字。k2kn-kk注意理解下表中错误图样与伴随式的关系。第19页，共37页，编辑于2022年，星期一C0 C1 C2 C2 -1 伴随式SkE2 E2+C1 E2+C2 E2+C2 -1kE3 E3+C1 E3+C2 E3+C2 -1kE2 E2 +C1 E2 +C2 E2 +C2 -1n-kn-kn-kn-kk例5-2 设码字X=X1X2X3X4X5中X1，X2为监督元，监督矩阵为H=11 0 0 01 0 1 1 1列出标准阵列，判断码字10010是否是正确码字，如果不是则它应该译为的正确码字是多少。第20页，共37页，编辑于2022年，星期一解：第一步 根据H求出所有许用码字C0,C1C7。第二步 确定错误图样的个数及形式，以及伴随式S 的形式。第三步 列出标准阵列表 C0 C1 C2 C3 C4 C5 C6 C7 伴随式00000 00011 00101 00110 11001 11010 11100 11111 S00100 00111 00001 00010 11101 11110 11000 11011 0101000 01011 01101 01110 10001 10010 10100 10111 1010000 10011 10101 10110 01001 01010 01100 01111 11码字10010显然不是正确码字，检查它在陪集中位于C5这一列，因而按最大似然法则，将它改正错误后译为C5，即11010。第21页，共37页，编辑于2022年，星期一说明：采用这种方法译码，需要存储2 个陪集元素(n为码长）。如果利用陪集首所列的错误图样和伴随式一一对应的关系列表则只需存2 个陪集首，因而可以节省许多存储量。nn-k例如：发送码字为11010，接收端错误地接收为11110，由公式 S =HY =TT11 0 0 01 0 1 1 111110=01查出陪集首为00100，固原发送码字为11110+00100=11010 但是当(n,k)码的码长n较大时即使只存储2 个陪集首及伴随式，译码器所需内存仍然相当大。因此寻求好的译码方法和简化译码设备是编码理论和应用中的重要课题。n-k第22页，共37页，编辑于2022年，星期一第七节第七节 汉明码汉明码汉明码是一类能纠正一位错误的线性码，此类码及其变型广泛应用于计算机存储系统和数据通信中。对于任意正整数m 3，存在具有下列参数的汉明码：码长：n=2 -1m信息位数：k=2 -m-1m监督位数：r=n-k=m最小码距：dmin=3（纠错位数tc=1）例5-3 取m=3，则n=7,k=4，为(n,k)=(7,4)汉明码。如监督方程组为x2+x3+x4=x5x1+x3+x4=x6x1+x2+x4=x7第23页，共37页，编辑于2022年，星期一则监督矩阵为HX =T0 1 1 1 1 0 010 1 1 0 1 01 1 0 1 0 0 1 x1x2x7=0TG=10 0 0 0 1 10 1 0 0 1 0 10 0 1 0 1 1 00 0 0 1 1 1 1如果将监督位设在x1,x2和x4，我们可以把题中给出的监督方程组等价变换，得到下面方程组x5+x6+x7=x4x3+x6+x7=x2x3+x5+x7=x1H=0 0 0 1 1 1 10 1 1 0 0 1 11 0 1 0 1 0 1第24页，共37页，编辑于2022年，星期一则在输出端求出译码用的伴随式的码元：S=HYs1=x4+x5+x6+x7s2=x2+x3+x6+x7s3=x1+x3+x5+x7根据公式S =HE 得出(7,4)汉明码的一种校验表。如下表示TTT错位指示伴随式s1s2s3无错x1x2x3x4x5x6x7000001010011100101110111第25页，共37页，编辑于2022年，星期一由上表可见，输出检错时很方便。因为由伴随式的各码元的值正好得出等于错误位置的二进制数。例如：当信息元为x3x5x6x7=1100,可求出对应的监督元x1x2x4=011,最后的码字x1x2x3x4x5x6x7=0111100假设传输过程中x7发生了错误，则接收端接收到错误码字x1x2x3x4x5x6x7=0111101，求出伴随式的码元值s1s2s3=111,二进制数为7，由上表可以判断错误的位置在第七位x7。通过将x7取反，进行纠错得到正确码字。注意：汉明码是纠正一位错的完备码，如果将汉明码的参数tc=1,n=2 -1,Q=2 ,且k=2 -m-1代入前面讲的求最大许用码字数的公式，可以发现等式两边正好相等。所以称汉明码为完备码。它表明码的m位监督元的2 种表达形式，正好全部用来指示码长n=2 -1位的每一位上的错误，再加上完全无错的一种情况，因此监督元的利用是最充分的。mkmmm第26页，共37页，编辑于2022年，星期一第九节第九节 卷积码的基本概念卷积码的基本概念卷积码是伊莱亚斯(Elias)1955年提出来的，它的特点是：每一段时间内所编出的几个码元不但与此段时间内进入的K个信息元有关，而且也与前面几段（如m段）时间内的信息元有关。1、编码电路、编码电路下图是一个卷积码的编码电路。DD输入输出12mjpj,1pj,2第27页，共37页，编辑于2022年，星期一D1、D2为移位寄存器。当一个信息元m 进入编码电路后，一面直接输出送往信道，另一方面与前两段时间中送入并移位存储在D1和D2中的信息元m ,m 进行模二相加，所生成的两个监督元jj-1j-2P =m m j,1jj-1P =m m j,2jj-2跟随在信息元m 后送入信道。j设刚开始工作时，D1、D2的状态为0，输入信息元m1=1,求出相应的监督元P1,1=1,P1,2=1，则送入信道的第一段码字为111。再输入信息元m2=0，求出相应的监督元P2,1=1,P2,2=0，第二段码字为010。如果每一段时间内送入k个信息元，编码电路送出n个码元，称n个码元的一段为子码。当输入信息元为mj,mj+1,mj+2时，送出的子码序列为Cj,Cj+1,Cj+2=mj,Pj,1,Pj,2,mj+1,Pj+1,1,Pj+1,2,mj+2,Pj+2,1,Pj+2,2。第28页，共37页，编辑于2022年，星期一可见第j段时间内所编成的子码Cj不仅与本段中输入的信息元mj有关，而且也与前面两个子码Cj-1,Cj-2有关，对后面的两个子码Cj+1,Cj+2也有影响。这种子码之间具有一环与一环相连的特点。因而卷积码称为连环码。前面讲的每一个子码的监督元，是本段时间内输入的信息组与前面m=2个子码的信息组的线性模二和，也就是与(m+1)k个信息元发生线性关系(此处k=1)，固卷积码编出的也是线性码。m称为编码存储级数，N=(m+1)称为编码约束度。编码约束长度定义为编码约束长度定义为：N =(m+1)nA(n,k,m)卷积码表示有k个输入，n个输出，存储级数为m的线性码。如果将移位寄存器和模二相加器间的关系以及信息元序列都用多项式形式来表示，则卷积编码运算可以化为多项式的代数运算。例如书P198介绍了一个k=1,n=2的卷积码编码电路。第29页，共37页，编辑于2022年，星期一2 监督矩阵监督矩阵将前面的(3,1,2)卷积码的两个监督方程改写为矩阵形式。0*mj-2+0*Pj-2,1+0*Pj-2,2+1*mj-1+0*Pj-1,1+0*Pj-1,2+1*mj+1*Pj,1+0*Pj,2=01*mj-2+0*Pj-2,1+0*Pj-2,2+0*mj-1+0*Pj-1,1+0*Pj-1,2+1*mj+0*Pj,1+1*Pj,2=0用矩阵表示：000 100 110100 000 101mj-2Pj-2,1Pj-2,2mj-1Pj-1,1Pj-1,2mjPj,1Pj,2=0第30页，共37页，编辑于2022年，星期一000 100 110100 000 101其中 h=P2T P1T P0T00I2称为基本监督矩阵。P2T且=01 P1T=10 P0T=110=0000I2=100 13 第一截分组码第一截分组码由前面的编码电路可以看出，每一个信息元影响的子码数目是有限的。因此在译某个码元时，只需要在一个约束长度内来考虑。假设编码约束度N=m+1=3,我们在三个子码Cj(j=0,1,2)中来讨论它的监督关系。写出如下三个监督方程组。1*m0+1*P0,1+0*P0,2=01*m0+0*P0,1+1*P0,2=0第31页，共37页，编辑于2022年，星期一0*m0+0*P0,1+0*P0,2+1*m1+0*P1,1+0*P1,2+1*m2+1*P2,1+0*P2,2=01*m0+0*P0,1+0*P0,2+0*m1+0*P1,1+0*P1,2+1*m2+0*P2,1+1*P2,2=01*m0+0*P0,1+0*P0,2+1*m1+1*P1,1+0*P1,2=00*m0+0*P0,1+0*P0,2+1*m1+0*P1,1+1*P1,2=0由上面方程组可以得到根据三个信息组m0,m1,m2编出来的第一截分组码的一致监督矩阵H为H=110101100 110000 101000 100 110100 000 101=P2T P1T P1T P0T P0T P0TI2I2I2000第32页，共37页，编辑于2022年，星期一H的意义：它表达了第一截分组码中的3个子码内，6个监督元与3个信息元之间的约束关系。它也代表了以后无限长码序列中各子码的约束关系。例：对下图示的n=2,k=1的卷积码编码电路，它的一致监督方程为Pj=mj+mj-2，求基本监督矩阵以及它的第一截分组码的一致监督矩阵。解：将监督方程化为矩阵形式D1D2输出mjPj输入基本监督矩阵h=100011第33页，共37页，编辑于2022年，星期一第一截分组码的一致监督矩阵H=110 0 1 11 0 0 0 1 14 生成矩阵生成矩阵设输入的信息序列为m0m1m2m3,则编码电路编出的码序列为m0P0,1P0,2m1P1,1P1,2m2P2,1P2,2。按照监督方程列出编码序列中每一个码元与输入信息元之间的关系如下：m0P0,1=m0P0,2=m0m1P1,1=m0+m1P1,2=m1m2P2,1=m1+m2P2,2=m0+m2m3P3,1=m2+m3P3,2=m1+m3.第34页，共37页，编辑于2022年，星期一将上述关系合并在一个矩阵表达式中，有m0P0,1P0,2m1P1,1P1,2m2P2,1P2,2m3P3,1P3,2=m0m1m2m3其中G =000 111 010 001 000 000 111 010 000 000 000 111 111 010 001 000 111 010 001 000 000 111 010 001 000 000 111 010 000 000 000 111 称为生成矩阵第35页，共37页，编辑于2022年，星期一仿照H矩阵的简便写法，将G 写成G =I1P0 0P1 0P2 I1P0 0P1 0P2 I1P0 0P1 式中I1是kxk=1x1阶单位方阵，Pi(I=0,1,2)是kx(n-k)=1x2阶矩阵，0为1x1阶全0方阵。第一截分组码生成矩阵为G=I1P0 0P1 0P2I1P0 0P1I1P0其中第一行 g=I1P0 0P1 0P2称为码的基本生成矩阵。第36页，共37页，编辑于2022年，星期一5 译码方法译码方法卷积码的译码通常有两种方式：P2041、门限译码：工作原理类似于分组码的译码电路。2、序列译码：概率译码的一种。第37页，共37页，编辑于2022年，星期一