第五章 信道编码.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章,信道编码,信道编码的基本概念和基本原理,线性分组码,循环码、卷积码和秩距离码,突发错误的纠正,级连码、交织码及,TCM,码,纠错码的应用,信源,检错、纠错,编码器,编码,信道,检错、纠错,译码器,信宿,噪声源,数字通信系统简化模型,编码信道：包括信道编码器、实际信道、信道译码器。,该模型是研究信道纠错编码和译码的模型，集中研究通信可靠性。,通信可靠性问题：,消息通过信道传输的时候，如何选择编码方案来减少差错。首先与信道统计特性有关，其次与编码方法、译码方法也有关系。,第一节 信道编码的基本概念和基本原理,信道是信号从信源传送到信宿的通路。,由于信道有干扰，使得传送的数据流,(,码流,),中产生误码。,误码的处理技术有纠错、交织、线性内插等。,信道编码的,目的,是提高信息传输或通信的可靠性。,信道编码的,任务,是降低误码率，使系统具有一定的纠错能力和抗干扰能力，提高数据传输效率。,信道编码的,过程,是在,源数据码流,中加插一些码元，达到在接收端进行检错和纠错的目的。,在带宽固定的信道中，总的传送码率是固定的，由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价了。,一、信道编码概念,目的,：降低错误译码概率,P,E,。,对象,：信息序列（设码元间彼此无关且等概出现）。,方法,在传输的信息码之中按一定规律产生一些附加数字，经信道传输，在传输中若码字出现错误，收端能利用编码规律发现码的内在相关性受到破坏，从而按一定的译码规则自动纠正或发现错误，降低误码率。,一、信道编码概念,实质,：在保持一定传输信息速率条件下，通过增加一定的码元多余度，使输出的码字具有特定的相关性，从而使收端易于发现或纠正由于信道噪声而引起的传输错误。,q,=,r,k,个,k,维矢量,信息序列,禁用码组,许用码组,码字,编码过程,n,重序列,r,n,个,信道,编码器,M,C,校验元,信息序列,码字,编码规则,r,k,个,C,0,C,1,C,i,C,j,C,2,k,-1,收端,传输模式,P,E,信道传输特征,P,E,译码方法,C,2,k,C,i,C,2,n,-1,许用码组,禁用码组,C,0,C,1,C,i,C,2,k,-1,许用码组,发端,不可检出错误传输,正确传输,可检出错误传输,二、信道编码的基本原理（检错、纠错原理）,寻找一种编码方法，使所加的监督码元最少，而检错纠错能力又高，且便于实现。,理论基础：香农第二定理,对于一个给定的有扰信道，如信道容量为,C,，只要发送端以低于,C,的速率,R,发送信息，则一定存在一种编码方法，使编码错误概率,p,随码长,n,的增加，按指数下降到任意小的值。也就是说，可以通过编码使通信过程实际上不发生错误，或使错误控制在允许数值之下。即：,信息传输率,E,(,R,),随机编码指数,码长,P,exp,-,nE,(,R,),E,(,R,),意义：,n,给定，则最佳编码的,P,上界既定。,适用于,DMC,，,有记忆信道及连续信道,;,香农第二定理说明：,P,E,0,，,可靠编码条件：,有噪信道编码逆定理,设离散无记忆信道,X,，,p,(,y,|,x,),，,Y,的信道容量为,C,，,R,是信息传输率，当,RC,时，则无论码长,N,多长，总找不到一种编码，使译码的平均错误概率任意小。,表述二,、设某信道有,r,个输入符号，,s,个输出符号，信道容量为,C,。,只要码长,N,足够长，总可以在输入的,r,N,个符号的集合中找到,M,（,M,2,N,(,C,-,),，,为任意小的正数）个码字，分别代表,M,个等可能性的消息，组成一个码以及相应的译码规则，使信道输出端的平均错误译码概率,P,E,达到任意小。,1),差错类型,1,随机错误,:,数据流中发生的错误彼此无关,表现为错,误之间的无相关性,.,2,突发错误,:,数据流中一个错误的发生,带来一连串错,误的发生,表现为误错之间的相关性,.,2),差错控制的途径,1,增加信道容量措施,扩展带宽、提高发送功率、降低噪声,2,编码措施,减小码率,、增加码长、交织器、,纠错码,3,传输方式措施,重复发送,、反馈,重发,、多进制信号,三、差错控制,需要双向信道，和前向信道有相同的通信容。,引入较大的停顿（不实时）。,可以纠正任何错误。,1,反馈检验法,(IRQ),分组,存储,发,收,收,发,k,I,k,I,3),差错控制的分类,2,检错重发法（,ARQ,）,自动请求重发,也需要反向信道，但容量可以降低，也会引入停顿,检错,编码,存储,发,收,收,发,k,I,k,I,检错,译码,3,前向纠错（,FEC,）,不需要双向信道,不会引入停顿,靠纠错编码,3,混合纠错检错（,HEC,）,4,),差错控制编码的基本原理,如用,三位二进制编码来代表八个字母,000 A100E,001 B101F,010C110G,011D111H,不管哪一位发生错误，都会使传输字母错误,如用三位字母传四个字母,000 A011B101 C110D,发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。,如用三位字母传二个字母,000 A111B,检三个错误，纠正一个错误。大数法则纠错。,结论,具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数,引入余度。,5,）、检错、纠错能力,码重,(weight),一个码组中“,1”,的数目,码距,(distance),两个码组之间对应位置上,1,、,0,不同的位数，又叫汉明,(Hamming),距。,10 1 1 0,码重：,3,01 1 0 0 2,距离：,3,为,检查出 个错误，要求最小码距为,为纠正 个错误，要求最小码距为,为纠正 个错误，同时检查出 个错误，要求最小码距为,纠正 个错误和,p,个删除，要求最小码距为：,检错、纠错能力,按,功能分,检错码,纠错码,纠删码（发现不可纠正的错误时，可发出指示或删除）,按信息码元和监督码元之间的校验关系分,线性码,非线性码,按信息码元和监督码元之间的约束方式分,分组码,卷积码,6,）、差错控制编码分类,卷积码,非线性码,线性码,纠错码,分组码,循环码,非循环码,纠随机错误码,纠突发错误码,纠随机和突发错误码,纠同步错误码,纠错码分类,第二节 线性分组码,表示：,(,n,k,),n:,帧（组）长,k/n,:,编码效率,特点,监督码只用来监督本帧中的信息位,分类,线性码 信息码与监督码之间为线性关系,非线性码 不存在线性关系,0,1,2,2,1,a,a,a,a,a,n,n,L,-,-,信息位,监督位,一、基本概念,分组码的监督方程,矩阵形式,监督矩阵,H,矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过初等变换运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。,生成矩阵,，通过监督矩阵可以得到生成码组。,如果输入码组为,A=0011,编码器输出码字为,:C=AG,由这种方式得到的生成矩阵称为,典型生成矩阵,，由它产生的分组码必定为,系统码，也就是信息码字保持不变，监督位附加其后，,每行一定是线性无关的，每行都是一个生成码组。,定理：设二元线性分组码,C,I,是由监督矩阵,H,所定义的，若,X,和,Y,为其中的任意两个码字，则,X+Y,也是,C,I,中的一个码字。,线性码的封闭性,对偶码,：以,G,作监督矩阵，以,H,为生成矩阵，得到另一个码,C,J,（,n,，,n-k,）线性码。,C,J,为原码,C,I,的对偶码。它们的码矢彼此正交，两个子空间是互为零化空间。,缩短码,：将分组码最左边,i,位为,0,的消息和对应的码字挑选出来，把最左边的,0,删去，构成（,n-i,，,k-i,）线性分组码。纠错检错能力与原码相同。,缩短码的监督矩阵：（,n,，,k,）一致监督矩阵删去最左边一列。,缩短码的生成矩阵,：（,n,，,k,）生成矩阵删去最左边一列和最上面的一行。,二、汉明码,能,纠正单个错误,的线性分组码,汉明码的监督矩阵,H,的列为所有非零的,r,维向量组成，一旦,r,给定，就可以构造出具体的（,n,，,k,）汉明码。,例：构造一个二元的（,7,，,4,，,3,）汉明码。,分析：,r=,n-k,=3,除,0,以外的所有,2,r,个元素构成矩阵,H,的列。,消息,码字,消息,码字,0000,0000000,1000,1000011,0001,0001111,1001,1001100,0010,0010110,1010,1010101,0011,0011001,1011,1011010,0100,0100101,11001100110,0101,0101010,1101,1101001,0110,0110011,1110,1110000,0111,0111100,1111,1111111,截短汉明码,(n,k),(,n-x,k-x,),如,(15,11),(12,8),监督矩阵,H,是将,原,H,的前,3,列 去掉,截短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。,能,纠,t,个错误的,(n,k),应,满足,取等号时为完备码,不同结构的线性码其纠错能力不同，能力和,dmin,有关，,dmin,越,大越好。,如果在汉明码基础上，再加上一位对所有码字进行校验的监督位,监督码字由,r,位增加到,r,1,位,信息位不变,码长 码结构,纠,1,位错，检测,2,位错,如（,8,，,4,），（,16,，,11,）,扩展汉明码,扩展汉明码的监督矩阵,编码器的实现,上例,m,=(,m,1,m,2,m,3,m,4,),m,1,m,2,m,3,m,4,0,1,C,i,=,mG,C,i,=(,c,1,c,2,c,3,c,4,c,5,c,6,c,7,),=(,m,1,m,2,m,3,m,4,m,1,+,m,2,+,m,3,m,2,+,m,3,+,m,4,m,1,+,m,2,+,m,4,),m,1,c,1,m,2,c,2,m,3,c,3,m,4,c,4,c,5,c,6,c,7,+,+,+,三、线性分组码的编码,根据线性码的监督矩阵或生成矩阵将长为,k,的信息组变换成长为,n,（,nk,）的码字。,四、线性分组码的译码,当给定接收码字,R,时，译码器的错误译码概率表示经过译码后平均接受到一个码字所产生的错误大小。,平均错误概率：,1,、最大似然译码,1),编码译码过程,源数据码流划分为信息组,m,编码译码过程如下,:,信息组,m,码字,C,i,接收字,R,C,i,的估值,干扰,2),译码,发送码字,C,i,接收字,R,;,译码器根据编码规则和信道特性,对接收码字,R,作出判决,此过程称为,译码,.,译码器的基本任务就是根据一套译码规则或算法,由接,收字,R,给出与发送信息组,m,的,最好估计值,.由于,m,与,C,之,间是一一对应的,这就等价于译码器根据,R,对,C,的,估计,.,编码器,译码器,信道,3),最佳译码,在已知接收字,R,的条件下,找出可能性最大的发送码字,C,i,作为译码的估值,令,这种,译码方法叫做最佳译码或最大后验译码,(MAP),根据,Bayes,公式,式中,p,(,C,i,),发送码字,C,i,的概率,p,(,R,),接收字,R,的概率,p,(,R,|,C,i,),先验概率,如果以下条件成立,码,C,中的,q,k,个码字以等概率发送,p,(,C,i,)=1/,q,k,p,(,R,),对于任何,R,都有,相同的值,p,(,R,)=1/,q,n,则后验概率,p,(C,i,|,R,),最大,等同于先验概率,p,(,R,|,C,i,),最大,.,4),最大似然译码,在已知接收字,R,的条件下,使得先验概率最大的译码方,法称为,最大似然译码,对于无记忆信道,若,C,i,=(,c,i,1,c,i,2,c,i,n,),R,=(,r,1,r,2,r,n,),则,最大似然函数,对数似然函数,5),最小距离译码,对于,BSC,信道,最大似然译码可以简化为最小距离译码,.,码,C,中任一码字,C,i,与,R,的距离为,d,则,d,表示,C,i,在,BSC,信道传输过程中码元传错的个数,.,因此此时的似然函数,结论,(1-,p,),n,是常数,而,p,/(1-,p,)1),的余数相同,;,或称为,a,和,b,对于,模,m,同余,.,最小非负剩余,:,a,=,r,(mod,m,);0,r,m,;,r,为,模,m,最小非负剩余,模,m,运算,:,a,b,0,1,2,m,-1;,r,为最小非负剩余,将,a,+,b,=,r,(mod,m,),a,b,=,r,(mod,m,),记为,这种求,a,+,b,和,a,b,的,模,m,最小非负剩余称为模,m,的加法,运算和,模,m,的乘法,运算,.,为了简单起见,以后将运算符号 简记为,+,和,.,2,模,2,运算,(,二进制,)3,模,q,运算,(q,进制,),例,:,模,3,运算,1+1+1=1,1+1+1+1=0,0-11,1-0=1,1-1=0,2),线性分组码,定义,1,设,C,i,=(,c,i,1,c,i,2,c,i,n,),C,j,=(,c,j,1,c,j,2,c,j,n,),是,二元码,C,的两个码字,则,C,i,与,C,j,的和,为,C,i,与,C,j,对应码元的模,2,运算,;,若,C,s,=(,c,s,1,c,s,2,c,s,n,),且,C,s,=,C,i,+,C,j,即,c,s,r,=,c,i,r,+,c,j,r,(,r,=1,2,n,),+,0,1,2,0,0,1,2,1,1,2,0,2,2,0,1,0,1,2,0,0,0,0,1,0,1,2,2,0,2,1,+,0,1,0,0,1,1,1,0,0,1,0,0,0,1,0,1,定义,2,设,(,n,k,),分组码,C,中的任意两个码字,1,C,中有全,0,码元的码字,;,2,C,中的任意两个码字的和仍为码,C,的码字,;,则分组码,C,称为,(,n,k,),线性分组码,.,推论 线性分组码,任意两个以上码字的和,仍为码,C,的码字,.,根据分组码的定义,信息组,m,的,k,个码元,(,信息位,),应包,含在线性分组码的码字中,.,定义,3,若信息组,m,的,k,个码元以整体不变的形式,放在码字,的任意位置中,该码为,系统码,.,否则,称为,非系统码,.,系统码通常如下图将信息组放在码字的最左边或最右边,.,k,位,信息位,n-k,位校验位,n-k,位校验位,k,位信息位,例 试构造,(5,2),线性分组码,且,d,min,=3,信息组,m,00 01 10 11,00000,00001 00010 00011 00100 00101 00110,00111,01000 01001 01010,01011,01100,01101,01110,01111,10000 10001 10010,10011,10100,10101,10110,10111,11000,11001,11010,11011,11100,11101,11110,11111,1,组,2,组,3,组,4,组,5,组,6,组,7,组,8,组,9,组,00000,00,000,00,000,00,000,00,000,00,000,00,000,00,000,00,000,01,011,01,011,01,011,01,101,01,101,01,101,01,110,01,110,01,110,10,101,10,110,10,111,10,011,10,110,10,111,10,011,10,101,10,111,11,110,11,101,11,100,11,110,11,011,11,010,11,101,11,001,11,001,3),码字的重量,定义,4 (,n,k,),码,C,的一个码字,C,i,中非零码元的个数称为码,字,C,i,的,Hamming,重量,简称,码重,记为,W,(,C,i,),.,定义,5 (,n,k,),码,C,中所有非零码字的,Hamming,重量的最小,值称为码,C,的,最小,Hamming,重量,或码,C,最小重量,记为,W,min,.,推论 设,C,i,C,j,为,二元,分组码,C,的任意两个码字,则,W,(,C,i,+,C,j,),=d,(,C,i,C,j,).,证明,C,i,C,j,的,对应码元相同时,则,C,i,+,C,j,对应,的,码元为,0;,C,i,C,j,的对应码元不同时,则,C,i,+,C,j,对应的码元为,1;,则,W,(,C,i,+,C,j,),为,C,i,C,j,的对应码元不同的个数,而,d,(,C,i,C,j,),为,C,i,C,j,的对应码元不同的个数,故推论成立,.,定理 二元,(,n,k,),线性分组码,C,的,最小距离,等于其,最小重量,.,证明 设,C,中的任意两个码字,C,i,C,j,且,C,i,C,j,则,C,s,=,C,i,+,C,j,是非零码字,同时是码,C,的码字,又因为,W,(,C,i,+,C,j,),=W,(,C,s,),=d,(,C,i,C,j,),因此,W,min,=d,min,结论,:,二元线性分组码,C,的最小重量,即非零码字“,1”,的个数,最少的码字决定了码,C,的检错或纠错能力,.,如何获得二元线性分组码,5.42,近世代数学初步,1),群的概念,定义,1,G,是一个非空集合，,*,是,G,中的一个代数运算，若,1,a,b,G,有,a,*,b,G,(,封闭性,),2,a,b,c,G,有,(,a,*,b,),*,c,=,a,*,(,b,*,c,)(,结合律,),3,存在单位元素,e,G,a,G,有,e,*,a=a,*,e=a,4,a,G,存在逆元素,a,-1,G,有,a,-1,*,a=a,-1,*,a=e,5,a,b,G,有,a,*,b=b,*,a,(,交换律,),如果这种运算,*,满足：,条件,1,2,3,4,则,G,称对代数运算为一个群,或称,G,为一个非交换群,.,条件,1,2,3,4,5,则称G,为一个,交换群,或,Abel,群,.,若运算*是普通的加法“,+”,则群称为,加群,.,若运算*是普通的乘法“,”,则群称为,乘群,.,定义,2,若群,G,仅有有限个原素则称为,有限群,;,否则为,无限群,.,1,无限群的例子,例,1,整数集对加法构成,Abel,群,对乘法不是群,.,例,2,有理数,、实,数,、复,数集对加法构成,Abel,群,不含数,0,的有理数,、实,数,、复,数集对乘法构成,Abel,群,.,例,3,n,维方阵的集合加法构成,Abel,群,对乘法不是群,.,例,4,n,维非奇异方阵对乘法构成非,Abel,群,.,2,有限群的例子,例,1,数,0,对加法构成群,数,1,对乘法构成群,.,例,2,集合,0,1,2,m,-1,对模,m,加法运算构成,Abel,群,对乘法不是群,.,例,3,当,m,为素数时,集合,1,2,m,-1,对模,m,乘法运,算构成,Abel,群,.,例,4,方程,x,n,-1=0,的本原根,e,j,2,k,/,n,k,=0,1,n,-1,对,乘法,构成,Abel,群,.,例,5,线性分组码构成,Abel,群,所以线性分组码又称为,群码,.,2),域的概念,定义,1,F,是一个非空集合,对于,F,的任意两个元素,a,和,b,定义集合元素的加法运算,记作,a,b,;,乘法运算,记作,a b,;,且有,如下规则,:,加法运算,1,a,b,F有,a,b,F,;,2,a,b,F,有,a,b,=,b,a,;,3,a,，,b,，,c,F,有,(,a,b,),c,=,a,(,b,c,);,4,存在,0,F,a,F ,有,a,0=,a,；,5,a,F,存在,-,a,F,有,a,(-,a,)=0;,乘法运算,1,a,b,F,有,a b,F,;,2,a,b,F,有,a b,=,b a,;,3,a,，,b,，,c,F,有,(,a b,),c,=,a,(,b,c,);,4,存在,e,F,a,F ,有,a,e,=,a,；,5,a,F,且,a,0,存在,a,-1,F,有,a a,-1,=,e,;,乘法对加法的分配律,a,b,c,F,有,a,(,b,c)=,a b,a c,以上运算规则都成立，则称,F,对于所规定的加法运算,和乘法运算是一个域,.,定义,2,设,F,是一个域,如果,F,中的元素个数无限,则,F,称为,无限域,.,如果,F,中的元素个数有限,则,F,称为有限,域，有限域亦称为,Galois,域,.,1,无限域的例子,例,1,有理数,、实,数,、复,数集对加法,乘法构成域,.,例,2,形如 的数对加法,乘法构成域,.,2,有限域的例子,例,1,集合,0,1,2,m,-1,对模,m,加法,乘法运算构成域,.,5.4.3,生成矩阵和校验矩阵,1),生成矩阵,例,1,试构造,(5,2),线性分组码,且,d,min,=3,m,=(,m1,m,2,)=(00),(01),(10),(11),C,i,=(,m,1,m,2,m,1,m,2,m,1,+,m,2,),(00),(,0 0,0 0 0)(,01),(,0 1,0 1 1),(10),(,1 0,1 0 1)(,11),(,1 1,1 1 0),1(,n,k,),线性分组码的生成矩阵,G,是一个,k,n,维矩阵,.,为了获得系统线性分组码,生成矩阵由两个分块矩阵组成,:,G,=,I,k,P,k,(,n,-,k,),I,k,:,k,维单位矩阵,以获得信息位,;,P,k,(,n,-,k,),:,k,(,n,-,k,),矩阵,以获得校验位,.,2,线性分组码生成矩阵的特点,生成矩阵不是唯一的,;,生成矩阵的行矢量均为线性分组码的码字,;,生成矩阵的行矢量是模,2,运算下线性无关,;,线性分组码任一码字是行矢量模,2,运算下的线性组合,.,3,如何获得生成矩阵,?,例,2,试构造,(7,4),线性分组码,且,d,min,=3,生成矩阵生成的线性分组码要有尽可能大的,d,min,即生,成矩阵的行矢量中的“,1”,的个数,d,min,且生成矩阵各行矢,量,(,码字,),的对应元素不相同的个数,d,min,.,2),一致校验矩阵,(,n,k,),线性分组码为一系统码,则码字有,(,c,1,c,2,c,k,c,k,+1,c,n,)=(,m,1,m,2,m,k,c,k,+1c,n,),由生成矩阵,G,生成的码字,(,c,1,c,2,c,k,c,k,+1,c,n,)=(,m,1,m,2,m,k,),G,=(,m,1,m,2,m,k,),I,k,P,k,(,n,-,k,),码字的校验位,(,c,k,+1,c,n,)=(,m,1,m,2,m,k,),P,k,(,n,-,k,),=(,c,1,c,2,c,k,),P,k,(,n,-,k,),(,c,1,c,2,c,k,),P,k,(,n,-,k,),-,(,c,k,+1,c,n,)=0,1,(,n,-,k,),(,c,1,c,2,c,k,),P,k,(,n,-,k,),+,(,c,k,+1,c,n,),I,(,n,-,k,),=0,1,(,n,-,k,),一致校验矩阵,H,(,简称校验矩阵,),H=,P,T,I,(,n,-,k,),(,n,-,k,),n,当系统码生成矩阵,G,确定后,校验矩阵,H,由生成矩阵中的,分块矩阵,P,k,(,n,-,k,),确定,.,由生成矩阵,G,生成的任一码字,C,i,均满足下式,不是,G,生成,码字则不满足下式,C,i,H,T,=0,1(,n,-,k,),或,H,C,i,T,=0,(,n,-,k,)1,因此,校验矩阵,H,可以判断是否为码字,.,3),极大最小距离码,(,n,k,),线性分组码要有尽可能大的,d,min,其的上限是什么,?,如何达到上限,.,令,H,=,h,1,h,2,h,n,h,1,h,2,h,n,为,(,n,-,k,),维列矢量,(,n,k,),线性分组码的任一非零码字,C,i,=(,c,i,1,c,i,2,c,i,n,),因为,H,C,i,T,=0,所以,c,i,1,h,1,+,c,i,2,h,2,+,c,i,n,h,n,=0,因此,矢量,h,1,h,2,h,n,是,线性相关的,.,(,n,k,),线性分组码的,d,min,=,W,min,设,C,s,为码重,最小的码,字,则,C,s,中,码元为“,1”,的个数,=,d,min,因为,H C,s,T,=0,所以,H,的列矢量至少要有,d,min,才,线性相关,.,而,H,的,d,min,-1,个列矢,量是线性无关的,否则就至少有一个码重为,d,min,1,的码,字,这与,d,min,相,矛盾,.,由于,H,是,n,(,n,-,k,),矩阵,其秩最多为,(,n,-,k,),最多有,(,n,-,k,),个,列矢量线性无关,因此,d,min,-1,(,n,-,k,),即,d,min,n,-,k+,1.,当,d,min,=,n,-,k+,1,时的码称为,极大最小距离码,.,