可编程Viterbi译码器设计与实现*

段高攀，杜慧敏，韩俊刚，唐凯林

(西安邮电大学 电子工程学院，陕西 西安 710121)

随着电子通信技术的发展，电子通信产品已成为人们生活不可或缺的产品，电子通信产品的产量有了巨大的提升，同时电子通信质量也有了相应的提升，信道编译码是影响通信系统传输质量的直接因素。在信道编码中应用最为广泛的是卷积码编码[1]，而卷积码的最佳译码方式是Viterbi译码[2]。近年来，卷积编码和 Viterbi译码技术已经有了长足的发展，不论是译码算法还是实现架构都达到了极高的水平。算法中间的各个功能单元也得到了改进，研究性的论文也层出不穷。虽然实现方法很多，但是仅能满足一种或两种通信标准，灵活性较差。如(2，1，9)格式的 Viterbi译码器，只能满足约束长度为9的信息序列。

为满足不同类型通信标准及传输速度的要求，设计一种能够满足多种标准的Viterbi译码器十分必要。从本质上看，Viterbi译码器完成的操作无非是分支度量计算、加比选、回溯，存在着很多的共性。在追求满意解而非完美解的情况下，完全可以设计一种在相似通信标准下的“专用”体系结构。采取这种折衷的方法，不但可以避免通用体系架构设计出来的译码芯片在性能及成本上的尴尬，还可以具有一定的重用性。本文的研究重点在于实现可编程Viterbi译码器，制定系统架构并完成各模块的设计。

1 Viterbi译码器设计

Viterbi译码器主要由分支度量计算模块(即路径度量模块，BMG单元)、加比选单元(ACS单元)、路径度量存储管理单元(MMU单元)、路径回溯单元(TB单元)和幸存路径存储管理单元(SMU单元)五部分组成。Viterbi译码器整体结构图如图1所示。

图1 Viterbi译码器的整体结构图

1.1 分支度量计算单元

分支度量单元[3]主要由编码器和距离计算单元两部分组成。分支度量单元的功能是对所有的状态进行编码，并且计算输入的待译码码元与这些编码的软距离。分支度量单元如图2所示。

图2 分支度量单元结构图

图2中，编码器与数据发送端使用的编码格式相同，此处编码器的功能是对每个状态进行编码，然后与输入的信息进行比较，求出其分支度量，即求其每个状态的期望值。距离计算单元主要用来计算输入待译码单元与状态编码之间的差异，并将这些差异送往对应的加比选单元。

1.2 加比选单元

加比选单元[4-5]作为Viterbi译码器的主要组成部分，其主要作用是将分支度量单元(BMU)送来的分支度量与路径度量单元(PMU)中的路径度量值进行累加，并且对每个分支的路径度量值进行比较，挑选出较小的一个将其存入PMU，并且标识出该最小值来源于哪个分支(0分支还是1分支)，即所谓的幸存比特，将其存到SMU中。在每次选择出最小路径度量时，将其存储起来，到下一个状态选出最小路径度量时，将二者进行比较，存储较小的一个及其状态。当达到回溯深度时，将最小状态送给TBU单元进行回溯。

1.3 路径度量存储管理单元

路径存储单元[6]PMU主要负责Viterbi译码过程中路径度量的存储管理，在每个处理时钟，向加比选单元提供所需的路径度量值，在加比选运算结束之后将新的路径度量存储。整个PMU的结构框图如3所示。

图3 PMU单元结构框图

Interface_P_S主要用在链接PMU与ACS单元的接口部分，用来将加比选单元送过来的4路并行路径度量值转换成串行信息后依次存入PMU_RAM；Interface_S_P也是PMU与ACS单元的接口部分，它与前者的作用刚好相反，它是将PMU中取来的4路路径度量信息转换成4路并行的路径度量值，然后送入到ACSU进行运算。

1.4 幸存路径度量存储管理单元

幸存路径存储单元[7-10](SMU)用来存储每一轮ACS单元产生的幸存比特信息。当达到译码深度时，再将其传递给回溯单元进行译码。在硬件电路设计中，如果得到所有信息的幸存比特信息之后再进行译码，必将产生较大的延迟。即使不考虑延迟，存储大量的比特信息对存储的要求也是无限大的，因此需存储回溯译码深度范围内的幸存信息，当达到译码深度之后，将其取出立即进行译码，从而可以大大地节省硬件资源。SMU的设计电路图如4所示。

图4 SMU结构框图

SMU_interface的主要作用是将每个处理周期的4个ACS单元的处理结果暂存起来，当所有状态处理完成之后，将data_in值传送给SMU_RAM 。SMU_RAM用来存储之前处理所得到的幸存比特信息。SMU_Control用来控制对SMU_RAM的读写控制，当码元输入的所有状态（由state_page控制）都处理完成时，将data_in输入到SMU_RAM，当达到译码深度（由 decode_page控制）时，将SMU_RAM中的数据输出到回溯单元。因为SMU_RAM中数据的存储是按照处理decode_page的顺序进行的，因此读地址必须使用一个减法计数器来实现，初始值设置为回溯译码深度。

1.5 回溯单元

回溯单元[11]（TBU）也是Viterbi译码器的一个重要组成部分，它的主要功能是对SMU_RAM中的幸存信息进行回溯并产生译码信息。回溯单元的结构框图如图5所示。

图5 回溯单元结构框图

当达到回溯译码深度，且当前所处理的所有状态的度量计算结束之后，TBU开始工作，将Start信号设置为1，通过选择器MUX将加比选单元计算得出的最小状态Low_state通过寄存器REG作为当前状态送给幸存比特产生模块S_BIT_GEN和次态产生模块NS_GEN进行处理，其后Start信号一直为低，直到下次到达译码深度再将其置为1。因此，其余时刻选择器输出端一直连接NS_GEN送来的次状态Next_State，将其暂存在REG中作为当前状态。在模块S_BIT_GEN中可以求出现态的幸存比特S_bit=DATA_SMU[Current_state]。由蝶形运算过程可以分析得出，根据当前状态的幸存比特可以在NS_GEN模块中反推出现态的上一个状态，也就是次态Next_State。有了现态和现态的幸存比特信息，就可以知道这个现态是由上一轮ACS运算的哪个状态转移而来的。因此，可以根据Viterbi译码算法依次找到每一个时刻的最小状态。NS_GEN可由当前状态产生正确的译码输出。

2 性能比对

为了能够科学地比较两种Viterbi译码器实现方法的性能优劣，两种设计均采用了卷积编码格式(2，1，7)，并且设计和实现均采用Xilinx公司的ISE工具，FPGA工具均采用Virtex4,对两种设计电路进行综合。

经FPGA综合结果表明，ASIC实现的Viterbi译码器的最大频率大于可编程Viterbi译码器的最大频率，具体对比结果如表1所示。

表1 两种实现方式译码器的性能对比

根据Viterbi译码器两种实现方式的性能对比可以发现，ASIC实现的Viterbi译码器速度较优，比可编程Viterbi译码器的最大工作频率高出30 MHz，而且使用的资源相对较少，在同一时钟工作频率下，两种译码器的吞吐量基本相等，但是，采用可编程方式实现的Viterbi译码灵活性较大，可以满足多种方式卷积编码的译码。因此，可以根据实际应用合理选择译码器的实现。

[1]陶杰，王欣，张天辉.基于VHDL语言的卷积码和 Viterbi译码的实现[J].微型机与应用，2012，31(16)：3-5.

[2]王新梅，肖国镇.纠错码——原理与方法[M].西安：西安电子科技大学大学出版，2001.

[3]FORNEY J G D.The Viterbi Algorithm[J].Proceedings of the IEEE，1973，61(3)：268-278.

[4]周炯槃，庞沁华.通信原理[M].北京：北京邮电大学出版社，2002.

[5]FETTWEIS G，MEYR H.Parallel Viterbi algorithm implementation：Breaking the ACS-bottleneck[J].Communications，IEEE Transactions on，1989，37(8)：785-790.

[6]RADER C.Memory management in a Viterbi decoder[J].Communications，IEEE Transactions on，1981，29(9)：1399-1401.

[7]付永庆，孙晓岩，李福昌.实现Viterbi译码器幸存路径存储及译码输出的一种新方法[J].应用科技，2003，30(3)：25-26.

[8]FEYGIN G，GULAK P.Architectural tradeoffs for survivor sequence memory management in Viterbi decoders[J].Communications，IEEE Transactions on，1993，41(3)：425-429.

[9]BLACK P J，MENG T H Y.Hybrid survivor path architec tures for Viterbi decoders[C].Acoustics，Speech，and Signal Processing，ICASSP-93，1993 IEEE International Conference on，1993，1：433-436.

[10]TRABER M.A low power survivor memory unit for sequential Viterbi-decoders[C].Circuits and Systems，ISCAS 2001，2001 IEEE International Symposium on，2001，4：214-217.

[11]BAEK J G，YOON S H，CHONG J W.Memory efficient pipelined Viterbi decoder with look-ahead trace back[C].Electronics，Circuits and Systems，ICECS 2001，the 8th IEEE International Conference on，2001，2：769-772.