OFDM系统中Viterbi译码器的设计及FPGA验证

摘要:本文在对Viterbi译码算法进行Matlab软件仿真的基础上,综合考虑硬件开销以及电力线OFDM传输系统中FEC解码的具体要求,确定了Viterbi译码器的各个设计参数.为了提高译码性能和译码速度,提出了一种改进的回溯算法.整个设计用Verilog语言编写,采用FPGA技术,通过系统联调,验证了设计的合理性与可靠性.

关键词:半导体技术;Viterbi译码器;正交频分复用;现场可编程门阵列;回溯

近几年来,家庭网络技术已成为研究热点之一,它主要实现智能家电的控制与管理、多媒体信息服务、Internet接入等功能.目前关于组建家庭内部网络有多种解决方案,其中电力线联网方式正越来越受到人们的关注.它利用现有的电力线为传输媒介,把分布在家庭各个角落的家电和PC机连成一个网络.其优点是成本低,无需额外布线,而且安装和连接都很方便;其缺点是传输速率低和抗干扰能力差.而近几年兴起的正交频分复用(OFDM)技术正好能弥补上述不足之处.

OFDM采用并行多载波传输,所以数据传输速率可以很大;子载波之间可以有频谱重叠,所以频谱利用率高;由于将数据并行传输,相当于把数据符号展宽,故能有效抗多径.正是具有以上优点,使得基于电力线的OFDM数字通信技术在家庭内部组网方面有很大的技术优势.

由于我国导线规范和标准混乱,使配电网的结构不规范,所使用导线的特性差异导致信道环境极其复杂,而且噪声很大.所以在基于电力线的OFDM系统中,为了保证数字信号能可靠传输,降低数字信号传输的误比特率,一般都要使用差错控制编码技术.卷积编码和Viterbi译码就是一种有效的前向纠错方法,它具有一定的克服突发错误的能力.

Viterbi译码算法是用于卷积码译码的一种最大似然译码算法,其复杂性(无论是硬件实现还是软件实现)均随约束长度成指数增长.然而,为了得到较低的译码错误概率,就必然需要增大约束长度,这样使得Viterbi译码器的幸存路径存储管理单元(SMU)电路变得异常复杂,而且译码延时也相应增加,这对于需要高速工作的环境下是不能忍受的.一些文章提出了改进的存储管理方法,虽然可以简化设计,但是它们要么是以牺牲译码性能为代价,要么不利于整个设计朝着可测性方向发展.

针对上述问题,本文对幸存路径存储管理提出了一种改进的回溯法,它在不损失(某些情况下还优于传统的回溯法)译码性能的同时,缩减了译码延时,提高了整个Viterbi译码器的工作频率.把该方法应用到设计电力线OFDM系统中的Viterbi译码器,并采用FPGA技术验证了整个译码电路,证明这种改进的回溯法取得了很好的效果.

1　Viterbi译码器的系统结构

Viterbi算法是通过寻找一个有限状态过程中最可能的状态转移过程来恢复原来的信息.下面简单介绍Viterbi算法的基本概念和系统结构.
　　
卷积编码器的基本结构如图1所示.

图1　(n,k,m)卷积编码器

一个(n,k,m)的卷积编码器有k个信元输入端,n个输出端,m级寄存器,其中,m称为编码存储,编码率为R=k/n,编码约束长度为m+1,另外生成多项式(Generator Polynomials)决定了当前编码输出由前m级中哪几位约束.每输入k位信元,就可以得到当前的编码输出C_n,同时这m级寄存器在时钟作用下右移一次,状态由(d_m-1,d_m-2,d_m-3,.,d₀)变成(d_m-2,d_m-3,.,d₀,d_in).所以可以很容易地得到状态转移图,但是状态图只能表示卷积码编码器在不同输入的信息序列下各状态之间的关系,而不能反映状态转移与时间的关系,所以需要引入网格图(Trellis).

图2是编码存储为2的(2,1,2)卷积编码器的网格图,生成多项式为g₀=(111)₂,g₁=(101)₂,图中假定了一组输入信息序列,得到了相应的编码输出,而黑实线就是编码器的状态“走过”的路径.

图2　(2,1,2)卷积编码器及其网格图

基于上述网格图,可以给出具体的Viterbi译码算法:
①从某一时刻j=m开始,根据接收到的数据Ri,对进入每一状态的所有分支计算其分支度量(Branch Metrics).

②对于每一状态,把计算好的所有分支度量同这些分支相连的前一时刻留选的路径度量(Path Metrics)相加,就可以得到这一时刻所有分支进入该状态的路径度量,然后进行比较,选出最小的路径度量,并记录下相应的路径转移信息,这一过程可以简称为“加-比-选”(ACS).

③对于每一状态,把步骤②选出的最小路径度量去更新旧的路径度量,同时把路径转移信息存入幸存路径(Survival Path).

④j增加1,转到步骤①,处理新的接收数据;同时判断幸存路径的长度是否达到译码深度,如果已达到,则开始回溯(Trace-back),产生译码后的输出数据.

在电力线OFDM传输系统中,卷积编码采用(2,1,6)码,共有64个状态,生成多项式为:g₀=(171)₈,g₁=(133)₈.根据上述的Viterbi算法,可以设计出译码器的硬件实现框图,见图3.从图中可看出,在进行回溯时需要处理大量数据,这样必然加大了译码延时,严重限制了整个译码电路的工作频率.需要改进回溯方法,在不损失译码器性能的前提下提高速度.

图3　Viterbi译码器框图

2　主要模块的设计

2.1　分支度量计算单元
分支度量单元主要计算接收的码元符号与期望的码元符号之间的距离.根据对接收码元处理方式的不同,译码过程可分为硬判决和软判决.在同一译码算法下,虽然硬判决译码较软判决译码简单而易于实现,但在性能上要损失2～3dB,因此本文实现的Viterbi译码器是基于软判决的.而对于软判决译码,分支度量就是计算接收码元S_i(n)与网格图中某分支的编码比特G(n)之间的欧氏距离(Euclidean distance),若以BM代表分支度量,则:BM(n,j)=[S_i(n)-G_j(n)]²,(1)其中,n为时间间隔,j是要计算的第j条路径,S_i(n)是进入译码器的i级量化的软判决数据.由于量化级数与码元的可信度有直接的关系,量化级数越多就越能准确反映接收码元的可信度,从而使译码器的译码性能更接近最大似然译码.但随着量化级数的增加,译码器的复杂性也随之增加.图4是用Matlab仿真得出的量化级数对Viterbi译码性能的影响.综合考虑译码器性能和硬件开销,本文采用了4bit量化.

图4　量化级数对译码性能的影响

2.2　ACS(加2比2选)单元
由卷积码的网格图可知,从n时刻到n+1时刻的状态转移是由2^m-1个碟形模块组成的,如图5所示.每个蝶形模块由S_j,S_j+2^m-1,S_2j,S_2j+1(其中j=0,1,.,(2_m-1-1))等4个状态组成.在n时刻的2个状态的路径度量分别为和,在接收到新的码元后,需要计算出在n+1时刻的2个新状态S_2j,S_2j+1的路径度量.由图可知,转移到新状态的可能路径有2条,分别计算出这2条路径的度量,选取其中较小的作为新状态的路径度量.路径度量的计算就是分支度量加上与这条分支相连的前一时刻的路径度量,所以,新状态的路径度量为:

由上述的计算公式可知,路径度量的数值是不断在累加的,这样会使确定字长的累加寄存器发生溢出,需要进行饱和处理(saturated).本文采用的方法是在每一步计算时将各个状态的路径度量减去所有状态路径度量的最小值.该方法的优点是使用较短字长的累加寄存器都不会发生溢出,这有利于节约硬件开销.最后通过Matlab仿真分析,本文选用9比特字长的累加寄存器,这样路径度量值既不会溢出,而且其存储量也最小.

在求出新状态的路径度量后,为了后面回溯的需要,还必须保存状态转移的信息,即经过“加比选”得到的新状态的路径度量是选择了哪条分支.最简单的方法是保留前一个状态,这样对于本文的设计,每保存一个幸存路径信息就需要6比特的存储空间,如果译码深度是30,保存所有64个状态的幸存路径需要的存储空间为:64×30×6=11520bit,这显然太大了.实际上,参照图5的蝶形图,可以做出以下约定:凡是从上面状态S_j+2^m-1转移过来的路径,称之为“1”路径,如图中虚线所示;凡是从下面状态S_j转移过来的路径,称之为“0”路径,如图中实线所示.这样每保存一个幸存路径信息只需要1比特,所有幸存路径的存储空间降为原来的1/6.

图5　卷积编码的蝶形模块

2.3　幸存路径存储器
从上面可知,ACS在计算出新状态的路径度量的同时,也得出了到达这个状态的转移信息(用1bit表示),该路径转移信息就需要保存在幸存路径存储器中,这样多个转移信息就可以“串成”一条完整的幸存路径.为了得到最好的译码性能,幸存路径的长度应该尽可能的长.但在实际应用中,幸存路径的长度通常取编码存储m的4～5倍.在本文设计中,幸存路径的长度l=31,所以幸存路径存储模块如图6所示.图中,每一个小方框是一个D触发器.对于每一个状态,由ACS模块得到的路径转移信息都移入各自的幸存路径.这样每一条幸存路径存储单元就是一个长度为31的移位寄存器.

图6　幸存路径存储模块

2.4　回溯单元
回溯单元的基本工作原理是,当幸存路径中路径转移信息的个数达到译码深度后,便开始回溯过程.回溯的起始点为当前具有最小路径度量的状态,从该状态的幸存路径中找出路径转移信息,就可以确定下一级回溯路径的节点,这样一直回溯下去,直到最后一级,并根据最后一级的路径转移信息给出译码输出.实际上在寻找起始点时,同一时刻往往会有多个状态具有最小路径度量,对于这个问题的处理,大多数的做法是按一定的顺序或随机地选取其中一个作为起始点.本文通过仿真分析,发现在信道环境很恶劣时,如果考虑前一次回溯的起始点来确定当前起始点的话,对译码性能会有一定的改善,如图7所示.

图7　改进后的回溯算法对译码性能的影响

改进后的回溯算法如下.
①判断前一次的回溯起始点是否具有最小路径度量值,如果是,就以该点作为当前回溯过程的起始点;如果不是,就选具有最小路径度量的状态作为回溯的起始点,如果有多个,就根据状态的编号,按从小到大的顺序选取.
②从与之对应的幸存路径存储器中获得路径转移信息.
③将回溯节点的状态值右移一位,最高位用路径转移信息代替,得到新的回溯节点.
④重复步骤②,③,直到最后一级.
⑤给出译码输出,它为最后回溯节点的最低位.

传统的回溯算法有一个缺点:回溯路径的延时太长,从而影响了整个电路的工作速度.本文为了减小回溯路径的延时,在回溯电路中插入了一级寄存器,这样一次完整的回溯过程分两步来完成,从而形成流水线(pipeline)式的回溯,大大降低了电路延时.考虑到前面选择回溯起始点的模块,所以一般在整个回溯过程的1/3处插入这一级寄存器.另外,由于回溯过程分两拍来完成,这也影响了幸存路径存储器的结构,见图6.正是为了配合流水线式的回溯,所以需要在幸存路径中多加一级寄存器(图中带阴影的小方框),从而使得最终幸存路径的长度是5m+1.虽然幸存路径的存储长度增加了一级,但是寄存器11的幸存路径信息是不参与回溯的,所以译码深度仍然是5m,即为30.本文设计的回溯电路模块见图8.

图8　回溯电路模块

3　结　论

本文利用Matlab建立了卷积编码/Viterbi译码的软件仿真模型,并利用高斯白噪声信道进行模拟,确定了一些关键的设计参数,并且对传统的回溯算法作了一些改进,主要改进了两方面:
①在寻找回溯起始点时要考虑前一次的回溯起始点;
②在幸存路径和回溯路径中各插入一级寄存器.改进后回溯算法的主要优点是,对译码性能没有损失,在信道环境较恶劣时还优于传统的回溯法;另外,由于是流水线式的回溯,使得硬件实现时的回溯路径的延时大大降低,所以提高了整个电路的工作频率.
整个设计用Verilog硬件描述语言进行了RTL级的描述,在功能仿真正确后,采用Artisan 0.18 μm-generic工艺的标准单元库进行逻辑综合,得到面积为32074个等效门的门级网表.利用Synopsys公司的静态时序分析工具Prime Time,可知本文设计的Viterbi译码电路的最高工作频率是150MHz,它与其他文献中译码器的比较结果见表1.



图9　FPGA验证环境

本文进行FPGA验证所用的开发板是XESS公司的XSV BoardV 1.1,它用的FPGA芯片是Xilinx公司的Virtex XCV800,见图9.为了验证的需要,本文还设计了一个SRAM接口模块和一个计数器,计数器对译码输出进行计数,当计到设定值就点亮板上的LED,表明已经处理完所有数据.具体的验证方法是:首先把经过高斯白噪干扰后的编码数据通过与PC机的数据接口存储到开发板上的SRAM中,然后通过SRAM接口模块把这些数据送给Viterbi译码电路,译码器的输出结果存储到开发板上的另一块SRAM中,当看到LED亮起时就通过数据接口把译码结果读出并与卷积编码前的数据进行比较,结果证明译码器的输出数据与软件仿真结果完全一致,具有较强的纠错功能.为了便于比较译码性能,本文又按照文献[ 7 ]提供的回溯算法建立了该译码器的Matlab模型,对它输入相同的数据,这样得到相应的误码率.FPGA验证及比较结果见表2.


最后值得一提的是本文的设计为全同步设计,没有使用三态门等不利于电路可测性的单元,非常适合像家庭网络这样SOC(System On Chip)级的IC设计.整个设计的接口简单、通用,完全可以作为一个IPCore,适用于其他情况下(2,1,6)卷积编码的解码.



参考文献:
[1 ] 　Kubota S ,Kato S , Ishitani T. Novel Viterbi decode VLSI implementation and its performance [J ] .
[2 ] 　韩　雁,石教英. Viterbi 译码器VLSI 设计中幸存路径存储管理的新方法[J ] .
[3 ] 　Onyszchuk I M. Truncation length for Viterbi decoding [J ] . I EEE Trans Communication .
[ 4 ] Jiang YT ,Tang YY,Wang YK, etal . A trace-back-free Viterbi decoder using a new survival path management algorithm [ EB/ OL ].
[5 ] 　Kai H ,Cauwenberghs G. Integrated 642state parallel analog Viterbi decoder [ EB/ OL ] .
[6 ] 　Chang Y N ,Suzuki H ,Parhi K P. A 22Mb/ s 2562state 102mW rate21/ 3 Viterbi decoder [J ] .
[7 ] 　Truong T K,Shih M T ,Reed I S ,et al . A VLSI design for a trace-back Viterbi decoder [J ] .