基于FPGA的高性能Viterbi译码器的设计.doc

论文原创性声明 本人郑重声明：此处所呈交的论文基于FPGA的Viterbi译码器的设计是作者独立进行研究所取得的研究成果，除了文中特别加以标注的地方外，论文中不包含其他人已经发表或撰写过的研究成果。作者签名：邱 磊 日期：2009年5月18日 基于FPGA的高性能Viterbi译码器的设计邱 磊(哈尔滨工业大学 深圳研究生院，深圳 518055)摘 要：卷积码的Viterbi译码算法已经被广泛地应用到通信和信号处理的各个领域。本文设计的(2,1,7)卷积码的Viterbi译码器采用串并结合的方式，兼顾了速度和面积。在Altera公司的Quartus II 7.2平台上进行布局布线后，达到5Mbps的译码速率，可满足实际需求。关键词：卷积码 Viterbi 串并结合 FPGAThe Design of High Performance Viterbi Decoder Based On FPGAQiu Lei(Harbin Institute of Technology Shenzhen Graduate School，Shenzhen 518055)Abstract: Convolutional code and its Viterbi decoding algorithm had been widely applied to various fields of communication and signal processing. This paper presents the decoding scheme of (2, 1, 7) convolutional code. In order to take both speed and size into account, the decoder combines parallel structure with serial structure. After the placing and routing in Alteras Quartus II 7.2 platform, the decoding rate could reach 5Mbps, which can meet the actual demand.Keywords: Convolutional code，Viterbi，Parallel structure with serial structure，FPGA 引言 随着现代通信技术的高速发展，对数据传输质量的要求也在不断提高。卷积编码充分利用了各组码字之间的相关性，具有信息位和码长都较小的优点，编码传输时延较小，可以串行或并行传输，并且容易实现最佳译码。1967年维特比(Viterbi)提出了卷积编码的一种概率译码算法Viterbi算法，它是一种最大似然译码算法。在码的约束度较小时，它比其它概率译码算法效率更高、速度更快，译码器也较简单。本文设计是针对卫星通信和其它通信系统中常用的(2,1,7)卷积码的Viterbi译码器在FPGA中的一种低成本实现方案。为了兼顾速度和面积，采用串并结合的译码方式，同时利用流水线结构来提高译码速度。一、Viterbi译码器的结构设计译码器主要由五部分组成：分支度量单元(Branch Metric Unit)、加比选单元(Add-Compare-Select Unit)、幸存路径管理单元(Survivor Management Unit)、判决输出单元(Decide-Output Unit)和控制单元(Control Unit)。其整体结构如图1所示：分支度量单元 (BMU)加比选单元(ACSU)幸存路径管理单元(SMU)控制单元(CU)输出接口输出输入接口输入判决输出单元(DOU)图1 Viterbi译码器总体结构 各单元之间的相互关系如下：接收到的输入数据首先被送入各分支度量单元中计算出相应的分支路径距离；加比选单元将旧的状态路径度量与相应的新产生的分支路径距离相加，通过比较后选择到达同一状态的两个路径度量值中较小的分支来更新路径度量；溢出处理防止加比选单元中的路径度量累加值发生溢出；幸存路径管理单元将加比选单元生成的路径信息进行存储管理；判决输出单元根据加比选单元选择的路径度量，从中选择一个最小值，并输出该最小值对应的幸存路径。所有这些单元都在控制单元的协调下工作。1、分支度量单元(BMU)分支度量表征该分支接收到的码元与期望码元之间的差别。对于硬判决，这种差别指不同码元的个数。硬判决分支度量值可以表示为： .(1)其中，y为接收码字，c为本地卷积码输出码字。对于码率为1/2硬判决译码方式，编码器输出信号可能为00、01、10、11，其路径度量取值(汉明距离)只有0，1，2三种可能，因此需要用一个2bit的寄存器来存储分支度量值。 在本文中，采用了4个ACS单元(每个ACS单元有两个累加器)并行计算，因此需要8个分支度量单元并行计算8个条支路的度量值，并将度量值送至ACS中的累加器。2、加比选单元(ACSU)S1S2S3S31S30S29S28S32S33S34S35S63S62S61S60S0S1S2S3S4S5S6S7S63S62S61S60S59S58S57S56S0T(i)T(i+1)图2 (2,1,7)卷积码的状态图ACS单元用来累加路径度量值并比较和选择进入某一状态的两条分支。本文中采用4个ACS单元并行计算，每16个状态复用一个ACS结构，同时兼顾了面积和速度。译码器的核心部分是ACS单元，传统的译码器结构每产生一位译码需要进行2(n-1)分支度量单元 加比选单元幸存路径管理单元控制单元输出输入判决输出单元次加比选运算，即22(n-1) =2n次加法运算和2(n-1)次比较选择运算。对于(2,1,7)码来说，需要进行128加法运算和64次比较选择运算，这将占用很多的资源并产生很大的功耗，因此，如果能够通过改进ACS单元的结构来降低其规模和功耗，将会使整个译码器的硬件规模和功耗大大降低。从图2所示的(2,1,7)码的状态图中可以看出：在T(i+1)时刻到达状态S0和S1的是T(i)时刻的状态S0和S32，在T(i+1)时刻到达状态S62和S63的是T(i)时刻的状态S31和S63。也就是说，T(i)时刻的状态Sj和Sj+32会达到T(i+1)时刻的相邻的两个状态，并且这两个状态是S2j和S2j+1(31j0)。这也就是图3所表示的基二蝶形单元(Butterflly Unit)。SjSj+2(n-2)S2jS2j+10110图3 基二蝶形单元 在图2中，T(i)时刻的状态Sj和Sj+32都是在输入0的时候转移到T(i+1)时刻的状态S2j，在输入1的时候转移到T(i+1)时刻的状态S2j+1。这也就意味着ACS单元中的比较器所比较的两个路径度量值(BM)来自数值上相差32的两个状态。路径度量的计算就是分支度量加上与这条分支相连的前一时刻的状态选择的路径度量，所以，新状态的路径度量为：.(2) .(3)从以上的分析中我们可以得出一个很重要的结论：从T(i)时刻的状态Sj(2(n-1)j0)生成的两条支路，唯一不同的信息就是该时刻状态Sj的输入数据，Sj的上支路输入的是0，下支路输入的是1。因此，一个状态可以只生成一条支路(上支路)，另一条支路(下支路)的信息已经包括在这条支路中，要恢复出下支路只需要将上支路的输入数据取反即可。图4所示的ACS单元结构中的累加器可以减少一半的工作量，对于本文中的(2,1,7)码的译码器，即由每产生一位译码工作16个时钟周期减少为8个时钟周期(可将时钟频率降为原来的1/2)，减少了复用次数，降低了ACS单元的复杂度和功耗。同时，由于ACS单元结构的优化，每个状态只需要生成一条路径，存储的幸存路径数也由原来的128条减少为64条，也同样使结构变得简单，功耗有所降低。ACS单元的改进流水线型结构如图4所示：S0S32S1S33S7S39图4 改进的流水线型ACS单元时序图由式(1)和式(2)可知，输入数据(datain)不同，卷积码的输出C0和C1也不同，因此，同一状态上支路的输出与下支路不同，上下支路状态输出及译码器的输入数据之间的关系如表1所示：表1 上下支路与输入数据的分支度量值输入数据上支路度量下支路度量输入数据上支路度量下支路度量00000112100011110111010121001010111000121120001110010100111111002110010102011101102010101011111001110002利用上下支路分支度量值的关系就可以从上支路路径度量累加值中计算出下支路路径度量累加值，用Verilog HDL语言描述为：case(up_branch_metric)2b00: down_path_add_metric = up_path_add_metric + 2b10;2b01: down_path_add_metric = up_path_add_metric;2b10: down_path_add_metric = up_path_add_metric2b10;default: down_path_add_metric = 7bxxx_xxxx;endcase另外，ACS单元中的累加器可以用超前进位加法器实现，这将使累加器不会成为速度的瓶颈。由于累加器使用固定长度的寄存器(本文中采用7bit的寄存器)，因此在不断累加过程中可能会发生溢出，影响译码结果。解决溢出常用的方法是到达译码深度时从所有状态的路径度量值中减去最小度量值。3、幸存路径管理单元(SMU)幸存路径管理单元用来完成对幸存路径的记录，处理ACSU输出的信息，为输出判决作准备。SMU的实现主要有Register Exchange (寄存器交换)和Trace Back(回溯)两种算法 4。由于寄存器交换算法比回溯有更小的译码延时，RE法中幸存路径寄存器记录了幸存路径所对应的解码信息，也就是译码输出。采用这种方法消除了根据当前状态往前追踪的必要，因此寄存器交换提供了一种速度很高的译码操作。本文采用寄存器交换算法。4、判决输出单元(DOU)判决输出单元(DOU)由两部分组成：最小值选择单元(MNSU：Minimum Number Select Unit)和译码输出单元(DOU：Decode Output Unit)。最小值选择单元是用来选出本文中前面4个ACS单元输的路径度量值中具有最小度量值的节点， 读取该结点保存的幸存路径，供译码输出单元输出译码值。判决输出单元的结构如图5所示：survived path registers：MUXMax numberdata0data1data14data15data2DecodeOutput图5 判决输出单元结构图5、控制单元(CU)控制单元(CU)产生控制各模块的时钟信号，是所有模块的有序运行的基础，如图6所示。各时钟信号功能如下：clk_load用于读取前一时刻各状态寄存器的内容，并产生各状态上支路的状态输出值；clk_BM用于计算各状态上支路的分支度量值并读取前一时刻各状态的路径度量值；clk_Add用于计算各状态上支路的路径度量值；clk_restore用于暂存各状态上支路度量值并恢复相应状态下支路的路径度量值；clk_C_S用于比较并选择达到同一状态的两支路的路径度量值的较小者，并存储各状态选择的幸存路径；clk_MNS用于选择各状态存储的路径度量值中的最小值，并保存该最小值对应的状态；min_sel_1和min_sel_2分两步选择4个MNSU选择结果的最小值，并选出最终的最小值对应的状态；Decode_Output用于读取该最小值对应状态存储的幸存路径，并输出译码结果。整个译码器分为6级流水线，每24个时钟周期产生一位译码。图6 控制单元时序三、性能分析本设计利用Verilog HDL语言进行RTL级描述，用ModelSim 6.2b进行功能仿真和时序仿真，选用Altera公司的FPGA 器件Stratix II EP2S30F484C5，用Synplify Pro 8.1进行综合，Quartus II 7.2进行布局布线。时序仿真结果如图7所示。(a)(b)(c)(d)图7 Viterbi译码器时序仿真结果图7(d)中左边黄色的箭头显示卷积码编码器的输出加入了噪声，每七个码字中有一个误码，而本文设计的Viterbi译码器可以纠正这种程度的错误，图7中(d)中右边的红色箭头指示局部放大结果。系统性能如图8所示，最高工作频率可以达到120MHz，译码速率可达120/24=5Mbps，译码延时为译码深度3524个时钟周期，即3524/120MHz=7us,进一步提高译码器的并行性，可以得到更高的译码速度。图8 系统时序分析结果系统占用资源情况如图9所示， 这其中除了译码器模块之外，还有存储在ROM中的256bit数据(作为信源)，以及读ROM的模块，卷积码模块，噪声模块等，实际译码器占用的资源会略少于图9中所示的结果。图9 系统占用资源情况四、结束语本文介绍了(2,1,7)卷积码的Viterbi译码算法，对其结构特别其中的ACS单元作了改进，降低了硬件规模和功耗。流水线的细化也使得系统速度大大提高，5Mbps的译码速率可满足大分部实际需求。本文中使用了4个ACS单元，并行程度有很大的提升空间，使用更多的单元并行工作将会使译码速率进一步提高。本文中译码器的结构同样适合(2,1,n)码。参考文献：1 李子臣信息论与编码M徐州：中国矿业大学出版社，2