第6章信道编码.ppt

《第6章信道编码.ppt》由会员分享，可在线阅读，更多相关《第6章信道编码.ppt（111页珍藏版）》请在三一办公上搜索。

1、1,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,第6章 信道编码,信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号线路编码如何避免少量差错信号对信息内容的影响纠错编码,2,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,本章内容,有扰离散信道的编码定理 纠错编译码的基本原理与分析方法线性分组码 卷积码编码与调制的结合TCM码运用级联、分集与信息迭代概念的纠错码,3,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1有扰离散信道的编码定理,差错和差错控制系统分类矢量空间与码空间 随机编码 信道编码

2、定理,4,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错类型,差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示对于二进制传输系统，符号差错等效于比特差错；对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。,5,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错图样（error pattern）,定量地描述信号的差错，收、发码之“差”：差错图样E发码C 收码R（模M）例：8进制(M=8)码元，若发码 C=（0,2,5,4,7,5

3、,2）收码变为 R=（0,1,5,4,7,5,4）差错图样E=CR=（0,1,0,0,0,0,6）（模8）二进制码：E=C R 或 C=R E，差错图样中的“”既是符号差错也是比特差错，差错的个数叫汉明距离。,6,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错图样类型,随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。,7,普通高等教育“十五”国家级规划教材信息论与编码

4、曹雪虹等编著,纠错码分类,从功能角度：检错码、纠错码 对信息序列的处理方法：分组码、卷积码码元与原始信息位的关系：线性码、非线性码 差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码、几何码、算术码、组合码等,8,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错控制系统分类,前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错 反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码 混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两

5、种能力,9,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.2矢量空间与码空间,F表示码元所在的数域，对于二进制码，F代表二元域0,1设n重有序元素的集合V=Vi,若满足条件：V中矢量元素在矢量加运算下构成加群；V中矢量元素与数域F元素的标乘封闭在V中；分配律、结合律成立，则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。,10,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间中矢量的关系,对于域F上的若干矢量线性组合：线性相关：其中任一矢量可表示为其它矢量的线性组合线性无关或线性独立：一组矢量中的任意一个都

6、不可能用其它矢量的线性组合来代替。,11,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间与基底,一组线性无关的矢量，线性组合的集合就构成了一个矢量空间V，这组矢量 就是这个矢量空间的基底。n维矢量空间应包含n个基底 基底不是唯一的，例：线性无关的两个矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可张成同一个两维空间。,12,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,二元域GF(2)上三重矢量空间,以（100）为基底可张成一维三重子空间V1，含21=2 个元素，即以(010)(001)为基底可张成二维三重子空间V2，含 22=4个元素，即以(

7、100)(010)(001)为基底可张成三维三重空间V,含 23=8个元素，V1和V2都是V的子空间。,13,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间,每个矢量空间或子空间中必然包含零矢量两个矢量正交：V1V2 0 两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交 正交的两个子空间V1、V2互为对偶空间(Dual Space)，其中一个空间是另一个空间的零空间（null space，也称零化空间）。,14,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,码空间,消息k长(n,k)码字n长,qk 种 分组编码器 qn种 k维k重矢

8、量 n维n重矢量,通常qn qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。,15,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,分组编码的任务,选择一个维n重子空间作为码空间。确定由k维k重信息空间到维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。,16,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3随机编码,运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作

9、随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。,17,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3随机编码,在(N,K)分组编码器中随机选定的码集有qNM种 第m个码集(记作cm)被随机选中的概率是设与这种选择相对应的条件差错概率是Pe(cm)全部码集的平均差错概率是,18,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3随机编码,必定存在某些码集某些码集若，就必然存在一批码集 即差错概率趋于零的好码一定存在,19,普通高等教育“

10、十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3随机编码,码集点数M=qK占N维矢量空间总点数qN的比例是F=qK/qN=q-(N-K)当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。当F0 即(N-K)时，能否让平均差错概率？Gallager在1965年推导了 的上边界，并证明这个上边界是按指数规律收敛的。,20,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,E(R)为可靠性函数，也叫误差指数 码率：R=(lbM)/N M是可能的信息组合数，M=qKN是每码字的码元数，R表示每码元携带的信息量，单位

11、是每符号比特（bit/symbol）,6.1.4信道编码定理,21,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,R在0,R0区间时E(R)R曲线是斜率为-1（-45）的直线，E(R)反比于R；而当R=C时E(R)=0即可靠性为零。,6.1.4信道编码定理,22,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R C，就不可能有任何一种编码能使差错概率任意小。,6.1.4信道编码定理,23,普通高等教

12、育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2 纠错编译码的基本原理与分析,纠错编码的基本思路 译码方法最优译码与最大似然译码,24,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2.1纠错编码的基本思路,R不变，信道容量大者其可靠性函数E(R)也大；C不变，码率减小时其可靠性函数E(R)增大,25,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2.1纠错编码的基本思路,增大信道容量C 扩展带宽加大功率降低噪声减小码率R Q、N不变而减小K Q、K不变而增大NN、K不变而减小Q增大码长N,26,普通高等教育“十五”国家级规划教材信息论与编码

13、曹雪虹等编著,6.2.2最优译码与最大似然译码,译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。译码算法的已知条件是：实际接收到的码字序列r,r=(r1,r2,rN)发端所采用的编码算法和该算法产生的码集XN,满足 信道模型及信道参数。,27,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,最佳译码，也叫最大后验概率译码(MAP)最大似然译码(MLD),6.2.2最优译码与最大似然译码,消息组mi 码字ci 接收码r 估值 消息,编码器 信道 译码 消息还原,28,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,如果构成码集的2K个码字以相同概率发送，满足

14、P(ci)=1/2K，i=1,2,2K P(r)对于任何r都有相同的值，满足P(r)=1/2K 则P(ci/r)最大等效于P(r/ci)的最大，在此前提下最佳译码等效于最大似然译码。,6.2.2最优译码与最大似然译码,29,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,对于无记忆信道，例：BSC信道的最大似然译码可以简化为最小汉明距离译码。汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。,6.2.2最优译码与最大似然译码,30,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3 线性分组码,消息m(n

15、,k)码字c,m=(mk-1,m1,m0)分组编码器 c=(cn-1,c1,c0)qk qn,码集C能否构成n维n重矢量空间的一个k维n重子空间？如何寻找最佳的码空间？qk个信息元组以什么算法一一对应映射到码空间。码率编码效率：Rc=k/n,31,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.1生成矩阵和校验矩阵,c m G 1n 1k kn 码字 消息 生成矩阵 Ggk-1g1g0T，有k个(1n)行矢量，如何选择呢？,32,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,线性分组码的形成,c=mk-1 gk-1+m1 g1+m0 g0 码空间的所有元素

16、（即码字）都可以写成k个基底的线性组合由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。当信息元确定后，码字仅由G矩阵决定，因此我们称这kn 矩阵G为该(n,k)线性分组码的生成矩阵。,33,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,生成矩阵G(kn)的特点,想要保证(n,k)线性分组码能够构成k维n重子空间，G 的k个行矢量gk-1,g1,g0必须是线性无关的，只有这样才符合作为基底的条件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。,34,普通高等教育“十五”

17、国家级规划教材信息论与编码 曹雪虹等编著,系统形式的生成矩阵,(n,k)码的任何生成矩阵都可以通过行运算（以及列置换）简化成“系统形式”。G=Ik P=Ik是kk单位矩阵，P是k(n-k)矩阵。,35,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,生成的码字C,前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的（n,k）码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。,36,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,

18、系统码,若通过行运算和列置换能将两个生成矩阵G互等，则称这两个G等效。非系统码的G可通过运算转变为系统码的G。等效的两个G生成的两个(n,k)线性码也是等效的。因此，每个(n,k)线性码都可以和一个系统的(n,k)线性码等效。,37,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,空间构成,n维n重空间有相互正交的n个基底选择k个基底构成码空间C选择另外的(n-k)个基底构成空间HC和H是对偶的 CHT0,GHT=0,38,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,校验矩阵,将H空间的n-k个基底排列起来可构成一个(n-k)n矩阵，称为校验矩阵H。用来校验接收

19、到的码字是否是正确的；G是(n,k)码的生成矩阵，H是它的校验矩阵；H是(n,n-k)对偶码的生成矩阵，它的每一行是一个基底。G则是它的校验矩阵。GHT=0，H PT In-k，二进制时，负号可省略。,39,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例6-2(6,3)线性分组码，其生成矩阵是 G=求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r=100110,检验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。,1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1

20、 0 1,40,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例6-2 码集与映射关系,信息 码字 系统码字000 000000 000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010,41,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例6-2 二元(6,3)线性分组码编码器,m0m1m2 输入 输出 c0c1c2,42,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.2

21、伴随式与标准阵列译码,m C=(cn-1,c1,c0)R=(rn-1,r1,r0)(n,k)信道定义差错图案E E(en1,e1,e0)RC(rn-1cn-1,r1c1,r0c0)二进制码中模2加与模2减是等同的，因此有E=R C 及R=C E,43,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,伴随式S的定义,因为CHT=0 所以RHT(CE)HTCHTEHT=EHT如果收码无误：必有RC即E0，则EHT=0 RHT=0。如果收码有误：即E 0，则RHT=EHT 0。在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义伴随式S S=(sn-k-1,s1,s0

22、)=RHT=EHT,44,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图案可能有相同的伴随式。接收端收到R后，因为已知HT，可求出 SRHT；如果能知道对应的E，则通过C=RE而求得C。RHT=S?C=RE R S E C 只要E正确，译出的码也就是正确的。,伴随式S的意义,45,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错图案E的求解(1),可以通过解线性

23、方程求解E：S=(sn-k-1,s1,s0)=EHT=(en-1,e1,e0)得到线性方程组：sn-k-1=en-1h(n-k-1)(n-1)+e1h(n-k-1)1+e0 h(n-k-1)0 s1=en-1h1(n-1)+e1 h11+e0 h10s0=en-1h0(n-1)+e1 h01+e0 h00,46,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,上述方程组中有n个未知数en1,e1,e0，却只有n-k个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-(n-k)=k个方程

24、导致每个未知数有2k个解。因此，由上述方程组解出的E可以有2k个解。到底取哪一个作为附加在收码R上的差错图案E的估值呢？概率译码：把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。,差错图案E的求解(2),47,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,依据：若BSC信道的差错概率是p，则长度n的码中错误概率：0个错 1个错 2个错 n个错(1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于p 出错越少的情况，发生概率越大，E的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。

25、,48,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,标准阵列译码表,上述的概率译码，如每接收一个码R就要解一次线性方程，那就太麻烦了。好在伴随式S的数目是有限的2n-k个，如果n-k不太大，我们可以预先把不同S下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做标准阵列译码表。,49,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,表中所列码字是接收到的码字R；将没有任何差错时的收码R放在第一行，收码等于发码R=C(CCi,i=0,1,2k-1),差错图案为全零

26、E0=(0,00)，伴随式为全零S0=(0,00)。由于有2k个码字，码表有2k列。在第2到第n+1的n行中差错图案的所有重量为1(共n个)。如果(1+n)2n-k，再在下面行写出全部带有2个差错的图案(共 个)。如果总行数(1+n+)仍然小于2n-k，再列出带有3个差错的图案，以此类推，直到放满2n-k行，每行一个Ej,对应一个不同的伴随式Sj。这样，表的行数2n-k正好等于伴随式的数目。,标准阵列译码表的构成,50,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,S0 E0S1 E1 Sj Ej,标准阵列译码表,E1+C1,51,普通高等教育“十五”国家级规划教材信息论与编码

27、 曹雪虹等编著,陪集和子集,译码表中有2n-k行，每行是一个陪集，每陪集的第一个元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式S0所对应的全零差错图案E0(无差错)，而第j行陪集的陪集首是伴随式Sj所对应的重量最小的差错图案Ej(C0=0,Rj=Ej)。译码表中有2k列，每列是一个子集，每子集的第一个元素(位于第一行)叫子集头。同一子集（同一列）中的所有元素对应同一个码字，第一列子集的子集头是全零码字C0，而第i列子集的子集头是码字Ci(E0=0,Ri=Ci)。,52,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,

28、例 6-3 一个(5,2)系统线性码的生成矩阵是G=设收码R=(10101)，构造标准阵列译码表，译出发码的估值解：(1)构造标准阵列译码表。分别以信息组m=(00)、(01)、(10)、(11)及已知的G求得4个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校验矩阵：H=PT I3=列出方程组：,53,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,伴随式有2n-k238种组合，差错图案中代表无差错的有一种，代表一个差错的图案有 种，已有6种。代表两个差错的图案有 种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先

29、将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，解得对应的Sj分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，(011)所对应的差错图案是2k个即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最轻，任选其中一个如(00011)。同样可得伴随式(110)所对应的最轻差错图案之一是(00110)。,例 6-3 译码表的构成,54,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例 6-3 标准阵列译码表,

30、55,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例 6-3 将接收码R10101译码,可选以下三种方法之一译码：直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。先求伴随式RHT=(10101)HT=(010)=S4，确定S4所在行，再沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找出码字(10111)。先求出伴随式RHT=(010)=S4并确定S4所对应的陪集首（差错图案）E4=(00010)，再将陪集首与收码相加得到码字C=R+E4=(10101)+(00010)=(10111)。上述三种方法由上而下，查表的时

31、间下降而所需计算量增大，实际使用时可针对不同情况选用。,56,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,对上例作进一步分析，还可以看到，该(5,2)码的dmin=3,纠错能力是t=INT(3-1)/2=1。因此，译码阵列中只有前6行具有唯一性、可靠性，真正体现了最大似然译码准则，而第7、8行的差错图案(00011)和(00110)中包含两个“1”，已超出了t=1的纠错能力，译码已不可靠。比如，当收码R(10100)时，根据码表译出的码字是(10111)，与收码R的汉明距离是2，然而收码R与全零码字(00000)的汉明距离也是2，为什么不能译成(00000)呢？事实上，码表的

32、第7、8行本身就不是唯一的。注意在码表计算过程中，伴随式(011)所对应的4个差错图案中有两个并列重量最轻，如果当时选的不是(00011)而是(10100)，那么码表第7行就不是现在这样了。,对例 6-3的分析,57,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.3码距、纠错能力、MDC码及重量谱,N重码矢c=(cn-1,c n-2,c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集 发码一定在这个子集里，传输无误时的收码也一定位于该子集 当出现差错时，接收的N重矢量:对应到子集外空间某一点 对应到该子集，却对应到该子集的另一点上

33、,58,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,t,d=7,dmin=3,d=5,C1,C2,C3,C4,C5,码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmin这里dmin=3，纠错能力是1，检错能力是2,6.3.3码距、纠错能力、MDC码及重量谱,59,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,定理6.1 任何最小距离dmin的线性分组码，其检错能力为（dmin-1）,纠错能力t为定理6.2 线性分组码的最小距离等于码集中非零码字的最小重量 dmin=min w(C i)C iC 及C i 0,6.3.3码距、纠错能力、MD

34、C码及重量谱,60,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,定理6.3(n,k)线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。定理6.4(n,k)线性分组码的最小距离必定小于等于(n-k+1)dmin(n-k+1),6.3.3码距、纠错能力、MDC码及重量谱,61,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例：H(7，4)线性码 各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k+14。,6.3.3码距、纠错能力、MDC码及重量

35、谱,62,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,（n,k）线性码最小距离dmin的上边界是n-k+1。如果我们设计的（n,k）线性码的dmin达到了n-k+1，就是达到了设计性能的极点。因此，dmin n-k+1的码称为极大最小距离码(MDC Maximized minimum Distance Code)。总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关。,6.3.3码距、纠错能力、MDC码及重量谱,63,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的

36、纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件 上式称作汉明限，任何一个纠t码都应满足上述条件。,6.3.4完备码(Perfect code),64,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.4完备码,某二元(n,k)线性分组码能使等式 成立，即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。这样的二元(n,k)线性分组码称为完备码。,65,普通高等教育“十五”国家级规

37、划教材信息论与编码 曹雪虹等编著,汉明码(Hamming Code),汉明码不是指一个码，而是代表一类码。汉明码的纠错能力t=1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-1-m)其中m=n-k，是正整数。当m3、4、5、6、7、8时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)。汉明码是完备码，因为它满足上述等式。,66,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,汉明码校验矩阵的构成,汉明码的校验矩阵H具有特殊的性质，能使构造方法简化。一个(n,k

38、)码的校验矩阵有nk行和n列，二进制时n-k个码元所能组成的列矢量总数是2n-k-1,恰好和校验矩阵的列数n=2m-1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。,67,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例 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=PT I3 1 0 1 0 1 0 1 1 1 0 1 0

39、 0 1再得生成矩阵G为 1 0 0 0 1 0 1 G=I4 P=0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1,68,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,高莱（Golay）码,是二进制（23，12）线性码，其最小距离dmin7，纠错能力t=3。是完备码，因为满足等式 223-12=2048=在(23,12)码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码，其最小距离dmin8。,69,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.5 循环码,循环码是线性码的一个子类；满足下列循环移位特性：码集C中

40、任何一个码字的循环移位仍是码字。,70,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,循环码的多项式描述,一般(n,k)线性分组码的k个基底之间不存在规则的联系，因此需用k个基底组成生成矩阵来表示一个码的特征。而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就足以表示一个码的特征。既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了。,71,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,把码字Ccn-1cn-2 c1c0 与一个不大于n-1次的码多项式C(x)对应起来。码多项式C(x)定义为：C(x)=cn-1xn-1+cn-2 xn-2

41、+c1x+c0对于二进制码，ci0,1,i=0,，n-1。,循环码的多项式定义,72,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,循环移一位：(cn-1cn-2 c1c0)(cn-2 c1c0 cn-1)循环移一位：C0(x)=cn-1 xn-1+cn-2 xn-2+c1x+c0 C1(x)=cn-2 xn-1+cn-3 xn-2+c0 x+cn-1比较循环移位的前后，可用如下的多项式运算来表达循环移位移1位：C1(x)=xC0(x)mod(xn+1)移2位：C2(x)=xC1(x)=x2C0(x)mod(xn+1)移n-1位：Cn-1(x)=xCn-2(x)=xn-1C0(

42、x)mod(xn+1),循环码的循环移位,73,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,码字的组成,根据码空间的封闭性，码字的线性组合仍是码字。C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+an-1xn-1C0(x)=(a0+a1x+a2x2+an-1xn-1)C0(x)=A(x)C0(x)mod(xn+1)其中C0(x)是一个码多项式，而A(x)是次数不大于n-1的任意多项式。对于二进制码，ai0,1,i=0,，n-1。,74,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,生成多项式,C(x)=m(x)g(x)码多 信息 生成 项式 多

43、项式 多项式生成多项式不是唯一的；g(x)x n-k+gn-k-1 x n-k-1+g2 x2+g1 x+1 是(n-k)次的首一码多项式，即(n-k)次项的系数为1。g(x)一定是(xn+1)的因子。,75,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,校验多项式,多项式xn+1可因式分解为xn+1g(x)h(x)的形式；如果g(x)代表(n，k)循环码的生成多项式，则h(x)代表该循环码的一致校验多项式，其阶次为k。h(x)的校验作用表现在：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码字与h(x)的乘积必不为0。C(x)h(x)=m(x)g(x)h(x)

44、=m(x)(xn+1)=0 mod(xn+1),76,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例 6.5 研究一个长度n=7的循环码的构成方法,(1)对(x7+1)作分解，找出n-k次因式。x7+1(x+1)(x3+x2+1)(x3+x+1)，n-k 因式g(x)对偶式h(x)循环码 1(x+1)(x3+x2+1)(x3+x+1)(7,6)3(x3+x2+1)(x+1)(x3+x+1)(7,4)3(x3+x+1)(x+1)(x3+x2+1)(7,4)4(x+1)(x3+x2+1)(x3+x+1)(7,3)4(x+1)(x3+x+1)(x3+x2+1)(7,3)6(x3+x

45、2+1)(x3+x+1)(x+1)(7,1),77,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,构成(7,3)循环码：选g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，则C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。当输入信息m=(011)时，m(x)=(x+1)，C(x)=(x+1)(x4x3x21)=x5+x2+x1+1，对应码矢C=(0100111)。,例 6.5 研究一个长度n=7的循环码的构成方法,78,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例 6.5 研究一个长度n=7的循环码的构成方法,7

46、9,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,系统循环码,码字的前k位原封不动照搬信息位而后面(nk)位为校验位：C(x)=xn-k m(x)+r(x)产生系统循环码的方法：将信息多项式m(x)预乘xn-k，即右移（n-k）位；将xn-k m(x)除以g(x)，得余式r(x)；得系统循环码的码多项式：C(x)=xn-k m(x)+r(x)。,80,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例6.6(7,3)循环码生成多项式是g(x)=x4+x3+x2+1，用式(6-3-35)产生系统循环码。解：先以输入信息m=(011)即m(x)=(x+1)为例，.xn

47、-k m(x)=x4(x+1)=x5+x4.(x5+x4)除以(x4+x3+x2+1)，得余式(x3+x).C(x)=xn-k m(x)+r(x)(x5+x4)+(x3+x),对应码矢(0111010)。依次将(000)(111)代入，可得全部码矢如表6-6。此表与表6-5对比，可见码集未变而映射规则变了，表6-6满足系统循环码要求。,81,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,扩展码,如果给每个码字添加一位奇偶校验位c校，构成（n1，k）线性码，称为扩展码。cn-1,c1,c0 cn-1,c1,c0,c校 c n1 c1 c0 c 校0 在二进制偶校验时：原来码字中1

48、的个数为偶数，则添加校验位0；原来码字中1的个数为奇数，则添加校验位1。如果某码原来的最小重量dmin是奇数，则新的最小距离变为dmin+1，检错能力增1。校验矩阵He,H,82,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,缩短码,把第一位为1的所有码字舍去，剩下另一半第一位为0的码字舍去它们的第一位后组成一个新的(n1，k1)码，称为缩短码。码长n1和信息位长度k1均缩短了。(n1，k1)缩短码共包含2k2=2k-1个码字。由于原先保留的均是第一位为0的码，舍去它们的第一位不会改变码的最小重量，因此缩短码与原码具有同样的dmin。称为（n-1,k-1,dmin）缩短码。,8

49、3,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例：(7,4)码的生成矩阵为 47,m3m2m1 m0ci2ci1ci0 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,CimG m3m2m1m0 码字中的c6去掉，c6是信息位m与G的第一列相乘结果，所以G的第一列应去掉；m3去掉，而m3是与G的第一行相乘，所以G的第一行也去掉。,84,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,得到

50、新的生成矩阵为 G 36原来的校验矩阵H为 H 37校验时，计算rHT，因r的第一位已没有，故HT的第一行应去掉，即H的第一列去掉。得到新的校验矩阵H为 H dmin不变，为3。36,85,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,循环冗余校验(CRC)码,信息位k和码长n可变，校验位长度n-k固定，符合(n-i,k-i)缩短循环码的特点。以一个选定的(n,k)循环码为基础，改变i值，得出任意信息长度的码字，而纠检错能力保持不变。循环冗余校验码（(CRC-Cyclic Redundancy Check)）是系统的缩短循环码。,86,普通高等教育“十五”国家级规划教材信息论与