第7章加密编码(新).ppt

*,*,Click to edit Master title style,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,第,6,章 信道编码,信道编码,是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：,如何正确接收载有信息的信号,线路编码,如何避免少量差错信号对信息内容的影响,纠错编码,1,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,本章内容,有扰离散信道的编码定理,纠错编译码的基本原理与分析方法,线性分组码,卷积码,编码与调制的结合,TCM,码,运用级联、分集与信息迭代概念的纠错码,2,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1,有扰离散信道的编码定理,差错和差错控制系统分类,矢量空间与码空间,随机编码,信道编码定理,3,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错类型,差错符号,：由符号发生差错引起，也叫,信号差错,，信号差错概率用,误码元率,表示,差错比特,：由信息比特发生差错引起，也叫,信息差错,，信息差错概率用,误比特率,表示,对于,二进制,传输系统，符号差错等效于比特差错；,对于,多进制,系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。,4,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错图样（,error pattern,）,定量地描述信号的差错，收、发码之“差”：,差错图样,E,发码,C,收码,R,（模,M,）,例：,8,进制,(M=8),码元，,若发码,C=,（,0,2,5,4,7,5,2,）,收码变为,R=,（,0,1,5,4,7,5,4,）,差错图样,E,=,C,R,=,（,0,1,0,0,0,0,6,）（模,8,）,二进制码：,E=C,R,或,C=R,E,，,差错图样中的“”既是符号差错也是比特差错，差错的个数叫汉明距离。,5,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错图样类型,随机差错,：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；,突发差错：,前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。,6,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,纠错码分类,从功能角度,：检错码、纠错码,对信息序列的处理方法,：分组码、卷积码,码元与原始信息位的关系,：线性码、非线性码,差错类型,：纠随机差错码、纠突发差错码、介于中间的纠随机,/,突发差错码。,构码理论,：代数码、几何码、算术码、组合码等,7,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错控制系统分类,前向纠错（,FEC,）,：,发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错,反馈重发（,ARQ,）：,收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码,混合纠错（,HEC,）：,前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力,8,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.2,矢量空间与码空间,F,表示码元所在的数域，对于二进制码，,F,代表二元域,0,1,设,n,重有序元素的集合,V=,V,i,若满足条件：,V,中矢量元素在矢量加运算下构成加群；,V,中矢量元素与数域,F,元素的标乘封闭在,V,中；,分配律、结合律成立，,则称集合,V,是数域,F,上的,n,维,矢量空间,，或称,n,维,线性空间,，,n,维矢量又称,n,重,(,n,-tuples,),。,9,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间中矢量的关系,对于域,F,上的若干矢量,线性组合,：,线性相关,：,其中任一矢量可表示为其它矢量的线性组合,线性无关,或,线性独立,：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。,10,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间与基底,一组线性无关的矢量 ，线性组合的,集合,就构成了一个,矢量空间,V,，,这组矢量 就是这个矢量空间的,基底,。,n,维矢量空间应包含,n,个基底,基底不是唯一的,，例：线性无关的两个矢量（,1,0,）和（,0,1,）以及（,-1,0,）和（,0,-1,）可张成同一个两维空间。,11,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,二元域,GF(2),上三重矢量空间,以（,100,）为基底可张成,一维三重,子空间,V,1,，含,2,1,=2,个元素，即,以,(010)(001),为基底可张成,二维三重,子空间,V,2,，含,2,2,=4,个元素，即,以,(100)(010)(001),为基底可张成,三维三重,空间,V,含,2,3,=8,个元素，,V,1,和,V,2,都是,V,的子空间。,12,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间,每个矢量空间或子空间中必然包含零矢量,两个,矢量正交,：,V,1,V,2,0,两个,矢量空间正交,：某矢量空间中的任意元素与另一矢量空间中的任意元素正交,正交的两个子空间,V,1,、,V,2,互为,对偶空间,(Dual Space),，,其中一个空间是另一个空间的,零空间,（,null space,，,也称零化空间）。,13,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,码空间,消息,k,长,(,n,k,),码字,n,长,q,k,种 分组编码器,q,n,种,k,维,k,重矢量,n,维,n,重矢量,通常,q,n,q,k,，分组编码的任务是要在,n,维,n,重矢量空间的,q,n,种可能组合中选择其中的,q,k,个构成一个,码空间,，其元素就是许用码的,码集,。,14,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,分组编码的任务,选择一个,维,n,重子空间作为码空间。,确定由,k,维,k,重信息空间到,维,n,重码空间的映射方法。,码空间的不同,选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。,15,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3,随机编码,运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作,随机码界,。,用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。,16,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3,随机编码,在,(N,K),分组编码器中随机选定的码集有,q,NM,种,第,m,个码集,(,记作,c,m,),被随机选中的概率是,设与这种选择相对应的条件差错概率是,P,e,(c,m,),全部码集的平均差错概率是,17,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3,随机编码,必定存在某些码集,某些码集,若,，就必然存在一批码集,即差错概率趋于零的好码一定存在,18,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3,随机编码,码集点数,M,=,q,K,占,N,维矢量空间总点数,q,N,的比例是,F,=,q,K,/,q,N,=,q,-,(,N-K,),当,K,和,N,的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。,当,F,0,即,(,N-K,),时，能否让平均差错概率？,Gallager,在,1965,年推导了 的上边界，并证明这个上边界是按指数规律收敛的。,19,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,E,(,R,),为,可靠性函数,，也叫误差指数,码率,：,R,=(,lb,M,),/,N,M,是可能的信息组合数，,M,=,q,K,N,是每码字的码元数，,R,表示每码元携带的信息量，单位是每符号比特（,bit/symbol,）,6.1.4,信道编码定理,20,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,R,在,0,R,0,区间时,E,(,R,),R,曲线是斜率为,-1,（,-45,）的直线，,E,(,R,),反,比于,R,；,而当,R,=,C,时,E,(,R,)=0,即可靠性为零。,E,(,R,),C,R,0,R,0,-45,E,(,R,),和,R,的关系曲线,6.1.4,信道编码定理,21,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,正定理,：只要传信率,R,小于信道容量,C,，,总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。,逆定理,：信道容量,C,是可靠通信系统传信率,R,的上边界，如果,R,C,，,就不可能有任何一种编码能使差错概率任意小。,6.1.4,信道编码定理,22,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2,纠错编译码的基本原理与分析,纠错编码的基本思路,译码方法最优译码与最大似然译码,23,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2.1,纠错编码的基本思路,R,不变,，信道容量大者其可靠性函数,E,(,R,),也大；,C,不变,，码率减小时其可靠性函数,E,(,R,),增大,E,(,R,),R,0,R,1,R,2,C,1,C,2,增大,E,(,R,),的途径,24,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2.1,纠错编码的基本思路,增大信道容量,C,扩展带宽,加大功率,降低噪声,减小码率,R,Q,、,N,不变而减小,K,Q,、,K,不变而增大,N,N,、,K,不变而减小,Q,增大码长,N,25,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2.2,最优译码与最大似然译码,译码器的任务,是从受损的信息序列中尽可能正确地恢复出原信息。,译码算法的已知条件是：,实际,接收到的码字序列,r,r,=,(,r,1,r,2,r,N,),发端所采用的编码算法和该算法产生的码集,X,N,满足,信道模型及信道参数。,26,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,最佳译码,，也叫最大后验概率译码,(MAP),最大似然译码,(MLD),6.2.2,最优译码与最大似然译码,消息组,m,i,码字,c,i,接收码,r,估值,消息,编码器 信道 译码 消息还原,27,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,如果,构成码集的,2,K,个码字以相同概率发送，满足,P,(,c,i,)=1/2,K,，,i,=1,2,2,K,P,(,r,),对于任何,r,都有相同的值，满足,P,(,r,)=1/2,K,则,P,(,c,i,/,r,),最大等效于,P,(,r,/,c,i,),的最大，在此前提下最佳译码等效于最大似然译码。,6.2.2,最优译码与最大似然译码,28,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,对于无记忆信道，,例：,BSC,信道的最大似然译码可以简化为,最小汉明距离译码,。,汉明距离译码是一种硬判决译码。由于,BSC,信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。,6.2.2,最优译码与最大似然译码,29,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3,线性分组码,消息,m (,n,k,),码字,c,m=(,m,k-,1,m,1,m,0,),分组编码器,c=(,c,n-,1,c,1,c,0,),q,k,出错越少的情况，发生概率越大，,E,的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。,47,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,标准阵列译码表,上述的概率译码，如每接收一个码,R,就要解一次线性方程，那就太麻烦了。好在伴随式,S,的数目是有限的,2,n-k,个，如果,n-k,不太大，我们可以预先把不同,S,下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做,标准阵列译码表,。,48,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,表中所列码字是接收到的码字,R,；,将没有任何差错时的收码,R,放在第一行，收码等于发码,R=,C(C,C,i,i,=0,1,2,k,-1,),差错图案为全零,E,0,=(,0,00,),，,伴随式为全零,S,0,=(,0,00,),。,由于有,2,k,个码字，码表有,2,k,列。,在,第,2,到第,n,+1,的,n,行中差错图案的所有重量为,1(,共,n,个,),。,如果,(1+,n,)2,n-k,，,再在下面行写出全部带有,2,个差错的图案,(,共 个,),。,如果总行数,(1+,n,+),仍然小于,2,n-k,，,再列出带有,3,个差错的图案，以此类推，直到放满,2,n-k,行，每行一个,E,j,对应一个不同的伴随式,S,j,。,这样，表的行数,2,n-k,正好等于伴随式的数目。,标准阵列译码表的构成,49,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,S,0,E,0,S,1,E,1,S,j,E,j,E,0,+C,0,=0+0=0,E,0,+C,1,=C,1,E,0,+C,i,=,C,i,E,1,+C,0,=E,1,E,1,+,C,i,E,j,+C,0,=,E,j,E,j,+,C,1,E,j,+,C,i,标准阵列译码表,E,1,+C,1,50,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,陪集和子集,译码表中有,2,n-k,行，每行是一个,陪集,，每陪集的第一个元素,(,位于第一列,),叫,陪集首,。同一陪集（同一行）中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式,S,0,所对应的全零差错图案,E,0,(,无差错,),，而第,j,行陪集的陪集首是伴随式,S,j,所对应的重量最小的差错图案,E,j,(C,0,=0,R,j,=,E,j,),。,译码表中有,2,k,列，每列是一个,子集,，每子集的第一个元素,(,位于第一行,),叫,子集头,。同一子集（同一列）中的所有元素对应同一个码字，第一列子集的子集头是全零码字,C,0,，,而第,i,列子集的子集头是码字,C,i,(E,0,=0,R,i,=,C,i,),。,51,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例,6-3,一个,(5,2),系统线性码的生成矩阵是,G=,设收码,R=(10101),，,构造标准阵列译码表，译出发码的估值,解：,(1),构造标准阵列译码表。分别以信息组,m=(00),、,(01),、,(10),、,(11),及已知的,G,求得,4,个许用码字为,C,1,=(00000),、,C,2,=(10111),、,C,3,=(01101),、,C,4,=(11010),。,求出校验矩阵：,H=P,T,I,3,=,列出方程组：,52,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,伴随式有,2,n,-,k,2,3,8,种组合，差错图案中代表无差错的有一种，代表一个差错的图案有 种，已有,6,种。,代表两个差错的图案有 种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将,E,j,=(00000),、,(10000),、,(01000),、,(00100),、,(00010),、,(00001),代入上面的线性方程组，解得对应的,S,j,分别是,(000),、,(111),、,(101),、,(100),、,(010),、,(001),。剩下的伴随式中，,(011),所对应的差错图案是,2,k,个即,(00011),、,(10100),、,(01110),、,(11001),其中,(00011),和,(10100),并列重量最轻，任选其中一个如,(00011),。同样可得伴随式,(110),所对应的最轻差错图案之一是,(00110),。,例,6-3,译码表的构成,53,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,S,0,=000,E,0,+C,0,=00000,C,1,=10111,C,2,=01101,C,3,=11010,S,1,=111,E,1,=10000,00111,11101,01010,S,2,=101,E,2,=01000,11111,00101,10010,S,3,=100,E,3,=00100,10011,01001,11110,S,4,=010,E,4,=00010,10101,01111,11000,S,5,=001,E,5,=00001,10110,01100,11011,S,6,=011,E,6,=00011,10100,01110,11001,S,7,=110,E,7,=00110,10001,01011,11100,例,6-3,标准阵列译码表,54,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例,6-3,将接收码,R,10101,译码,可选以下三种方法之一译码：,直接搜索码表，查得,(10101),所在列的子集头是,(10111),，因此译码输出取为,(10111),。,先求伴随式,RHT=(10101),HT=(010)=S,4,，,确定,S,4,所在行，再沿着行对码表作一维搜索找到,(10101),最后顺着所在列向上找出码字,(10111),。,先求出伴随式,RHT=(010)=S,4,并确定,S,4,所对应的陪集首（差错图案）,E,4,=(00010),，,再将陪集首与收码相加得到码字,C=R+E,4,=(10101)+(00010)=(10111),。,上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。,55,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,对上例作进一步分析，还可以看到，该,(5,2),码的,d,min,=3,纠错能力是,t,=INT(3-1)/2=1,。,因此，译码阵列中只有前,6,行具有唯一性、可靠性，真正体现了最大似然译码准则，而第,7,、,8,行的差错图案,(00011),和,(00110),中包含两个“,1”,，已超出了,t,=1,的纠错能力，译码已不可靠。比如，当收码,R,(10100),时，根据码表译出的码字是,(10111),，与收码,R,的汉明距离是,2,，然而收码,R,与全零码字,(00000),的汉明距离也是,2,，为什么不能译成,(00000),呢？事实上，码表的第,7,、,8,行本身就不是唯一的。注意在码表计算过程中，伴随式,(011),所对应的,4,个差错图案中有两个并列重量最轻，如果当时选的不是,(00011),而是,(10100),，那么码表第,7,行就不是现在这样了。,对例,6-3,的,分析,56,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.3,码距、纠错能力、,MDC,码及重量谱,N,重码矢,c,=(,c,n,-1,c,n,-2,c,1,c,0,),可与,N,维矢量空间,X,N,中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集,发码一定在这个子集里，传输无误时的收码也一定位于该子集,当出现差错时，接收的,N,重矢量,:,对应到子集外空间某一点,对应到该子集，却对应到该子集的另一点上,57,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,t,d=,7,d,min,=,3,d=,5,C,1,C,2,C,3,C,4,C,5,码集各码字间的距离是不同的，码距最小者决定码的特性，称之为,最小距离,d,min,这里,d,min,=3,，,纠错能力是,1,，检错能力是,2,6.3.3,码距、纠错能力、,MDC,码及重量谱,58,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,定理,6.1,任何最小距离,d,min,的线性分组码，其检错能力为（,d,min,-1,）,纠错能力,t,为,定理,6.2,线性分组码的最小距离等于码集中非零码字的最小重量,d,min,=min w(,C,i,),C,i,C,及,C,i,0,6.3.3,码距、纠错能力、,MDC,码及重量谱,59,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,定理,6.3,(,n,k,),线性分组码最小距离等于,d,min,的充要条件是：校验矩阵,H,中有（,d,min,-1),列线性无关。,定理,6.4,(,n,k,),线性分组码的最小距离必定小于等于,(,n-k,+1),d,min,(,n-k,+1),6.3.3,码距、纠错能力、,MDC,码及重量谱,60,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例：,H,(7,，,4),线性码,各列都不相同，任意,2,列之和不等于,0,，,2,列线性无关；任意,2,列之和一定等于矩阵中某一列，任意,3,列线性相关。所以该码的最小距离为,3,，小于,n-k,+1,4,。,6.3.3,码距、纠错能力、,MDC,码及重量谱,61,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,（,n,k,）,线性码最小距离,d,min,的上边界是,n-k,+1,。,如果我们设计的（,n,k,）,线性码,的,d,min,达到了,n-k,+1,，,就是达到了设计性能的极点。因此，,d,min,n-k,+1,的码称为,极大最小距离码,(MDC,Maximized minimum Distance Code,),。,总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关。,6.3.3,码距、纠错能力、,MDC,码及重量谱,62,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,任何一个二元,(,n,k,),线性分组码都有,2,n-k,个伴随式，假如该码的纠错能力是,t,，,则对于任何一个重量小于等于,t,的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件,上式称作,汉明限,，任何一个纠,t,码都应满足上述条件。,6.3.4,完备码,(Perfect code),63,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.4,完备码,某二元,(,n,k,),线性分组码能使等式,成立，即该码的伴随式数目不多不少恰好和不大于,t,个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于,t,的差错图案选作陪集首，而没有一个陪集首的重量大于,t,，,这时的校验位得到最充分的利用。这样的二元,(,n,k,),线性分组码称为,完备码,。,64,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,汉明码,(Hamming Code),汉明码不是指一个码，而是代表一类码。,汉明码的纠错能力,t,=1,，,既有二进制的，也有非二进制的。二进制时，汉明码码长,n,和信息位,k,服从以下规律：,(,n,k,)=(2,m,-1,2,m,-1-,m,),其中,m,=,n-k,，,是正整数。,当,m,3,、,4,、,5,、,6,、,7,、,8,时，有汉明码,(7,4),、,(15,11),、,(31,26),、,(63,57),、,(127,120),、,(255,247),。,汉明码是完备码，因为它满足上述等式。,65,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,汉明码校验矩阵的构成,汉明码的校验矩阵,H,具有特殊的性质，能使构造方法简化。一个,(,n,k,),码的校验矩阵有,n,k,行和,n,列，二进制时,n-k,个码元所能组成的列矢量总数是,2,n-k,-1,恰好和校验矩阵的列数,n,=2,m,-1,相等。只要排列所有列，通过列置换将矩阵,H,转换成系统形式，就可以进一步得到相应的生成矩阵,G,。,66,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例,6.4,构造一个,m,=3,的二元,(7,，,4),汉明码。,解：先利用汉明码的特性构造一个,(7,，,4),汉明码的校验矩阵,H,，,再通过列置换将它变为系统形式：,0 0 0 1 1 1 1,列置换,1 1 1 0 1 0 0,H=0 1 1 0 0 1 1,0 1 1 1 0 1 0 =P,T,I,3,1 0 1 0 1 0 1 1 1 0 1 0 0 1,再得生成矩阵,G,为,1 0 0 0 1 0 1,G=I,4,P=0 1 0 0 1 1 1,0 0 1 0 1 1 0,0 0 0 1 0 1 1,67,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,高莱（,Golay,）,码,是二进制（,23,，,12,）线性码，,其最小距离,d,min,7,，,纠错能力,t,=3,。,是完备码，因为满足等式,2,23-12,=2048=,在,(23,12),码上添加一位奇偶位即得二进制线性（,24,，,12,）扩展高莱码，其最小距离,d,min,8,。,68,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.5,循环码,循环码是线性码的一个子类,；,满足下列循环移位特性：码集,C,中任何一个码字的循环移位仍是码字。,69,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,循环码的多项式描述,一般,(,n,k,),线性分组码的,k,个基底之间不存在规则的联系，因此需用,k,个基底组成生成矩阵来表示一个码的特征。,而循环码的,k,个基底可以是同一个基底循环,k,次得到，因此用一个基底就足以表示一个码的特征。,既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了。,70,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,把码字,C,c,n,-1,c,n,-2,c,1,c,0,与一个不大于,n,-1,次的,码多项式,C,(,x,),对应,起来。,码多项式,C,(,x,),定义为：,C,(,x,)=,c,n,-1,x,n,-1,+,c,n,-2,x,n,-2,+,+,c,1,x,+,c,0,对于二进制码，,c,i,0,1,i,=0,，,n,-1,。,循环码的多项式定义,71,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,循环移一位：,(,c,n,-1,c,n,-2,c,1,c,0,)(,c,n,-2,c,1,c,0,c,n,-1,),循环移一位：,C,0,(,x,)=,c,n,-1,x,n,-1,+,c,n,-2,x,n,-2,+,c,1,x,+,c,0,C,1,(,x,)=,c,n,-2,x,n,-1,+,c,n,-3,x,n,-2,+,c,0,x,+,c,n,-1,比较循环移位的前后，可用如下的多项式运算来表达循环移位,移,1,位：,C,1,(,x,)=,xC,0,(,x,),mod(,x,n,+1),移,2,位：,C,2,(,x,)=,xC,1,(,x,)=,x,2,C,0,(,x,),mod(,x,n,+1),移,n-,1,位：,C,n-,1,(,x,)=,xC,n,-2,(,x,)=,x,n-,1,C,0,(,x,),mod(,x,n,+1),循环码的循环移位,72,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,码字的组成,根据码空间的封闭性，码字的线性组合仍是码字。,C,(,x,)=,a,0,C,0,(,x,)+,a,1,xC,0,(,x,)+,a,2,x,2,C,0,(,x,)+,a,n,-1,x,n,-1,C,0,(,x,),=(,a,0,+,a,1,x,+,a,2,x,2,+,a,n,-1,x,n,-1,),C,0,(,x,),=,A,(,x,),C,0,(,x,),mod(,x,n,+1),其中,C,0,(,x,),是一个码多项式，而,A,(,x,),是次数不大于,n,-1,的任意多项式。对于二进制码，,a,i,0,1,i,=0,，,n,-1,。,73,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,生成多项式,C,(,x,)=,m,(,x,),g,(,x,),码多 信息 生成,项式 多项式 多项式,生成多项式不是唯一的；,g,(,x,),x,n-k,+,g,n-k,-1,x,n-k,-1,+,g,2,x,2,+,g,1,x,+1,是,(,n-k,),次的,首一,码,多项式，即,(,n-k,),次项的系数为,1,。,g,(,x,),一定是,(,x,n,+1),的因子。,74,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,校验多项式,多项式,x,n,+1,可因式分解为,x,n,+1,g,(,x,),h,(,x,),的形式；,如果,g,(,x,),代表,(,n,，,k,),循环码的生成多项式，则,h,(,x,),代表该循环码的,一致校验多项式,，其阶次为,k,。,h,(,x,),的校验作用表现在：任何码多项式,C,(,x,),与,h,(,x,),的模,x,n,+1,乘积一定等于,0,，而非码字与,h,(,x,),的乘积必不为,0,。,C,(,x,),h,(,x,)=,m,(,x,),g,(,x,),h,(,x,)=,m,(,x,)(,x,n,+1)=0 mod(,x,n,+1),75,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例,6.5,研究一个长度,n,=7,的循环码的构成方法,(1),对,(,x,7,+1),作分解，找出,n,-,k,次因式。,x,7,+1,(,x,+1)(,x,3,+,x,2,+1)(,x,3,+,x,+1),，,n,-,k,因式,g(,x,),对偶式,h(,x,),循环码,1 (,x,+1),(,x,3,+,x,2,+1)(,x,3,+,x,+1)(7,6),3 (,x,3,+,x,2,+1)(,x,+1)(,x,3,+,x,+1)(7,4),3 (,x,3,+,x,+1)(,x,+1)(,x,3,+,x,2,+1)(7,4),4 (,x,+1)(,x,3,+,x,2,+1)(,x,3,+,x,+1)(7,3),4 (,x,+1)(,x,3,+,x,+1)(,x,3,+,x,2,+1)(7,3),6 (,x,3,+,x,2,+1)(,x,3,+,x,+1),(,x,+1)(7,1),76,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,构成,(7,3),循环码：,选,g,(,x,)=(,x,+1)(,x,3,+,x,+1)=(,x,4,+,x,3,+,x,2,+1),，则,C,(,x,)=,m,(,x,),g,(,x,)=(,m,2,x,2,+,m,1,x,+,m,0,)(,x,4,+,x,3,+,x,2,+1),。,当输入信息,m=,(011),时，,m,(,x,)=(,x,+1),，,C,(,x,)=(,x,+,1)(,x,4,x,3,x,2,1)=,x,5,+,x,2,+,x,1,+,1,，,对应码矢,C,=(0100111),。,例,6.5,研究一个长度,n,=7,的循环码的构成方法,77,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,信息矢量,m,(m,2,m,1,m,0,),码矢,C,(c,6,c,5,c,4,c,3,c,2,c,1,c,0,),000,001,010,011,100,101,110,111,0000000,0011101,0111010,0100111,1110100,1101001,1001110,1010011,例,6.5,研究一个长度,n,=7,的循环码的构成方法,78,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,系统循环码,码字的前,k,位原封不动照搬信息位而后面,(,n,k,),位为校验位：,C,(,x,)=,x,n-k,m,(,x,)+,r,(,x,),产生系统循环码的方法：,将信息多项式,m,(,x,),预乘,x,n-k,，,即右移（,n-k,）,位；,将,x,n-k,m,(,x,),除以,g,(,x,),，,得余,式,r,(,x,),；,得系统循环码的码多项式：,C,(,x,)=,x,n-k,m,(,x,),+,r,(,x,),。,79,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例,6.6,(7,3),循环码生成多项式是,g,(,x,)=,x,4,+,x,3,+,x,2,+1,，,用式,(6-3-35),产生系统循环码。,解,：先以输入信息,m,=(011),即,m,(,x,)=(,x,+1),为例，,.,x,n-k,m,(,x,)=,x,4,(,x,+1)=,x,5,+,x,4,.(,x,5,+,x,4,),除以,(,x,4,+,x,3,+,x,2,+,1),，,得余式,(,x,3,+,x,),.,C,(,x,)=,x,n-k,m,(,x,),+,r,(,x,),(,x,5,+,x,4,)+(,x,3,+,x,),对应码矢,(0111010),。,依次将,(000)(111),代入，可得全部码矢如表,6-6,。此表与表,6-5,对比，可见码集未变而映射规则变了，表,6-6,满足系统循环码要求。,80,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,扩展码,如果给每个码字添加一位奇偶校验位,c,校,，构成（,n,1,，,k,）,线性码，称为,扩展码,。,c,n-,1,c,1,c,0,c,n-,1,c,1,c,0,c,校,c,n,1,c,1,c,0,c,校,0,在二进制偶校验时：,原来码字中,1,的个数为偶数，则添加校验位,0,；,原来码字中,1,的个数为奇数，则添加校验位,1,。,如果某码原来的最小重量,d,min,是奇数，则新的最小距离变为,d,min,+1,，,检错能力增,1,。,校验矩阵,H,e,H,81,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,缩短码,把第一位为,1,的所有码字舍去，剩下另一半第一位为,0,的码字舍去它们的第一位后组成一个新的,(,n,1,，,k,1),码，称为,缩短码,。,码,长,n,1,和信息位长度,k,1,均缩短了。,(,n,1,，,k,1),缩短码共包含,2,k,2=2,k,-1,个码字。,由于原先保留的均是第一位为,0,的码，舍去它们的第一位不会改变码的最小重量，因此缩短码与原码具有同样的,d,min,。,称为（,n,-1,k,-1,d,min,）,缩短码。,82,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例：,(7,4),码的生成矩阵为,47,m,3,m,2,m,1,m,0,c,i,2,c,i,1,c,i,0,0 0 0 0 0 0 0,0 0 0 1 0 1 1,0 0 1 0 1 1 0,0 0 1 1 1 0 1,0 1 0 0 1 1 1,0 1 0 1 1 0 0,0 1 1 0 0 0 1,0 1 1 1 0 1 0,C,i,mG,m,3,m,2,m,1,m,0,码字中的,c,6,去掉，,c,6,是信息位,m,与,G,的第一列相乘结果，所以,G,的第一列应去掉；,m,3,去掉，而,m,3,是与,G,的第一行相乘，所以,G,的第一行也去掉。,83,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,得到新的生成矩阵为,G,36,原来的校验矩阵,H,为,H,37,校验时，计算,rH,T,，因,r,的第一位已没有，故,H,T,的第一行应去掉，即,H,的第一列去掉。得到新的校验矩阵,H,为,H,d,min,不变，为,3,。,36,84,普通高等教育“十五”国家级规划教材信息论与编码 曹