信息论与编码第五讲优秀课件.ppt

《信息论与编码第五讲优秀课件.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第五讲优秀课件.ppt（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码第五讲第1页，本讲稿共103页主要内容主要内容uRS编译码编译码u卷卷积编译码积编译码第2页，本讲稿共103页5.1RS码码第3页，本讲稿共103页5.1.1RS编码编码RS码码=Reed-Solomoncode=里德里德-索洛蒙码索洛蒙码是是BCH码最重要的一个子类。码最重要的一个子类。可视为可视为BCH码的特例码的特例,是是m=1,m0=1时的时的q元本原元本原BCH码码。由由于于最最小小多多项项式式的的次次数数不不会会超超过过m,当当m=1时时，2t个个连连续续幂幂次次的的根根(x-)(x-2)(x-2t)既既是是q元元扩扩域域GF(q1)上上的的根根多多项式，又是项式，又是

2、q元基域元基域GF(q)上的最小多项式。上的最小多项式。这这种种性性质质给给多多元元BCH码码的的设设计计带带来来了了很很多多的的方方便便，因因为为我我们们在在前前面面已已经经看看到到，由由扩扩域域i次次幂幂根根 i求求基基域域对对应应的的最最小小多多项项式式是是十十分分麻麻烦烦的的事事，而而RS码码的的一一次次根根式式(x-)就就是是最最小多项式，无需另外再去计算。小多项式，无需另外再去计算。第4页，本讲稿共103页本原本原RS码具有如下参数：码具有如下参数：码长：码长：n=q-1校验位：校验位：n-k=2t最小距离：最小距离：dmin=2t+1生成多项式：生成多项式：g(x)=(x-)(x

3、-2)(x-2t)=an-k xn-k+an-k-1 xn-k-1+a1x+a0(4-32)式中，式中，g(x)的各次系数的各次系数ai 取自扩域取自扩域GF(q1)ai 0,1,2,q-2(i=0n-k)(4-33)由以上参数可见由以上参数可见 dmin=2t+1=n-k+1 因此，因此，RS码也是码也是MDC码码（极大最小距离）（极大最小距离）第5页，本讲稿共103页注意：注意：GF(q)和和GF(q1)含义不同含义不同GF(q)是是数域数域，q必须是素数必须是素数GF(q1)是是多项式域多项式域，q不一定是素数，不一定是素数，工程上，工程上，q通常取为通常取为2的幂次。的幂次。GF(8)

4、?01234567表表4-9 用用x3+x+1产生的产生的GF(81)GF(81)多项式多项式3重重000 0 0110 0 1 0 1 0 2 21 0 0 3+10 1 1 4 2+1 1 0 5 2+11 1 1 6 2+11 0 14+5=1mod8 3+4=64的乘法逆元？的乘法逆元？第6页，本讲稿共103页例例4.10试设计一个试设计一个(7,3,5)本原本原RS码。码。解解：由由于于码码长长n=q-17，可可断断定定码码元元是是8进进制制的的。8进进制制域域元素可以用根的幂次、多项式或元素可以用根的幂次、多项式或3重矢量表示。重矢量表示。若若令令 是是本本原原多多项项式式p(x)

5、=x3+x+1的的根根，即即 3=+1，我我们可以列出表们可以列出表4-9。因题中要求因题中要求dm=5t=INT(dm-1)/2=2这这说说明明生生成成多多项项式式g(x)有有4个个连连续续根根、2、3、4。由由(式式4-32):g(x)=(x-)(x-2)(x-3)(x-4)=x2-(+2)x+3x2-(3+4)x+7=x2-4x+3x2-6x+1=x4-(6+4)x3+(1+10+3)x2-(4+9)x+10=x4+3x3+x2+x+3在上式运算中用到了关系式在上式运算中用到了关系式 3=+1以及二元扩域的一些以及二元扩域的一些运算规则，比如运算规则，比如 i+i=0、7=1等等。第7页

6、，本讲稿共103页此此8进制进制(7,3,5)RS码的生成矩阵为：码的生成矩阵为：G=通过矩阵行运算可以将它系统化通过矩阵行运算可以将它系统化,得得G=1 31 300第第行行01 31 30第第行行001 31 3第第行行100 41 4 5+3+2010 21 6 6+3001 31 3生成多项式的运算同样可用除法器实现，只是所作的生成多项式的运算同样可用除法器实现，只是所作的运算是运算是GF(81)域的乘、加运算。域的乘、加运算。第8页，本讲稿共103页例例：用上面设计的：用上面设计的(7,3,5)本原本原RS码，对一个二元序列码，对一个二元序列（111011010）实行编码。）实行编码

7、。解解：将二元序列化作：将二元序列化作GF(81)元素，得元素，得m:（111011010）(5 3)C=mG=(5 3)=(5,3,9+5+4,5+3+,2+2+2,3+2+4)=(5,3,6,4,2,1)对应的对应的(21,9)二进制衍生码字是：二进制衍生码字是：（111011010101110100001）1 0 0 4 1 4 50 1 0 2 1 6 60 0 1 3 1 3第9页，本讲稿共103页(7,3,5)RS码的码的t=2,能纠能纠2个差错。个差错。衍生为衍生为(21,9)二元码后，纠随机差错能力与原二元码后，纠随机差错能力与原(7,3)RS码一码一样样t=2，还能纠长度，还

8、能纠长度4的任何突发差错。这是因为信道的任何突发差错。这是因为信道上长度为上长度为4的突发差错最多影响到两个二进制的突发差错最多影响到两个二进制3重矢量，相重矢量，相当于两个当于两个8进码元出错，仍在进码元出错，仍在t=2范围之内。范围之内。(5,3,6,4,2,1)（111,011,010,101,110,100,001）能纠的随机差错能纠的随机差错（111,011,010,101,110,100,001）能纠的突发差错能纠的突发差错（111,011,010,101,110,100,001）（111,011,010,101,110,100,001）不能纠不能纠第10页，本讲稿共103页上述这

9、种用二进制码表示的上述这种用二进制码表示的q进制进制RS码称为该码称为该RS码的二进衍生码，衍生指码的二进衍生码，衍生指GF(q1)和和GF(2)两个域间的映两个域间的映射。可以证明，这种映射是把射。可以证明，这种映射是把线性码映射成线性码线性码映射成线性码，映射后的二进衍生码一定是线性分组码，但映射后的二进衍生码一定是线性分组码，但不一定是不一定是循环码循环码。一一般般来来说说，一一个个随随机机差差错错能能力力为为t的的RS码码，其其二二进进衍衍生生码码可可以以纠纠正正小小于于等等于于t个个随随机机差差错错，或或者者纠纠正正单单个个长度为长度为b的突发差错，的突发差错，b(t-1)m+1(4

10、-35)以及其它大量错误图样。以及其它大量错误图样。可见，二进衍生码特别适用于纠突发差错，这就是它可见，二进衍生码特别适用于纠突发差错，这就是它在无线通信中被广泛采用的原因。在无线通信中被广泛采用的原因。第11页，本讲稿共103页 q进进制制RS码码也也可可以以扩扩展展。对对于于(n,k,d)RS码码(n=q-1)，我我们可以给每个码字：们可以给每个码字：(C0,C1,Cn-1)增加一个全校验位增加一个全校验位Cn(modq)(4-36)使此扩展使此扩展RS码字的全体码元码字的全体码元C0,C1,Cn-1之和为零。之和为零。可以证明：如果该码字生成多项式可以证明：如果该码字生成多项式g(x)不

11、含不含(x-1)因子因子(或或1不是不是g(x)的根的根)，那么加了一个全校验位后，能使扩展，那么加了一个全校验位后，能使扩展码的最小距离增加码的最小距离增加1，即得到，即得到(n+1,k,d+1)扩展扩展RS码。比如码。比如上例上例(7,3,5)RS码扩展出来的码扩展出来的(8,3,6)码，其二进衍生码是码，其二进衍生码是(24,9)二元码二元码。第12页，本讲稿共103页IBM3370磁盘存储系统采用磁盘存储系统采用256进制进制(255,252)RS码的缩短码，并对应成码的缩短码，并对应成8比特比特(1(1字节字节)一组的二进制衍生一组的二进制衍生码。该码的基本参数是：码。该码的基本参数

12、是：q=28=256,n=q-1=255,t=1。该该RS码的码元取自本原多项式码的码元取自本原多项式P(x)=x8+x4+x3+x2+1生成的扩域生成的扩域GF(28),通过列出类似表通过列出类似表4-9那样的对照表，可那样的对照表，可以找出域元素运算及与二进制以找出域元素运算及与二进制8重矢量映射（衍生）关系，重矢量映射（衍生）关系，其生成多项式是：其生成多项式是：g(x)=(x-1)(x-1)(x-)使用时，一个扇区的使用时，一个扇区的512字节加一个字节加一个0字节变为字节变为513字节，分字节，分成成3组、每组组、每组513 3171字节，编成字节，编成3个由个由(255，252)缩

13、短缩短下来的下来的(174，171)RS码字。实际介质中使用的是码字。实际介质中使用的是（8174，8171）RS衍生码。衍生码。第13页，本讲稿共103页在在CD唱片中，采用了两级纠错加交织器的差错控制方唱片中，采用了两级纠错加交织器的差错控制方案。纠错码用的是案。纠错码用的是q=28=256进制的进制的(255，251)RS码，纠码，纠错能力错能力t=2。使用时，将它缩短为。使用时，将它缩短为(28,24)的外码和的外码和(32,28)的内码两种。的内码两种。每秒每秒44.1k采样、每采样采样、每采样16比特的比特的数字音频码流数字音频码流(1644.1k=1.41Mb/s)被分割成被分割

14、成24字节字节（192bit）的信息组，每字节对应一个）的信息组，每字节对应一个256进制的码元，进制的码元，经（经（28，24）RS编码器编出编码器编出28字节（字节（224bit）一组的）一组的256进制的外码码元。这些码元经进制的外码码元。这些码元经4行行5列列(45字节交织器字节交织器)交织交织后由后由(32，28)RS编码器二次编码，输出编码器二次编码，输出32字节（字节（256bit）一组内码码元，每码元写入一组内码码元，每码元写入CD盘的一个字节。读出是写盘的一个字节。读出是写入的逆过程，包括入的逆过程，包括RS（32，28）内码译码、去交织和）内码译码、去交织和RS（28，24

15、）外码译码。）外码译码。第14页，本讲稿共103页 整个过程中，整个过程中，24字节音频信号转为字节音频信号转为32字节磁盘存字节磁盘存储，码率为储，码率为0.75，要求，要求CD盘的读出速率至少大于盘的读出速率至少大于1.41 0.75=1.88Mb/s(没考虑其它任何开销没考虑其它任何开销)。具体译码中，当内码遇到一个可检不可纠的差错时具体译码中，当内码遇到一个可检不可纠的差错时将会对外码发送一个信息以提高外码的纠错能力；当差将会对外码发送一个信息以提高外码的纠错能力；当差错超过外码的纠错能力时，会对播放系统发送一个信息，错超过外码的纠错能力时，会对播放系统发送一个信息，将该译码样值删除而

16、改用前、后样值的插值将该译码样值删除而改用前、后样值的插值(interpolating)。如果差错太多而超出了插值运算的能力，。如果差错太多而超出了插值运算的能力，播放系统将插入一段静音播放系统将插入一段静音(mute)替代这个突发差错。替代这个突发差错。第15页，本讲稿共103页在宇航中，在宇航中，RS码和卷积码是一对黄金搭配，码和卷积码是一对黄金搭配，用于深空用于深空(deepspace)通信中的纠错编码。通信中的纠错编码。深空信道属随机差错信道，用卷积码比较合适。深空信道属随机差错信道，用卷积码比较合适。但一旦信道噪声超出卷积码的纠错能力，就将导致突但一旦信道噪声超出卷积码的纠错能力，就

17、将导致突发性质的译码差错，这时用发性质的译码差错，这时用RS码来对付将是最佳选择。码来对付将是最佳选择。在在“探险者号探险者号”(Voyager)飞向木星和土星的飞向木星和土星的旅程中，信息就是以旅程中，信息就是以RS码为外码、卷积码为内码的级码为外码、卷积码为内码的级联码实现信道编码的。这种级联码性能优良，已被认为联码实现信道编码的。这种级联码性能优良，已被认为是一种宇航通信标准而称为是一种宇航通信标准而称为NASA码，可带来码，可带来57dB的编码增益。的编码增益。第16页，本讲稿共103页探险者探险者Voyager采用了采用了(255,223)RS码，在误比码，在误比特率特率Pb=10-

18、6时可获得时可获得2.5dB额外编码增益（与仅用额外编码增益（与仅用卷积码相比）。该卷积码相比）。该RS码每码字的码每码字的255个码元取值于个码元取值于256进制进制GF（256）的衍生二进制扩域）的衍生二进制扩域GF（28），生），生成扩域元素的本原多项式是成扩域元素的本原多项式是P(x)=x8+x4+x3+x2+1，生成多项式是生成多项式是g(x)=（x-）（）（x-2）（）（x-3）（x-32）式中式中 是本原多项式是本原多项式P(x)的根。由于生成多项式含的根。由于生成多项式含32个连续幂次的根，可知该码的纠错能力个连续幂次的根，可知该码的纠错能力 t=16码元码元（256进制），或

19、长度进制），或长度121(式式4-35)的二进制突发差错。的二进制突发差错。第17页，本讲稿共103页5.1.2 RS码迭代译码码迭代译码RS码码是是BCH码码的的子子类类，必必然然存存在在某某些些构构码码特特点点和和能能最最大大程程度度发发挥挥其其纠纠错错潜潜力力的的专专用用译译码码方方法法。RS码码译译码方法主要有：迭代译码码方法主要有：迭代译码和和快速译码。快速译码。RS码码是是MDC码码，码码的的最最小小距距离离d=n-k+1=2t-1，因因此此g(x)有有2t个个即即d-1个个连连续续幂幂次次的的根根。RS码码可可以以用用类类似似于于BCH码的迭代方式来译码，但必须增加一个步骤：码的

20、迭代方式来译码，但必须增加一个步骤：确确定定了了差差错错码码元元位位置置后后还还要要确确定定差差错错幅幅度。度。第18页，本讲稿共103页假设有假设有 个差错分布在个差错分布在j1、j2、j 位上，而位上，而差错幅值分别是差错幅值分别是ej1、ej2ej，则，则E(x)=ej1x j1+ej2x j2+ej x j(4-80)（0 j1 j2L时，效率损失趋于时，效率损失趋于0因而可忽略不计，每一个因而可忽略不计，每一个k 位信息组产生一个位信息组产生一个n 位位码字，卷积编码码率与分组码码率一样为码字，卷积编码码率与分组码码率一样为R=k/n。相反，相反，M相对于相对于L越小则效率损失越大，

21、当越小则效率损失越大，当M=1时码率损失系数接近时码率损失系数接近1。由此可见，卷积码的适用对象是电路交换的连续由此可见，卷积码的适用对象是电路交换的连续信息流，或包交换的信息流，或包交换的“流媒体流媒体”，或复用级的信息，或复用级的信息流，而不适合短突发、目的地分散的用户端包交换流，而不适合短突发、目的地分散的用户端包交换纠错编码。纠错编码。第66页，本讲稿共103页5.3.1卷积码的距离特性卷积码的距离特性卷卷积积码码的的性性能能取取决决于于卷卷积积码码距距离离特特性性和和译译码码算算法法。其其中中，距距离离特特性性是是卷卷积积码码本本身身的的属属性性，它它决决定定了了该该码码的的纠纠错错

22、能能力力，而而译译码码方方法法只只是是研研究究如如何何将将这这种种潜潜在在的的纠纠错错能力转化为现实的纠错能力。能力转化为现实的纠错能力。表表述述距距离离特特性性的的最最好好方方法法是是利利用用网网格格图图。若若序序列列C、C”是是从从同同一一时时刻刻（不不妨妨称称为为0时时刻刻）由由零零状状态态出出发发的的两两个个不不同同的的码码字字序序列列，它它们们所所对对应应的的信信息息序序列列分分别别是是M 和和M”，且且M M”。对对于于二二元元码码，序序列列距距离离d(C,C”)指指汉汉明明距距离离，等等于于C、C”的的对对应应项项逐逐一一模模2加加后后所所得得的的序序列列C的的重重量量，也也等等

23、于于序序列列C和和全全零零序序列列0的的距距离离或或序序列列C的的重量。重量。d(C,C”)=W(C C”)=W(C 0)=d(C,0)(5-16)第67页，本讲稿共103页 式式(5-16)默认：两码字序列之和仍是码字序列，这样默认：两码字序列之和仍是码字序列，这样任任意两码字序列间意两码字序列间最小距离才能等效于最小距离才能等效于全零序列与某非全零序列与某非全零序列的距离全零序列的距离。全零序列在网格图上表现为保持在零状。全零序列在网格图上表现为保持在零状态的一条横线，故两序列的最小距离也就是非全零路径与全态的一条横线，故两序列的最小距离也就是非全零路径与全零状态路径距离最小者。零状态路径

24、距离最小者。序序列列距距离离还还与与序序列列长长度度有有关关，同同一一序序列列对对在在不不同同长长度度比比较较时时显显然然距距离离也也不不同同。将将长长度度l 的的任任意意两两序序列列间间的的最最小小距距离离定定义义为为l 阶阶列列距距离离。以以长长度度l为为变变量量的的列列距距离离特特性性称称之之为为列距离函数列距离函数，用，用dc(l)来表示：来表示：dc(l)mind(Cl,C”l):M0 M”0(5-17)第68页，本讲稿共103页所所谓谓M0 M”0即即“不不同同”的的两两序序列列，在在网网格格图图上上的的表表现现就就是是从从零零时时刻刻起起两两序序列列轨轨迹迹从从零零状状态态分分道

25、道扬扬镳镳形形成成分分叉叉点点。由式由式(5-16)，式，式(5-17)可改写为可改写为dc(l)minW(C lC”l):M 0 M”0=minW(Cl):M0 0(5-18)由由于于早早期期卷卷积积码码译译码码方方法法与与约约束束长长度度（L+1）有有关关，于于是是曾曾把把（L+1）阶列距离称为最小距离）阶列距离称为最小距离dmdm=minW(CL+1):M0 0(5-19)而而把把由由零零状状态态零零时时刻刻分分叉叉的的无无限限长长的的两两个个序序列列之之间间的的最最小距离定义为小距离定义为自由距离自由距离：df=minW(C):M0 0(5-20)第69页，本讲稿共103页列距离、最小

26、距离、自由距离三者之间的关系是：列距离、最小距离、自由距离三者之间的关系是：dmdc(l)|l=L+1 (5-21)df=dc(l)(5-22)以下举例说明三个距离的求法。以下举例说明三个距离的求法。例例5-3二进制二进制(3,1,2)卷积码网格图如图卷积码网格图如图5-9，试求该码，试求该码1至至6阶列距离、最小距离和自由距离。阶列距离、最小距离和自由距离。解：距离的求法参见图解：距离的求法参见图5-10。第70页，本讲稿共103页110011010101000100000000000000000101111011001100010110101300100111011001001001101

27、145657667786998100100001111 最轻码字序列最轻码字序列列距离函数列距离函数dc(l)l1 S0S2 dc(1)=3 l2 S0S2S3 dc(2)=4 l3 S0S2S3S1 dc(3)=5(最小距离最小距离dm)l4 S0S2S3S1S0 dc(4)=6 或或S0S2 S1S0 S0 l5 S0S2 S1S0 S0 dc(5)=6 l6 S0S2 S1S0 S0 S0 dc(6)=6第71页，本讲稿共103页 由上例可推广出一个一般结论：自由距离就是从由上例可推广出一个一般结论：自由距离就是从零状态分叉后又回到零状态的所有路径中重量最轻的零状态分叉后又回到零状态的所

28、有路径中重量最轻的那一条的重量。那一条的重量。早期的卷积码文献都将最小距离早期的卷积码文献都将最小距离dm看作是最重要的看作是最重要的距离参数，这是由于那时的主要译码算法只有一个约距离参数，这是由于那时的主要译码算法只有一个约束长度（束长度（L+1）的记忆容量。后来维特比译码和序列译）的记忆容量。后来维特比译码和序列译码成为主要方法，这些译码算法的记忆长度在理论上可码成为主要方法，这些译码算法的记忆长度在理论上可不受限制，因此与这两种译码相联系的自由距离不受限制，因此与这两种译码相联系的自由距离df成了成了主要的列距离参数。加上主要的列距离参数。加上df又是决定卷积码性能的一个又是决定卷积码性

29、能的一个主要参数，以致在主要参数，以致在df逐步替代逐步替代dm的过程中有些人把这两的过程中有些人把这两个概念混为一谈了。个概念混为一谈了。df对卷积码的性能是决定性的，有对卷积码的性能是决定性的，有必要专门讨论一下必要专门讨论一下df的计算方法。的计算方法。第72页，本讲稿共103页5.3.2自由距离自由距离df的计算的计算 对于像例对于像例5-3-1那样简单的卷积码，可以直接从网格图那样简单的卷积码，可以直接从网格图中找出中找出df。但随着限制长度的增加，状态数将以指数速度。但随着限制长度的增加，状态数将以指数速度增加，网格图将变得非常复杂庞大，直接找出增加，网格图将变得非常复杂庞大，直接

30、找出df往往变往往变得不可能了。一般来说，在状态数小于得不可能了。一般来说，在状态数小于16或或32时，可以时，可以采用解析法，借助信号流图来求自由距离。采用解析法，借助信号流图来求自由距离。以下介绍两种计算方法：信号流图法和计算机搜索法。以下介绍两种计算方法：信号流图法和计算机搜索法。第73页，本讲稿共103页一一信号流图法信号流图法 卷积码的状态流图卷积码的状态流图(见见5.2.3节节)与信号流图之间具有拓与信号流图之间具有拓扑等效性，可将信号流图的理论和方法应用于卷积码的扑等效性，可将信号流图的理论和方法应用于卷积码的研究。研究。原则上，利用信号流图可计算任何一个以支路为原则上，利用信号

31、流图可计算任何一个以支路为基础线性积累的量。如果希望这个量以基础线性积累的量。如果希望这个量以“和和”的形式积的形式积累，可将这个量写作某个特定底数的指数，并令其幂为该累，可将这个量写作某个特定底数的指数，并令其幂为该支路的增益。若干支路的串联构成一条路径，路径增益是支路的增益。若干支路的串联构成一条路径，路径增益是组成此路径的各支路增益之乘积（其指数是各支路增益指组成此路径的各支路增益之乘积（其指数是各支路增益指数之和）。数之和）。作为研究对象的两个节点间可能有不止一条的路径，作为研究对象的两个节点间可能有不止一条的路径，所以路径增益的和式便是全图增益，称之为两节点之间所以路径增益的和式便是

32、全图增益，称之为两节点之间考虑对象量的考虑对象量的生成函数生成函数T(D)。第74页，本讲稿共103页将信号流图法用于自由距离计算时，一个将信号流图法用于自由距离计算时，一个“状态状态”对应一对应一个节点，我们感兴趣的量是不同转移间的距离（与个节点，我们感兴趣的量是不同转移间的距离（与全零转移相比就是重量），在连续转移中是以和的全零转移相比就是重量），在连续转移中是以和的形式累积的。因此，我们以各转移所形式累积的。因此，我们以各转移所对应的码字重量对应的码字重量Wj为指数来定义支路增益为指数来定义支路增益 和路径和路径增益增益 。由于自由距离是由零状态出。由于自由距离是由零状态出发又回到零状态

33、的最轻序列的重量，我们可以将零状态拆发又回到零状态的最轻序列的重量，我们可以将零状态拆开成两个节点：一个是始发点，一个是归宿点。这样，沿开成两个节点：一个是始发点，一个是归宿点。这样，沿着任一条由始发点到归宿点的路径都有一个路径增益，其着任一条由始发点到归宿点的路径都有一个路径增益，其中指数最小者就是最轻路径。中指数最小者就是最轻路径。第75页，本讲稿共103页从生成函数从生成函数T(D)的角度看，如果将所有指数相同的路的角度看，如果将所有指数相同的路径增益合并，各路径增益的和式可写作：径增益合并，各路径增益的和式可写作：(5-23)式中，系数式中，系数Ad 是路径增益指数为是路径增益指数为d

34、的不同路径的条数。的不同路径的条数。T(D)最低次非零项的指数就是最轻序列的重量，即自由最低次非零项的指数就是最轻序列的重量，即自由距离距离df。对对(5-23)式的分析揭示了生成函数式的分析揭示了生成函数T(D)与自由距离与自由距离df 的关系，这样就允许我们借用信号流图中所有计算生成的关系，这样就允许我们借用信号流图中所有计算生成函数的方法来计算卷积码的自由距离。函数的方法来计算卷积码的自由距离。第76页，本讲稿共103页实际中可供选用的方法主要有三种：实际中可供选用的方法主要有三种：(1).利利用用Mason的的增增益益公公式式参参见见S.J.MasonElectronicCircuit

35、,signalandsystem1960。这这种种方方法法过过去去使使用用较较多，有人称之为标准方法。多，有人称之为标准方法。(2).根根据据有有向向图图列列出出线线性性状状态态方方程程，从从而而把把“图图解解”的的问问题题转转化化为为解解线线性性方方程程的的问问题题。这这是是一一种种经经典典的的方方法法。因因为为列列方方程程有有一一定定的的规规律律，解解方方程程则则有有许许多多现现成成的的程程序和方法可供使用。序和方法可供使用。(3).通通过过图图论论变变换换吸吸收收部部分分节节点点，从从而而简简化化甚甚至至直直接接求求出生成函数出生成函数T(D)，这适用于较简单的流图。，这适用于较简单的流

36、图。第77页，本讲稿共103页例例5-4 二进制二进制(3,1,2)卷积码状态流图如图卷积码状态流图如图5-7。试用信号。试用信号流图法求该码自由距离流图法求该码自由距离df。解：将卷积码状态图（图解：将卷积码状态图（图5-7）的零状态）的零状态S0拆成一始发一拆成一始发一归宿两个节点归宿两个节点(图图5-12),状态的自环是全零码，在信号流状态的自环是全零码，在信号流图中不画出。图中不画出。令各支路的增益为令各支路的增益为D j（这里（这里j是与相应转移对应的码是与相应转移对应的码字重量，比如码字字重量，比如码字011的重量为的重量为2，对应的支路增益是，对应的支路增益是D2），可得信号流图

37、），可得信号流图(图图5-13)。再根据信号流图的一些初。再根据信号流图的一些初等变换规则（图等变换规则（图5-14），将图），将图5-13步步简化（图步步简化（图5-15），），最后得到生成函数：最后得到生成函数：第78页，本讲稿共103页 101 S3 100 010 111 110 001 S0 S2 S1 S0 011 图图5-12零状态拆分后零状态拆分后的状态流图的状态流图图图5-13相应信号流图和相应信号流图和各支路增益各支路增益 D2 D D S0 D3 S2 D2 S1 D S0 D2第79页，本讲稿共103页 A B A B A A+B B B BC A D AB D C A

38、 B图图5-14信号流图的初等变换信号流图的初等变换 AB 1-CC D2 D3 D D图图5-15卷积码信号流图的简化卷积码信号流图的简化 D2 1-D2 D2第80页，本讲稿共103页运用多项式除法（长除法），得：运用多项式除法（长除法），得：(5-24)(5-24)这这是一个无限多项式，多项式的每项对应网格图上的一类非是一个无限多项式，多项式的每项对应网格图上的一类非零路径：零路径：幂次表示此类非零路径的重量，系数表示具有此幂次表示此类非零路径的重量，系数表示具有此重量的非零路径的条数。重量的非零路径的条数。比如，比如，(5.24)式式生成函数告诉我生成函数告诉我们：从零状态分叉又回到零

39、状态的非零路径中，有们：从零状态分叉又回到零状态的非零路径中，有2条是条是重量为重量为6的序列，有的序列，有1条重量为条重量为8，有，有5条重量为条重量为10。显然，。显然，自由距离等于其中最轻者即次数最低的第一项，本例自由距离等于其中最轻者即次数最低的第一项，本例df6。第81页，本讲稿共103页110011010101000100000000000000000101111011001100010110101300100111011001001001101145657667786998100100001111对照例对照例5-3的图的图5-11，可以验证，可以验证df确是确是6，而且重量，而且

40、重量为为6的最轻非零序列确有两条，的最轻非零序列确有两条，一条是一条是S0S2S1S0,另一条是另一条是S0S2S3S1S0。重量为重量为8的非零路径有一条，的非零路径有一条，即即S0S2S3S3S1S0。第82页，本讲稿共103页二二.计算机搜索法计算机搜索法这这种种方方法法吸吸取取了了维维特特比比译译码码算算法法的的思思路路，只只要要知知道道卷卷积积码码网网格格图图，就就可可以以利利用用事事先先编编好好的的程程序序很很快求出自由距离，这是目前最实用的方法。快求出自由距离，这是目前最实用的方法。设设某某卷卷积积码码网网格格图图有有N个个状状态态，任任何何一一个个状状态态j(j=0,1,2N-

41、1)可可以以由由上上一一时时刻刻的的K个个状状态态转转移移而而来来，我们把可能转移到我们把可能转移到j状态的上一状态状态的上一状态(predecessor)记作：记作：P(i,j)(i=0,1,K-1,j=0,1,N-1)而而把把与与上上述述转转移移对对应应的的码码字字重重量量记记作作W(i,j)(见见图图5-16)。第83页，本讲稿共103页状态状态(l-1)时刻时刻l时刻时刻S0 S1P(0,j)P(1,j)jSj P(2,j)SN-2P(K-1,j)S N-1 图图5-16计算机搜索最轻路径计算机搜索最轻路径设设(l-1)时时刻刻到到达达j状状态态最最轻轻序序列列的的重重量量是是d(l-

42、1)(j)，l时时刻刻到到达达j状状态态的的最最轻轻路路由由的的重重量量是是d(l)(j)，那那么么计计算算d(l)(j)的的方方法法应应是是将将所所有有l时时刻刻能能够够到到达达j状状态态的的K个个前前状状态态P(i,j)在在(l-1)时时刻刻的的重重量量d(l-1)(P(i,j)加加上上本本次次转转移移的的重重量量，然然后后在在K个个结结果果中中选选出出最最轻轻者者作作为为d(l)(j)。用用数数学学语语言表示即：言表示即：(5-25)第84页，本讲稿共103页5.4 卷积码的译码卷积码的译码卷积码译码可分代数译码和概率译码两类。卷积码译码可分代数译码和概率译码两类。代代数数译译码码一一般

43、般仅仅用用于于简简单单的的卷卷积积码码。其其优优点点是是译译码码电电路路简简单单，时时延延小小，适适合合于于高高速速译译码码。不不足足之之处处在在于于：编编码码增增益益一一般般都都不不大大，且且仅仅适适合合于于硬硬判判决决译译码码。现现代代通通信信使使用用代代数数译码的场合较少。译码的场合较少。第85页，本讲稿共103页卷卷积积码码本本质质上上是是一一个个有有限限状状态态机机，它它的的码码字字前前后后相相关关。对对于于编编码码器器编编出出的的任任何何码码字字序序列列，在在网网格格图图上上一一定定可可以以找找到到一一条条连连续续的的路路径径与与之之对对应应，这这种种连连续续性性正正是是卷卷积积码

44、码字前后相关的体现。码码字前后相关的体现。在在译译码码端端，一一旦旦传传输输、存存储储过过程程中中出出现现差差错错，输输入入到到译译码码器器的的接接收收码码字字流流在在网网格格图图上上就就找找不不出出一一条条对对应应的的连连续续路路径径，而而只只有有若若干干不不确确定定、断断续续的的路路径径供供作作译译码码参参考考。而而从从译译码码器器译译出出的的码码字字序序列列必必须须与与编编码码器器一一样样，也也是是对对应应一一条连续路径，否则肯定是译码出了差错。条连续路径，否则肯定是译码出了差错。第86页，本讲稿共103页卷积码概率译码的基本思路：卷积码概率译码的基本思路：以以断断续续的的接接收收码码流

45、流为为基基础础，逐逐个个计计算算它它与与其其它它所所有有可可能能出出现现的的、连连续续的的网网格格图图路路径径的的距距离离，选选出出其其中中可可能能性性（概概率率）最最大大的的一一条条作作为为译译码码估估值值输输出出。概概率率最最大大在在大大多多数数场场合合可可解解释释为为距距离离最最小小，这这种种最最小距离译码体现的正是最大似然的准则。小距离译码体现的正是最大似然的准则。第87页，本讲稿共103页当当前前最最实实用用的的卷卷积积码码译译码码算算法法是是维维特特比比(VB)算算法法(Viterbi,1967)。小小村村(Omura，1969)两两年年后后指指出出：维维特特比比算算法法等等价价于

46、于在在一一个个加加权权图图上上求求取取最最短短路路径径。1973年年福福尼尼(Forney)最最终终证证明明了了维维特特比比算算法法实实质质上上就就是卷积码的是卷积码的最大似然译码最大似然译码。由由于于最最优优的的特特性性和和相相对对适适中中的的复复杂杂度度，维维特特比比算算法法在在L 10的的卷卷积积码码译译码码中中已已成成为为首首选选、最最普普遍遍采采用用的的算法。算法。第88页，本讲稿共103页5.4.1卷积码的最大似然译码卷积码的最大似然译码卷卷积积码码的的最最大大似似然然译译码码与与分分组组码码的的最最大大似似然然译译码码在在原原理理上上是是一一样样的的，但但实实现现方方法法上上略略

47、有有不不同同。主主要要区区别别在在于于：分分组组码码是是孤孤立立地地求求解解单单个个码码组组的的相相似似度度，而而卷卷积积码码是是求求码码字字序序列列之间的相似度。之间的相似度。设发码序列设发码序列C=(C0,C1,Cl,)(网格图上连续路径）网格图上连续路径）收码序列收码序列R=(R0,R1,R l,)（断断续续）（断断续续）译码估值序列译码估值序列 Cj,Cj=(Cj0,Cj1,Cjl,)，j=(1,2)将将所所有有可可能能的的Cj 与与R作作比比较较(计计算算距距离离)，选选出出其其中中“最最佳佳”的那个序列作为译码序列的那个序列作为译码序列。所谓所谓“最佳最佳”是指具有最大后验条件概率

48、是指具有最大后验条件概率(5-34)第89页，本讲稿共103页90信信道道模模型型只只知知道道先先验验的的转转移移概概率率，因因此此必必须须通通过过贝贝叶叶斯斯公式找出先、后验两种概率间关系：公式找出先、后验两种概率间关系：(5-35)这这里里P(R/Cj)是是发发送送码码字字序序列列Cj而而得得到到接接收收序序列列R的的概概率率，也也称称似似然然度度。当当各各可可能能序序列列等等概概发发送送时时，P(Cj)是是常常数数；当当信信道道对对称称时时，P(R)是是常常数数。这这时时MaxP(Cj/R)与与MaxP(R/Cj)等价，最大似然译码也就是最佳译码。等价，最大似然译码也就是最佳译码。似似然

49、然度度是是以以“积积”的的形形式式（联联合合概概率率)积积累累的的,这这不不利利于于简简化化运运算算。如如希希望望似似然然度度能能以以“和和”的的形形式式积积累累，可可用的方法之一就是取对数。用的方法之一就是取对数。第90页，本讲稿共103页91logx虽虽然然是是非非线线性性的的，却却是是单单调调的的，大大者者取取对对数数后后仍仍为为大大，比比大大小小时时相相对对关关系系不不变变。因因此此MaxP(R/Cj)与与MaxlogP(R/Cj)是是一一致致的的，我我们们称称后后者者为为对对数数似似然然函函数数。如如果果说说序序列列的的似似然然函函数数是是各各码码字字似似然然函函数数之之积积，那那么

50、么序序列列的的对对数数似似然然函函数数等等于于组组成成该该序序列列的的各各码码字字对对数似然函数之数似然函数之和和logP(R/Cj)=(5-36)L是组成序列的码字的个数是组成序列的码字的个数，是是第第l个个发发送送码码字字与与接接收收码码字字的的对对数数似似然然度度，又又等等于于组组成成第第l码字的码字的n个码元的对数似然度之和：个码元的对数似然度之和：=(5-37)第91页，本讲稿共103页92最最大大似似然然译译码码就就是是把把似似然然度度最最大大的的那那个个序序列列选选为为译译码估值序列码估值序列=(5-38)序序列列的的似似然然度度与与序序列列长长度度L有有关关。如如果果我我们们把