卷积码中的维特比译码和序贯译码算法

《卷积码中的维特比译码和序贯译码算法》由会员分享，可在线阅读，更多相关《卷积码中的维特比译码和序贯译码算法（5页珍藏版）》请在装配图网上搜索。

1、的约束长度)。同样，在卷积码译码过程中，不仅从此时刻收到的码组中提取的码组中提取有关信息。而且卷积码的纠错能力随约束长度的增加而增强，(n,k,m)主要用来纠随机错误，它的码元与前后码元有一定的约束关系，编码复杂度可用编码约束长度最小距离d表明了卷积码在连续m段以内的距离特性，该码可以在 m个连续码流内纠正(d-1)/2与约束长度有关，还与采用的译码方式有关。总之，由于n，k较小，且利用了各组之间的性条件下，无论理论上还是实践上都证明：卷积码的性能至少不比分组码差。相关性，在同样的码率和设备的复杂概述回目录卷积码是1955年由Elias等人提出的，是一种非常有 前途的编码方法。我们在一些资料上

2、可以找到关于分组 码的一些介绍，分组码的实现是将编码信息分组单独进 行编码，因此无论是在编码还是译码的过程中不同码组 之间的码元无关。卷积码和分组码的根本区别在于，它不是把信息序列分组后再进行单独编码，而是由连续输入的信息序列得到连续输出的已 编码序列。即进行分组 编码时，其本组中的 n-k个校验元 仅与本组的 k个信息 元有关，而与其它各组信息无关；但在卷积码中，其编 码器将k个信息码元编为n个码元时，这 n个码元不仅与当前段的一种卷积码编码器k个信息有关，而且与前面的(m- 1)段信息有关(m为编码译码信息，而且还要利用以前或以后各时刻收到差错率则随着约束长度增加而呈指数下降。卷积码m*n

3、来表示。一般地， 个错误。卷积码的纠错能力不仅卷积码编码器列，其多项式表示为c(x)，它可看作是两个子码序列c(1) (x)和c(2) (x)经过合路开关S 合成的，其中 c(1) (x) = u( x) g(1,1) (x)和 c(2) (x)编码原理回目录以二元码为例，编码器如图。输入信息序列为u= (Uo，U1，,)，其多项式表示为u(x) = U0+U1X +, + UlX +,。编码器的连接可用多项式表示为g1,1(X) = 1+x+x2和g(1,2) (x) = 1+x2,称为码的子生成多项式。它们的系数矢量g(1,1) =(111)和g(1,2) =(101)称作码的子生成元。以

4、子 生成多项式为阵元构成的多项式矩阵G(x)=g(1,1) ( x), g(1,2) ( x)，称为码的 生成多项式矩阵。由生 成元构成的半无限矩阵称为码的生成矩阵。其中(11,10,11) 是由g(1,1)和g(1,2)交叉连接构成。编码器输出序列为c= u G称为码序卷积，卷积码由此得名u(x) g(1,2) (x),它们分别是信息序列和相应子生成元的在一般情况下，输入信息序列经过一个时分开关被分成ko个子序列，分别以U(x)表示，其中 i=1 ,2, ko,即 u(x) = u(x),(x)编码器的结构由kox rt阶生成多项式矩阵给定。输出码序列由rt个子序列组成，即c(x) = c

5、(x), c(x)，,， c(x)，且c(x)= u(x) G(x)。若m是所有子生成多项式(x)中最高次式的次数，称这种码为5，ko，m卷积码表示方法回目录码树和网格图 等，这里我们主要介绍和卷积码编码器结构密切相关描述卷积码编码器过程的方法有很多，如矩阵法、多项式、的多项式法，以及与卷积码译码密切相关的网格图法。1. 多项式法多项式法就是由卷积码的生成多项式直接得出其编码器的结构图。如前面例子中的（2 ,1,2）卷积码的生成多项式矩阵为：G（D）=1D D2,1 D2其中，D是延迟算子，生成多项式的第一项为1 D D2，表示输出编码的第一个码元等于输入码元x（ n）与前两个时刻输入的码元x

6、（ n-1 ）、x（ n-2 ）的模2和，同理第二项类似。2. 状态图将编码器寄存器中的内容组合（x（ n-1 ）、x（ n-2 ）定义为编码器状态。如仍以前面所举的例子（2，1，2）为例，则该编码器的状态有四种：00，10，01和11,下面分别用 a，b，c，d来代替。编码器在每一个 时钟沿打入一个输入信息x（ n），因此图示 寄存器组合内容就变为（x（ n），x（ n-1 ）即状态发生了转移，并同时输出G0（ n）、G1（ n）。由此我们可以将图所示编码过程用右图所示的状态图 表示。卷积码状态图由图所示，随着信息序列不断输入，编码器就不断从一个状态转移到另一个状态并同时输出相应的码序列，所

7、以图3所示状态图可以简单直观的描述编码器的编码过程。因此通过状态图很容易给出输入信息序列的编码结果，假定输入序列为110100，首先从零状态开始即图示a状态，由于输入信息为“1 ”，所以下一状态为b并输出“ 11 ”，继续输入信息“1 ”，由图知下一状态为d、输出“ 01” ”其它输入信息依次类推，按照状态转移路径a-b-d-c-b-c-a输出其对应的编码结果“110101001011 ”。3. 网格图状态图可以完整的描述编码器的工作过程，但是其只能显示状态转移的过程而不能显示状态转移发生的时刻，由此引出用来表示卷积码的另一种常用方法一一网格图。网格图就是时间与对应状态的转移图（如图），在网格

8、图中每一个点表示该时刻的状态，状态之间的连线表示状态转移。通过观察网格图可以发现在网格图中输入信息x（ n）并没有标出，但如观察到转移后的状态表示（x（ n），x（ n-1 ）就可以发现输入信息已经隐含在转移后的状态中。在图中还可以发现两个网格图不同主要集中在 转移后状态位置不同。重新排序结构（即所谓蝶型结构）是为了优化运算而设计的，因为其中蝶型与蝶型之间是相互独立的。网格图下面就让我们来看看网格图是如何描述卷积编码过程的：仍以（2,1,2）为例，假定输入序列为1011010100，起始状态（零时刻）为状态a （零状态）。第一个有效时钟沿来临后，编码器接收到输入信息“1”，根据图所示网格图知该

9、时刻（即时刻1）状态为b，并输出其对应的编码结果“11 ”，同样在下一个时刻（时刻2）接收到输入信息“0”，状态变为c并输出“ 10”，接下来的输入数据依次类推”，由此我们可以用网格图作出该例子的卷积编码过程，如图5所示，其中两个状态连线之间的信息为输出结果。译码方法回目录若信道干扰序列为，其中接收序列为艮(厂)尹一 +冬仃=i2环)m其中和 这里“ +”为模2运算(q=p元码按模 p运算)。译码就是根据 编码规则和信道干扰的统计特性，对信息序列 u(x)作出估值的方法。 常用的有三类译码方法，即代数译码、维特比译码和序贯译码。1. 代数译码代数译码是将卷积码的一个编码约束长度 的码段看作是n

10、o(m+1)，ko(n+1)线性分组码，每次根据(n+1)分支长接收数字，对相应的最早的那个分支上的信息数字进行估计，然后向前推进一个分支。上例中信息序列a= (10111)，相应的码序列c=(11100001100111)。若接收序列 R= (10100001110111), 先根据 R的前三个分支(101000 )和码树中前三个分支长的所有可能的8条路径(000000 , )、(000011 , )、(001110 , )、(001101 , )、(111011 , )、(111000 , )、(110101 ,)和(110110 ,)进行比较， 可知(111001)与接收序列(10100

11、0)的距离最小，于是判定第0分支的信息数字为0。然后以 R的第13分支数字(100001)按同样方法判决，依此类推下去，最后得到信息序列的估值为皿=(10111)，遂实现了纠错。这种译码法，译码时采用的接收数字长度或译码约束长度为(叶1) rt，所以只能纠正不多于(dmin-1)/2 个错误(n长上的)。实用中多采用反馈择多逻辑译码法实现2. 维特比译码维特比译码过程维特比译码是根据接收序列在码的格图上找出一条与接收序列距离(或其他量度)为最小的一种算法。它和运筹学中求最短路径的算法相类似。若接收序列为R=(10100101100111)，译码器从某个状态,例如从状态 a出发，每次向右延伸一个

12、分支(对于 I L,只有一种可能)，并与接收数字相应分支进行 比较，计算它们之间的距离，然后将计算所得距离加到 被延伸路径的累积距离值中。对到达每个状态的各条路径(有2 =2条)的距离累积值进行比较，保留距离值最小的一条路径，称为幸存路径 (当有两条以上取最小值时，可任取其中之一)，译码过程如图。图中标出到达各级节点的幸存路径的距离累积值。对给定R的估值序列为 =(10111)。这种算法所保留的路径与接收序列之间的似然概率为最大，所以又称为最大似然译码。这种译码的译码约束长度常为编码约束长度的数倍，因而可以纠正不多于(d2)个错误。维特比译码器的复杂性随m呈指数增大。实用中m不大于10。它在卫

13、星和深空通信 中有广泛的应用。在解决 码间串扰和数据压缩中也可应用。3. 序贯译码序贯译码是根据接收序列和编码规则，在整个码树中搜索(既可以前进，也可以后退)出一条与接收序列距离(或其他量度)最小的一种算法。由于它的译码器的复杂性随m值增大而线性增长 ，在实用中可以选用较大的m值(如2040)以保证更高的可靠性。许多深空和 海事通信系统都采用序贯译码。Viterbi译码流程及实现优化回目录卷积码的Viterbi 译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程，找到最佳路径即完成了译码过程，并可以纠正接收码字中的错误比特。Viterbi译码算法步骤如下描述： 根据接收码符号R ,计算出

14、相应的 分支量度 值BM（ R/Cj）, j = 1、2 ； 进入某一状态的2条分支量度 BM （ R/ Cj）与其前状态路径量度 PM累加求和；对所有的256个状态都实施上述加、比、选(ACS)运算;1011PLViterbi译码示例比较到达当前状态的 2条新的路径量度 PM的大小， 选择最大者作为新的状态路径量度存储起来， 并保存与 此路径对应的码字；在每一译码时刻，满足延时就从256条留存路径中，选择路径量度最大的一条路径作为译码数据输出;进入下一译码时刻，重复以上步骤，直至译码结束。由于卷积码译码的复杂度随着约束长度的增加以非线性方式迅速增加，在实际应用中，卷积码的实际应用性能往往受限

15、于存储器容量和系统运算速度，尤其是对约束长度比较大的卷积码。为了在有限的硬件或软件资源条件下保证系统较高的译码性能，下面对算法进行优化。1. 留存路径更新算法优化传统的实现留存 路径存储器（SMU）更新的算法，有 寄存器交换法 RE和回溯法TB，其详细内容请参考有关文献。寄存器交换法利用数据在寄存器中不断交换，来更新留存路径，实现信息的译码，相对于TB法不断读写存储数据和需要延时回溯判决，其优点是存储单元少、译码延时短。RE方法的缺点是内联关系过于复杂，不适合约束长度比较大的卷积码译码器的FPGA实现。基于RE提出了对留存路径存储及输出优化的实现方法，具体描述如下： 逐状态分配 256个存储器

16、单元，单元位数由延时D （译码深度）决定，每单元存储一个码字； 每一个状态当前留存路径存储器的值由选定的前一状态存储器值和路径对应的码字决定（见上述Viterbi译码算法步骤描述 ）； 每一个译码时刻只向存储单元中存人留存路径的码字，并把选定码字写入存储单元中最低位； 当译码时刻大于延时D时，判决出当前时刻的所有状态中具有最大路径量度的状态，并将其对应的留存路径存储单元中的最高位作为译码结果输出； 在实现存储单元的移位时，可采用循环移位的方式，避免重复读写，在软件实现时如果采用指针的方式读写地址，也可以做到只用一套存储器，这样就能继续在节省空间和提高运算速度上更进一步，在Matlab仿真中由于

17、系统本身的特点，只须用简单的命令完成以上操作。由于留存路径存储器中存入的只是路径信息，因而节省了存储空间；当译码输出时，只读出具有最大路径量度的状态所对应的留存路径存储单元最高位即可，不须向前回溯，减少了读RAM的次数（由D次减少至1次）提高了译码速度。2. 优化判决输出在输出时需要做延时判断，以确定延时足够再输出正确数据。但每一时刻做延时的后果是增加了运算量，导致系统效率较低，根据仿真实现的特点，可以做以下修改：为了避免重复做延时判断，节省运算量，译码输出时省略这一判断，每一时刻都有判决输出码字，只是在接收译码数据时把开始D时刻的接收码字丢弃， 相当于译码单元从D时刻开始输出，这是一种把部分系统功能从复杂模块转移分离到相对简单模块的思想。相对于在译码过程不断重复做判断，这种做法无论在软件或者硬件实现中， 都能一定程度上提高运算速度。