信息论与编码第6章(2).ppt

信道编码,1,6.3线性分组码,2,线性分组码,3,Ggk1,gk210,.g,g,T,线性分组码的码空间C是由k个线性无关的基底gk-1,，g1，g0张成的k维n重子空间，所有码字都可写成k个基底的线性组合，即c=mk-1gk-1+m1g1+m0g0如果gi表示第i个基底，并写成行矩阵的形式gigi(n1),gi(n2),.gi1,gi0,k个基底可以排列成k行n列的形式，如下所示：,.g(k1)1.g11.g01,g(k1)(n1).g1(n1)g0(n1),g(k1)0.g10g00,6.3.1生成矩阵和校验矩阵,4,码空间中任何一个码字都可以写成基底的线性组合，即：Ccn1,cn2,.,c1,c0mk1gk1mk2gk2.m1g1m0g0mG当信息元确定后，码字仅由G矩阵决定，因此我们称这kn矩阵G为该(n,k)线性分组码的生成矩阵。如果已知线性分组码的生成矩阵，则任何一个k位信息组对应的码字都可以由mG运算得到。,生成矩阵,5,(n,k)线性分组码共有多少个码字?,问题,答：2k个码字。,6,想要保证(n,k)线性分组码能够构成k维n重子空间，G的k个行矢量gk-1,g1,g0必须是线性无关的，只有这样才符合作为基底的条件。由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。,生成矩阵G(kn)的特点,7,已知(7,4)线性分组码的生成矩阵为如果输入的四位信息组为m0,1,1,0时，其对应的码字为：,举例,8,(n,k)码的任何生成矩阵都可以通过行运算（不改变码集，只改变映射规则）简化成“系统形式”。,Ik是kk单位矩阵，P是k(n-k)矩阵。,系统形式的生成矩阵,9,前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的（n,k）码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。,系统码,10,已知(7,3)线性分组码的生成矩阵为如果输入的三位信息组为m0,1,1时，其对应的码字为：特点：码字的前面k位就是信息组中的k位，而后面的校验位为信息组的线性组合。,系统码,11,n维n重空间有相互正交的n个基底选择k个基底构成码,空间C选择另外的(n-k)个基底构成空间DC和D是对偶的,空间构成,12,将D空间的n-k个基底排列起来可构成一个(n-k)n矩阵，称为校验矩阵H，也称监督矩阵。用来校验接收到的码字是否是正确的；即：若c为码空间C中的任意码字，则若不满足此等式，则c必定不是码空间C中的码字。,校验矩阵,13,G是(n,k)码的生成矩阵，H是它的校验矩阵；H是(n,n-k)对偶码的生成矩阵，它的每一行是对偶码的一个码字。G则是它的校验矩阵。GHT=0，HPTIn-k，二进制时，负号可省略。,校验矩阵,14,校验矩阵与生成矩阵的关系,15,某线性分组码，其生成矩阵是,求：,(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r=100110,检验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。,111010G=110001011101,例6-2,16,码集与映射关系,信息000001010011100101110111,码字000000011101110001101100111010100111001011010110,系统码字000000001011010110011101100111101100110001111010,例6-2,17,二元(6,3)线性分组码编码器,例6-2,18,下面是某线性二元码的全部码字：,求n,k的值；构造这码的生成矩阵G；构成这码的一致校验矩阵H。,C1000000C2001111,C3010001,C4011110,C5100011,C6101100,C71110010,C8111101,举例,19,定义差错图案EE(en1,e1,e0)RC(rn-1cn-1,r1c1,r0c0)二进制码中模2加与模2减是等同的，因此有,E=RC及,R=CE,6.3.2伴随式与标准阵列译码,20,因为CHT=0,所以RHT(CE)HTCHTEHT=EHT如果收码无误：必有RC即E0，则EHT=0RHT=0。如果收码有误：即E0，则RHT=EHT0。在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义RHT的运算结果为伴随式SS=(sn-k-1,s1,s0)=RHT=EHT,伴随式的定义,21,只要E正确，译出的码也就是正确的。,从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图案可能有相同的伴随式。接收端收到R后，因为已知HT，可求出SRHT；如果能知道对应的E，则通过C=RE而求得C。,伴随式的意义,22,译码过程框图,译码过程,23,差错图案E的求解(1),24,上述方程组中有n个未知数en1,e1,e0，却只有n-k个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-(n-k)=k个方程导致每个未知数有2k个解。概率译码：把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。,差错图案E的求解(2),25,依据：若BSC信道的差错概率是p，则长度n的码中错误概率,出错越少的情况，发生概率越大，E的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。显然，在进行概率译码时，每接收一个码字就要解一次线性方程，非常复杂麻烦。但如果nk不太大，我们可以预先把不同校正子S情况下的所有方程组都预先解出来，将各种情况下的最大概率译码输出列成一个标准阵列译码表。这样，在实际译码时就不必解方程，只要查译码表就可以了。,差错图案E的求解依据,26,伴随式S的数目是有限的2n-k个，如果n-k不太大，我们可以预先把不同S下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做标准阵列译码表。表中所列码字是接收到的码字R；将没有任何差错时的收码R放在第一行，收码等于发码R=C(CCi,i=0,1,2k-1),差错图案为全零E0=(0,00)，伴随式为全零S0=(0,00)。由于有2k个码字，码表有2k列。,标准阵列译码表的构成,27,在第2到第n+1的n行中差错图案的所有重量为1(共n个)。如果(1+n)2n-k，再在下面行写出全部带有2个差错的图案(共n个)。2,如果总行数(1+n+,差错的图案，以此类推，直到放满2n-k行，每行一个Ej,对应一个不同的伴随式Sj。这样，表的行数2n-k正好等于伴随式的数目。,n2)仍然小于2n-k，再列出带有3个,标准阵列译码表的构成,28,标准阵列译码表,29,解：(1)构造标准阵列译码表。分别以信息组m=(00)、(01)、(10)、(11)及已知的G求得4个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。,一个(5,2)系统线性码的生成矩阵是设收码R=(10101)，构造标准阵列译码表，译出发码,求出校验矩阵：,例6-3,30,列出方程组：s2e4h24e3h23e2h22e1h21e0h20e4e3e2s1e4h14e3h13e2h12e1h11e0h10e4e1s0e4h04e3h03e2h02e1h01e0h00e4e3e0由RHT确定S后，对应的E可以有2k(22=4)个解，究竟取哪一个作为差错图样E的解?最简单明了的处理方法是概率译码，即对所有2k个解的重量(差错图样E中1的个数)进行比较，选择重量最小的作为E的估值。由于E=R+C，E重量最小，就是R和C的汉明距离最小。,例6-3,31,例6-3,32,例6-3,标准阵列译码表,33,将接收码R10101译码可选以下三种方法之一译码：直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。先求伴随式RHT=(10101)HT=(010)=S4，确定S4所在行，再沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找出码字(10111)。先求出伴随式RHT=(010)=S4并确定S4所对应的陪集首（差错图案）E4=(00010)，再将陪集首与收码相加得到码字C=R+E4=(10101)+(00010)=(10111)。,例6-3,34,对例6-3的分析在制定标准阵列译码表的过程中，由S决定差错图案E时只有前6行真正体现了最大似然译码准则，而第7、8行的差错图案选择不是唯一的。比如第7行可有(00011)和(10100)两个选择，如果当时选的不是(00011)而是(10100)，那么码表第7行就不是现在这样了。那么在译码时最后的结果也就不一样了。为什么会出现这种情况呢？伴随式的个数2n-k与n、k及纠错能力t有一定的数量关系。,例6-3,35,N重码矢c=(cn-1,cn-2,c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集发码一定在这个子集里，传输无误时的收码也一定位于该子集当出现差错时，接收的N重矢量:对应到子集外空间某一点对应到该子集，却对应到该子集的另一点上,6.3.3码距、纠错能力、MDC码及重量谱,36,dmin=3td=7d=5,C1,C2,C3,C4,C5,码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmin,这里dmin=3，纠错能力是1，检错能力是2,码距,37,dmin=minw(Ci),CiC及Ci0,定理6.1任何最小距离dmin的线性分组码，其检错能力为（dmin-1）,纠错能力t为最小距离dmin表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力就越强，是衡量分组码性能的最重要的指标之一。定理6.2线性分组码的最小距离等于码集中非零码字的最小重量,纠错能力,38,于(n-k+1),即,dmin(n-k+1),定理6.3(n,k)线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。定理6.4(n,k)线性分组码的最小距离必定小于等,纠错能力,39,例：H,(7，4)线性码,各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k+14。,纠错能力,40,d02t1,(1)为检测e个错码，要求最小码距d0e1(2)为纠正t个错码，要求最小码距,(3)为纠正t个错码，同时检测e个错码，要求最小码距d0te1,最小码距与检错能力图示,41,（n,k）线性码最小距离dmin的上边界是n-k我们设计的（n,k）线性码的dmin达到了n-k达到了设计性能的极点。因此，dminn-k为极大最小距离码(MDCMaximized,+1。如果+1，就是+1的码称minimum,DistanceCode)。(1)二进制码中，除了将一位信息重复n次的（n,1）码外，不存在其它二进制MDC码；(2)非二进制码中，MDC码是存在的，如RS码（reed-solomon)。,MDC码(MaximizedminimumDistanceCode),42,含义：在码长n的码集里，包含重量为0的码字A0个，重量为1的码字A1个，-，重量为n的码字An个。,纠错能力t只是说明距离t的差错一定能纠，并非说距离大于t的差错一定不能纠。（除非完备码）总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关。把码距（码重）的分布特性称为距离（重量）谱，其中最小重量就是dmin。当所有码距相差不大时（重量谱为窄谱），性能较好。重量谱多项式表示：,重量谱,43,任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件,上式称作汉明限，任何一个纠t码都应满足上述条件。,6.3.4完备码(Perfectcode),44,某二元(n,k)线性分组码能使等式,成立，即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。这样的二元(n,k)线性分组码称为完备码。,2,nk,ti0,nI,完备码,45,汉明码的纠错能力t=1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-1-m)，其