通信原理第九章学习教案.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,#,单击此处编辑母版标题样式,会计学,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,会计学,1,通信(tng xn)原理第九章,第一页，共40页。,9.1,引 言,检错重发法,9.1.2 差错控制的方法(fngf),9.1.1 编码(bin m)的目的：提高信号抗加性干扰的能力,干扰种类(zhngli)：加性 克服方法：差错控制编码,加性干扰的特征：,突发信道：出现错码成串集中。,混合信道：前两者中和。,乘性 克服方法：均衡器,随机信道：出现错码是随机的，相互间统计独立。（白噪声）,反馈校验法,前向纠错方法,定义,误码率标准,第1页/共40页,第二页，共40页。,速率,(b/s),线路类别,误码率标准,300,电话交换线,专用线,10,-,4,5,10,-,5,600,电话交换线,专用线,10,-,3,5,10,-,5,1200,电话交换线,专用线,10,-,5,5,10,-,5,2400,专用线,10,-,5,CCITT 建议(jiny)的误码率标准,第2页/共40页,第三页，共40页。,检错重发法：在接收端检测出错码时，通知发端重发信号，直到接收正确(zhngqu)为止。此方法只能判断是否有错码，不能判断具体的错码位置。所以，只能检错不能纠错，且需要双向通道。,前向纠错方法：在收端检测(jin c)出错码时，可以确定错码的位置，并予纠正。此方法只需要单向通道。实时性好，但设备复杂。,反馈校验法：接收端将收到的信号(xnho)原封不动的发回发端，由发端将其与原发信号(xnho)相比较，如果有错则重发。这种方法需双向通道，效率低，但设备简单。,第3页/共40页,第四页，共40页。,在信息(xnx)码序列中加监督码元（也称纠错码）,自动(zdng)请求重发系统（ARQ）,9.1.3 差错控制编码(bin m)的原理：,不同的编码方法，有不同的检错或纠错能力，监督码元越多，检、纠错能力越强。,由于信息码元是随机序列，收端无法预知信号状态，因而无法判别接收码是否有错。增加了监督码元之后，监督码和信息码之间存在一种逻辑关系，因此，收端可以利用这种逻辑关系发现或纠正存在的错码。,第4页/共40页,第五页，共40页。,自动请求(qngqi)重发系统（ARQ）,工作(gngzu)过程：,3）重发控制器收到重发命令时，控制输入缓冲(hunchng)储存器重发一次当前码组，否则发送后一码组。,2,）收端解码器检测出错码时由指令发生器产生重发命令传给发端，同时发出删除命令，删除输出缓冲器内容。,1,）收发正常时，重发控制与指令发生器不工作。,重发控制,信,源,双,向,通,道,指令发生器,解码器,输出缓存器,收,信,者,错误时删除,编码,输入缓存器,优点：,1,）监督码少，占总码的,(20%),2,）对各种信道有一定的适应能力。,3,）成本及复杂性低。,缺点：,1,）需要双向通道,2,）干扰大时系统可能处于重发循环中，效率降低,3,）实时性差,第5页/共40页,第六页，共40页。,9.2 纠错(ji cu)编码的基本原理,9.2.1 分组码的概念(ginin),9.2.2 分组码参数(cnsh),第6页/共40页,第七页，共40页。,例：天气预报(tinqybo),9.2.1 分组码的概念(ginin),特征(tzhng)：分组码中的监督码元仅监督本码组中的信息码元。,分组码,定义：,将,信息码分组，为每组信息码后附加若干监督码元形成的码集合。,分组码检错、纠错能力的体现,信源,发送信息码,晴,0 0,云,0 1,阴,1 0,雨,1 1,接收信息码,判别,0 1,云,10,阴,0 0,晴,1 0,阴,结论：,虽然接收码组有错，但接收端无法识别。,讨论,第7页/共40页,第八页，共40页。,信源,发送信息码,监督码,晴,0 0,0,云,0 1,1,阴,1 0,1,雨,1 1,0,接收码组,判别,001,、,010,、,100,010,、,001,、,111,100,、,111,、,001,111100,、,010,建立(jinl)分组码 A,错,1,位,接收码组,判别,011,、,110,、,101,云、雨、阴,000,、,101,、,110,晴、阴、雨,110,、,000,、,011,雨、晴、云,101,、,000,、,011,阴、晴、云,错,2,位,结论(jiln)：只能检测出 1 位错码，但不能纠正。,禁用(jn yn)码组：非信息码组,许用码组：有效,信息,码组,第8页/共40页,第九页，共40页。,结论：能纠正(jizhng)1 位错码，或检测出 2 位错码。,信源,发送信息码,监督码,晴,0 0,000,云,0 1,011,阴,1 0,101,雨,1 1,110,接收码组,判别,00001,、,00010,、,00100,、,01000,、,10000,01010,、,01001,、,01111,、,00011,、,11011,10100,、,10111,、,10001,、,11101,、,00101,11111,、,11100,、,11010,、,10110,、,01110,建立(jinl)分组码 B,错,1,位,接收码组,判别,11000,、,10100,、,10010,、,10001,、,01100,、,01010,、,01001,、,00110,、,00101,、,00011,10011,、,11111,、,11001,、,11010,、,00111,、,00001,、,00010,、,01101,、,01110,、,01010,01101,、,00001,、,00111,、,00110,、,11001,、,11110,、,11101,、,10011,、,10000,、,10100,00110,、,01010,、,01100,、,01111,、,10010,、,10100,、,10111,、,11000,、,11011,、,11111,错,2,位,第9页/共40页,第十页，共40页。,k：码组中信息码元的数目。,n：码组的总位数，又称为(chn wi)码组长度。,r=n-k：码组中监督码元的数目。,结构(jigu),符号(fho)(nk),码长,n=k+,r,k,个信息位,r,个监督位,码组重量,码组中“,1,”,的数目,9.2.2,分组码参数,a,n-1,a,n-2,a,r,a,r-1,a,0,码距,d,：两个码组对应位上不同的码元个数称为码组间的汉明距离,码距与码集合,检、纠错能力的关系,第10页/共40页,第十一页，共40页。,例：,码组（,a,2,a,1,a,0,）,=,1 1 0,（,b,2,b,1,b,0,）,=,0 1 1,码距的几何(j h)概念,码距是,2,最小码距 d0 ：码集合中任意(rny)两两码组间距离的最小值,（,0 1 0,）,（,1 1 0,）,（,0 0 0,）,（,1 0 0,）,（,1 0 1,）,（,0 0 1,）,（,0 1 1,）,（,1 1 1,）,a,1,a,0,a,2,选许用码组：,0 0 0,0 1 1,1 1 0,1 0 1,令 n=3,共有(n yu)8 个码组,沿立方体各边行走，,4,个码组的距离均为,2,个边长,d,0,=2,第11页/共40页,第十二页，共40页。,检测(jin c)e 个错码，要求最小码距,纠正(jizhng)t 个错码，要求最小码距,纠正(jizhng)t 个错码、同时检测 e 个错码，要求最小码距,码距与码集合检、纠错能力的关系,A,B,例：,A=(00000),、,B=(11111),，,d,0,=5,结论：,e=4,或,t2,或,e=3,、,t=1,d=1,d=2,d=3,第12页/共40页,第十三页，共40页。,9.3 常用(chn yn)的简单编码,9.3.1 奇偶(q u)监督码,9.3.2,正反码,第13页/共40页,第十四页，共40页。,奇数(j sh)监督码:,偶数(u sh)监督码:,监督(jind)码元 1 位,使码组中“1”的个数为奇,监督码元,1,位,使码组中,“,1”,的个数为偶,只能检测奇数个错码,二维奇偶监督码（矩阵码）,能检测部分偶数个错码,生成规则：,许用码组写成一行（包括信息码和,1,位监督码），设共有,m,行。第,m+1,行为按列增加的监督码。（构成监督码行）,例,9.3.1奇偶监督码,一维奇偶监督码,例,监督方程,监督方程,第14页/共40页,第十五页，共40页。,例,:,信源,发送信息码,a,2,a,1,监督码,a,0,晴,0 0,0,云,0 1,1,阴,1 0,1,雨,1 1,0,一维偶数(u sh)监督码,接收码组,判别,001,、,010,、,100,010,、,001,、,111,100,、,111,、,001,111,、,100,、,010,错,1,位,满足(mnz)：,检验(jinyn)不满足,只能检错，不能纠错,第15页/共40页,第十六页，共40页。,2,）当,同时出错，则按行按列均不能检测出有错。,能检测部分偶数个错码适用(shyng)于突发信道。,若仅一行有奇数个错码时，可通过(tnggu)列确定错码位置并纠正。,1,）设 和,发生错码，按行无法检测出有错，而按列可检测。,a,2,a,1,a,0,0 0,0,0 1,1,1 0,1,1 1,0,0 0 0,例：二维偶数(u sh)监督码,通式,结论：,方阵码除对构成矩形四角的错码无法检测外，其余均能检测。,第16页/共40页,第十七页，共40页。,特征(tzhng)：具有纠正 1 位错码、检测 2 位和大部分 2 位以上错码的能力,定义：信息(xnx)码位数与监督码位数相同,编码(bin m),规则：,1,）当信息位中有,奇,数个,“,1”,时，监督位是信息位的重复。,2,）当信息位中有,偶,数个,“,1”,时，监督位是信息位的反码。,1 0 0 0 1,例：,若信息码为,1 1 0 0 1,9.3.2,正反码,则正反码为,1 1 0 0 1,1 1 0 0 1,1 0 0 0 1,0 1 1 1 0,1,）,将接收码组中信息码和监督码对应按位模,2,加，得,合成码组,2,）根据接收码组中信息码含,“,1”,的奇偶情况，由合成码组生成,校验码组,3,）根据校验码组的组成，依表判断错码情况，并予检错与纠错,译码,规则：,“1”,为奇 校验,=,合成,“,1”,为偶 校验,=,例,第17页/共40页,第十八页，共40页。,例：发,1 1 0 0 1,1 1 0 0 1,1,）收无错,信息(xnx)码中含奇数个“1”,2,）收有错、为,1,0,0 0 1,1 1 0 0 1,合成(hchng)码组=,1 1 0 0 1,1 1 0 0 1,0 0 0 0 0,译码判决(pnju)：,校验码组,错码情况,1,全,“,0”,无错码,2,4,个,“,1”,1,个,“,0”,信息码中有一位错码，对应校验码组中的,“,0”,的位置,3,4,个,“,0”,1,个,“,1”,监督码中有一位错码，对应校验码组中的,“,1”,的位置,4,其他组成,错码多于,1,个,校验码组,=,合成码组,=,00000,判断接收无错码,合成码组,=,1,0,0 0 1,1 1 0 0 1,0,1,0 0 0,信息码中含偶数个,“,1”,查表知信息码第二位错,特征：,编码效率低,第18页/共40页,第十九页，共40页。,9.4,线性分组码,9.4.1 汉明码的编码(bin m)原理,9.4.2 一般线性分组码的编码(bin m)原理,9.4.3 线性码分组码的数学(shxu)描述,第19页/共40页,第二十页，共40页。,9.4.1 汉明码的编码(bin m)原理,定义：能纠正一位错码，且编码(bin m)效率较高的线性分组码,问题：在正反码中，为纠正一位错码，其监督码位数与信息码位数一样多，能否减少监督码位数但纠错(ji cu)能力不变？,如何实现纠错？,思路：,分组码,(n,k)只可能出现,n,个一位错码事件，若某种逻辑组合具有,n,个状态，就能利用这种逻辑组合描述一位错码事件并予纠正。,例：,分析偶数监督码，寻找逻辑组合,汉明码,监督方程,则接收时解码是在计算,0,无错,1,有错,定义：,校正子,S=,只能表示出错,不能描述错码位置,一位监督码对应一个监督方程,结论：若增加监督码元，建立多个监督方程，多个校正子就能形成逻辑组合描述错码位置,第20页/共40页,第二十一页，共40页。,汉明码,确定(qudng)监督码元位数 r,确定监督(jind)关系表,建立(jinl)监督方程,建立编码方程,分组码,(n,k),共需,n+1,个状态描述无错及,n,个有错事件,为提高编码效率，,r,取最小值,例：,已知,(7,4),码，,r=3,共有,3,个监督方程，构成,3,个校正子,S,1,S,2,S,3,S,1,S,2,S,3,0 0 0,无错,0 0 1,a,0,错,0 1 0,a,1,错,1 0 0,a,2,错,1 1 0,a,3,错,0 1 1,a,4,错,1 1 1,a,5,错,1 0 1,a,6,错,例,第21页/共40页,第二十二页，共40页。,例：已知(7,4)汉明码，求码组集合(jh),解：,S,1,S,2,S,3,0 0 0,无错,0 0 1,a,0,错,0 1 0,a,1,错,1 0 0,a,2,错,1 1 0,a,3,错,0 1 1,a,4,错,1 1 1,a,5,错,1 0 1,a,6,错,监督(jind)方程,编码(bin m)方程,k=4,，,信息码组有,16,个,a,6,a,5,a,4,a,3,a,2,a,1,a,0,0 0 0 0,0 0 0,0 0 0 1,1 1 0,0 0 1 0,0 1 1,0 0 1 1,1 0 1,.,1 1 0 0,0 1 0,1 1 0 1,1 0 0,1 1 1 0,0 0 1,1 1 1 1,1 1 1,r=3,第22页/共40页,第二十三页，共40页。,例：汉明码的监督(jind)方程为,矩阵(j zhn)表达式,9.4.2 一般线性分组码的编码原理（矩阵(j zhn)方程）,记为：H,：监督矩阵,A,：码组向量,当,称,H,为典型矩阵,（含单位阵）,思路：,确定编码矩阵方程，,构造,生成矩阵,第23页/共40页,第二十四页，共40页。,又 根据监督方程(fngchng)确定了编码方程(fngchng),两边(lingbin)同取转置,构造(guzo)生成矩阵,称,G,为典型生成矩阵,（含单位阵）,编码矩阵方程,特点：信息位不变，监督位附加于其后。,定义,系统码：由典型生成矩阵得出的码组,A,第24页/共40页,第二十五页，共40页。,生成(shn chn)矩阵,G 中每行均为一个(y)码组，且线性无关,第25页/共40页,第二十六页，共40页。,译码运算(yn sun)，当,S 为校正(jiozhng)子。说明 S 与E 间有确定的线性关系,若 E 的数目有限，能与 S 一一对应，,则 说明 S 能描述错码的位置，具有(jyu)纠错能力。,9.4.3,线性码分组码的数学描述,令 发码组为,A,、收码组为,B,错码图样,E=B,-,A,收发码组的关系,0,无错,1,有错,令,B=E,+,A,例,第26页/共40页,第二十七页，共40页。,发码组,A,=,1 1 0 0,0 1 0,收码组,B,=,1,0,0 0,0 1 0,译码运算(yn sun),例：,(7,4),汉明码,S,1,S,2,S,3,0 0 0,无错,0 0 1,a,0,错,0 1 0,a,1错,1 0 0,a,2,错,1 1 0,a,3,错,0 1 1,a,4,错,1 1 1,a,5,错,1 0 1,a,6,错,a,5,错,含义：错码图样(tyng)E=（0 1 0 0 0 0 0）只有一位错码,第27页/共40页,第二十八页，共40页。,定义(dngy)：线性码中任意两个码组之和仍为这种码中的一个码组,证：设 A1 、A2 为线性码中两个(lin)许用码组,两式相加,是许用码组,推广(tugung)：,1,）两个码组间的距离必是另一码组的重量,2,）除,0,码组之外，码组的最小重量是码集合的最小距离。,线性分组码具有,封闭性,第28页/共40页,第二十九页，共40页。,9.5循环码,9.5.1,码多项式,9.5.2 循环码的特性(txng),9.5.3,循环码的编码方法,第29页/共40页,第三十页，共40页。,码多项式的按模运算(yn sun)：,9.5.1,码多项式,码多项式,定义(dngy)：以码组中各码元为系数的多项式,T(x)=a,n-1,x,n-1,+a,n-2,x,n-2,+,.,+a,1,x+a,0,设 多项式 F(x)、除数(ch sh)为 N(x),记：模,N(x),注：,多,项式按模,N(x),运算过程中，其系数按,模,2,加,运算（系数为二进制，只能取,0,或,1,，系数的相减均为模,2,加）。,x,仅为码元位置的标记,例,R(x),：,余式,例：,(110,0101,)T(x)=x,6,+x,5,+x,2,+1,第30页/共40页,第三十一页，共40页。,例：,解：,记为：,余式,第31页/共40页,第三十二页，共40页。,定理(dngl)：若 T(x)对应一个码长为 n 的许用码组，,证：,令,T(x)的系数(xsh)是 T(x)中系数(xsh)向左循环移位 i 次的结果,9.5.2 循环码的特性(txng),码集合中任意一个码组，左移或右移一位得到的新码组必是该码集合中另一码组,循环码的定义,循环码的码多项式,则,x,i,T(x),按模,x,n,+,1,运算后,余式,T,(,x),仍为许用码组。,例,第32页/共40页,第三十三页，共40页。,例：,(7,3),循环码,码组为,(110,0101,),，求,码多项式,T(x),。,验证 x 3 T(x)按模 x 7+1 运算(yn sun)后余式仍是一个许用码组。,解：,T(x)=a,n-1,x,n-1,+a,n-2,x,n-2,+,.,+a,1,x+a,0,T(x)=x,6,+x,5,+x,2,+1,x,3,T(x),=x,9,+x,8,+x,5,+x,3,余式T(x)对应(duyng)码组为(0101110),是,T,(,x),码组左移三位,第33页/共40页,第三十四页，共40页。,循环码的生成(shn chn)矩阵 G,9.5.3,循环码的编码方法,思路：确定编码(bin m)矩阵方程，构造生成矩阵,码生成(shn chn)多项式 g(x)的定义,循环码的监督矩阵,H,码生成多项式,g,(x),的求解,例,G,是,G(x),的系数矩阵,循环码的检、纠错能力,与,n,、,k,的值相关,第34页/共40页,第三十五页，共40页。,循环码生成(shn chn)矩阵 G 的数学描述,已知,(7,4),汉明码,G 中每行均为一个(y)码组，且线性无关是线性分组码的共性。,循环码是线性分组码成员之一，其 G 除满足上述特性(txng)外，每行之间必须满足循环性。,循环码每个码组对应一个码多项式,以最简方式寻找,k,个线性无关的码多项式就能建立,G(x)第35页/共40页,第三十六页，共40页。,码生成(shn chn)多项式 g(x)的定义,定义(dngy)：幂次为(n-k)的码多项式。（具有唯一性）,分析(fnx)循环码：循环码(n,k)的形成方法是在信息码后加监督码且保持移位循环的特征。除全零码组外，权值最小的信息码组为 0 0.0 0 1，且监督位 a0 不可能为零，否则循环数次后码组前 k 位均为零，而监督位不为零的情况，这不符合监督码的定义,结论：信息码组,0 0,.,0 0 1,对应的码多项式必为,(n-k),次幂，且常数项不等于零,信息码组,0 0,.,0 0 1,唯一,码多项式唯一，且,幂次最低，记为,g,(x),与,g,x),线性无关的,k,-,1,个,码多项式为,x,g,(x),、,.,x,k-1,g,(x),，,可组成生成矩阵,G(x),第36页/共40页,第三十七页，共40页。,码生成(shn chn)多项式 g(x)的求解,定理：循环码(n,k)的 g(x)是 x n+1 的一个(y)(n-k)次因子。,证：,g,(x),是幂次最低的码多项式,任意一个(y)码多项式 T(x)都是 g(x)倍数,令,T,(x)=,h,(x),g,(x),余式,为码组,x,k,g,(x)=,x,n,+,1,+,T,(x),x,n,+,1,=,x,k,g,(x),+,T,(x),模,2,加,=,x,k,g,(x),+,hx),g,(x),=,x,k,+,h,(x),g,(x),得证,第37页/共40页,第三十八页，共40页。,例：已知(7,3)循环码，求码组集合(jh)、监督矩阵 H。,解：,n=7,x,7,+,1,=,(,x,+,1,)(,x,6,+,x,5,+,x,4,+,x,3,+,x,2,+,x+1),=,(,x,+,1,)(,x,3,+,x,2,+,1)(,x,3,+,x+1),g,1,(x)=(,x,+,1,)(,x,3,+,x,2,+,1)=,x,4,+,x,2,+,x,+,1,g,2,(x)=(,x,+,1,)(,x,3,+,x,+,1)=,x,4,+,x,3,+,x,2,+,1,取,g,x)=,g,1,(x)=,x,4,+,x,2,+,x,+,1,第38页/共40页,第三十九页，共40页。,A=(,a,6,a,5,a,4,a,3,a,2,a,1,a,0,),a,6,a,5,a,4,a,6,a,5,a,4,a,3,a,2,a,1,a,0,0 0 0,0 0 0 0 0 0 0,0 0 1,1,）,0 0 1 0 1 1 1,0 1 0,2,）,0 1 0 1 1 1 0,0 1 1,4,）,0 1 1 1 0 0 1,1 0 0,3,）,1 0 1,1 1 0 0,1 0 1,7,）,1 0 0,1 0 1 1,1 1 0,5,）,1 1 1,0 0 1 0,1 1 1,6,）,1 1 0,0 1 0 1,监督(jind)方程：,d,0,=4 t=1,第39页/共40页,第四十页，共40页。,