《基于FPGA的高性能Viterbi译码器的设计.doc》由会员分享，可在线阅读，更多相关《基于FPGA的高性能Viterbi译码器的设计.doc（10页珍藏版）》请在金锄头文库上搜索。
1、论文原创性声明 本人郑重声明：此处所呈交的论文基于FPGA的Viterbi译码器的设计是作者独立进行研究所取得的研究成果，除了文中特别加以标注的地方外，论文中不包含其他人已经发表或撰写过的研究成果。作者签名：邱 磊 日期：2009年5月18日 基于FPGA的高性能Viterbi译码器的设计邱 磊(哈尔滨工业大学 深圳研究生院，深圳 518055)摘 要：卷积码的Viterbi译码算法已经被广泛地应用到通信和信号处理的各个领域。本文设计的(2,1,7)卷积码的Viterbi译码器采用串并结合的方式，兼顾了速度和面积。在Altera公司的Quartus II 7.2平台上进行布局布线后，达到5Mb
2、ps的译码速率，可满足实际需求。关键词：卷积码 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 communicat
3、ion 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 co
4、uld reach 5Mbps, which can meet the actual demand.Keywords: Convolutional code，Viterbi，Parallel structure with serial structure，FPGA 引言 随着现代通信技术的高速发展，对数据传输质量的要求也在不断提高。卷积编码充分利用了各组码字之间的相关性，具有信息位和码长都较小的优点，编码传输时延较小，可以串行或并行传输，并且容易实现最佳译码。1967年维特比(Viterbi)提出了卷积编码的一种概率译码算法Viterbi算法，它是一种最大似然译码算法。在码的约束度较小时，它比
5、其它概率译码算法效率更高、速度更快，译码器也较简单。本文设计是针对卫星通信和其它通信系统中常用的(2,1,7)卷积码的Viterbi译码器在FPGA中的一种低成本实现方案。为了兼顾速度和面积，采用串并结合的译码方式，同时利用流水线结构来提高译码速度。一、Viterbi译码器的结构设计译码器主要由五部分组成：分支度量单元(Branch Metric Unit)、加比选单元(Add-Compare-Select Unit)、幸存路径管理单元(Survivor Management Unit)、判决输出单元(Decide-Output Unit)和控制单元(Control Unit)。其整体结构如图
6、1所示：分支度量单元 (BMU)加比选单元(ACSU)幸存路径管理单元(SMU)控制单元(CU)输出接口输出输入接口输入判决输出单元(DOU)图1 Viterbi译码器总体结构 各单元之间的相互关系如下：接收到的输入数据首先被送入各分支度量单元中计算出相应的分支路径距离；加比选单元将旧的状态路径度量与相应的新产生的分支路径距离相加，通过比较后选择到达同一状态的两个路径度量值中较小的分支来更新路径度量；溢出处理防止加比选单元中的路径度量累加值发生溢出；幸存路径管理单元将加比选单元生成的路径信息进行存储管理；判决输出单元根据加比选单元选择的路径度量，从中选择一个最小值，并输出该最小值对应的幸存路径
7、。所有这些单元都在控制单元的协调下工作。1、分支度量单元(BMU)分支度量表征该分支接收到的码元与期望码元之间的差别。对于硬判决，这种差别指不同码元的个数。硬判决分支度量值可以表示为： .(1)其中，y为接收码字，c为本地卷积码输出码字。对于码率为1/2硬判决译码方式，编码器输出信号可能为00、01、10、11，其路径度量取值(汉明距离)只有0，1，2三种可能，因此需要用一个2bit的寄存器来存储分支度量值。 在本文中，采用了4个ACS单元(每个ACS单元有两个累加器)并行计算，因此需要8个分支度量单元并行计算8个条支路的度量值，并将度量值送至ACS中的累加器。2、加比选单元(ACSU)S1S
8、2S3S31S30S29S28S32S33S34S35S63S62S61S60S0S1S2S3S4S5S6S7S63S62S61S60S59S58S57S56S0T(i)T(i+1)图2 (2,1,7)卷积码的状态图ACS单元用来累加路径度量值并比较和选择进入某一状态的两条分支。本文中采用4个ACS单元并行计算，每16个状态复用一个ACS结构，同时兼顾了面积和速度。译码器的核心部分是ACS单元，传统的译码器结构每产生一位译码需要进行2(n-1)分支度量单元 加比选单元幸存路径管理单元控制单元输出输入判决输出单元次加比选运算，即22(n-1) =2n次加法运算和2(n-1)次比较选择运算。对于(
9、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)。S
10、jSj+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，
11、下支路输入的是1。因此，一个状态可以只生成一条支路(上支路)，另一条支路(下支路)的信息已经包括在这条支路中，要恢复出下支路只需要将上支路的输入数据取反即可。图4所示的ACS单元结构中的累加器可以减少一半的工作量，对于本文中的(2,1,7)码的译码器，即由每产生一位译码工作16个时钟周期减少为8个时钟周期(可将时钟频率降为原来的1/2)，减少了复用次数，降低了ACS单元的复杂度和功耗。同时，由于ACS单元结构的优化，每个状态只需要生成一条路径，存储的幸存路径数也由原来的128条减少为64条，也同样使结构变得简单，功耗有所降低。ACS单元的改进流水线型结构如图4所示：S0S32S1S33S7S3
12、9图4 改进的流水线型ACS单元时序图由式(1)和式(2)可知，输入数据(datain)不同，卷积码的输出C0和C1也不同，因此，同一状态上支路的输出与下支路不同，上下支路状态输出及译码器的输入数据之间的关系如表1所示：表1 上下支路与输入数据的分支度量值输入数据上支路度量下支路度量输入数据上支路度量下支路度量00000112100011110111010121001010111000121120001110010100111111002110010102011101102010101011111001110002利用上下支路分支度量值的关系就可以从上支路路径度量累加值中计算出下支路路径度量累
13、加值，用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单元中的累加器可以用超前进位加法器实现，这将使累加器不会成为速度的瓶颈。由于累加器使用固定长
14、度的寄存器(本文中采用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 n
