很好的汉明码介绍实用教案

1、 9.1 引言(ynyn)设计数字通信系统时，应首先合理选择调制、解调方法及发送功率。若不满足要求，则考虑差错控制。 从差错控制角度看，信道可以分为(fn wi)三类：即随机信道、突发信道和混合信道。随机信道在随机信道中、错码的出现是随机的，且错码之间是统计独立的。突发信道错码是成串集中出现的。混合信道存在随机和突发两种错码。第1页/共119页第一页，共120页。常用(chn yn)的差错控制方法有以下几种： 检错重发法接收端在收到的信码中检测出(发现)错码时，即设法通知发送端重发，直到正确收到为止。前向纠错法接收端不仅能发现错码，还能够确定错码的位置，能够纠正它。反馈校验法接收端将收到的信码

2、原封不动地转发回发送端与原信码比较。若发现错误则发端重发。三种差错控制方法可以结合使用。第2页/共119页第二页，共120页。接收端根据什么来识别有无错码由发送端的信道编码器在信息码元序列中增加一些监督码元。这些监督码和信码之间有确定的关系(gun x)，使接收端可以利用这种关系(gun x)由信道译码器来发现或纠正可能存在的错码。 在信息码元序列中加入监督码元就称为差错控制编码，有时也称为纠错编码。差错控制编码原则上是以降低信息传输速率为代价来换取传输可靠性的提高。第3页/共119页第三页，共120页。ARQ系统(xtng)组成信源编码器和缓冲存储重发控制双向信道译码器指令产生缓冲存储收信者

3、ARQ优点：冗余码元少、对信道有自适应能力、成本和复杂性低；ARQ缺点：需要反向信道、重发控制较复杂、干扰(gnro)大通信效率低、实时性差。第4页/共119页第四页，共120页。例：3位二进制数字(shz)构成的码组，共有8种不同的组合。若将其全部利用来表示天气，则可以表示8种不同的天气。000(晴)，001(多云)，010(阴)，011(雨)，100(雪)， 101(霜)， 110(雾)， 111(雹)。任一码组在传输中若发生一个或多个措码则将变成另一信息码组。这时接收端将无法发现错误。 9. 2 纠错(ji cu)编码的基本原理第5页/共119页第五页，共120页。若：000=晴001

4、=不可(bk)用010 =不可(bk)用011=云100 =不可(bk)用101=阴110=雨111 =不可(bk)用则： 虽然只能传送4种不同的天气但是接收消却有可能发现码组中的一个错码。 例如，若000(晴)中错了一位，则接收码组将变成100或010或001，这三种码组都是不准许(zhnx)使用的，称为禁用码组，故接收端在收到禁用码组时，就认为发现了错码。第6页/共119页第六页，共120页。但是这种码不能发现(fxin)两个措码，因为发生两个错码后产生的是许用码组。上述码只能检测错误，不能纠正错误。例如，当收到的码组为禁用码组100时，无法判断是哪一位码发生了错误因为晴、阴、雨三者错了一

5、位都可以变成100。要想能纠正错误，还要增加多余度。例如，苦规定许用码组只有两个：000(晴)、111(雨)、其余都是禁用码组。这时，接收场能检测两个以下错码，或能纠正一个错码。第7页/共119页第七页，共120页。 分组码的一般概念。 为了传输4种不同的信息，用两位二进制码组就够了，它们是：00、01、10、11。代表所传信息的这些两位码，称为信息位。前面使用3位码，多出的一位称为监督位。 信息码分组，每组信码附加(fji)若干监督码的编码集合，称为分组码。 例如第8页/共119页第八页，共120页。第9页/共119页第九页，共120页。分组码的结构(jigu) 符号(fho) (n，k)表

6、示分组码 k信息码元数 n码组长度(码长) n-k监督码元数an-1an-2arar-1a0k位信息位r位监督位n=k+r时间第10页/共119页第十页，共120页。码重、码距与码的纠检错能力(nngl) 码重“1”的数量称为码组的重量 码距两个码组对应位上数字不同的位数称为码组的距离，简称码距。又称汉明(Hamming)距离。 最小码距某种编码(bin m)中各个码组间距离的最小值称为最小码距(d0)。 若记： d0 最小码距； e检错位数； t纠错位数； 则有：第11页/共119页第十一页，共120页。（1） e +1 d0，即码的检错能力e比最小码距d0小1位；（2）2t+1 d0，即码

7、的纠错(ji cu)能力t的2倍比最小码距d0小1位；（3） e +t+1 d0 ，即若码同时纠t个错并检出e个错误，则e +t比最小码距d0小1位。以下说明：第12页/共119页第十二页，共120页。（1） e +1 d0第13页/共119页第十三页，共120页。（2） 2t +1 d0第14页/共119页第十四页，共120页。（3） t +e+1 d0第15页/共119页第十五页，共120页。差错控制编码(bin m)的效用 假设:发送“0”的错误概率和发送“1”的错误概率相等(xingdng)，都等于P，且P1，则在码长为n的码组中恰好发生r个错码的概率为rrnrrnnprnrnpprP

8、C)!( !)1 ()(例如(lr)，当码长n7时，p=10-3则有P7(1) 7p= 710-3 ；P7(2) 21p2=2.110-5 ；第16页/共119页第十六页，共120页。P7(3) 35p3=3.510-8。可见，采用差错控制编码，即使仅能纠正(或检测)这种码组中12个错误，也可以使误码率下降几个数量级。这就表明，即使是较简单(jindn)的差错控制编码也具有较大实际应用价值。第17页/共119页第十七页，共120页。 9. 3 常用的简单(jindn)编码1奇偶监督码奇偶监督码包括奇数( j sh)监督码和偶数监督码。只有一位监督位。在偶监督码中，监督位使码组中“l”的个数为偶

9、数，即满足下式条件在奇监督码中，监督位使码组中“l”的个数为奇数( j sh)，即满足下式条件0021aaann1021aaann第18页/共119页第十八页，共120页。2二维奇偶(q u)监督码又称方阵码。每一行是奇偶(q u)监督码的一个码组，若干码组再按列排列成矩阵，每列增加一位监督位。第19页/共119页第十九页，共120页。二维奇偶监督(jind)码特点：可检测偶数个错误适于检测突发错码。不仅可检错，还可纠一些错。检错能力强。第20页/共119页第二十页，共120页。 3恒比码每个码组均含有相同数目(shm)的“1”(和“0”)。 应用：电传机传输汉字，每个汉字用4位阿拉伯数字表示

10、。每个阿拉伯数字又用5位二进制符号构成的码组表示。每个码组的长度为5位，其中恒有3个1，称为5中取3恒比码。可能编成的不同码组数等于从5中取3组合数30。30种许用码组恰好可用来表示10个阿拉伯数字。第21页/共119页第二十一页，共120页。 4正反码(fn m)一种简单的能够纠正错码的编码。其中的监督位数与信息位数相同，监督码元与信息码元相同(是信息码的重复)或者相反(是信息码的反码(fn m)。 由信息码中“1”的个数而定。解码方法：先将接收码组中信息位和监督值按位模2相加，产生校验码组。最后，观察校验码组中“1”的个数，按表93进行判决及纠正可能发现的错码。第22页/共119页第二十二

11、页，共120页。 9. 4 线性分组码 从上节介绍的一些简单( jindn)编码可以看出，每种编码所依据的原理各不相同，而且是大不相同，其中奇偶监督码的编码原理利用了代数关系式。我们把这类建立在代数学基础上的编码称为代数码。在代数码中，常见的是线性码。线性码中信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的。本节将以汉明(Hamming)码为例引入线性分组码的一般原理。第23页/共119页第二十三页，共120页。回顾奇偶监督码在接收端解码时，实际上就是在计算若S0，认为无错；若S1，认为有错。上式称为监督关系式，S称为校正子。S只有两种取值，只能代表有、无错两种

12、信息(xnx)，不能指出错码位置。如果监督位增加一位，则增加一个监督关系式。由于两个校正子的可能值有4种组合：00，01，10，11，故能表示4种不同状态。0021aaann021aaaSnn第24页/共119页第二十四页，共120页。若用其一种表示无错，则其余3种就可能用来指示一位错码的3种不同位置。同理r个监督关系式能指示一位错码的(2r-1)个可能位置。 一般(ybn)地，若码长为n，信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求 2r-1 n，或者 2r r+k+1第25页/共119页第二十五页，共120页。 举例说明如

13、何构造监督关系式： 设(n，k)分组码中r=4。为了纠正一位错码，要求监督拉数r 3。若取r=3，则n=k+r=7。校正子与错码位置的对应(duyng)关系如表94规定(也可以另外规定) 。S1S2S3错码位置S1S2S3错码位置001A0101A4010A1110A5100A2111A6011A3000无错第26页/共119页第二十六页，共120页。 由表可见，当一错码在a2,a4，a5或a6时校正子S为1；否则S为0即构成如下(rxi)关系 同理24561aaaaS13562aaaaS03463aaaaS在发送端编码时，信息位a6a5a4a3的值决定于稳入信号(xnho)，因此它们是随机的

14、。监督值a2a1ao应根据信息位的取值按监督关系来确定即监督位应使上三式中的值为零(表示编成的码组中应无错码)，由此得到方程组第27页/共119页第二十七页，共120页。01356aaaa00346aaaa02456aaaa由此解出3561aaaa3460aaaa4562aaaa给定信息位后，可直接(zhji)按上式算出监督位，其结果如表95所列。第28页/共119页第二十八页，共120页。信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0000000010001110001011100110000101011010010001111010110010100110

15、1100001010110111010100110011111010001110001111111第29页/共119页第二十九页，共120页。 接收端收到每个码组后，先按监督方程计算出S1、S2、 S3 ，再按表94判断错码情况。例，接收0000011，可得： S1S2S3=011 。由表94可知(k zh)在a3位有错码。 (7，4)汉明码： 最小码距d0=3 纠一个错码或检测两个错码。 编码效率k/n=(2r-1-r)(2r-1)=I-rn。当n很大时，则编码效率接近1。第30页/共119页第三十页，共120页。 线性分组码的般原理。线性分组码是指信息位和监督位满足一组线性方程(xin x

16、n fn chn)的编码。 改写为01356aaaa00346aaaa02456aaaa01356aaaa000101110123456aaaaaaa001010110123456aaaaaaa010011010123456aaaaaaa第31页/共119页第三十一页，共120页。0001011001110101011101000123456aaaaaaa(模2)简记(jin j)为 或TTHA00TAH第32页/共119页第三十二页，共120页。101100111010101110100H称为监督(jind)矩阵IrPH001010100101111011110H矩阵(j zhn)的各个行是

17、线性无关的行数=监督位数，列数=码字长度典型(dinxng)阵第33页/共119页第三十三页，共120页。3561aaaa3460aaaa4562aaaa345620111aaaaa345611011aaaaa345601101aaaaa第34页/共119页第三十四页，共120页。3456012101111011110aaaaaaa Qaaaaaaaaaaa34563456012011101110111转置(zhun zh)得第35页/共119页第三十五页，共120页。 Gaaaaaaaaaaaaaaa3456345601234560111011101110001001001001000QIG

18、knk0111011101110001001001001000称为(chn wi)生成矩阵第36页/共119页第三十六页，共120页。GaaaaA3456生成矩阵G的每一行都是一个码组。例如(lr)，（参照前页矩阵G）。利用生成矩阵，码字TTHA0再由 得，0TTTMHGMGHMG0THG第37页/共119页第三十七页，共120页。 译码,若发送(f sn)码组为 接收码组为 二者之差为 其中E称为错误图样。021,aaaAnn021,bbbBnn021,eeeABEnniiiiibabae, 1, 0表示(biosh)该位接收码元无错；表示(biosh)该位接收码元有错。第38页/共119页

19、第三十八页，共120页。 接收端译码时计算 当接收码组无错时S等于零 有错但不超过检错能力时， S不等于零。 在错码超过检错能力时，B变为另一许用码组，仍能成立S等于零。这样的错码是不可检测的。 S称为(chn wi)校正子(伴随式) 。S只与E有关，而与A无关，意味着S与E有的线性变换关系，能与E一一对应，可指示错码位置。SEHEHAHHEABHTTTTT)(第39页/共119页第三十九页，共120页。 线性码重要性质之一，是它具有封闭性。 若：A1和A2是线性码中的两个(lin )许用码组，则：(A1+A2)仍为其中的一个码组。 由封闭性，两个(lin )码组之间的距离必是另一码组的重量。

20、故码的最小距离即是码的最小重量(除全“0”码组外)。 线性码又称群码，这是由于线性码的各许用码组构成代数学中的群。第40页/共119页第四十页，共120页。 9. 5 循环码 9. 5 . 1 循环码原理： 在线性分组码中，有一种(y zhn)重要的码称为循环码。循环码除了具有线性码的一般性质外还具有循环性，即任一码组循环一位(将最右端的码元移至左端，或反之)以后，仍为该码中的一个码组。即若 是许用码组，则 也是许用码组。021,aaaAnn102,nnaaaA第41页/共119页第四十一页，共120页。 循环码举例( j l)(7,3)循环码码组信息位监督位码组 信息位监督位编号a6a5a4

21、a3a2a1a0编号a6a5a4a3a2a1a00000000041001011100101115101110020101000611001013011100171110010第42页/共119页第四十二页，共120页。 码组的多项式表示码多项式。 例如(lr) A=1100101 A(x)=1x6+1x5+0 x4+0 x3+1x2+0 x1+1x0 =x6+x5+x2+1 码多项式表示具有线性的性质021,aaaAnn0112211)(axaxaxaxAnnnn第43页/共119页第四十三页，共120页。 码多项式的按模运算 循环移位 对应(duyng)的码多项式 如果规定xn=x0，即规

22、定xn+1=0，则有021,aaaAnn102,nnaaaA1102312)( nnnnnaxaxaxaxA)()( xAxxA第44页/共119页第四十四页，共120页。 这种xn+1=0的规定(gudng)，实质上是一xn+1为模的运算。对于整数m,若可以表示为 则称m=p(模n) ，或称m与p是同余的。 码多项式也有类似的运算。多项式F(x)被n次多项式N(x)除，得到商式q(x)和一个次数小于n的余式R(x)，即 F(x)q(x)N(x)+R(x) 则写为F(x)R(x) ( 模N(x) )npQnm第45页/共119页第四十五页，共120页。 码多项式系数仍按模2运算，即只取值0和1

23、。例如(lr) 于是，可以有 由此可见为了使xn=1，只需做模xn+1的运算即可。 例如(lr)：x4+x2+1=x2+x+1 模x3+1111111133333xxxxx) 1(mod133xx第46页/共119页第四十六页，共120页。 由前面(qin mian)的分析可知，若T(x)是码多项式，则在模xn+1的运算条件下， xiT(x)仍然是码多项式。 第47页/共119页第四十七页，共120页。2循环码的生成矩阵G 若能找到k个线性无关(wgun)的码组,就能构成矩阵G。在循环码中，一个(n，k)码有2k个不同码组，若用g(x)表示其中前(k-1)位皆为0的码组，即 g(x)=0 1x

24、 x k位 n-k位则g(x) 、xg(x)，x2g(x) ，xk-1g(x)都是码组，而且这k个码组是线性无关(wgun)的。因此可以用来构成循环码的生成矩阵G。 第48页/共119页第四十八页，共120页。第49页/共119页第四十九页，共120页。 例 表96的循环码, 唯一的一个(n-k)次码多项式代表(dibio)的码组是0010111，相对应的码多项式为)()()()(21xgxxgxgxxgxGkk一旦(ydn)确定了g(x)，则整个(nk)循环码就被确定了。因此,循环码的生成矩阵G可以写成第50页/共119页第五十页，共120页。 这个生成矩阵不是系统码的生成矩阵，可以通过(t

25、nggu)行变换，变换成系统码的生成矩阵。001011101011101011100)()()(2xgxxgxgxG g(x)x4+x2+x+1将此g(x)代入上式，得到(d do)第51页/共119页第五十一页，共120页。g(x)的性质：g(x)必须是一个常数项a0=1；次数(csh)为(n-k)次；唯一的(n-k)次多项式；我们称这唯一的g(x)为码的生成多项式。g(x)是xn+1的因式（见后面分析）。第52页/共119页第五十二页，共120页。说明g(x)是xn+1的因式。因为(yn wi)任码多项式T(x)都是g(x)的倍式，所以有 T(x)=h(x)g(x)g(x)本身也是一个码组

26、，其次数为n-k次。把它循环移位k次仍为一个码组。所以xkg(x)是n次多项式，在模xn+1 运算下，所以即) 1(mod),()(nkxxTxgx1)()(1)(nnkxxTxQxxgx第53页/共119页第五十三页，共120页。因为xkg(x)是n次的，所以Q(x)=1 。所以所以即 g(x)是xn+1的因式。 这样就可以通过对xn+1的因式分解(yn sh fn ji)得到g(x).1)()(11)(11)(nnnkxxgxhxxTxxgx1)()(nkxxgxhx第54页/共119页第五十四页，共120页。因为所有码多项式T(x)都可被g(x)整除(zhngch)。所以非系统码编码：T

27、(x)=m(x)g(x)系统码编码：用xn-k乘m(x)，即把m(x)左移n-k位；用xn-k除以g(x)，得余式r(x)；T(x) =xn-km(x)+ r(x)9.5.2 循环码的编、解码(jim)方法第55页/共119页第五十五页，共120页。 例：信息(xnx)码110， 信息(xnx)码多项式m(x)=x2+x 生成多项式g(x)=x4+x2+x+1 即 于是，编出码字1100000+101=1100101第56页/共119页第五十六页，共120页。硬件(yn jin)实现固定除式的多项式除法abcd信息(xnx)码元输入移存器反馈输出mabcddf00000011110111100

28、11101010100010100000101100001000000011校验码元第57页/共119页第五十七页，共120页。2循环码的解码(jim)方法检错解码的要求有两个：检错和纠错。码多项式T(x)应能被生成多项式g(x)整除。若接收码组与发送(f sn)码组相同，即R(x)=T(x)，则接收码组R(x)必定能被g(x)整除；若码组在传输中发生错误，则R(x)除以g(x) 时可能有余项，即有 R(x)/g(x)=Q(x)+r(x)/g(x)第58页/共119页第五十八页，共120页。检错电路(dinl)见图9-7(a)接收(jishu)码组缓冲移位寄存器除法电路反相与门重发指令输出信息

29、码余式等于1 时输出1余式等于0 时输出0第59页/共119页第五十九页，共120页。2循环码的解码方法(fngf)纠错前提：每个可纠正的错误图样必须与伴随(bn su)式一一对应。步骤：由接收多项式除以生成多项式得到余式r(x)；通过余式r(x)与错误图样的关系得到错误图样e(x)；从接收多项式中减去错误图样村e(x)。电路如下：第60页/共119页第六十页，共120页。图9-7(b)第61页/共119页第六十一页，共120页。 假定接收( jishu)码组为10*O0101，其中右上角打*号者为错码。此码组进入除法电路后，移位寄存器各级的状态变化过程列于表97(b)。(见演示)输入移存器

30、输出fabcde0000001111000*01110011010010000110100001010100100000011000000第62页/共119页第六十二页，共120页。9.5.3 缩短(sudun)循环码通过缩短循环码，可以满足系统设计中，码长、信息位和纠错能力的不同(b tn)要求。对于(n,k)循环码，使前i(0ik)个信息位为零可得到有2k-i个码组的集合，然后从这些码组中删去这i个零信息位，得到一种新的(r-i，k-i)的线性码，称为缩短循环码。缩短循环码与产生该码的原循环码至少具有相同的纠错能力。缩短循环码的编码和译码可用原循环码使用的电路完成。第63页/共119页第六

31、十三页，共120页。 例：若要求(yoqi)构造一个能够纠正一位错误的(13，9)码，则可以由(15，11)汉明码选出前面两个信息位均为零的码组。然后在发送时，这两个零信息不发送，即发送的是(13，9)缩短循环码。 因校验位数相同，(13，9)码与(15，11)循环码具有相同的纠错能力。第64页/共119页第六十四页，共120页。9.5.4 BCH码BCH码是一类纠正多个随机错误的特殊的循环码。特点是可以(ky)根据给定的纠错能力，找出生成多项式。 BCH码分两类：本原BCH码和非本原BCH码。本原BCH码的码长为n=2m-1(M 3)，生成多项式g(x)中含有最高次数为m次的本原多项式；非本

32、原BCH码的码长n是2m-1的一个因子，它的生成多项式中不含有最高次数为m的本原多项式。第65页/共119页第六十五页，共120页。 对于正整数m(M3)和t(t 2)必存在有下列参数的二进制BCH码：码长n=2m-1，监督( jind)位数rmt，能纠正所有的小于或等于t个随机错误的BCH码。 BCH码生成多项式 g(x)=LCMm1(x)，m2(x)， m2t-1(x) 式中t可纠正的错误个数； mi(x)最小多项式; LCM( )指取括号内所有多项式的最小公倍式.第66页/共119页第六十六页，共120页。 查表法得到生成多项式，用八进制数表示(biosh)。 例如当n=7,k=4,t=

33、1 g=(13)8 意指 g=(001011)2 g(x)=x3+x+1 n=3 kt g(x)117 n=7kt g(x)41131377表98（部分(b fen)）第67页/共119页第六十七页，共120页。 R-S码是一类具有很强纠措能力的多进制BCH码。 伽罗华域(即有限域) ：对于有限个符号，若符号的数目(shm)是一素数的幂，可以定义有加法和乘法，则构成符号域为有限域；若它是2m个符号的域则称之为伽罗华域GF(2m) . 例如，两个符号0、1，定义有模2加法和模2乘法，即 0+0=0，0+1=1，1+1=0； 00=0，01=1，111，则称之为二元域，也是伽罗华域。9.5.5 里

34、德-索罗门码（R-S码）第68页/共119页第六十八页，共120页。从两个符号0和1及一个m次多项式p(x)开始，并引入一个新符号 ，设p()=0。若适当地选择p(x)就可得到的各次幂，一直(yzh)到2m-2次幂，都不相同，并且m-1 =1。这样一来， 构成GF(2m)的所有元素。域中每个非零元素还可以用上面元素的和来表示。例如，m=4和p(x)=x4+x+1，则2242, 1 , 0m第69页/共119页第六十九页，共120页。 得到(d do)GF(24)的所有元素，详见表9-10。01 2 3 4= +1 5= (+1)=2+ 6=(2+)= 3+2第70页/共119页第七十页，共12

35、0页。 7=(3+ 2)= 3+2 = 3+1 8=(3+1)= 4+2 +1=2 +1 9=(2 +1)= 3+ 10=(3+)= 2 +1 11=(2 +1)= 3+ 2 + 12= (3+ 2 +)= 3+ 2 +1 13= (3+ 2 +1)= 3+ 2+1 14=(3+ 2+1)= 3 +1第71页/共119页第七十一页，共120页。R-S码是q进制BCH码的子类。具有如下的参数：码长：n=q-1符号监督位数： r=2t符号纠错位数： t 符号生成多项式：每个码元都是q进制的，通常令q=2m，则每个q进制码元都可以表示(biosh)为m位二进制码元，于是码长mn位，监督位数mr位，信

36、息位数： mn- mr位。)()()(22txxxxg第72页/共119页第七十二页，共120页。R-S码应用(yngyng)： 由于采用多进制，所以对于多进制调制是自然和方便(fngbin)的编码手段; 因为RS码能够纠正t个q位二进制码，即对以纠t个连续的突发性二进制错误,所以适合衰落信道应用; RS码可应用在计算机存储系统中以克服系统的差错。第73页/共119页第七十三页，共120页。 卷积编码则把k比特信息段编成n比特的码组，但所编的n长码组不仅同当前(dngqin)的k比特信息段有关联，而且还同前面的(N-1)个信息段有关联，人们常称这N为该卷积码的约束长度。 一般来说，对于卷积码，

37、k和n是较小的整数, 常把卷积码记作(n,k,N)卷积码，它的编码效率为R=k/n。 9. 6 卷积码第74页/共119页第七十四页，共120页。961 卷积码的图形(txng)描述 (3,1,3)卷积码编码器第75页/共119页第七十五页，共120页。 编码器的输入(shr)和输出第76页/共119页第七十六页，共120页。树状图第77页/共119页第七十七页，共120页。状态图第78页/共119页第七十八页，共120页。状态图第79页/共119页第七十九页，共120页。网格(wn )图第80页/共119页第八十页，共120页。网格图特点： 有2N-1种状态；对于k个输入信息比特，相应(xi

38、ngyng)出现有2k条支路；码树中的上支路用实线表示，下支路用虚线表示：支路上标注的码元为输出比特；从第N个节点开始，图形开始重复，且完全相同。第81页/共119页第八十一页，共120页。 例9-1 (3,1,3)编码器，起始状态为a，输入序列为1101011，求输出(shch)序列和相应状态变化路径。 解：由卷积码的网格图，可找出编码时网格图中的编码路径如图913所示，由此即可得到输出(shch)序列。为第82页/共119页第八十二页，共120页。第83页/共119页第八十三页，共120页。9.6.2 卷积码的解析(ji x)描述1生成矩阵卷积码是一种(y zhn)线性码。一个线性码完全由

39、一个监督矩阵H或生成矩阵G所确定。生成矩阵G 输入第一个信息比特m1时，y1,1=m1； y21=m1 ；y31=m1。 输入第二个信息比特m2时，y1,2=m2； y22=m2 ；y32= m1 + m2。第84页/共119页第八十四页，共120页。输入第j个信息比特mj时， y1j=mj； y2j=mj +mj-2 ； y3j= mj +mj-1+mj-2上式可写成矩阵(j zhn)形式 mj +mj-1+mj-2 A = y1j y2j y3j第85页/共119页第八十五页，共120页。 其中生成矩阵为 在过渡(gud)时刻 m1 0 0 T1 = y11 y21 y31 m1 m2 0

40、 T2 = y12 y22 y32 其中111100110A第86页/共119页第八十六页，共120页。0000001111T 输出(shch)矩阵与输入矩阵的关系有 Y=MG0001111002TAAAATTG00000021第87页/共119页第八十七页，共120页。 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 上面矩阵空白处均为0元素。该生成(shn chn)矩阵是半无限矩阵。第88页/共119页第八十八页，共120页。2 . 多

41、项式描述例如：输入序列(xli)1101110 可表示为 m(x)=1+x+x3+x4+x5+连接关系表示为 g1(x)=1 g2(x)= 1+x2 g3(x)= 1+x+x2编码输出为 y1(x)=m(x)g1(x)= 1+x+x3+x4+x5+ y2(x)=m(x)g2(x)=(1+x+x3+x4+x5+)(1+x2)第89页/共119页第八十九页，共120页。=1+x+x3+x4+x5+ +x2+x3+x5+x7+ = 1+x +x2 +x4 +x7 y3(x)= (1+x+x3+x4+x5+)(1+x+x2)= 1+x+x3+x4+x5+ x+x2+x4+x5+x6+ x2+x3+x5

42、+x6+ x7+ =1+ x5 + x7+ 对应(duyng)的序列为第90页/共119页第九十页，共120页。 y1=1 1 0 1 1 1 0 0； y2=1 1 1 0 1 0 0 1 y3=1 0 0 0 0 1 0 1 总的输出序列为 Y=y11,y21,y31,y12,y22,y32, = 1 1 1, 1 1 0, 0 1 0, 1 0 0, 1 1 0, 1 0 1, 0 0 0, 0 1 1, 结果(ji gu)与网格图是一样的。 第91页/共119页第九十一页，共120页。卷积码编码器的一般(ybn)结构第92页/共119页第九十二页，共120页。9.6.3 卷积码译码卷积

43、码的译码方法有两类：一类是大数逻辑(lu j)译码，又称门限译码：另一类是概率译码。概率译码又分为维特比译码和序列译码两种。门限译码方法是以分组码理论为基础的其译码设备简单，速度快，但其误码性能要比概率译码法差。下面只介绍维特比译码。第93页/共119页第九十三页，共120页。9.6.3维特比译码维特比译码算法，简称VB算法。维特比(viterbi)译码和序列译码都属于概率译码。当卷积码的约束长度不太大时，与序列译码相比，维持比译码器比较简单，计算速度更快。VB算法在前向纠错系统中用得较多，在卫星通信中已被采用(ciyng)作为标准技术。第94页/共119页第九十四页，共120页。 概率译码的

44、基本想法是：把已接收序列与所有(suyu)可能的发送序列做比较，选择其中码距最小的一个序列作为发送序列。 如果发送L组信息比特，对于(n,k)卷积码来说，可能发送的序列有2kL个，计算机或译码器需存储这些序列并进行比较，以找到码距最小的那个序列。当传信率和信息组数人较大时，使得泽码器难以实现。第95页/共119页第九十五页，共120页。VB算法则对上述概率译码(又称最大似然译码)做了简化，使其成为一种实用的译码算法。它并不是在网格图上一次比较所有可能的2kL条路径(序列)，而是接收(jishu)一段，计算和比较一段，选择一段有最大似然可能的码段。从而达到整个码序列是一个有最大似然值的序列。以下

45、以（2,1,3)卷积码为例说明：第96页/共119页第九十六页，共120页。第97页/共119页第九十七页，共120页。第98页/共119页第九十八页，共120页。设输入信息数目L=5，所以画有L+N=8个时间单位。编码器从a状态开始(kish)工作。该网格图的每一条路径都对应着不同的输入信息序列。由于所有的可能输入信息序列共有2kL=32个.第99页/共119页第九十九页，共120页。 设输入编码器的信息序列为(11011000)，则由编码器输出的序列 y(1101000010,11100)，编码器的状态转移路线为abdcbdca。 若收到的序列为R=0101011001011100，对照(

46、duzho)网格图来说明维特比译码的方法。 前3步输入R=010101；根据不同输入信息，编码器的输出序列以及它们与接收序列的距离见下表第100页/共119页第一百页，共120页。R=010101信息编码路径距离000000000 aaaa3001000011 aaab3010001110 aabc4011001101 aabd2100111011 abca4101111000 abcb4110110101 abdc1111110110 abdd3前3步对应网格图幸存路径(ljng)，如下页第101页/共119页第一百零一页，共120页。对应4条幸存路径的序列(xli)分别为： a-a-a-a

47、000000 a-a-a-b000011 a-b-d-c110101 a-a-b-d001101.第102页/共119页第一百零二页，共120页。到第5步的幸存路径和对应(duyng)的序列分别为： a-a-b-d-d-c001101 1001. a-b-d-c-a-a110101 1100 a-b-d-c-a-b110101 1111 a-b-d-c-b-d110101 1101第103页/共119页第一百零三页，共120页。到第8步的幸存路径和对应的序列分别为： a-b-d-c-b-d-c-a-a 11 01 01, 00 01 01 11 00对应信息(xnx)1 1 0 1 1 0 0

48、 0与发送信息(xnx)相同。对比接收0*1 01 01 1*0 01 01 11 00纠正了两个错误。第104页/共119页第一百零四页，共120页。总结与复习第一章 绪论通信系统的基本组成模型；模拟(mn)与数字通信系统组成；通信系统分类；数字通信系统优点；模拟(mn)与数字通信系统的性能指标；离散消息的信息量和平均信息量 ；例题：例1.4.1，习题2、4、6、7 第105页/共119页第一百零五页，共120页。 第二章 随机信号分析 平稳随机过程的定义、性质； 什么是广义平稳随机过程？ 平稳随机过程的自相关函数与功率谱密度(md)如何定义，有何性质？ 平稳随机过程通过线性系统后，均值、自

49、相关与方差、功率谱密度(md)有何关系？第106页/共119页第一百零六页，共120页。 什么是高斯噪声？什么是高斯白噪声？什么是窄带高斯噪声？ 窄带高斯噪声的幅度和相位服从什么分布(fnb)？ 窄带高斯噪声的同相分量和正交分量服从什么分布(fnb)？ 习题1、2、3、7、8、12第107页/共119页第一百零七页，共120页。 第三章 信道 信道分类：广义信道与狭义信道、调制信道与编码信道、恒参信道与变参信道； 什么是幅频畸变、什么是相频畸变、什么是群延迟？ 什么是多径，它对信号(xnho)的传输产生哪些影响（平坦瑞利衰落、频率选择性衰落）？ 什么是分集，它的作用是什么？有哪写分集方式？有哪几种合并方式？第108页/共119页第一百零八页，共120页。 离散信道信道的信道容量是如何定义的，它的物理(wl)意义是什么？ 连续信道信道的信道容量是如何定义的（山农公式）？ 习题8、13、14、15 第五章 数字信号的基带传输 基带传输系统组成模型。 基带数字信号的时域表达式、功率谱密度的一般表达式；第109页/共119页第一百零九页，共120页。 码型的概念与常用码型（单极性非归零、单极性归零、双极性非归零、差