第9章-差错控制编码.ppt

1,第9章差错控制编码,9.1引言9.2纠错编码的基本原理9.3常用的简单编码9.4线性分组码9.5循环码9.6卷积码,2,9.1引言,差错控制编码的基本方法在发送端被传输的信息序列上附加一些监督码元,这些多余码元与信息码元之间以某种确定的规则相互关联(约束),接收端按照既定的规则检验信息码元与监督码元之间的关系.,3,常用差错控制方法,检错重发前向纠错,发,收,检错码,应答信号,发,收,纠错码,4,混合纠错,发,收,纠检错,应答信号,常用检错重发系统:停发等候重发,返回重发和选择重发,5,停发等候重发,1,2,3,3,1,TI,2,3,发,接收,ACK,NAK,发现错误,这是一种半双工的通信方式,原理简单,效率低.,6,返回重发,12345623456789,12345623456789,发,接收,发现错误,NAK,从码组2开始重发,(传输效率最高,需复杂的控制,收、发数据缓存),选择重发,7,9.2纠错编码的基本原理,分类按差错控制编码的功能：检错码、纠错码、纠删码。按信息码元和附加的监督码元之间的检验关系：线性码、非线性码。按信息码元和监督码元之间的约束方式：分组码、卷积码。,8,例：3位二进制数构成的码组表示天气,9,如不要检（纠）错，传输4种不同的信息，用两位码组就够了，这两位码代表所传信息，称为信息位，多增加的称为监督位。,将信息码分组，为每组信码附加若干监督码的编码，称为分组码。在分组码中，监督码元仅监督本码组的中的信息码元。分组码用（n，k）表示，n码组长度，k信息位数，nk=r监督位数。1的数目称为码组的重量，两个码组对应位上数字不同的位数称为码组距离（汉明距离）。各码组间距离的最小值为最小码距d0,10,d0的大小直接关系着编码的检，纠错能力。,为检测e个错码，要求d0e+1为纠正t个错码，要求d02t+1为纠正t个错码，同时检测e个错码，要求d0e+t+1,B,d0,B,A,1,2,B,B,3,4,5,d0,11,A,B,1,t,e,若随机信道中，发送“0”和发送“1”时的错误概率相等，为P，且P1,则码长为n的码组恰好发生r个错码的概率为:,12,当n=7P=10-3时,P(1)710-3P(2)2.110-5P(3)3.510-8可见,采用差错控制编码,即使仅能纠正这种码组中的12个错误,也可以使误码率下降几个数量级.,13,9.3常用的简单编码,奇偶监督码无论信息位有多少,监督位只有一位,使码组中“1”的数目为偶(或奇)数.接收端,这种码能够检测奇数个错码,适用检测随机错误,14,二维奇偶监督码,把上述奇偶监督码的若干码组排列成矩阵,每一码组写成一行,然后,再按列的方向增加第二维监督位,15,恒比码,每个码组均含有相同数目的“1”(和“0”).由于“1”的数目与“0”的数目之比保持恒定,故得此名.正反码是一种简单的能够纠正错码的编码,监督位数目与信息位数目相同,监督位与信息位相同或相反,由信息码中的“1”的个数而定.,16,9.4线性分组码,线性分组码中信息码元和监督码元是用线性方程联系起来的.线性码建立在代数学群论基础上,线性码各许用码组的集合构成代数学中的群,因此,又称群码.主要性质任意两许用码组之和(模2和)仍为一许用码组.(封闭性)码的最小距离等于非零码的最小重量,17,奇偶监督码是一种最简单的线性码,偶校验时,S称为校正子,又称伴随式.S=0无错,S=1有错.一般,由r个监督方程式计算得r个校正子,可以用来指示2r-1种错误,对于一位误码来说,就可以指示2r-1个误码位置.对于(n,k)码,如果满足2r-1n则可能构造出纠正一位或一位以上错误的线性码.,18,设分组码(n,k)中k=4,为纠正一位错码,要求r3,则n=k+r=7,19,计算监督位,判断错码位置,按上述方法构造的纠正单个错误的线性分组码称为汉明码。码长n=2r1信息位k=2r1r监督位r,（1）,（2）,20,编码速率=,（1）改写为,表示成矩阵形式,=,21,简记为或,H称为监督矩阵，H确定，则编码时监督位和信息位的关系就完全确定了。P为rk阶Ir为rr阶单位方阵具有PIr形式的H矩阵称为典型阵。（2）改写为：,=,22,或,Q,生成矩阵,G,A,G,23,具有形式的生成矩阵称为典型生成矩阵。,由典型生成矩阵得出的码组A中，信息位不变，监督位附加其后，这种码称为系统码。,24,发送码组A在传输过程中可能发生误码，设接收到的码组为B=bn-1bn-2b0,则BA=EE=en-1en-2e0错误图样也可写作B=A+E,25,接收端计算校正子为,错误图样与校正子之间有确定的关系,26,例设且有3个接收码组,验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？,27,解：1）若无错，则错误图样为0，S为0,B1无错,B2错,B3错,2）,S2=H第1列E=100000第1位错同理S3=H第3列E=001000第3位错,28,线性码的重要性质,封闭性任意许用两个码组之和仍为许用码组两个码组之间的距离必是另一码组的重量,故最小码距即码的最小重量(除全0码外),29,9.5循环码9.5.1循环码原理,循环码是一种重要的线性分组码,易于实现,性能较好.循环码除具有线性码的一般性质外,还具有循环性,即循环码中任一码组循环一位以后,仍为该码中的一个码组.一长为n的码组可表示成码多项式,30,码多项式的按模运算若F(x)=N(x)Q(x)+R(x),则F(x)R(x)(模N(x)例,31,在循环码中,若T(x)是一个长为n的许用码组,则xiT(x)在按模xn+1运算下,也是一个许用码组.,即若则T(x)也是一个许用码组,32,在循环码中，一个（n，k）码有2k个不同码组,假设用g（x）表示一个前k-1位皆为0（第k位不为0）的码组则在循环码中，除全0码外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能k-1位。因此g（x）必须是一个常数项不为“0”的n-k次多项式,生成多项式,33,g(x),xg(x),x2g(x),xk-1g(x)都是码组,且线性无关,故循环码的生成矩阵G可写成,假如输入信息码元mk-1mk-2m0则,34,所有码多项式T(x)都可被g(x)整除,而且,任一次数不大于k-1的多项式乘g(x)都是码多项式.,生成多项式g(X)的确定T(x)=h(x)g(x)又g(x)为一个码组,故xkg(x)在模xn+1运算下也为一码组,故可写成,=1,35,故g(x)是xn+1的一个nk次因式,此即寻找g(x)的方法.例,36,9.5.2循环码的编、解码方法编码步骤,根据给定的（n,k)选定生成多项式g(x),即从xn+1的因子中选一n-k次多项式作为g(x).所有码多项式T(x)都可被g(x)整除,据此对给定的信息位m(x)进行编码.信息码后附加n-k个0,37,监督位,信息位,例(7,3)循环码m(x)=x2+x,g(x)=x4+x2+x+1,解,r(x),38,a,+,b,+,c,d,+,输入m,输出f,e,S,（7，3）码编码器,mabcdef00000001111011110011101010100010100000101100001000000011,f=m,f=e,39,循环码的解码,将接收码组R(x)用g(x)去除,若未发生错误,R(x)能被g(x)整除,发生错误则有余项.,40,9.6卷积码在编码器复杂性相同的情况下,卷积码的性能优于分组码.,卷积码把k个信息位编n位,k和n通常很小,特别适宜于串行形式传输,延时小.n个码元与当前段的k个信息位有关,而且与前N-1段的信息有关,编码过程相互关联的码元为Nn个.N或nN称为卷积码的约束长度,常把卷积码记作(n,k,N),41,654321,+,输入bi,ci,输出,bici,卷积码编码器k=1,n=2,N=6,42,b6b5b4b3b2b1,+,一级移存,+,S6S5S4S3S2S1,+,门限电路,(2,1,6)卷积码门限译码器,输入,bi,ci,重算ci,输出,校正子,“1”的个数3?,43,假定b1以前各码元均未发生错误,则,(1),44,(1)式经线性变换,这是一组正交于E(b1)的正交校验方程,在所考察的12个码元(b1b6,c1c6)中错误不多于2个的条件下,仅当E(b1)=1,(2)式才有可能有3个或3个以上方程等于1.门限电路门限设为3,此时,门限电路输出“1”,纠正b1错误,同时送到受E(b1)影响的各级校正子移存器纠正其中错误.,(2),45,监督矩阵H假定b1进入编码器之前，各级移存器处于“0”状态,则即,46,H1,用矩阵表示为,11001100001110000011101000001110101000001100101010000011,n,n-k,47,H1：截短监督矩阵自第7行起，每行结构相同，只是每行的起始比上一行多两个“0”。,一般，卷积码的截短监督矩阵形式为：,48,In-kn-k阶单位方阵Pi（n-k）k矩阵0n-k阶全零方阵,基本监督矩阵h=PN0PN-10PN-20P1In-k只要给定h，H1随之确定。,49,生成矩阵G基本生成矩阵gg=IKQ10Q20Q30QN,截短生成矩阵,Ikk阶单位方阵Qi=PiTk（n-k）矩阵0k阶全零方阵,50,卷积码的图解表示,（3，1，3）卷积码编码器a状态m1m2为00，b状态m1m2为01，c状态m1m2为10，d状态m1m2为11。,M3M2M1,+,+,输入序列mj,mj,y1，j,Y2，j,51,（3，1，3）卷积码的树状图,a,52,（3，1，3）卷积码的网格图,53,（3，1，3）卷积码的状态图,a,a,b,b,c,c,d,a,111,110,101,000,011,100,001,