2014.线性分组码

第8章线性分组码•线性分组码的基本概念–(n,k)线性分组码是把信息流的每k个码元（symbol）分成一组，通过线性变换，映射成由n个码元组成的码字(codeword)。•对于二进制–k位二进制信息有2k种组合，n位二进制数有2n种组合；–纠错编码的任务是在2n种可能组合中选择2k个构成许用码组集合C，然后设法将k比特信息组一一对应地映射到许用码组集合C。–不同的编码算法对应不同的码集C以及不同的映射算法，这样得到的码称为(n,k)线性分组码，或(n,k,d)线性分组码。–不编码时，一个二进制码元携带1b信息，编码后，n个二进制码元携带k比特信息。•二进制(5,3)码–K位信息空间23n位编码空间25•00000000000010001000011•00100100001010011000111•01001000010010101001011•01101100011010111001111•10010000100011001010011•10110100101011011010111•11011000110011101011011•11111100111011111011111•对于多进制情况，–长度为k的q进制信息组有qk种组合；–n位q进制数有qn种组合；–编码的任务是在qn种可能组合中选择qk个构成码集C，使之与信息码能一一对应地映射。三进制(3,2)码–K位信息空间32n位编码空间33•00000001002•01010011012•02020021022•10100101102•11110111112•12120121122•20200201202•21210211212•22220221222表3-1［7，3］码的码字表信息组码字00000101001110010111011100000000011101010011101110101001110101001111010011110100•线性码的性质–两个码字的和仍是一个属于该码的码字。–全零字总是一个码字–一个线性码的两个码字之间的最小距离等于任何非零码字的最小重量–例：C＝{0000，1010，0101，1111}是n＝4的线性分组码。•码字之间所有十种可能的和•全零码，最小距离，最小码重。码的一致校验矩阵与生成矩阵一、码的校验矩阵与生成矩阵–［n，k，d］分组码的编码问题就是在满足给定条件(码的最小距离d或码率R)下，如何从已知的k个信息元求得r=n-k个校验元。这相当于建立一组线性方程组，已知k个系数，求n-k个未知系数，使得到的码符合相关要求。如要求d=2，可检错1位，可采用奇偶校验（偶监督为例）接收端计算矫正子1210naaaaS……01210naaaa……监督关系式监督位信息位举例说明如何编码和译码当S＝0，无错；若S＝1，有错。00——无错01——位置1错10——位置2错11——位置3错12rr个监督关系式能指示一位错码的()个可能位置。两个矫正子S1S2=如果要求d=3，有两个监督位，能纠正一位错误？01210naaaa……线性方程一般来说，若码长为n,信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求nr12例：如信息位为7位，要构成能纠正1位错码的线性分组码，至少要加几位监督码？其编码效率为多少？265416530643aaaaaaaaaaaa6543210111110101011aaaaaaa654654321031111101010110000100001000011aaaaaaaaaaa生成矩阵G系数矩阵P|GIP对于（7，4）线性分组码，•生成矩阵提供了一种简明而有效地表示一个线性分组码的方法。k×n阶矩阵可以生成qk个码字。–二元（46，24）码的总码字数224＝1777216–码字查询表n×2k＝771751936(bit)–生成矩阵n×k=46×24＝1104（bit）654265316430000aaaaaaaaaaaa6543210111010001101010010110010aaaaaaa6543210111110101000011100010001aaaaaaa一致校验矩阵H码字C简写为H·CT=0(3.2.6)或C·HT=0(3.2.7)PT|THPI•校验矩阵H用于检测码字的合法性。若c是个合法的码字，则cHT＝0。c=mGmGHT＝0GHT＝0|0TTPGHIPI0TPGHIPI•二进制情况下•系统码的生成矩阵通常为G=［IkP］k位信息位n-k位校验位图系统码的一种结构形式|GIP通常，我们称与矩阵为码的典型(标准)生成矩阵和典型校验矩阵。|THPI•生成矩阵可以通过初等行变换简化成系统型（标准型，典型）–G=[I|P]–其中I是k×k单位阵，P是k×(n-k)矩阵–例：二进制的（7，4）码生成矩阵0001001001011011G011110100000•系统码的编码相对而言较为简单，且由G可以方便地得到H(反之亦然)，容易检查编出的码字是否正确。同时，对分组码而言，系统码与非系统码的纠错能力完全等价。因此，今后若无特别声明，仅讨论系统码形式。•缩短码–在某些情况下，如果不能找到一种比较合适的码长或信息位个数，则可把某一［n，k，d］码进行缩短，以满足要求。–在［n，k，d］码的码字集合中，挑选前i个信息位数字均为0的所有码字，组成一个新的子集。由于该子集的前i位信息位均取0，故传输时可以不送它们，仅只要传送后面的n-i位码元即可。这样该子集组成了一个［n-i，k-i，d］分组码，称它为［n，k，d］码的缩短码。由于缩短码是原码的一个子集，其纠错能力至少与原［n，k，d］码相同。•缩短码的G矩阵只要在原［n，k，d］码的G矩阵中，去掉左边i列和上边i行即可。•［n-i，k-i］缩短码是［n，k］码缩短i位得到的，因而码率R比原码要小，但纠错能力不一定比原码强。因此总的看来，缩短码比原码的性能要差。•.设一个［7，4］码的生成矩阵为0111000110010010100101110001G(1)求出该码的全部码矢；(2)求出该码的一致校验矩阵。|GIP|THPIc=mG•例：一个［8，4］系统码，它的一致校验方程为：c0=m1+m2+m3c1=m0+m1+m2c2=m0+m1+m3c3=m0+m2+m3式中，m0，m1，m2，m3是信息位，c0，c1，c2，c3是校验位。找出该码的G和H。11011101110111111101H10001101010010110010011100011110Gc0=m1+m2+m3c1=m0+m1+m2c2=m0+m1+m3c3=m0+m2+m3设c=m3m2m1m0c3c2c1c0线性分组码的译码•信道中的噪声随机地将所传输的码字的符号转变为其他符号。若噪声只改变被传输码字的一个符号，该出错码字与原来传输的码字的汉明距离为1。若噪声改变了t个符号，则汉明距离为t。•错误模式–发送:00000000001111111111–接收:01101001001111001001–错误:01101001000000110110–错误模式中的0表示这码位没有错,1表示有错。•码的纠检错能力–一个码字只要不转变成另一个合法码字，就能检测到错误。如果码字之间的最小距离为d*，要使一个码字转变成另一个码字，错误模式的重量必须至少为d*。因此，一个(n,k,d*)码•至少可以检测所有重量小于或等于(d*-1)的非零错误模式。•至少有一个重量为d*的错误模式检测不到，与两个距离最近的码字相对应。•可能有些重量大于或等于d*的错误模式也能检测到，但并不是所有重量为d*的错误模式都能检测到。•例：码C1={000,111}–最小距离3，可以检测重量为2和1的错误模式。–{011,101,110,001,010,100}•例：码C2={001,110,101}–最小距离1–重量为1的错误模式010可以检测，重量为1的错误模式100不能检测。–不能检测所有重量为1的错误模式•纠错的目标是由收到的码字猜测发送的码字。•最近邻译码–以汉明距离为度量，收到的码字和合法码字的距离哪个最小，就认为发送的是哪个码字。–如果接收到的字与多个码字有相同的汉明距离，接收方•任意选择最小相同距离的一个邻码•要求发送端重新传送•为确保收到的字（最多有t个错误）离原始码字最近，而离所有其他码字都更远，需使码的最小距离d*≥2t＋1•译码球–每个码字可以用q元n维线性空间的一个点描述。–所有汉明距离小于等于t的字都位于以该码字为中心，半径为t的球中。–如果码的最小距离为d*且满足条件d*≥2t＋1，那么这些球不会重叠。–任意一个接收到的在某个球内的向量将离它的中心比离其他码字的距离更近。–我们称与码字相关的球为译码球。c1tc2td*≥2t＋1译码球q元n维线性空间中的译码球•不满足条件d*≥2t＋1时，不确定能纠正t个错误•例：码C={00000,01010,10101,11111}，最小距离2–设发送码字11111，接收到码字11110，t＝1•d(11110,00000)=4,d(11110,01010)=2•d(11110,10101)=3,d(11110,11111)=1•根据最近邻译码，判断发送码字为11111–设发送码字00000，接收到码字01000，t＝1•d(01000,00000)=1,d(01000,01010)=1•d(01000,10101)=4,d(01000,11111)=4•没有明确判决•不完全译码器–收到的码字只在能找到一个离它最近的码字时才能译码。在不确切的情况下，译码器声明收到的字无法辨认，要求发信端重传。•完全译码器–对收到的任何字都译码。•实际中大多采用不完全译码器。伴随式与译码设k位信息编成n位线性分组码C=(cn-1,…,c1,c0)接收码R=(rn-1,…,r1,r0)定义差错图案E=(en-1,…,e1,e0)=(rn-1-cn-1,…,r1-c1,r0-c0)=R-C对于二进制码，模2加减法相同E=R-C；E=R+C；R=E+C•伴随式对于合法码字c，cHT＝0。接收到码字RRHT=(C+E)HT=CHT+EHT=0+EHT=EHT若RHT=EHT＝0，说明R=C，无差错；否则出错。RHT=EHT的值仅与差错图案E有关，而和码字C无关。定义伴随式S=(sn-k-1,…,s1,s0)=RHT=EHT•伴随式译码S=(sn-k-1,…,s1,s0)=RHT=EHT–接收端收到R后，可计算伴随式S，从而得到E和C。–由于S只有2n-k种可能组合，而差错图案E有2n种可能组合，同一伴随式可能对应若干个不同的差错图案。译码的关键是由S确定E。编码mGRHT=0计算E输出R+EmCER输出RyesnoC~编译码过程框图•可通过解线性方程来求解ES=(sn-k-1,…,s1,s0)=RHT=EHT=(en-1,…,e1,e0)HT少n-(n-k)=k个方程，有2k个解•概率译码–把所有解的重量作比较，选择最轻的作为E的估值。由于p1，•例：某一个（5，2）系统线性码的生成矩阵为设接收码R＝（10101），请先构造该码的标准阵列译码表，然后译出发送码的估值。04列出方程组：S2=e4+e3+e2=0S1=e4+e1=1S0=e4+e3+e0=0如果R=00000/10111/01101/11010，S=000解出E=00000