信息论与编码第五讲

1、信息论与编码第五讲第1页，共103页，2022年，5月20日，1点17分，星期一主要内容RS编译码卷积编译码第2页，共103页，2022年，5月20日，1点17分，星期一5.1 RS码第3页，共103页，2022年，5月20日，1点17分，星期一5.1.1 RS编码RS码= Reed-Solomon code=里德-索洛蒙码是BCH码最重要的一个子类。可视为BCH码的特例,是m=1, m0=1时的q元本原BCH码。由于最小多项式的次数不会超过m, 当m=1时，2t个连续幂次的根(x-) (x-2) (x-2t)既是q元扩域GF(q1)上的根多项式，又是q元基域GF(q)上的最小多项式。这种性质

2、给多元BCH码的设计带来了很多的方便，因为我们在前面已经看到，由扩域i次幂根i求基域对应的最小多项式是十分麻烦的事，而RS码的一次根式(x-)就是最小多项式，无需另外再去计算。第4页，共103页，2022年，5月20日，1点17分，星期一本原RS码具有如下参数：码长：n=q-1校验位：n-k=2t最小距离：dmin=2t+1生成多项式：g(x)=( x-)( x-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)由以上参数可见 dm

3、in= 2t+1 = n-k +1 因此， RS码也是MDC码（极大最小距离）第5页，共103页，2022年，5月20日，1点17分，星期一注意：GF(q)和GF(q1)含义不同GF(q)是数域， q必须是素数GF(q1)是多项式域，q不一定是素数， 工程上，q通常取为2的幂次。GF(8)?01234567表4-9 用x3+x+1产生的GF(81)GF(81)多项式3重000 0 0110 0 10 1 0221 0 03+10 1 142+1 1 052+11 1 162+11 0 14+5=1 mod 83 + 4 = 6 4的乘法逆元？第6页，共103页，2022年，5月20日，1点17

4、分，星期一例4.10 试设计一个(7,3,5)本原RS码。解：由于码长n=q-17，可断定码元是8进制的。8进制域元素可以用根的幂次、多项式或3重矢量表示。 若令是本原多项式p(x)=x3+x+1的根，即3=+1，我们可以列出表4-9。因题中要求dm=5 t = 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+

5、 3 在上式运算中用到了关系式3=+1以及二元扩域的一些运算规则，比如i+ i= 0、7= 1等 。第7页，共103页，2022年，5月20日，1点17分，星期一此8进制(7,3,5)RS码的生成矩阵为：G =通过矩阵行运算可以将它系统化,得G = 1 3 1 3 0 0 第行0 1 3 1 3 0 第行0 0 1 3 1 3 第行1 0 0 4 1 4 5 +3 +20 1 0 2 1 6 6 +30 0 1 3 1 3 生成多项式的运算同样可用除法器实现，只是所作的运算是GF(81)域的乘、加运算。第8页，共103页，2022年，5月20日，1点17分，星期一例：用上面设计的(7,3,5)

6、本原RS码，对一个二元序列（111011010）实行编码。解：将二元序列化作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)二进制衍生码字是：（111 011 010 101 110 100 001）1 0 0 4 1 4 50 1 0 2 1 6 60 0 1 3 1 3第9页，共103页，2022年，5月20日，1点17分，星期一(7,3,5)RS码的t=2,能纠2个差错。衍生为 (21,9)二元码后，纠随机差错能

7、力与原(7,3)RS码一样t=2，还能纠长度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页，2022年，5月20日，1点17分，星期一

8、 上述这种用二进制码表示的q进制RS码称为该RS码的二进衍生码，衍生指GF(q1)和GF(2)两个域间的映射。可以证明，这种映射是把线性码映射成线性码，映射后的二进衍生码一定是线性分组码，但不一定是循环码。 一般来说，一个随机差错能力为t的RS码，其二进衍生码可以纠正小于等于t个随机差错，或者纠正单个长度为b的突发差错， b(t-1)m+1(4-35)以及其它大量错误图样。 可见，二进衍生码特别适用于纠突发差错，这就是它在无线通信中被广泛采用的原因。 第11页，共103页，2022年，5月20日，1点17分，星期一 q进制RS码也可以扩展。对于(n,k,d)RS码(n=q-1)，我们可以给每个

9、码字：(C0, C1, Cn-1)增加一个全校验位Cn (mod q) (4-36) 使此扩展RS码字的全体码元C0, C1, Cn-1之和为零。可以证明：如果该码字生成多项式g(x)不含(x-1)因子 (或1不是g(x)的根)，那么加了一个全校验位后，能使扩展码的最小距离增加1，即得到(n+1,k,d+1)扩展RS码。比如上例 (7,3,5)RS码扩展出来的(8,3,6)码，其二进衍生码是(24,9)二元码。 第12页，共103页，2022年，5月20日，1点17分，星期一 IBM 3370磁盘存储系统采用256进制(255,252) RS码的缩短码，并对应成8比特(1字节)一组的二进制衍生

10、码。该码的基本参数是：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组、每组5133171字节，编成3个由(255，252)缩短下来的(174，171) RS码字。实际介质中使用的是（8174，8171）RS衍生码。 第13页，共103页，2022年，5月20日，1点17分，星期一 在C

11、D 唱片中，采用了两级纠错加交织器的差错控制方案。纠错码用的是q=28=256进制的(255，251) RS码，纠错能力t =2。使用时，将它缩短为(28,24)的外码和(32,28)的内码两种。 每秒44.1k采样、每采样16比特的数字音频码流(1644.1k= 1.41Mb/s)被分割成24字节（192bit）的信息组，每字节对应一个256进制的码元，经（28，24）RS编码器编出28字节（224bit）一组的256进制的外码码元。这些码元经4行5列(45字节交织器)交织后由(32，28) RS编码器二次编码，输出32字节（256bit）一组内码码元，每码元写入CD盘的一个字节。读出是写入

12、的逆过程，包括RS（32，28）内码译码、去交织和RS（28，24）外码译码。第14页，共103页，2022年，5月20日，1点17分，星期一 整个过程中，24字节音频信号转为32字节磁盘存储，码率为0.75，要求CD盘的读出速率至少大于1.410.75=1.88Mb/s (没考虑其它任何开销)。 具体译码中，当内码遇到一个可检不可纠的差错时将会对外码发送一个信息以提高外码的纠错能力；当差错超过外码的纠错能力时，会对播放系统发送一个信息，将该译码样值删除而改用前、后样值的插值(interpolating)。如果差错太多而超出了插值运算的能力，播放系统将插入一段静音(mute)替代这个突发差错。

13、 第15页，共103页，2022年，5月20日，1点17分，星期一 在宇航中，RS码和卷积码是一对黄金搭配，用于深空(deep space)通信中的纠错编码。 深空信道属随机差错信道，用卷积码比较合适。但一旦信道噪声超出卷积码的纠错能力，就将导致突发性质的译码差错，这时用RS码来对付将是最佳选择。 在“探险者号”(Voyager) 飞向木星和土星的旅程中，信息就是以RS码为外码、卷积码为内码的级联码实现信道编码的。这种级联码性能优良，已被认为是一种宇航通信标准而称为NASA码，可带来57dB的编码增益。第16页，共103页，2022年，5月20日，1点17分，星期一探险者Voyager采用了(

14、255,223)RS码，在误比特率Pb=10-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进制），或长度121 (式4-35)的二进制突发差错。第17页，共103页，2022年，5月20日，1点17分，星期一5.1.2 RS码迭代译码 RS码是BCH码的子类，

15、必然存在某些构码特点和能最大程度发挥其纠错潜力的专用译码方法。 RS码译码方法主要有：迭代译码 和 快速译码。 RS码是MDC码，码的最小距离d= n-k+1=2t-1，因此g(x)有2t个即d-1个连续幂次的根。RS码可以用类似于BCH码的迭代方式来译码，但必须增加一个步骤： 确定了差错码元位置后还要确定差错幅度。第18页，共103页，2022年，5月20日，1点17分，星期一假设有个差错分布在j1、j2、j位上，而差错幅值分别是 ej1 、ej2 ej ，则 E(x) = ej1 x j1+ ej2 x j2 + ej x j (4-80) （0 j1 j2L时，效率损失趋于 0 因而可忽

16、略不计，每一个 k 位信息组产生一个 n 位码字，卷积编码码率与分组码码率一样为R=k/n。 相反，M相对于L越小则效率损失越大，当M =1时码率损失系数接近1。 由此可见，卷积码的适用对象是电路交换的连续信息流，或包交换的“流媒体”，或复用级的信息流，而不适合短突发、目的地分散的用户端包交换纠错编码。 第66页，共103页，2022年，5月20日，1点17分，星期一卷积码的距离特性 卷积码的性能取决于卷积码距离特性和译码算法。其中，距离特性是卷积码本身的属性，它决定了该码的纠错能力，而译码方法只是研究如何将这种潜在的纠错能力转化为现实的纠错能力。 表述距离特性的最好方法是利用网格图。若序列C

17、、C”是从同一时刻（不妨称为0时刻）由零状态出发的两个不同的码字序列，它们所对应的信息序列分别是M 和M”，且M M”。对于二元码，序列距离d(C,C”)指汉明距离，等于C、C”的对应项逐一模2加后所得的序列C的重量，也等于序列C和全零序列0的距离或序列C的重量。d(C,C”) = W(CC”) = W(C0) = d(C,0) (5-16)第67页，共103页，2022年，5月20日，1点17分，星期一 式(5-16)默认：两码字序列之和仍是码字序列，这样任意两码字序列间最小距离才能等效于全零序列与某非全零序列的距离。全零序列在网格图上表现为保持在零状态的一条横线，故两序列的最小距离也就是非

18、全零路径与全零状态路径距离最小者。 序列距离还与序列长度有关，同一序列对在不同长度比较时显然距离也不同。将长度l 的任意两序列间的最小距离定义为l 阶列距离。以长度l为变量的列距离特性称之为列距离函数，用dc(l)来表示： dc( l ) min d(Cl,C”l): M0 M”0 (5-17) 第68页，共103页，2022年，5月20日，1点17分，星期一所谓M0 M”0即“不同” 的两序列，在网格图上的表现就是从零时刻起两序列轨迹从零状态分道扬镳形成分叉点。由式(5-16)，式(5-17)可改写为dc( l )min W(ClC”l): M0 M”0 = min W(Cl): M0 0

19、(5-18)由于早期卷积码译码方法与约束长度（L+1）有关，于是曾把（L+1）阶列距离称为最小距离dmdm= min W(CL+1): M0 0 (5-19)而把由零状态零时刻分叉的无限长的两个序列之间的最小距离定义为自由距离： df = min W(C ): M0 0 (5-20)第69页，共103页，2022年，5月20日，1点17分，星期一列距离、最小距离、自由距离三者之间的关系是：dmdc( l )|l=L+1 (5-21)df = dc( l ) (5-22)以下举例说明三个距离的求法。例5-3二进制(3,1,2)卷积码网格图如图5-9，试求该码 1至6阶列距离、最小距离和自由距离。

20、 解：距离的求法参见图5-10。 第70页，共103页，2022年，5月20日，1点17分，星期一110011010101000100000000000000000101111011001100010110101300100111011001001001101145657667786998100100001111 最轻码字序列 列距离函数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

21、)= 6 l6 S0S2 S1S0 S0 S0 dc(6)= 6第71页，共103页，2022年，5月20日，1点17分，星期一 由上例可推广出一个一般结论：自由距离就是从零状态分叉后又回到零状态的所有路径中重量最轻的那一条的重量。 早期的卷积码文献都将最小距离dm看作是最重要的距离参数，这是由于那时的主要译码算法只有一个约束长度（L+1）的记忆容量。后来维特比译码和序列译码成为主要方法，这些译码算法的记忆长度在理论上可不受限制，因此与这两种译码相联系的自由距离df成了主要的列距离参数。加上df又是决定卷积码性能的一个主要参数，以致在df逐步替代dm的过程中有些人把这两个概念混为一谈了。df对

22、卷积码的性能是决定性的，有必要专门讨论一下df的计算方法。 第72页，共103页，2022年，5月20日，1点17分，星期一5.3.2自由距离df的计算 对于像例5-3-1那样简单的卷积码，可以直接从网格图中找出df。但随着限制长度的增加，状态数将以指数速度增加，网格图将变得非常复杂庞大，直接找出df往往变得不可能了。一般来说，在状态数小于16或32时，可以采用解析法，借助信号流图来求自由距离。 以下介绍两种计算方法：信号流图法和计算机搜索法。 第73页，共103页，2022年，5月20日，1点17分，星期一一信号流图法 卷积码的状态流图(见节)与信号流图之间具有拓扑等效性，可将信号流图的理论

23、和方法应用于卷积码的研究。 原则上，利用信号流图可计算任何一个以支路为基础线性积累的量。如果希望这个量以“和”的形式积累，可将这个量写作某个特定底数的指数，并令其幂为该支路的增益。若干支路的串联构成一条路径，路径增益是组成此路径的各支路增益之乘积（其指数是各支路增益指数之和）。 作为研究对象的两个节点间可能有不止一条的路径，所以路径增益的和式便是全图增益，称之为两节点之间考虑对象量的生成函数T(D)。第74页，共103页，2022年，5月20日，1点17分，星期一将信号流图法用于自由距离计算时，一个“状态”对应一个节点，我们感兴趣的量是不同转移间的距离（与全零转移相比就是重量），在连续转移中是

24、以和的形式累积的。因此，我们以各转移所对应的码字重量Wj为指数来定义支路增益 和路径增益 。由于自由距离是由零状态出发又回到零状态的最轻序列的重量，我们可以将零状态拆开成两个节点：一个是始发点，一个是归宿点。这样，沿着任一条由始发点到归宿点的路径都有一个路径增益，其中指数最小者就是最轻路径。第75页，共103页，2022年，5月20日，1点17分，星期一从生成函数T(D)的角度看，如果将所有指数相同的路径增益合并，各路径增益的和式可写作： (5-23)式中，系数Ad 是路径增益指数为d的不同路径的条数。T(D)最低次非零项的指数就是最轻序列的重量，即自由距离df 。 对(5-23)式的分析揭示

25、了生成函数T(D)与自由距离df 的关系，这样就允许我们借用信号流图中所有计算生成函数的方法来计算卷积码的自由距离。 第76页，共103页，2022年，5月20日，1点17分，星期一实际中可供选用的方法主要有三种： (1).利用Mason的增益公式参见S.J.Mason Electronic Circuit,signal and system 1960。这种方法过去使用较多，有人称之为标准方法。(2). 根据有向图列出线性状态方程，从而把“图解”的问题转化为解线性方程的问题。这是一种经典的方法。因为列方程有一定的规律，解方程则有许多现成的程序和方法可供使用。 (3). 通过图论变换吸收部分节点

26、，从而简化甚至直接求出生成函数T(D)，这适用于较简单的流图。第77页，共103页，2022年，5月20日，1点17分，星期一例5-4 二进制(3,1,2)卷积码状态流图如图5-7。试用信号流图法求该码自由距离df。解：将卷积码状态图（图5-7）的零状态S0拆成一始发一归宿两个节点(图5-12),状态的自环是全零码，在信号流图中不画出。 令各支路的增益为D j （这里j是与相应转移对应的码字重量，比如码字011的重量为2，对应的支路增益是D2），可得信号流图(图5-13)。再根据信号流图的一些初等变换规则（图5-14），将图5-13步步简化（图5-15），最后得到生成函数： 第78页，共103

27、页，2022年，5月20日，1点17分，星期一 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页，2022年，5月20日，1点17分，星期一 A B AB A A+B B B BC A D AB D C A B图5-14信号流图的初等变换 AB 1-CC D2 D3 D D图5-15卷积码信号流图的简化 D2 1-D2 D2第80页，共103页，2022年，5月20日，1点17分，星期一运用多项式除法（长除法），

28、得： (5-24)这是一个无限多项式，多项式的每项对应网格图上的一类非零路径：幂次表示此类非零路径的重量，系数表示具有此重量的非零路径的条数。比如，(5.24)式生成函数告诉我们：从零状态分叉又回到零状态的非零路径中，有2条是重量为6的序列，有1条重量为8，有5条重量为10。显然，自由距离等于其中最轻者即次数最低的第一项，本例df6。第81页，共103页，2022年，5月20日，1点17分，星期一1100110101010001000000000000000001011110110011000101101013001001110110010010011011456576677869981001

29、00001111对照例5-3的图5-11，可以验证df确是6，而且重量为6的最轻非零序列确有两条，一条是S0S2S1S0, 另一条是S0S2S3S1S0。重量为8的非零路径有一条，即S0S2S3S3S1S0。 第82页，共103页，2022年，5月20日，1点17分，星期一二.计算机搜索法 这种方法吸取了维特比译码算法的思路，只要知道卷积码网格图，就可以利用事先编好的程序很快求出自由距离，这是目前最实用的方法。 设某卷积码网格图有N个状态，任何一个状态j ( j=0,1,2N-1)可以由上一时刻的K个状态转移而来，我们把可能转移到j状态的上一状态(predecessor)记作： P( i ,

30、j ) (i = 0,1,K-1, j = 0,1,N-1) 而把与上述转移对应的码字重量记作W( i , j )(见图5-16)。第83页，共103页，2022年，5月20日，1点17分，星期一 状态 (l-1)时刻 l时刻 S0 S1 P(0,j) P(1,j) j Sj P(2,j) SN-2 P(K-1, j) S N-1 图5-16计算机搜索最轻路径设(l-1)时刻到达j状态最轻序列的重量是d(l-1)(j)，l时刻到达j状态的最轻路由的重量是d(l)(j)，那么计算d(l)(j)的方法应是将所有l时刻能够到达j状态的K个前状态P( i , j )在(l-1)时刻的重量d(l-1)(

31、 P( i , j )加上本次转移的重量，然后在K个结果中选出最轻者作为d(l)(j)。用数学语言表示即： (5-25)第84页，共103页，2022年，5月20日，1点17分，星期一5.4 卷积码的译码卷积码译码可分代数译码和概率译码两类。代数译码一般仅用于简单的卷积码。其优点是译码电路简单，时延小，适合于高速译码。不足之处在于：编码增益一般都不大，且仅适合于硬判决译码。现代通信使用代数译码的场合较少。第85页，共103页，2022年，5月20日，1点17分，星期一 卷积码本质上是一个有限状态机，它的码字前后相关。对于编码器编出的任何码字序列，在网格图上一定可以找到一条连续的路径与之对应，这

32、种连续性正是卷积码码字前后相关的体现。 在译码端，一旦传输、存储过程中出现差错，输入到译码器的接收码字流在网格图上就找不出一条对应的连续路径，而只有若干不确定、断续的路径供作译码参考。而从译码器译出的码字序列必须与编码器一样，也是对应一条连续路径，否则肯定是译码出了差错。 第86页，共103页，2022年，5月20日，1点17分，星期一 卷积码概率译码的基本思路： 以断续的接收码流为基础，逐个计算它与其它所有可能出现的、连续的网格图路径的距离，选出其中可能性（概率）最大的一条作为译码估值输出。概率最大在大多数场合可解释为距离最小，这种最小距离译码体现的正是最大似然的准则。第87页，共103页，

33、2022年，5月20日，1点17分，星期一 当前最实用的卷积码译码算法是维特比(VB) 算法(Viterbi,1967)。小村(Omura，1969)两年后指出：维特比算法等价于在一个加权图上求取最短路径。1973年福尼(Forney)最终证明了维特比算法实质上就是卷积码的最大似然译码。 由于最优的特性和相对适中的复杂度，维特比算法在L10的卷积码译码中已成为首选、最普遍采用的算法。第88页，共103页，2022年，5月20日，1点17分，星期一5.4.1 卷积码的最大似然译码 卷积码的最大似然译码与分组码的最大似然译码在原理上是一样的，但实现方法上略有不同。主要区别在于：分组码是孤立地求解单

34、个码组的相似度，而卷积码是求码字序列之间的相似度。 设发码序列C=(C0, C1, Cl,) (网格图上连续路径） 收码序列R=(R0, R 1, R l,) （断断续续）译码估值序列 Cj ,Cj=(Cj0,Cj1,Cjl,)，j= (1,2) 将所有可能的Cj 与R 作比较(计算距离)， 选出其中“最佳”的那个序列作为译码序列 。 所谓“最佳”是指具有最大后验条件概率 (5-34)第89页，共103页，2022年，5月20日，1点17分，星期一90信道模型只知道先验的转移概率，因此必须通过贝叶斯公式找出先、后验两种概率间关系： (5-35)这里P(R/Cj)是发送码字序列Cj而得到接收序列

35、R的概率，也称似然度。当各可能序列等概发送时，P(Cj)是常数；当信道对称时，P(R)是常数。这时MaxP(Cj/R)与MaxP(R / Cj)等价，最大似然译码也就是最佳译码。 似然度是以“积”的形式（联合概率)积累的, 这不利于简化运算。如希望似然度能以“和”的形式积累，可用的方法之一就是取对数。第90页，共103页，2022年，5月20日，1点17分，星期一91logx虽然是非线性的，却是单调的，大者取对数后仍为大，比大小时相对关系不变。因此MaxP(R/ Cj)与MaxlogP(R / Cj)是一致的，我们称后者为对数似然函数。如果说序列的似然函数是各码字似然函数之积，那么序列的对数似

36、然函数等于组成该序列的各码字对数似然函数之和logP(R / Cj)= (5-36)L是组成序列的码字的个数， 是第l个发送码字与接收码字的对数似然度，又等于组成第l码字的n个码元的对数似然度之和： = (5-37)第91页，共103页，2022年，5月20日，1点17分，星期一92最大似然译码就是把似然度最大的那个序列选为译码估值序列 = (5-38) 序列的似然度与序列长度L有关。如果我们把码组似然度(5-37式)称作分支量度(BMbranch metric)，把序列的累积似然度logP(R / Cj)称为路径量度(PMpath metric)，那么在同样序列长度下（此长度L应足够大），具

37、有最大路径量度的那个序列应选作为译码估值序列 输出。第92页，共103页，2022年，5月20日，1点17分，星期一935.4.2 硬判决（BSC信道）的维特比译码 例5.6 二进制(3,1,2)卷积码网格图如图5-21。设发码序列是C=(000,111,011,001,000,000,), 收码序列是R=(110,111,011,001,000,000,),试用维特比算法译码。 第93页，共103页，2022年，5月20日，1点17分，星期一 R1=110 R2=111 R3=011状态0 PM0(0)=0 PM1(0)=2 PM2(0)=5 PM3(0)=3 状态1 PM0(1)= PM1

38、(1)= PM2(1)=2 PM3(1)=2 (最似然)状态2 PM0(2)= PM1(2)= 1 PM2(2)= 2 PM3(2)=4 状态3 PM0(3)= PM1(3)= PM2(3)= 3 PM3(3)=5 图5-22 l=3时的PMl(i) （i表示状态）和网格图000(2) 111(0)000(2)111(1)111(1)000(3)011(1)100(2)101(2)100(3)011(0)110(2)001(1)010(1)第94页，共103页，2022年，5月20日，1点17分，星期一最似然输出000110011100010101111001 Rl = 110 111 011

39、 001 000 时刻l=0 1 2 3 4 5 0 PM=0 2 5 32 2 1 PM= 2 2 5 7 2 PM= 1 2 4 5 5 3 PM= 3 5 6 6 图5-24 时刻l=5000000011111000第95页，共103页，2022年，5月20日，1点17分，星期一从上例我们看到：每个状态都有自己的留存路径和路径量度，但最后只有其中一个被采纳作为译码估值序列的输出。在硬判决时，支路量度BM表示一次转移的差错数，路径量度PM表示一条路径上差错数的累计，而留存路径是到达该状态的所有路径中差错累计数最少的那条路径 所对应的码字序列的片断(长度D)。第96页，共103页，2022年，5月20日，1点17分，星期一如果传输中没有误码(R = C)，那么总有一个状态的路径长度等于0。如果传输中发生误码，那么没有一个状态的路径长度为0（所有候选序列都与接收序列有差距），我们只能选择其中最小者作为译码估值序列。如果接收序列R和发送序列C之间的距离小于和其它任何一条路径的距离，则 = C，译码是正确的。如果信道误码大到一定程度而使R和C之间的距离大于R和其它某一条路径的距离，则 C，译码差错便