线性分组码课件.ppt

《线性分组码课件.ppt》由会员分享，可在线阅读，更多相关《线性分组码课件.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性分组码第1页，此课件共62页哦对于二进制k位二进制信息有2k种组合，n位二进制数有2n种组合；纠错编码的任务是在n维矢量空间的2n种可能组合中选择2k个构成一个子空间，或称许用码组集合C，然后设法将k比特信息组一一对应地映射到许用码组集合C。不同的编码算法对应不同的码集C以及不同的映射算法，这样得到的码称为(n,k)线性分组码，或(n,k,d)线性分组码。不编码时，一个二进制码元携带1b信息，编码后，n个二进制码元携带k比特信息。第2页，此课件共62页哦二进制(5,3)码K位信息空间23 n位编码空间250000000000001000100001100100100001010011000

2、111010010000100101010010110110110001101011100111110010000100011001010011101101001010110110101111101100011001110101101111111100111011111011111第3页，此课件共62页哦对于多进制情况，长度为k的q进制信息组有qk种组合；n位q进制数有qn种组合；编码的任务是在n维矢量空间的qn种可能组合中选择qk个构成一个子空间，或码集C，使之与信息矢量能一一对应地映射。第4页，此课件共62页哦三进制(3,2)码K位信息空间32 n位编码空间3300000001002010

3、1001101202020021022101001011021111011111212120121122202002012022121021121222220221222第5页，此课件共62页哦表3-1 7，3码的码字表 信息组 码 字 000001010011100101110111 00000000011101010011101110101001110101001111010011110100 第6页，此课件共62页哦线性码的性质两个码字的和仍是一个属于该码的码字（群的封闭性）。全零字总是一个码字一个线性码的两个码字之间的最小距离等于任何非零码字的最小重量GF(2)上n，k，d线性分组码中

4、，任何两个码字C1，C2之间有关系：d(C1，C2)w(C1)+w(C2)例：C0000，1010，0101，1111是n4的线性分组码。码字之间所有十种可能的和全零码，最小距离，最小码重。第7页，此课件共62页哦3.2 码的一致校验矩阵与生成矩阵 一、码的校验矩阵与生成矩阵n，k，d分组码的编码问题就是在n 维线性空间Vn 中，如何找出满足一定要求的，有2k 个矢量组成的k 维线性子空间Vn，k。或者说，在满足给定条件(码的最小距离d或码率R)下，如何从已知的k 个信息元求得r=n-k 个校验元。第8页，此课件共62页哦这相当于建立一组线性方程组，已知k 个系数，求n-k个未知系数，使得到的

5、码符合相关要求。如要求d=2，可检错1位，可采用奇偶校验（偶监督为例）接收端计算矫正子监督关系式监督位信息位举例说明如何编码和译码第9页，此课件共62页哦当S0，无错；若S1，有错。00无错01位置1错10位置2错11位置3错r个监督关系式能指示一位错码的()个可能位置。两个矫正子 S1S2=如果要求d=3，有两个监督位，能纠正一位错误？线性方程第10页，此课件共62页哦 一般来说，若码长为n,信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求 第11页，此课件共62页哦如何具体构造这些监督关系式?设分组码(n，k)中k4。为了纠正

6、一位错码，要求监督位数r=3。若取r=3，则n=k+r=7。我们用表示这7个码元，用 表示三个监督关系式中的校正子，规定：举例：第12页，此课件共62页哦 错码位置 0 0 0 无错 0 0 1a0 0 1 0 a1 1 0 0 a20 1 1 a3 1 0 1 a4 1 1 0 a5 1 1 1 a6 （r个监督位对整个码组的各个码元都起监督作用）校正子与错码位置第13页，此课件共62页哦当发生一个错码，其位置在 S1为1；否则S1为0S2为1；否则S2为0S3为1；否则S3为0构成监督关系式第14页，此课件共62页哦 在发送端编码时，信息位的值决定于输入信号，因此它们是随机的。而监督位应根

7、据信息位的取值按监督关系来确定，即监督位应使式中的S1,S2和S3均为零(表示编码组中无错码)，于是有下列方程组 由上式经移项运算，解出监督位为 第15页，此课件共62页哦已知信息位后，就可直接计算出监督位。由此得出16个许用码组 信息码 监督码 a6a5a4a3a2a1a00 0 0 00 0 0 1 0 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 00 1 11 0 11 1 01 1 01 0 10 1 10 0 0 信息码 监督码a6a5a4a3a2a1a01 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11

8、 1 1 01 1 1 10 1 11 0 00 1 00 0 10 0 10 1 01 0 01 1 1表4-5（7，4）汉明码的许用码组第16页，此课件共62页哦 接收端收到每个码组后，计算S1,S2,S3，如不全为0，则可按上表确定误码的位置，然后加以纠正。例：接收码组为0100101此(7,4)线性码的最小码距3，这种码能纠正一个错码或检测两个错码。101000010110001S1 S2 S3 011，a3错（校正子与错码位置）第17页，此课件共62页哦例：如信息位为7位，要构成能纠正1位错码的线性分组码，至少要加几位监督码？其编码效率为多少？第18页，此课件共62页哦例：已知信息码

9、为1101，求所对应的（7，4）线性分组码。此（7，4）码为1101010 解：由监督方程求监督码第19页，此课件共62页哦例：接收端收到码1001010，是否有错？错码位置为何？校正子为110，此码有错，错码位置为a5 解：计算较正子第20页，此课件共62页哦生成矩阵G系数矩阵P第21页，此课件共62页哦生成矩阵提供了一种简明而有效地表示一个线性分组码的方法。kn阶矩阵可以生成qk个码字。二元（46，24）码的总码字数2241 777 216码字查询表n2k771 751 936(bit)生成矩阵nk=46241104（bit）第22页，此课件共62页哦一致校验矩阵H码字C简写为简写为 HC

10、T=0 (3.2.6)或或 CHT=0 (3.2.7)PT第23页，此课件共62页哦校验矩阵H用于检测码字的合法性。若c是个合法的码字，则cHT0。c=mG mGHT0 GHT0二进制情况下第24页，此课件共62页哦系统码的生成矩阵通常为 G=Ik Pk 位信息位 n-k 位校验位 图 3-1 系统码的一种结构形式 通常，我们称 与 矩阵为码的典型(标准)生成矩阵和典型校验矩阵。第25页，此课件共62页哦生成矩阵可以通过初等行变换简化成系统型（标准型，典型）G=I|P其中I是kk单位阵，P是k(n-k)矩阵例：GF(2)上的（7，4）码生成矩阵第26页，此课件共62页哦第27页，此课件共62页

11、哦系统码的编码相对而言较为简单，且由G可以方便地得到H(反之亦然)，容易检查编出的码字是否正确。同时，对分组码而言，系统码与非系统码的纠错能力完全等价。因此，今后若无特别声明，仅讨论系统码形式。第28页，此课件共62页哦缩短码在某些情况下，如果不能找到一种比较合适的码长或信息位个数，则可把某一n，k，d码进行缩短，以满足要求。在n，k，d码的码字集合中，挑选前i个信息位数字均为0的所有码字，组成一个新的子集。由于该子集的前i位信息位均取0，故传输时可以不送它们，仅只要传送后面的n-i 位码元即可。这样该子集组成了一个n-i，k-i，d分组码，称它为n，k，d码的缩短码。由于缩短码是k 维子空间

12、Vn，k 中取前i位均为0的码字组成的一个子集，显然该子集是Vn，k 空间中的一个k-i维的子空间Vn，k-i，因此n-i，k-i，d缩短码的纠错能力至少与原n，k，d码相同。第29页，此课件共62页哦缩短码的G矩阵只要在原n，k，d码的G矩阵中，去掉左边i列和上边i行即可。n-i，k-i缩短码是n，k 码缩短i位得到的，因而码率R 比原码要小，但纠错能力不一定比原码强。因此总的看来，缩短码比原码的性能要差。第30页，此课件共62页哦.设一个7，4码的生成矩阵为(1)求出该码的全部码矢；(2)求出该码的一致校验矩阵。第31页，此课件共62页哦例：一个8，4系统码，它的一致校验方程为：c0=m1

13、+m2+m3 c1=m0+m1+m2 c2=m0+m1+m3 c3=m0+m2+m3 式中，m0，m1，m2，m3是信息位，c0，c1，c2，c3是校验位。找出该码的G和H。第32页，此课件共62页哦c0=m1+m2+m3c1=m0+m1+m2c2=m0+m1+m3c3=m0+m2+m3设c=m3 m2 m1 m0 c3 c2 c1 c0第33页，此课件共62页哦3.3 线性分组码的译码信道中的噪声随机地将所传输的码字的符号转变为其他符号。若噪声只改变被传输码字的一个符号，该出错码字与原来传输的码字的汉明距离为1。若噪声改变了t个符号，则汉明距离为t。错误模式发送:00000000001111

14、111111接收:01101001001111001001错误:01101001000000110110错误模式中的0表示这码位没有错,1表示有错。第34页，此课件共62页哦码的纠检错能力一个码字只要不转变成另一个合法码字，就能检测到错误。如果码字之间的最小距离为d*，要使一个码字转变成另一个码字，错误模式的重量必须至少为d*。因此，一个(n,k,d*)码至少可以检测所有重量小于或等于(d*-1)的非零错误模式。至少有一个重量为d*的错误模式检测不到，与两个距离最近的码字相对应。可能有些重量大于或等于d*的错误模式也能检测到，但并不是所有重量为d*的错误模式都能检测到。第35页，此课件共62页

15、哦例：码C1=000,111最小距离3，可以检测重量为2和1的错误模式。011,101,110,001,010,100例：码C2=001,110,101最小距离1重量为1的错误模式010可以检测，重量为1的错误模式100不能检测。不能检测所有重量为1的错误模式第36页，此课件共62页哦纠错的目标是由收到的码字猜测发送的码字。最近邻译码以汉明距离为度量，收到的码字和合法码字的距离哪个最小，就认为发送的是哪个码字。如果接收到的字与多个码字有相同的汉明距离，接收方任意选择最小相同距离的一个邻码要求发送端重新传送第37页，此课件共62页哦为确保收到的字（最多有t个错误）离原始码字最近，而离所有其他码字

16、都更远，需使码的最小距离d*2t1第38页，此课件共62页哦译码球每个码字可以用q元n维线性空间的一个点描述。所有汉明距离小于等于t的字都位于以该码字为中心，半径为t的球中。如果码的最小距离为d*且满足条件d*2t1，那么这些球不会重叠。任意一个接收到的在某个球内的向量将离它的中心比离其他码字的距离更近。我们称与码字相关的球为译码球。第39页，此课件共62页哦c1tc2td*2t1译码球q元n维线性空间中的译码球第40页，此课件共62页哦不满足条件d*2t1时，不确定能纠正t个错误例：码C=00000,01010,10101,11111，最小距离2设发送码字11111，接收到码字11110，t

17、1d(11110,00000)=4,d(11110,01010)=2d(11110,10101)=3,d(11110,11111)=1根据最近邻译码，判断发送码字为11111设发送码字00000，接收到码字01000，t1d(01000,00000)=1,d(01000,01010)=1d(01000,10101)=4,d(01000,11111)=4没有明确判决第41页，此课件共62页哦不完全译码器收到的码字只在能找到一个离它最近的码字时才能译码。在不确切的情况下，译码器声明收到的字无法辨认，要求发信端重传。完全译码器对收到的任何字都译码。实际中大多采用不完全译码器。第42页，此课件共62页

18、哦伴随式与译码设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第43页，此课件共62页哦伴随式对于合法码字c，cHT0。接收到码字RRHT=(C+E)HT=CHT+E HT=0+EHT=E HT若RHT=E HT 0，说明R=C，无差错；否则出错。RHT=E HT的值仅与差错图案E有关，而和码字C无关。定义伴随式S=(sn-k-1,s1,s0)=RHT=E HT第44页，此课件共62页哦伴随式译码

19、S=(sn-k-1,s1,s0)=RHT=E HT接收端收到R后，可计算伴随式S，从而得到E和C。由于S只有2n-k种可能组合，而差错图案E有2n种可能组合，同一伴随式可能对应若干个不同的差错图案。译码的关键是由S确定E。第45页，此课件共62页哦编码mGRHT=0计算E输出R+EmCER输出RyesnoC编译码过程框图第46页，此课件共62页哦可通过解线性方程来求解ES=(sn-k-1,s1,s0)=RHT=E HT=(en-1,e1,e0)HT少n-(n-k)=k个方程，有2k个解第47页，此课件共62页哦概率译码把所有解的重量作比较，选择最轻的作为E的估值。由于p1，第48页，此课件共6

20、2页哦构造标准阵列译码表1.用概率译码确定各伴随式对应的差错图案将S的各种可能取值代入线性方程组，对应每个S都有2k个解，取重量最小者为E的估值。2.确定标准阵列译码表的第一行和第一列在第一行的2k位置放2k码字，第一个放全零码在第一列的2n-k位置放2n-k最轻解，重量轻者在前。首行存放全零S所对应的零重量全零差错图案E0。第2到n1行填上所有重量为1的差错图案，n个再后面填入两个差错的图案，最多 直到放满2n-k行3.在码表的第j行第i列填入CiEjn2()第49页，此课件共62页哦标准阵列译码表S0S1S2S2n-k-1第50页，此课件共62页哦例：某一个（5，2）系统线性码的生成矩阵为

21、设接收码R（10101），请先构造该码的标准阵列译码表，然后译出发送码的估值。第51页，此课件共62页哦04第52页，此课件共62页哦伴随式有8种组合，对应到8个最轻的差错图案列出方程组：S2=e4+e3+e2S1=e4+e1S0=e4+e3+e0第53页，此课件共62页哦第54页，此课件共62页哦画出标准阵列译码表第55页，此课件共62页哦00000101110110111010列出方程组：S2=e4+e3+e2S1=e4+e1S0=e4+e3+e0第56页，此课件共62页哦00000000101110110111010111100001010100010000100010000100010

22、0001第57页，此课件共62页哦0000000010111011011101011110000101010001000010001000010001000010110001111000110第58页，此课件共62页哦0000000010111011011101011110000001111110101010101010001111100101100101000010010011010011111001000010101010111111000001000011011001100110110110001110100011101100111000110100010101111100第59页，此课

23、件共62页哦若接收码R=(10101),可用以下三种方法之一译码。直接搜索码表先求伴随式，找到伴随式所在行，再搜索码表的行找到列先求伴随式，确定差错图案，再与接收码字相加得到码字。第60页，此课件共62页哦0000000010111011011101011110000001111110101010101010001111100101100101000010010011010011111001000010101010111111000001000011011001100110110110001110100011101100111000110100010101111100第61页，此课件共62页哦译码后的错误概率任意译码方案的错误概率是译码器输出一个错误码字的概率。也称剩余错误率。能检测并纠正m个错误的码的错误概率是第62页，此课件共62页哦