卷积码Viterbi译码算法的FPGA实现

卷积码Viterbi译码算法的FPGA实现

发布日期:2006-04-20 作者:赵旦峰 刘会红

摘 要：探讨了卷积码Viterbi译码的FPGA实现问题。在Viterbi译码算法中，提出了减少路径量度的位数和流水线回索法的幸存路径等方法，能有效地减少存储量、降低功耗、提高速度，使得K＝7的Viterbi译码算法可在以单片FPGA为主的器件上实现。

关键词：差错控制；Viterbi译码；FPGA实现；卷积码

1 引 言

在数字通信中，如何降低数据传输的误码率，提高通信质量是一个很关键的问题。卫星通信系统以很远的距离传送数据，由于衰落、噪声和干扰等的影响，信号在传输过程中将产生严重的畸变。这就要求信号应具有尽可能大的能量，但是，由于卫星体积和载重等的限制，不可能给信号提供太大的能量，这样，就要求采用具有很强纠错能力的差错控制方法［1］以保证误码率在允许的范围之内。为实现强大的纠错能力，除了构造所谓“好码”之外还要求译码时采用最大似然译码算法。一般认为卫星通信信道是功率受限，对于卫星通信采用编码来改善通信效率是特别有吸引力的。

自1985年Xilinx公司推出第一片FPGA至今，FPGA已经历了十几年的发展历史，占据了巨大的市场，逐渐取代了ASIC，其原因在于： FPGA不仅解决了电路系统小型化、低功耗、高可靠性等问题，而且其开发周期短、开发软件投入少、芯片价格不断降低，特别是对小批量、多品种的产品需求，使FPGA成为首选［2］。

针对FPGA设计的特点，本方案在不改变纠错性能的前提下提出了一系列的方法。如减少连接线、流水线回索法等。目的是减少存储器的容量，降低功耗，提高速度。

2 Viterbi译码算法

在卷积码译码中，Viterbi译码算法是纠错能力很强的一种，已广泛应用于卫星通信系统。Viterbi译码算法是一种最大似然译码算法［1］。

Viterbi译码算法的步骤：

（1）根据接收码符号，计算出相应的分支量度值；

（2）将进入某一状态的2条分支量度与其前面的状态量度累加求和；

（3）比较到达同一状态的2条新的路径量度的大小，选择最小者作为新的状态量度存储起来，并记住与此路径（幸存路径）对应的信息码元；

（4）对所有的2m个状态都实施上述相加／比较／选择（ACS）运算；路径量度最小的一条路径（约为以前码元长度的5倍）作为译码数据输出；

（6）将译码时刻向前延伸一步，重复以上步骤，直至译码结束。

3 Viterbi译码器的实现

下面将介绍（2，1，7）卷积码8电平量化的Viterbi译码器的实现。其编码器如图1所示。译码器的方框图如图2所示。

Viterbi译码器主要有5部分组成：

（1）输入转换及分支量度计算电路。

（2）相加／比较／选择电路及状态量度存储器。

（3）路径判据存储器、最佳状态选择和输出缓冲器。

（4）同步电路。

（5）时序电路。

输入转换电路用一些简单的逻辑电路实现，分支量度计算用ROM来实现。分支量度单元接收I和Q两路数据，产生路径量度需要的分支量度。对于本方案，采用8电平软判

决，I和Q路数据各用3 b表示，分支量度用欧氏距离计算，经过压缩整数化可用4 b表示。对于3 b表示的I和Q路数据，能够产生64个分支量度。实际上，可用64个字，每个字16 b的查找表实现。

对于（2，1，7）卷积码，有64个状态，也就意味着，在每一步，要计算64个路径量度。基于速度要求，采用全并行算法［3］，即在每一步同时计算64个路径量度，需要64个并行处理的ACS模块或32个蝶形结构 （每一个蝶形结构由2个ACS模块组成）。每一个ACS单元由2个加法器和1个比较器构成，这样总共有128个加法器和64个比较器。显然，路径量度单元是整个Viterbi译码器的核心，对于提高速度有着实质的影响。ACS实现结构如图3所示。

文献［1］中，已经证明在每一步的量度的最大值与最小值的差值用下面的公式计算：

的路径量度和最小的路径量度之间的最大差值为84。这样要求用7 b来表示路径量度。事实上，在每一步的路径量度的归一化操作保证了具有最小量度的路径量度不受路径量度的比特数的影响。

经过验证，用5 b表示路径量度的Viterbi译码器的性能仍然很好。为了防止溢出，当每一个路径量度都大于或等于所选择的固定的数值时，在下一个周期，所有的路径量度都减去这个固定的数。在本方案中选择4为固定的数值，是基于比较器简单和快速，用或非门实现。只要路径量度中最高3位有一个为1就意味着此量度大于或等于 4。若所有的路径量度都大于或等于4时，进行归一化操作，即从所有的路径量度中减去4。这样还需要一个64输入的或非门电路，来产生归一化标志。

在Viterbi算法中，幸存路径存储的实现有2种传统方法：寄存器交换法RE（Register Exchange）和回索法TB（Trace Back）。

寄存器交换法采用专用寄存器作为存储主体，存储的是路径上的信号信息，利用数据在寄存器阵列中的不断交换实现信息的译码。优点是存储单元少，译码延时短，I／O端固定。缺点是内连关系过于复杂，不适于大状态译码器的FPGA实现。

回索法使用通用的RAM作为存储体，存储的是 幸存路径的格状连接关系，通过读写RAM来完成数据的写入为回索输出。优点是内连关系简单、规则，适

合用FPGA实现。缺点是译码延时较长。

本文提出了一种基于流水线结构的回索法［4］，提高了译码的速度。流水线回索算法如图4所示。在每一个时钟周期进行一次回索，同时幸存信息进行移位操作，最佳状态暂存在寄存器中，随着下一阶段的回索，上一步的最佳状态被覆盖。这种方法的好处就是可以使用更高的时钟来处理，缺点是延时较长。但综合考虑，译码速率还是较快的。

以上这些操作都用VHDL语言描述，利用XILINX公司专用软件ISE编译，并用Modelsim专用仿真软件进行了功能及时序仿真。

4 结 语

本文探讨了适合于卫星通信的标准（2，1，7）卷积码Viterbi译码器的实现

问题，主要是为了提高译码速度。在Xilinx公司的FPGA上利用VHDL语言编程实现了上述算法的Viterbi译码器，其性能符合卫星通信标准。利用8路并行结构可达到300 Mb／s的译码速度。

参考文献

［1］王新梅，肖国镇．纠错码—原理与方法［M］．西安：西安电子科技大学出版社，2001．

［2］朱明程．Xilinx数字系统现场集成技术［M］．南京：东南大学出版社，2001．

［3］宣建华，姚庆栋．高速Viterbi处理器的并行算法和结构［J］．信号处理，1993．

［4］韩雁，王匡．一种寄存器回索型Viterbi译码器的VLSI设计［J］．浙江大学学报工学版，1997，（4）．