从FPGA实现的角度对大约束度Viterbi译码器中路径存储

1 引言

Viterbi译码算法是一种最大似然译码算法，目前广泛应用于各种数据传输系统，特别是卫星通信和移动通信系统中。近年来随着FPGA技术的迅速发展，使得基于FPGA实现Viterbi译码的算法成为研究的热点。

由于Viterbi译码器的复杂性随约束长度k成指数增加，大约束度不但使Viterbi译码器硬件复杂度大为增加，同时也限制了译码速度。而其中以加比选(Add Compareselect，ACS)运算为最主要的瓶颈，的递归运算使流水线结构的应用变得困难。本文以(2，1，9)卷积码为例，用FPGA实现大约束度Viterbi译码器，其中ACS设计采用串并结合的方法来兼顾面积和速度，并用流水线结构来提高译码速度，对路径度量存储则采用同址存储方法，实现了在占用少量硬件资源的前提下，提高译码速度。

2 算法简述及系统结构分析

Viterbi译码原理详见文献[1，2],下面仅作简要说明。

图1为(2，1，9)卷积码的2个状态之间的状态转移图。根据输入路径的不同(图中实线表示输入为0，虚线表示输入为1)，仅仅首位不同的两个状态可转移到仅仅末位不同的两个状态。将所有状态的状态转移图按时间往前衍生，即可得到(2，1，9)卷积码的网格(Trellis)图。Viterbi译码过程就是：根据接收序列，按照最大似然法则，分段地在网格图上计算寻找有最大度量的路径的过程。一般来说，维特比泽码器主要有4个单元所组成，其结构框图如图2所示。

分支度量单元(BMU) 主要是计算分支度量值。所谓分支度量值就是码字与接收码之间的距离。

加-比较-选择单元(ACSU) 主要是做路径度量值与分支度量值的叠加，并决定幸存路径度量值及决定位元(decision bit)。

路径度量存储单元(PMMU) 主要用来存储幸存路径度量值。

幸存路径存储单元(SMU) 主要用来存储决定位元。

如图2所示，接收序列先通过分支度量单元计算出各状态所有分支度量，然后经过ACS单元，将上一时刻的路径度量值与当前时刻的分支度量值作加-比较-选择等运算，计算出当前时刻的幸存路径和路径度量值，并找出决定位元(decision bit)，把新的路径度量值存储到路径度量存储单元(PMMU)，并把相应的幸存路径的决定位元(de-cision bit)存储到幸存路径存储单元(SMU)，当译码到译码深度后，判决输出单元输出译码序列。由此可见：

(1) 每计算一接收序列，所有状态的路径度量都要更新一次。若这些路径度量存储于一块RAM中，则RAM读写的次数为待译卷积码的状态数，当卷积码的约束度比较大时，对RAM的读写周期要求将会很高，很可能成为限制译码速度的瓶颈；

(2) 在ACS单元，要完成路径度量的累加，比较并选择有最大度量的路径，是算法实现的关键电路，也是硬件资源耗费最大的部分。所以ACS单元的数目太多会大大增加译码器的硬件规模，太少则影响译码速度。因此，合理安排ACS单元与路径度量RAM是提高译码速度，减少硬件消耗的关键所在。

针对问题(1)，本文从改进Viterbi译码算法和路径度量RAM分块两方面同时人手。首先，表示Viterbi算法过程的网格图可以进行分解与折叠。图3所示为(2，1，9)卷积码的部分网格图的分解与折叠。可以看出折叠后，ACS计算时由读写状态路径度量，得出一步后的更新结果，变为读写四状态路径度量，得出两步后的更新结果。省去了中间路径度量的读写，减少了RAM的读写次数。

当然，这种分解与折叠很容易扩展为基8或基16的网格图，RAM的读写次数将进一步减少，但此时ACS要同时处理8个或16个路径度量，复杂性几乎成指数增加，其计算速度也可能成为新的瓶颈。综合考虑，本文采用4个基4算法，每次同时处理16个状态。在基于4个基4算法的16个状态路径度量读写中，本文将路径度量RAM分为16块，每块存储16个状态的路径度量。16块RAM并行工作时，对每块RAM的读写周期要求降为原来的1／16。

[1] [2] [3]  下一页