基于FPGA的卷积编译码器的设计与实现

刘杨，章敏

（桂林电子科技大学 广西 桂林 541004）

卷积码是Elias在1955年最早提出的，稍后，Wozencraft在1957年提出了一种有效译码方法，即序列译码。Massey在1963年提出了一种性能稍差，但比较实用的门限译码方法，由于这一实用性进展使卷积码从理论走向实用。而后Viterbi在1967年提出了最大似然译码法，该方法对存储器级数较小卷积码的译码很容易实现，并具有效率高、速度快、译码器简单等特点，人们后来称其为维特比算法或维特比译码，广泛应用于现代通信中。本文主要论述了基于Xilinx公司的FPGA的卷积编码器及相应的维特比译码器的研究，并在幸存路径存储与译码输出判决方面提出了改进算法，从而使译码器结构得到简化。

1 卷积码的编码原理与实现

卷积码是一种重要的前向纠错编码 FEC，用（n，k，m）表示，分组码不同，其监督元与本组的信息元和前若干组的信息元有关。这种编码的纠错能力强，不仅可纠正随机差错，而且可纠正突发差错。卷积码根据需要，有不同的结构及相应的纠错能力，但都有类似的编码规律。卷积码的编码器是一个具有k个输入位（端）、n个输出位（端），m级移位寄存器的有限状态记忆系统，通常称为时序网络。其中R=k/n为编码效率，m为约束长度。卷积码编码原理如图1所示。

图1卷积码编码器原理图Fig.1 Principle diagram of convolutional encoder

卷积编码充分利用各组信息元之间的相关性，在误码率和复杂度相同的情况下性能优于分组码，并且最佳译码更易实现，因此在通信系统中得到广泛应用。但是卷积码没有严格的代数结构，尚未找到严密的数学手段将纠错性能与码的构成有规律地联系起来，目前大都采用计算机搜索好码。通常是（2，1，3）卷积码，本文以生成多项式 G=（111，101）的（2，1，3）卷积码为例介绍设计和实现过程。

设初始状态为S0编码为00，根据生成矩阵分别带入输入0和输入1时得到下一个状态和相应输出。依次代入，可得到如图2所示的状态图。

图2编码器状态图Fig.2 State diagram of encoder

描述卷积码的方法主要有两类[1]：图解表示和解析表示。上文提到的生成多项式G=（111，101）即是解析表示。卷积码的图解表示又可分为树状图、网格图和状态图3种。下面介绍常用的树状图表示（网格图表示将在译码部分介绍）。在图2所示的卷积编码树状图中，假设移位寄存器的起始状态全为0，当第1个输入比特为0时，输出比特为00；若输入比特为1时，则输出比特为11。随着第2个比特输入，第1个比特右移1位，此时输出比特同时受当前输入比特和第1个输入比特的影响。第3个比特输入时，第1、2比特分别右移1位，同时输出2个由这3位移位寄存器存储内容所共同决定的比特。当第4个比特输入时，第1个比特移出移位寄存器而消失。移位过程可能产生的各种序列如图3中的二叉树。

图3 （2，1，3）卷积码的树状图表示Fig.3 Tree diagram of（2,1,3）convolutional codes

2 Veterbi（维特比）译码器原理

卷积码的译码方式有3种：Veterbi译码、门限译码和序列译码。其中维特比译码具有最佳译码性能，但硬件实现相对复杂。veterbi算法是检测离散马儿可夫过程有限状态序列的优化算法[4]。在数字通信系统中，前向纠错卷积码编码和维特比译码用来提高系统性能，应用广泛。

维特比算法是一种最大似然译码算法。它不是在网格图上一次比较所有可能的2条完整路径，而是接收一段，计算比较一段，选择一段最有可能的码段，从而达到整个码序列是一个有最大似然函数的序列。其基本原理是：以断续的接收码流为基础，逐个计算它与其他所有可能出现的连续的格状图路径的距离，选出其中概率最大的一条作为译码输出。

维特比（Veterbi）译码算法是基于卷积码的网格图表示中路径的计算，其核心思想就是通过计算路径矢量进而寻找最短路径从而最终得到译码序列并可以纠正传输过程中的错误码字。 图4中给出（2，1，3）卷积码的网格图表示[1-2]。

图 4中的网格图中共有 2k（N-1）种状态，每个状态（节点）有2k条支路进入，同时也有2k条支路引出。由于本文讨论的是（2，1，3）卷积码的情况，因此 k=1,假设起始状态为全 0。

图4 （2，1，3）卷积码的网格图表示Fig.4 Trellis of（2,1,3）convolutional codes

在不同时刻对于同一节点的所有8个状态，分别计算以其为终点的2条分支路径的对数似然函数累加值并进行比较，舍弃其中对数似然函数累加值小的路径，保留对数似然函数累加值较大的路径，并将此路径称为剩余路径。由此可见，上述过程可以归纳为“加-比-选”算法，经过“加-比-选”电路以后，通过结束信息来确定最终得到的译码序列，其中每到来一个结束信息时，只将与已知发送信息相符的那条支路保留，以此类推，经过N-1个结束信息后，即可得到与发送序列最相似的译码路径。

3 译码器设计与实现

维特比译码器包括4个子模块，如图5所示。

图5维特比译码器的总体框架Fig.5 Overall framework of veterbi decoder

1）控制单元 向各个功能模块提供控制信号，保证译码器的工作时序正确，协调各个功能模块从而促使整个译码器的正常工作。

2）路径度量和“加-比-选单元” 计算和比较每条支路的路径度量，得到并保存剩余路径提供给回溯单元。对于（2，1，3）卷积码，译码深度 D=5（m+1）=20，为保证存储单元和回溯单元同时并行工作，存储单元为2D（m+1）2m=1 280 bit。

3）回溯单元 从前面“加-比-选”电路送来的剩余路径中选择量度最小的剩余路径，从这条路径对应的状态开始向前寻找，直到找完前面所有状态，并从存储单元中读出译码信息送给译码控制单元。

4）译码控制单元 将回溯单元送来的译码序列反转顺序输出即为所要输出的正确的接收序列。其中反转顺序的操作可由RAM实现，顺序写入倒序读出。

4 译码器设计中改进和优化算法

本文采取状态路径和判决比特同时存储，在表示状态信息的比特前加上1位判决比特来表示相应状态的输入支路的译码信息，因此，译码器在回溯时就可直接输出判决比特作为译码器的输出，降低了译码器的判决难度，节省了存储回溯路径所需要的内存，从而降低了译码器结构复杂性。

本设计中译码器在计算所有状态的路径量度的同时进行路径存储，从而大大提高了译码速度。路径量度是指每个状态的2条输入支路和2条输出支路，路径存储指的是状态存储以及相应的译码判决比特存储。该结构的译码器对每一个状态都具有独立的处理单元，彼此互补影响，并行工作，提高了译码速度。对于（2，1，3）卷积码，一个时钟需要进行 2×2×2m=32次路径量度计算和2m=8次4比特存储操作。充分发挥了FPGA拥有大量LCS和RAM的优势。

在网格图中，随着状态的改变，每个状态的输出支路的路径量度逐渐增加，造成存储资源压力增大，设计中在每次进行路径量度计算时，将该状态的量度值与上次剩余路径量度的最小值做差后进行保存，以达到减小存储器空间的需求。对于编码效率为1/2的卷积码，以上差值最大不超过2m，因此，路径量度的量化宽的为 lb（2m）。 对于（2，1，3）卷积码，存储路径量度的寄存器位宽为 lb（2×3）=3。

5 验证仿真

本设计采用Xilinx公司的ISE 9.2i为开发平台，选用的是Xilinx Virtex 4 FPGA为开发芯片用于设计和验证所提出的卷积编码和维特比（Veterbi）译码算法。

5.1 卷积编码器

如图6所示，clk为时钟信号，reset为复位信号，din为输入信号，out_1,out_2为编码后得到的并行码字序列。可看出：输入码元为“101010111011 000100011011111111100……”经过编码得到编码结果为“110100010001001010100010 101100110111001110100101010101010101011”结果正确。

5.2 Verterbi译码器

Verterbi译码器仿真波形如图7所示，rev[1:0]为输入译码器的接收序列，clk为时钟信号，rst为复位信号，enable为使能信号，h_out为译码器输出序列。可看出：译码输出码元为“101010111011000100011011111111100……”，结果正确。

图6卷积编码器的仿真波形Fig.6 Simulation waveform of convolutional encoder

图7维特比译码器的仿真波形Fig.7 Simulation waveform of veterbi decoder

6 结束语

通过对卷积编码原理与维特比译码算法的深入研究，在理解传统实现方法的基础上提出适合FPGA存储器和独立运算单元丰富的特点的优化算法，有效地提高了译码器的处理速度，简化了译码器的复杂程度。

[1]曹志刚.现代通信原理[M].北京：清华大学出版社，1994.

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

[3]夏宇闻.Verilog数字系统设计教程[M].北京:北京航空航天大学出版社，2003.

[4]ViterbiAJ.Errorboundsofconvolutionalcodesandanasymptotically optimum decoding algorithm [J].IEEE Transations on Information Theory,1967,13（2）:260-269.

[5]Anderson J B,Offer E.Reduced-state sequence detection with convolutional codes[J].IEEE Transactions on Information Theory,1994,40（3）:965-972.

[6]Proakis J G， Salehi M.Digital communications[M].北京：电子工业出版社，2006.