线性码及其应用

线性码及其应用第一页，共三十七页，2022年，8月28日定义2码字X=x1x2…xn的汉明重量是码字中非零码元的位数，用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说明：为尽量避免码字受到干扰而出错，总是希望码字间有尽可能大的距离，最小码距代表了一个码组中最不利的情况。从安全出发，往往选用最小码距来分析码的检错纠错能力。第二页，共三十七页，2022年，8月28日第二节检错能力与纠错能力1、码距为1时，能保证码字的唯一性，但不能检错和纠错。2、码距为2时，能检查出一位错误，但无法纠错。3、码距为3时，能检查出一位或两位错误，并且还可纠正一位错误。例：设码长为3，取000、111作为码字，其余为禁用码字。如接收端收到001，它是禁用码字，知道出错，由于001与000相差一个码元，与111相差两个码元，根据最大似然译码原则将001译为000。最大似然译码原则：当Ci为若干个发送码字中的一个，R为接收码字，若条件概率P(R/Ci)为最大，则认为码字Ci就是发送码字。第三页，共三十七页，2022年，8月28日结论：（一）、要检出码字中任意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第四页，共三十七页，2022年，8月28日第三节寄偶监督码寄偶监督码是最简单的一种检错码，是目前计算机系统用得最多的一种差错控制码。寄偶监督码的编码方式：是在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码表示的十个数字符号的寄偶校验位。第五页，共三十七页，2022年，8月28日判别方法：接收端收到编好的寄偶监督码后，用与发送端相同的规则检查“1”的个数是否仍保持奇数或偶数，从而确定传输过程中是否有错误。特点：能发现一位码元或所有奇数位码元出错的情况。但不能纠正任何错误以及发现偶数位码元错误。简单寄偶码的效率高：η=n-1n寄偶监督码的实现：1、硬件法：采用模二相加的异或电路。C1C2C3C4C5C6C7C0C0’第六页，共三十七页，2022年，8月28日2、软件法（见P170图5-6的流程图）为了改进差错控制性能，引入二维寄偶监督码（水平-垂直寄偶监督码、方阵码、纵横寄偶监督码）。就是在水平方向进行寄偶监督的同时，再按垂直方向进行一次寄偶监督。如P171图5-7，图5-8（二维水平-斜向寄偶监督码）。二维寄偶监督码特点：能检出每一行或每一列的两位或偶数位错误。可以用水平、垂直两个方向上的监督码元，来确定单个错误码元的位置，从而进行纠正。但它无法检出四个错误码元构成矩形（或平行四边形）四个顶点的错误图样，也无法检出双向成偶的错误图样。第七页，共三十七页，2022年，8月28日第五节监督矩阵与生成矩阵设有待编码的消息序列为M=[m1m2…mk],对应的信息元序列[X1X2…Xk]。为了进行差错控制，我们按线性代数关系来添加监督码元序列[Xk+1Xk+2…Xn]，则称此码长n，信息元数k的码字序列[X1X2…Xk|Xk+1Xk+2…Xn]为线性分组码。记为(n,k)，如果其最小码距为d，也可记为(n,k,d)或[n,k,d]。其中监督元数r=n-k。用线性的监督方程组来表示：a11X1+a12X2+……+a1kXk=Xk+1a21X1+a22X2+……+a2kXk=Xk+2……ar1X1+ar2X2+……+arkXk=Xn式中加号均表示模二加第八页，共三十七页，2022年，8月28日或a11X1+a12X2+……+a1kXk+Xk+1+0+……+0=0a21X1+a22X2+……+a2kXk+0+Xk+2+……+0=0……ar1X1+ar2X2+……+arkXk+0+0……+Xn=0若用矩阵表示，则a11a12…a1k10…0a21a22…a2k01…0…ar1ar2…ark00…1…X1X2…XkXk+1…Xk=[0]简写为HXT=0TH：监督矩阵XT：行矩阵X=[X1X2…Xn]的转置矩阵第九页，共三十七页，2022年，8月28日例5-1一个(7,3)码的信息元[X1X2X3]和监督元[X4X5X6X7]间的监督方程组为X1+X3+X4=0X1+X2+X3+X5=0X1+X2+X6=0X2+X3+X7=0求出对应信息元的监督元。解：列出各种信息元组合，依据监督方程组求出对应监督元如下表所示。信息元监督元编成码字0000010100111001011101110000110101111010111000111001010000000000011101010011101110101001110101001111010011110100第十页，共三十七页，2022年，8月28日还可以写出监督矩阵形式HX=011000111010011000100110001TX1X2X3X4X5X6X7=0000第十一页，共三十七页，2022年，8月28日说明：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列线性无关。第十二页，共三十七页，2022年，8月28日例如：例题中0011101是码字，码重为4，它应该满足监督方程组。即HXT=0110001110100110001001100010011101=1101+1000+0100+0001=0000第十三页，共三十七页，2022年，8月28日下面讨论一下监督矩阵H与生成矩阵G的关系。HXT=[A|Ir]X1X2…XkXk+1Xk+2…Xn=0T或[A]X1X2…Xk+[Ir]Xk+1Xk+2…Xk=0T则Xk+1Xk+2…Xn=-[A]X1X2…Xk=-[A]…mkm1m2令X1X2…Xk=[Ik]…mkm1m2第十四页，共三十七页，2022年，8月28日X1X2…Xk=Ik-Am1m2…mk两边取转置得X=MGX，M为行矩阵的形式；G=[Ik|-AT]称为生成矩阵。利用G可由M直接生成码X。以前面的例题为例，知道A，可求出[-A]T=11001111101[Ik]=00010001设有信息元组m1m2m3=101则由X=MG求出对应码字[1010011]G=100111001001110011101可以观察G的三行分别是例5-1求出的第5，3，2个码字第十五页，共三十七页，2022年，8月28日这三个码字组成的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的关系（注意理解）第十六页，共三十七页，2022年，8月28日1001110010011000111011011000111010011000100010001krkr此处有H(7,4)=G(7,3)或H(7,3)=G(7,4)如H(7,4)=G(7,3)=100111001001100011101可以通过矩阵变换将上面矩阵化为典型监督矩阵形式第十七页，共三十七页，2022年，8月28日第六节伴随式与标准阵列设发送的码序列X=[X1X2…Xi…Xn]接收的码序列Y=[Y1Y2…Yi…Yn]两者的差别E=Y-X=[e1e2…ei…en]称为差错序列或错误图样用监督矩阵来校验接收到的码字时，有HY=H(X+E)=HX+HETTTT=HET(X是码字，HX=0)T令S=HY=HETTT则S=EHTS称为伴随式，或校验子，用它来检查接收码字中的错误。P182-184用例5-1的监督矩阵为例讨论了接收端可能遇到的几种错误情况，可以看出一种码的检错和纠错能力受码距的限制，超过此限度就会检不出错误，或者造成误判。注意S是一个r维的行矩阵第十八页，共三十七页，2022年，8月28日标准阵列问题：设有一个(n,k)线性码，它共有2个码字C0,C1,C2…,C-1。将它排列成下表所示形式。其中零码矢C0放在第一列，它的下面放置各种错误图样。当监督元有n-k个时，在C0下放有2-1个错误图样。在C0以后各码字C1,C2,…C2-1的同一列下，各放置一些元素，这些元素为该列码字与相应行的错误图样模二相加而成。我们称同一行的这些元素为陪集，C0下面那些错误图样称为陪集首。每一行对应着唯一的一个伴随式。如果将标准阵列预先存储在接收端，则当接收到某个错误码字序列时，可以按照相应的陪集位于哪一列，而依据最大似然法则将其译成该列之首的那个码字。k2kn-kk注意理解下表中错误图样与伴随式的关系。第十九页，共三十七页，2022年，8月28日C0C1C2…C2-1伴随式SkE2E2+C1E2+C2…E2+C2-1kE3E3+C1E3+C2…E3+C2-1k…………E2E2+C1E2+C2…E2+C2-1n-kn-kn-kn-kk例5-2设码字X=[X1X2X3X4X5]中X1，X2为监督元，监督矩阵为H=100010111列出标准阵列，判断码字10010是否是正确码字，如果不是则它应该译为的正确码字是多少。第二十页，共三十七页，2022年，8月28日解：第一步根据H求出所有许用码字C0,C1…C7。第二步确定错误图样的个数及形式，以及伴随式S的形式。第三步列出标准阵列表C0C1C2C3C4C5C6C7伴随式0000000011001010011011001110101110011111S001000011100001000101110111110110001101101010000101101101011101000110010101001011110100001001110101101100100101010011000111111码字10010显然不是正确码字，检查它在陪集中位于C5这一列，因而按最大似然法则，将它改正错误后译为C5，即11010。第二十一页，共三十七页，2022年，8月28日说明：采用这种方法译码，需要存储2个陪集元素(n为码长）。如果利用陪集首所列的错误图样和伴随式一一对应的关系列表则只需存2个陪集首，因而可以节省许多存储量。nn-k例如：发送码字为11010，接收端错误地接收为11110，由公式S=HY=TT10001011111110=01查出陪集首为00100，固原发送码字为11110+00100=11010但是当(n,k)码的码长n较大时即使只存储2个陪集首及伴随式，译码器所需内存仍然相当大。因此寻求好的译码方法和简化译码设备是编码理论和应用中的重要课题。n-k第二十二页，共三十七页，2022年，8月28日第七节汉明码汉明码是一类能纠正一位错误的线性码，此类码及其变型广泛应用于计算机存储系统和数据通信中。对于任意正整数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第二十三页，共三十七页，2022年，8月28日则监督矩阵为HX=T01111000110101101001x1x2x7…=[0]TG=000011010010100101100001111如果将监督位设在x1,x2和x4，我们可以把题中给出的监督方程组等价变换，得到下面方程组x5+x6+x7=x4x3+x6+x7=x2x3+x5+x7=x1H=000111101100111010101第二十四页，共三十七页，2022年，8月28日则在输出端求出译码用的伴随式的码元：S=HYs1=x4+x5+x6+x7s2=x2+x3+x6+x7s3=x1+x3+x5+x7根据公式S=HE得出(7,4)汉明码的一种校验表。如下表示TTT错位指示伴随式s1s2s3无错x1x2x3x4x5x6x7000001010011100101110111第二十五页，共三十七页，2022年，8月28日由上表可见，输出检错时很方便。因为由伴随式的各码元的值正好得出等于错误位置的二进制数。例如：当信息元为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第二十六页，共三十七页，2022年，8月28日第九节卷积码的基本概念卷积码是伊莱亚斯(Elias)1955年提出来的，它的特点是：每一段时间内所编出的几个码元不但与此段时间内进入的K个信息元有关，而且也与前面几段（如m段）时间内的信息元有关。1、编码电路下图是一个卷积码的编码电路。DD输入输出12mjpj,1pj,2第二十七页，共三十七页，2022年，8月28日D1、D2为移位寄存器。当一个信息元m进入编码电路后，一面直接输出送往信道，另一方面与前两段时间中送入并移位存储在D1和D2中的信息元m,m进行模二相加，所生成的两个监督元jj-1j-2P=mmj,1jj-1P=mmj,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…。第二十八页，共三十七页，2022年，8月28日可见第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的卷积码编码电路。第二十九页，共三十七页，2022年，8月28日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用矩阵表示：000100110100000101mj-2Pj-2,1Pj-2,2mj-1Pj-1,1Pj-1,2mjPj,1Pj,2=0第三十页，共三十七页，2022年，8月28日000100110100000101其中h=P2TP1TP0T00I2称为基本监督矩阵。P2T且=01P1T=10P0T=110=0000I2=0013第一截分组码由前面的编码电路可以看出，每一个信息元影响的子码数目是有限的。因此在译某个码元时，只需要在一个约束长度内来考虑。假设编码约束度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第三十一页，共三十七页，2022年，8月28日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=110101100110000101000100110100000101=P2TP1TP1TP0TP0TP0TI2I2I2000第三十二页，共三十七页，2022年，8月28日H的意义：它表达了第一截分组码中的3个子码内，6个监督元与3个信息元之间的约束关系。它也代表了以后无限长码序列中各子码的约束关系。例：对下图示的n=2,k=1的卷积码编码电路，它的一致监督