基于FPGA的Viterbi译码器设计及实现

admin

摘要：
          卷积码是广泛应用于卫星通信、无线通信等各种通信系统的信道编码方式。Viterbi算法是一种最大似然译码算法。在码的约束度较小时，它比其它概率译码算法效率更高、速度更快，译码器的硬件结构比较简单。随着可编程逻辑技术的不断发展，其高密度、低功耗、使用灵活、设计快速、成本低廉、现场可编程和反复可编程等特性，使FPGA逐步成为Viterbi译码器设计的最佳方法。项目目的是用FPGA实现一个Viterbi译码器。
          关键词：FPGA  Viterbi译码器  卷积码 Verilog
           
          一、译码器功能分析
          译码器是一种具有“翻译”功能的逻辑电路，这种电路能将输入二进制代码的各种状态，按照其原意翻译成对应的输出信号。Viterbi译码器是以Viterbi算法为基础设计的一种译码器，译码器主要由五部分组成：分支度量单元(Branch Metric Unit)、加比选单元(Add-Compare-Select Unit)、幸存路径管理单元(Survivor Management Unit)、判输出单元(Decide-Output Unit)和控制单元(Control Unit)。其整体结构如图1。
           

       

        图1  译码器结构框图

         

          各单元之间的相互关系如下：接收到的输入数据首先被送入各分支度量单元中计算出相应的分支路径距离；加比选单元将旧的状态路径度量与相应的新产生的分支路径距离相加，通过比较后选择到达同一状态的两个路径度量值中较小的分支来更新路径度量；溢出处理防止加比选单元中的路径度量累加值发生溢出；幸存路径管理单元将加比选单元生成的路径信息进行存储管理；判决输出单元根据加比选单元选择的路径度量，从中选择一个最小值，并输出该最小值对应的幸存路径。所有这些单元都在控制单元的协调下工作。
           
          1　分支度量单元
          分支度量表征该分支接收到的码元与期望码元之间的差别。对于硬判决，这种差别指不同码元的个数。硬判决分支度量值可以表示为：
                                    (式1)
          其中，y为接收码字，c为本地卷积码输出码字。对于码率为1/2硬判决译码方式，编码器输出信号可能为00、01、10、11，其路径度量取值(汉明距离)只有0、1、2三种可能，因此需要用一个2bit的寄存器来存储分支度量值。
           
          在本文中，采用了4个ACS单元(每个ACS单元有两个累加器)并行计算，因此需要8个分支度量单元并行计算8个条支路的度量值，并将度量值送至ACS中的累加器。
           
          2　加比选单元
          ACS单元用来累加路径度量值并比较和选择进入某一状态的两条分支。本文中采用4个ACS单元并行计算，每16个状态复用一个ACS结构，同时兼顾了面积和速度。
           

       

        图 2  （2，1，7）卷积码的状态图

         

          译码器的核心部分是ACS单元，传统的译码器结构每产生一位译码需要进行2(n-1)次加比选运算，即2×2(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(31≥j≥0)。这也就是图形单(ButterfllyUnit)。

       

        图3  基二蝶形单元

         

          在图3中，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)≥j≥0)生成的两条支路，唯一不同的信息就是该时刻状态Sj的输入数据，Sj的上支路输入的是0，下支路输入的是1。因此，一个状态可以只生成一条支路(上支路)，另一条支路(下支路)的信息已经包括在这条支路中，要恢复出下支路只需要将上支路的输入数据取反即可。图4.2所示的ACS单元结构中的累加器可以减少一半的工作量，对于本文中的(2,1,7)卷积码的译码器，即由每产生一位译码工作16个时钟周期减少为8个时钟周期(可将时钟频率降为原来的1/2)，减少了复用次数，降低了ACS单元的复杂度和功耗。同时，由于ACS单元结构的优化，每个状态只需要生成一条路径，存储的幸存路径数也由原来的128条减少为64条，也同样使结构变得简单，功耗有所降低。
           
          由式(2)和式(3)可知，输入数据(datain)不同，卷积码的输出C0和C1也不同，因此，同一状态上支路的输出与下支路不同，上下支路状态输出及译码器的输入数据之间的关系如表1所示：
           

        表1  上下支路与输入数据的分支度量值

输入                                                                         数据	上支路	度量	下支路	度量	输入                                                                         数据	上支路	度量	下支路	度量
00	00	0	11	2	10	00	1	11	1
	01	1	10	1		01	2	10	0
	10	1	01	1		10	0	01	2
	11	2	00	0		11	1	00	1
01	00	1	11	1	11	00	2	11	0
	01	0	10	2		01	1	10	1
	10	2	01	0		10	1	01	1
	11	1	00	1		11	0	00	2

           
          利用上下支路分支度量值的关系就可以从上支路路径度量累加值中计算出下支路路径度量累加值，用Verilog HDL语言描述为：
          case(up_branch_metric)
          2'b00: down_path_add_metric <= up_path_add_metric + 2'b10;
          2'b01: down_path_add_metric <= up_path_add_metric;
          2'b10: down_path_add_metric <= up_path_add_metric－2'b10;
          default: down_path_add_metric <= 7'bxxx_xxxx;
          endcase
           
          另外，ACS单元中的累加器可以用超前进位加法器实现，这将使累加器不会成为速度的瓶颈。由于累加器使用固定长度的寄存器(本文中采用7bit的寄存器)，因此在不断累加过程中可能会发生溢出，影响译码结果。解决溢出常用的方法是到达译码深度时从所有状态的路径度量值中减去最小度量值。
           
          3　幸存路径管理单元
          幸存路径管理单元用来完成对幸存路径的记录，处理ACSU输出的信息，为输出判决作准备。SMU的实现主要有Register Exchange (寄存器交换)和Trace Back(回溯)两种算法。由于寄存器交换算法比回溯有更小的译码延时，RE法中幸存路径寄存器记录了幸存路径所对应的解码信息，也就是译码输出。采用这种方法消除了根据当前状态往前追踪的必要，因此寄存器交换提供了一种速度很高的译码操作。
           
          4　判决输出单元
          判决输出单元(DOU)由两部分组成：最小值选择单元(MNSU：Minimum Number Select Unit)和译码输出单元(DOU：Decode Output Unit)。最小值选择单元是用来选出本文中前面4个ACS单元输的路径度量值中具有最小度量值的节点， 读取该结点保存的幸存路径，供译码输出单元输出译码值。判决输出单元的结构如图4所示：
           

                             

        图4  判决输出单元结构图

         
          5　控制单元
          控制单元(CU)产生控制各模块的时钟信号，是所有模块的有序运行的基础。各时钟信号功能如下：clk_load用于读取前一时刻各状态寄存器的内容，并产生各状态上支路的状态输出值；clk_BM用于计算各状态上支路的分支度量值并读取前一时刻各状态的路径度量值；clk_Add用于计算各状态上支路的路径度量值；clk_restore用于暂存各状态上支路度量值并恢复相应状态下支路的路径度量值；clk_C_S用于比较并选择达到同一状态的两支路的路径度量值的较小者，并存储各状态选择的幸存路径；clk_MNS用于选择各状态存储的路径度量值中的最小值，并保存该最小值对应的状态；min_sel_1和min_sel_2分两步选择4个MNSU选择结果的最小值，并选出最终的最小值对应的状态；Decode_Output用于读取该最小值对应状态存储的幸存路径，并输出译码结果。
           
          二、项目实施方案
          Viterbi译码器大致可以分为四个部分：支路度量模块(BMU)、加比选模块(ACS)、幸存路径管理模块(SMU)和输出产生模块。其 中支路度量模块用于完成译码器输入信号与网格图上的可能路径信号的分支度量计算；加比选模块主要把前一个状态的路径度量与当前输入信号的分支度量相加，以得到该分支的路径度量，然后比较不同分支路径度量的大小，同时找出最小的度量值，并更新该状态的度量值，最后输出状态转移信息；路径管理模块可对加比选单 元输出的状态转移信息进行处理，以便为输出判决做准备。输出模块可根据幸存路径管理单元的输出进行输出判决，最后输出译码信息。Viterbi译码器基本原理框图如下所示。