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

1、 卷积码是1955年由Elias等人提出的,是一种非常有前途的编码方法。我们在一些资料上可以找到关于分组码的一些介绍,分组码的实现是将编码信息分组单独进行编码,因此无论是在编码还是译码的过程中不同码组之间的码元无关。卷积码和分组码的根本区别在于,它不是把信息序列分组后再进行单独编码,而是由连续输入的信息序列得到连续输出的已编码序列。即进行分组编码时,其本组中的n-k个校验元仅与本组的k个信息元有关,而与其它各组信息无关;但在卷积码中,其编码器将k个信息码元编为n个码元时,这n个码元不仅与当前段的k个信息有关,而且与前面的(m-1段信息有关(m为编码的约束长度。同样,在卷积码译码过程中,不仅从此

2、时刻收到的码组中提取译码信息,而且还要利用以前或以后各时刻收到的码组中提取有关信息。而且卷积码的纠错能力随约束长度的增加而增强,差错率则随着约束长度增加而呈指数下降 。卷积码(n,k,m 主要用来纠随机错误,它的码元与前后码元有一定的约束关系,编码复杂度可用编码约束长度m*n来表示。一般地,最小距离d表明了卷积码在连续m段以内的距离特性,该码可以在m个连续码流内纠正(d-1/2个错误。卷积码的纠错能力不仅与约束长度有关,还与采用的译码方式有关。总之,由于n,k较小,且利用了各组之间的相关性,在同样的码率和设备的复杂性条件下,无论理论上还是实践上都证明:卷积码的性能至少不比分组码差。编码原理回目

3、录以二元码为例,编码器如图。输入信息序列为u =(u 0,u 1,其多项式表示为u (x =u 0+u 1x +u l x l +。 编码器的连接可用多项式表示为g (1,1(x =1+x +x 2和g (1,2(x =1+x 2,称为码的子生成多项式。它们的系数矢量g (1,1=(111和g (1,2=(101称作码的子生成元。以子生成多项式为阵元构成的多项式矩阵G (x =g (1,1(x ,g (1,2(x ,称为码的生成多项式矩阵。由生成元构成的半无限矩阵 称为码的生成矩阵。其中(11,10,11是由g (1,1和g (1,2交叉连接构成。编码器输出序列为c =u ·G ,称

4、为码序列,其多项式表示为c (x ,它可看作是两个子码序列c (1(x 和c (2(x 经过合路开关S 合成的,其中c (1(x =u (x g (1,1(x 和c (2(x =u (x g (1,2(x ,它们分别是信息序列和相应子生成元的卷积,卷积码由此得名。卷积码编码器在一般情况下,输入信息序列经过一个时分开关被分成k 0个子序列,分别以u (x 表示,其中i =1,2,k 0,即u (x =u (x ,u (x 。编码器的结构由k 0×n 0阶生成多项式矩阵给定。输出码序列由n 0个子序列组成,即c (x =c (x ,c (x ,c (x ,且c (x =u (x 

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

6、卷积码状态图将编码器寄存器中的内容组合(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、卷积码的另一种常用方法网格图。网格图就是时间与对应状态的转移图(如图,在网格图中每一个点表示该时刻的状态,状态之间的连线表示状态转移。通过观察网格图可以发现在网格图中输入信息x(n并没有标出,但如观察到转移后的状态表示(x(n,x(n-1就可以发现输入信息已经隐含在转移后的状态中。在图中还可以发现两个网格图不同主要集中在转移后状态位置不同。重新排序结构(即所谓蝶型结构是为了优化运算而设计的,因为其中蝶型与蝶型之间是相互独立的。 网格图下面就让我们来看看网格图是如何描述卷积编码过程的:仍以(2,1,2为例,假定输入序列为1011010100,起始状态(零时刻为状态a(零状态。第一个有效时钟沿来临

8、后,编码器接收到输入信息“1”,根据图所示网格图知该时刻(即时刻1状态为b,并输出其对应的编码结果“11”,同样在下一个时刻(时刻2接收到输入信息“0”,状态变为c 并输出“10”,接下来的输入数据依次类推,由此我们可以用网格图作出该例子的卷积编码过程,如图5所示,其中两个状态连线之间的信息为输出结果。译码方法回目录若信道干扰序列为,其中。接收序列为其中和。这里“+”为模 2 运算(q =p 元码按模p 运算。译码就是根据编码规则和信道干扰的统计特性,对信息序列u (x 作出估值的方法。常用的有三类译码方法,即代数译码、维特比译码和序贯译码。 1. 代数译码样方法判决,依此类推下去,最后得到信

9、息序列的估值为=(10111,遂实现了纠错。这种译码法,译码时采用的接收数字长度或译码约束长度为(m +1n 0,所以只能纠正不多于(d min -1/2个错误(n 长上的。实用中多采用反馈择多逻辑译码法实现。2. 维特比译码 维特比译码过程维特比译码是根据接收序列在码的格图上找出一条与接收序列距离(或其他量度为最小的一种算法。它和运筹学中求最短路径的算法相类似。若接收序列为出发,每次向右延伸一个分支(对于l <L ,从每个节点出发都有2=2种可能的延伸,其中L 是信息序列段数,对l L ,只有一种可能,并与接收数字相应分支进行比较,计算它们之间的距离,然后将计算所得距离加到被延伸路径的

10、累积距离值中。对到达每个状态的各条路径(有2=2条的距离累积值进行比较,保留距离值最小的一条路径,称为幸存路径(当有两条以上取最小值时,可任取其中 之一,译码过程如图。图中标出到达各级节点的幸存路径的距离累积值。对给定 R 的估值序列为=(0111。这种算法所保留的路径与接收序列之间的似然概率为最大,所以又称为1最大似然译码。这种译码的译码约束长度常为编码约束长度的数倍,因而可以纠正不多于(d f /2个错误。维特比译码器的复杂性随m 呈指数增大。实用中m 不大于10。它在卫星和深空通信中有广泛的应用。在解决码间串扰和数据压缩中也可应用。 3. 序贯译码序贯译码是根据接收序列和编码规则,在整个

11、码树中搜索(既可以前进,也可以后退出一条与接收序列距离(或其他量度最小的一种算法。由于它的译码器的复杂性随m 值增大而线性增长,在实用中可以选用较大的m 值(如2040以保证更高的可靠性。许多深空和海事通信系统都采用序贯译码。Viterbi 译码流程及实现优化回目录 Viterbi 译码示例卷积码的Viterbi 译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程,找到最佳路径即完成了译码过程,并可以纠正接收码字中的错误比特。Viterbi 译码算法步骤如下描述:根据接收码符号R ,计算出相应的分支量度值BM( R/ Cj , j = 1 、2 ;进入某一状态的2 条分支量度BM ( R

12、/ Cj与其前状态路径量度PM累加求和;比较到达当前状态的2 条新的路径量度PM 的大小,选择最大者作为新的状态路径量度存储起来,并保存与此路径对应的码字;对所有的256 个状态都实施上述加、比、选(ACS 运算;在每一译码时刻,满足延时就从256 条留存路径中,选择路径量度最大的一条路径作为译码数据输出; 进入下一译码时刻,重复以上步骤,直至译码结束。由于卷积码译码的复杂度随着约束长度的增加以非线性方式迅速增加,在实际应用中,卷积码的实际应用性能往往受限于存储器容量和系统运算速度,尤其是对约束长度比较大的卷积码。为了在有限的硬件或软件资源条件下保证系统较高的译码性能,下面对算法进行优化。 1

13、. 留存路径更新算法优化传统的实现留存路径存储器(SMU 更新的算法,有寄存器交换法RE 和回溯法TB ,其详细内容请参考有关文献。寄存器交换法利用数据在寄存器中不断交换,来更新留存路径,实现信息的译码,相对于TB 法不断读写存储数据和需要延时回溯判决,其优点是存储单元少、译码延时短。RE 方法的缺点是内联关系过于复杂,不适合约束长度比较大的卷积码译码器的FPGA 实现。基于RE 提出了对留存路径存储及输出优化的实现方法,具体描述如下:.逐状态分配256 个存储器单元,单元位数由延时D (译码深度 决定,每单元存储一个码字;每一个状态当前留存路径存储器的值由选定的前一状态存储器值和路径对应的码

14、字决定(见上述Viterbi 译码算法步骤描述 ;每一个译码时刻只向存储单元中存人留存路径的码字,并把选定码字写入存储单元中最低位;当译码时刻大于延时D 时,判决出当前时刻的所有状态中具有最大路径量度的状态,并将其对应的留存路径存储单元中的最高位作为译码结果输出;在实现存储单元的移位时,可采用循环移位的方式,避免重复读写,在软件实现时如果采用指针的方式读写地址,也可以做到只用一套存储器,这样就能继续在节省空间和提高运算速度上更进一步,在Matlab 仿真中由于系统本身的特点,只须用简单的命令完成以上操作。由于留存路径存储器中存入的只是路径信息,因而节省了存储空间;当译码输出时,只读出具有最大路径量度的状态所对应的留存路径存储单元最高位即可,不须向前回溯,减少了读RAM 的次数(由D次减少至1 次 提高了译码速度。 2. 优化判决输出在输出时需要做延时判