高速Viterbi译码器的优化和实现_通信网络论文
关键词：卷积码 viterbi译码 acs 路径度量存储 fpga实现
viterbi算法是一种基于最大后验概率的卷积译码算法，应用广泛。cdma的is-95标准和wcdma 3 gpp标准将卷积码作为高速实时数据传输的信道纠错编码，使viterbi译码器成为移动通信系统的重要组成部分。
为保证纠错性能，卷积码结束度一般选择比较大的，在3 gpp中规定约束度k=9。出于实时性的考虑，移动通信系统中对译码时延的要求比较高，需要高速译码器的支持。可是viterbi译码算法的复杂度、所需存储器容量与结束长度成指数增长关系，成为限制译码器速度的瓶颈。viterbi译码器每解码一位位就需对2 k-1个寄存器的状态进行路径度量，并对相应的存储单元进行读写。这种情况下，可以采用状态路径存储单元分块的方法，以提高其译码性能，缺点是acs单元与存储器之间的接口电路十分复杂，不易实现。
本文分析和优化了viterbi译码器的结构，提出了一种fpga实现方案，简化了接口电路，提高了速度。用这种结构实现的单片集成译码器译码速率达350kbps、时钟频率30mhz。以下先分析译碱器总体结构，然后对各模块设计和实现做详细说明。
1 算法简述及译码器结构
本文采用3 gpp标准规定的k=9，码率r=1/2的(753,561)卷积码，卷积编码器送出的码序列c，经过信道传输后送入译码器的序列为r。译码器根据接受序列r，按最大似然准则力图找出正确的原始码序列。
viterbi译码过程可用状态图表示，图1表示2个状态的状态转移图。sj,t和sj+n/2,t表示t时刻的两个状态。在t+1时刻，这两个状态值根据路径为0或者1，转移到状态s2j+1和s2j+1,t+1。每一种可能的状态转移都根据接收到的有噪声的序列r计算路径度量，然后选择出各个状态的最小度量路径（幸存路径）。viterbi算法就是通过在状态图中寻找最小度量路径向前回溯l步，最后得到的即为译码输出。
本设计采用xilinx virtex600e fpga芯片，在aldec公司的active-hdl仿真环境下，用verilog语言完成，并用xilinx的ise4综合实现。viterbi译码器系统框图如图2所示，主要由bmg(路径计算模块)、acs(加比选模块)、tb(路径回溯模块)、mmu（路径存储模块）等部分组成。采用并行流水线结构，各个模块在控制信号统一监控下工作，减少了读取数据所需时间，充分发挥了fpga高速计算的特性，提高了整个系统的效率。
2 子模块的优化和实现
2.1 acs模块
由于采用的卷积码约束度k=9，在译码过程中，每一时刻有2k-1=256个状态，512个度量路径值，为了获得高速率，需采用尽可能多的acs单元。但由于实际应用中需求电路面积小、功耗低，决定了acs单元的数目不能太多。经过实验证明，采用4个acs单元并行处理，完成可以达到应用要求。
图3 度量路径状态分组图
acs单元用来计算选择状态的路径度量。它需要不断地读出路径度量作为操作数，然后将更新的度量写回各个状态。由于采用4个acs单元并行处理，为不造成流水线堵塞，如何对ram中的度量数据进行读写是关键。如前述，本文采用状态路径存储单元分块的方法。将所有状态分成4组，分别对应于4个acs。每次运算时，4个acs同时从各组状态值中读取数据进行操作。
由图1可知，状态sj和sj+2/n在状态转移中同时得到两个新状态s2j和s2j+1。因此为了acs能够同时取出这两个状态值，sj和sj+2/n必须存储在不同的ram组中。同样，两个计算出来的新状态s2j和s2j+1也应如此。遵循这种准则，则时也简化接口电路，采用如下的分组算法：假设待分配状态=sj=sk-2sk-1…s1s0，所对应的ram组为rm，由于ram共分成4组，则m=(sk-2s1)s0（两位二进制数表示）。状态分组图如图3所示，从中可以看出，从状态s128开始的后续状态都有规律地交错位置存储。由此，acs单元和状态路径存储单元的接口电路只需采用两个2×2交换器，如图4所示。每一个交换器上连着两个acs单元和两个ram组。这两个交换器由输入状态sj的最高位sk-2控制。当sk-2=1时，交换器交叉互联，如果sk-2为0时，各acs和ram直接相连。这种接口设计十分容易实现。
在viterbi译码算法中，译码状态的转移导致度量的读出和写入地址的不同，这样用fpga实现时就需要两块ram采用乒乓模式实现。本文更新路径存储采用原位运算方法，也就是找出状态转移的规律性，建立转移后的新状态和转移前的老状态际址映射关系，使度量的更新在原位上进行，使存储空间减小一半。
2.2幸存路径管理模块
幸存路径的存回溯是viterbi算法关键的一步，最终的译码输出从对幸存的回溯中得到。由于采用基2的状态转移算法，当前时刻对应的前序时刻状态只有2个，所以在路径回溯中采用1bit指针算法。也就是说，在每个状态路径更新时，只需写1bit路径状态转移。幸存路径存储单元可看作一个存储器阵列，每列对应一个状态，一列中的每个单元都有一个1位的指针。在实际设计中，考虑到数据总线的带宽有限，对于8位的幸存路径数据总线，在幸存路径存中将256个状态分成32块。对应幸存路径时，先通过当前状态地址寻址的方式来选择所对应的幸存路径块。
在实际应用中，为了保证译码的准确度，幸存路径的回溯长度通常取4～5倍约束长度，本文回溯长度定为64。如图5所示，当一个解码初始信号进来后，系统把当前所有状态中的最小状态，也就是最小状态值作为当前状态值，路径回溯模块把地址值送入mmu中，从32个分组块中选取相应的幸存路径存到幸存状态值（8位），然后根据当前状态的指针从这8位数据中得到1位幸存路径比特，而下一个状态值由当前状态的低7位和这个幸存路径比特决定。当回溯了64步后，控制信号给出一个输出指示时，当前状态值的最高位即是解码输出值。
图5 路径回溯模块框图
本文重点从acs的并行处理、度量路径的存储管理和路径回溯上对viterbi译码方法进行了讨论。从实际应用出发，考虑到硬件功耗的面积的减小，采用了4个acs并行，路径的存储和管理都采取了分组的模式，简化了接口电路，译码达到了较高的速度，完全可以满足3 gpp标准的要求。用xilinx的virtex600e fpga芯片实现了k=9、码率为1/2、编码速率为350kbps、时钟频率40mhz的viterbi译码器。表1列出了xilinx ise对本设计综合布线报告中提供的参数。
表1 viterbi译码器布线参数表
| number of slices:1,596 out of 6,192 23% slice flip flops:620 4 input luts:1,320 number of slices containing unrelated logic:0 out of 1,596 0% number of bonded iobs:30 out of 153 19% number of block rams:20 out of 72 34% |
| total equivalent gate count for design:474,210 |