第30卷 第5期2007年10月电子器件Ch inese Jou r nal Of Elect ro n DevicesVol.30 No.5Oct.2007FP G A Design of Ser ial V iter bi DecoderL IU Yan g 2mei ,YU N in g 2mei ,SO N G L i a n 2g uo ,WA N G Tao(Dept.of Elect ronic Engi neerin g ,Xi ’an Univ.of Technol ogy ,Xi ’an 710048,Chi na)Abstract :The t heor y of (2,1,6)convol ut ional encodi ng and Vit erbi decoding ba sed on U WB (Ult ra Wi dt h Band)com munication syst em i s int roduced.S i mul ta neously ,t he i mplementi ng circuit of serial Vi ter bi de 2coder and i t s sub 2module i s accomplished .The hardware design of Vit erbi decoder i s i mplemented sucess 2f ull y i n F PGA wit h Alt era company ’s Apex20ke series.It adopt s serial st r uct ure and t raceback algori t hmso as to only t ake up 2195L Es i n FP pared wi t h parallel decoder ,i t saves about 50%ha rdware re 2souce.K ey w or ds :UWB ;convolutional encode ;Vi terbi decoder ;t raceback EEACC :6120B;6150C一种串行Viter bi 译码器的FP GA 设计与实现刘阳美,余宁梅,宋连国,王 韬(西安理工大学电子工程系,西安710048)收稿日期:2006210225作者简介:刘阳美(19822),女,硕士,主要研究方向为超宽带UWB 通信系统及VLSI 设计,yangmeiliu2000@ ;余宁梅(632),女,博士,博士生导师,主要研究方向为专用集成电路设计技术及工艺的研究;宋连国(2),男,硕士,主要研究方向为SI 数字前端与OFDM 芯片的研究;王 韬(82),男,硕士,研究方向超宽带UWB 通信系统及VL SI 设计摘 要:介绍了基于超宽带(UWB )通信系统的(2,1,6)卷积码和Viter bi 译码基本原理,设计了串行Viterbi 译码器以及各个子模块实现电路,采用Altera 公司的Apex20ke 系列F P G A 来综合实现,完成了Viter bi 译码器硬件设计.该设计使用串行结构,回溯算法,占用L Es 仅2195个,与并行译码相比节省了约50%的硬件资源.关键词:超宽带;卷积码;Viter bi 译码器;回溯中图分类号:TN 764 文献标识码:A 文章编号:100529490(2007)0521890204 超宽带(UWB)是一种采用纳秒级脉冲信号宽度,占用吉赫量级信号频谱,发送功率极低,适用于短距离的无线通信技术.以高分辨率,高截获率,信息含量大和能探测隐蔽目标等优点而成为无线通信领域研究和开发的一个热点[1].降低数据传输的误码率,提高通信质量是一个关键问题.UWB 系统采用的IEEE 802.15.3协议规定了信息传输的差错控制方案是(2,1,6)卷积码和最大似然的Viter bi 译码方案.Vit erbi 译码算法是卷积码译码的一种主流算法,基于码的代数结构基础,利用了信道的统计特性,使译码错误概率降到很小.在码的约束度较小时,Vi ter bi 译码算法效率高、速度快,易于硬件实现.Vit erbi 译码实现时一般可采用3种结构:并行,串行,串并结合.并行Vit erbi 译码速度快,但实现所需的资源随卷积码约束度的增加呈指数增长.串行Viter bi 译码实现所需资源较少,但以牺牲译码速度为代价.串并结合的译码则是在译码速度和资源之间取一个折中.本文对U WB 系统采用的(2,1,6)卷积码和Viter bi 译码的实现技术进行了研究.在保证译码速度和尽量减少硬件资源的原则下,完成了U WB 系统的串行Vit erbi 译码器的F PGA 硬件设计与实现.8191979A C 194.1 V iter bi 译码器(2,1,6)卷积码的约束长度k =7,子生成元为(171,133),均为8进制数,生成多项式G(D)=[1+D +D 2+D 3+D 6,1+D 2+D 3+D 5+D 6],D 是延时因子.每个时刻输入1bit 原始信息,移位寄存器根据生成多项式进行异或运算,得出2bit 编码信息.移位寄存器根据输入信息的不同有规律地进入不同的状态[2].编码器结构和状态转移图如图1所示.(a )(2,1,6)卷积编码图 (b )状态转移图图1 卷积编码图和状态转移图Vit erbi 译码器的工作原理:依据编码器状态转移图,对输入数据进行分支度量计算,送入加比选(ACS 单元),选择较小累加度量的路径,保存其幸存路径信息,用具有最小度量路径的状态标号进行回溯并选择幸存路径信息译出码字.Vit erbi 译码器主要由分支度量计算模块,加比选计算模块,累加度量存储模块,最小度量判决模块和回溯与判决输出模块组成,如图2所示.串行译码通过控制逻辑实现对分支度量计算和蝶型(2个A CS 单元)的复用,只需要一组分支度量和蝶型,而全并行译码需要32个相同的单元,因此串行译码可有效地节省资源.图2 Viterbi 译码框图1.1 分支度量计算分支度量计算模块计算进入当前状态的两条分支路径的度量.1/2卷积码共有4个分支值:00,01,10,11.对于硬判决,分支度量是接收到的码字与分支值的汉明码距,软判决则是欧式距离[2].本文采用硬判决,因而计算汉明码距.由于k =7的卷积码一共有=6个状态,每个状态对应两条不同的分支,共有8个分支值这些值已经按图()状态转移图的规律生成存放在ROM 中采用F G 外挂ROM 而不用卷积编码器生成分支度量的方式,只用了FP GA 内的一个地址控制器,易于实现,有效的节省了硬件资源.1.2 加比选(ACS 单元)计算加比选(ACS )单元是整个Vit erbi 译码的核心,完成每个状态累加度量值的计算,比较并选出幸存路径信息.如图3所示ACS 的原理图,M (2i ,t -1)和M (2i +1,t -1)是t -1时刻2i 和2i +1节点对应的累加度量值,B M (2i ,t )和BM (2i +1,t )是t 时刻的分支度量值,M (i ,t )是计算得出t 时刻i 节点的累加度量值,M (i ,t)既作为下一译码周期的累加度量输入,又作为当前译码周期判断选择最小累加度量状态标号的输入,SU R (i ,t )是t 时刻的幸存路径信息.在实际设计中,使用了一个蝶型(2个ACS 单元),完成的操作如下:M (i ,t )=min (M (2i ,t -1)+[B M](2i ,t ),M (2i +1,t -1)+[BM ](2i +1,t ))M(i +32,t)=min (M(2i ,t -1)+[BM ](2i +1,t),M (2i +1,t -1)+[BM ](2i ,t ))图3 加比选(ACS)单元如果选的是蝶型上支M (i ,t )则幸存路径信息为“0”,如果选的是下支M (i +32,t )则幸存路径信息为“1”.由于卷积码的状态转换具有蝶型规律,与使用单个ACS 单元相比可以少读写一次累加度量的地址,从而在兼顾资源地前提下速度提高一倍.1.3 累加度量存储累加度量的存储是配合加比选(AC S )单元的关键操作,体现了整个Vi terbi 译码算法的速度.经典方式是由贝尔实验室最先提出来的“乒乓操作”,即:前一时刻读出数据的两块RAM 作为当前时刻的写入RAM ,前一时刻写入的两块RA M 作为当前时刻的读出RAM [4].由于这种方法要使用4块RAM ,不能很好的利用FP GA 资源.为了有效的节省资源,本文使用一块RAM ,采用改进的“乒乓操作”对累加度量进行存储和更新.在同一块RAM 中要读出一个状态的两个度量,同时还要保证读出和写入的数据不被覆盖,地址控制成了关键,具体实现如下1981第5期刘阳美,余宁梅等:一种串行Vit erbi 译码器的F P G A 设计与实现82k-1412.1b .P A :k =7卷积码共有64个状态,使用双口RAM ,读写地址和数据输入输出分开,同时读写,地址宽度为7.RA M 分为A ,B 两个区,A 区地址为0～63,B 区地址为64～127.首先用64个时钟周期对A 区RAM 进行初始化,初始化值为0,相当于写地址为0～63,写入数据为0.当初始化完毕时,开始AC S 运算,ACS 是组合逻辑运算,运算得出当前时刻的累加度量值存到B 区.这个时候按照蝶型地址规律,读地址依次为(0,1,2…63),写地址为(64,96,65…127).此时,第一个译码周期完成,历时64个时钟周期A 区数据已经读出,B 区数据为下一译码周期所要读出的累加度量.第二个译码周期开始,A ,B 区读写方式切换,A 区为写数据区,B 区为读数据区,读地址依次为(64,65,66…127),写地址为(0,32,1…63).第三个译码周期A ,B 区读写功能继续切换,地址控制与第一个周期相同,以后的译码周期与前面相同,直到译码结束.与此同时,蝶型单元每处理完一个状态,得到1bit 幸存路径信息.当所有的状态都处理完了以后,可以得到64bit 的幸存路径信息,将这64bit 作为一个单元存入幸存路径RAM.对于约束度为k 的1/2卷积码的硬判决译码,每一步的最大值和最小值之差即度量跨度不超过2(k -1),用二进制表示的度量跨度最多需要log 22(k -1)bit.当k =7时,最少可以用4bit 来存储累加度量值[3].传统的归一化方式是一个译码周期完成,找到最小的累加度量值,然后让所有的值都减去最小值,这样做比较浪费时钟和硬件资源.本文采用的除2归一法是一种既不浪费时钟而且结构简单节省资源,它更适合FPG A 实现的方法.具体实现如下:处理前一组信息时一旦发现有累加度量超过门限值(由数据位宽决定)就给出一个信号,在下次读出累加值的时候统一右移一位(相当于除以2).1.4 最小度量判决为了回溯的需要,处理完一组译码信息后要得到最小的累加度量值所对应的状态标号.如图4最小度量判决模块实现框图,采用图1(b )蝶型结构时,输出口依次为(S0,S32)、(S1,S33)…(S31,S63),要从这64个值中选出最小值的状态标号,首先用一个加法计数器产生一个(0,1,2…31)序列,计数器值和状态标号具有固定的对应关系,0代表处理(S0,S32),1代表处理(S1,S33),…31代表处理(S31,S63).然后采用串行比较结构实现选出最小值的功能最小值寄存器初值为55(数据位宽为8),然后让(S ,S3)对应的M (,)和M (3,)两个累加度量和55比较,得到一个最小度量M M 2ric 送入最小值寄存器,如果最小值来自S0的路径则最小状态Mi nStat e 是此时刻计数器的值,如果来自S32则最小状态Mi nSt at e 是此时刻计数器加32.下一时刻(S1,S33)的累加度量到达,将这两个值和上次的最小值比较,得到新的最小值,同时记下新的最小状态.依次类推,ACS 做完的同时也得到了64个累加值中最小的一个所对应的状态标号.这个状态标号是回溯的必要条件.图4 最小度量判决1.5 回溯与判决输出在Vite rbi 译码器中,除了累加度量存储器外,还有一个幸存路径存储器,它用来保存每一级所有节点的幸存路径,这些值将用于回溯单元产生译码器的译码输出.幸存路径存储器的结构主要有两种:一种是寄存器交换结构,另一种是回溯结构.前者采用专用寄存器作为存储主体,存储的是路径上的输入信号信息,利用数据在寄存器阵列中的不断交换来实现译码.这种方法虽然具有存储单元少,译码延时短的优点,但由于其内连关系过于复杂,不适合大状态Vit erbi 译码器的F P G A 实现;而后者也就是本文采用的回溯法利用通用的RAM 作为存储主体,存储的是幸存路径的格状连接关系,通过读写RA M 来完成数据的写入和回溯输出.其优点是内连关系简单、规则.k =7卷积码有64个状态,即一组幸存路径有64bit.实际应用中,为了保证译码的准确度,幸存路径的回溯长度通常取4～5倍约束长度,本文回溯长度定为42.如图5为回溯与判决输出框图.使用一个42×64的RAM 来实现幸存路径的存储.具体操作如下:当处理完第42组译码信息后,得到了此时的最小状态和42×64bit 的幸存路径信息.把该最小状态送入最小状态寄存器,同时从幸存路径RA M 中读出第42组的幸存路径,用最小状态标号去选择这64比特的幸存路径得到1比特信息,通过移位拼接运算完成状态更新后得到了前一次的最小状态,再用这个状态标号去选择第组幸存路径依次循环,从第组幸存路径选出的最小状态的最2981电 子 器 件第30卷8.2020t 2t 2i n et 42.1高位就是第1个译码比特.此时,第一组幸存路径信息已经不对译码造成影响,下一次回溯时,刚好把第43组幸存路径存储到第1组位置.此时以后的每个比特都按照此算法译出,直至完成全部译码.由于每回溯一次都可以用一组新幸存路径信息覆盖一组旧幸存路径信息,因而节省FPA G 硬件资源,也正是回溯法的优势所在.图5 回溯与判决输出框图2 电路功能验证与误码性能分析整个系统使用Verilog HDL 完成了设计,在Model sim 6.0平台上进行了仿真,并且分别在X ilinx ISE 和Quart us Ⅱ平台上进行了综合.选用Altera 的Apex20ke 系列FP G A 来综合实现,得到电路的等效L Es 仅为2195.比参考文献[3]中说明的全并行算法L Es 大于4000的硬件资源大约节省了50%.整个系统的FP G A 资源使用效率如表1所示.表1 F PGA 的使用效率系列AP EX20KE 器件EP20KE200EFC48422X 逻辑单元数2195/832026%管脚数20/3765%存储器比特数12288/10649611% 本设计一方面利用Mo del Sim 对Q uart us Ⅱ综合的网表进行了后仿真,验证结果如图6所示.sy 2sclk 是系统时钟,周期为100ns ,sysclk1是译码输入时钟,由于一个译码信息需要64个时钟周期,故sy 2sclk1是6400ns ,st a_t b 是回溯的状态,dec_bi t 是译出码字.图示为第一个回溯操作过程部分结果:当sysclk1输入了42组译码数据时,再经过42个sy 2sclk 周期的回溯,sta_t b 的最高位即是译码信息.图中粗线所示dec_bi t 为“1”的译码比特,与编码器输入结果一致,说明译码正确.同时利用Tekt ronix 的TLA60逻辑分析仪对下载好程序的FP GA 进行实测,得到电路波形与后仿结果一致.图6 回溯后仿真波形串行Vi ter bi 译码与并行译码相比只是实现结构不同,其核心算法加比选(ACS )完全一样,对误码性能不造成影响.图7是借助第三方工具Ma tlab 中的Si mulink 平台,把串行Vi terbi 译码用Matla b 语言编写为S 2Function 得到的误码性能.由图可见,误码率达到信噪比为5时误码率小于10-4的信道要求.图7 误码性能3 结论本文通过对U WB 通信系统的(2,1,6)卷积码Viter bi 译码的F PA G (Field Progra mmable G at e Array 现场可编程门阵列)实现算法的研究,设计了采用了单蝶型(2个ACS )串行方式,双口RAM ,改进的“乒乓操作”,深度为42的回溯算法硬判决Vit 2er bi 译码器.该译码器在满足译码速度的条件下与并行算法相比节省了约50%的硬件资源;并且可以通过改进串并方式和判决方式移植到其他系统中,因此便于与其他模块整合.参考文献:[1] 李明晶,谭晓辉.超宽带技术浅谈[J ].吉林省经济管理干部学院学报,2005,19(5):61263.[2] 王新梅,肖国镇.纠错码-原理与方法(修订版)[M ],西安:西安电子科技大学出版社,2001:4432460.[3] 陈春霞,王匡.基于FP GA 的串行维特比译码的实现[J ].计算机工程,2003,29(14):1692171.[4] 张荣兵,和应民.参数化Vi terbi 译码器的FP G A 实现[D].哈尔滨工业大学2005.[5] Truon g T K,Shih Mi ng 2Tang ,Reed Irving S , E.H.Sat ori 2us.A VL SI Design for a Trace 2Back Vit erbi Decoder[J ].IE EE Transact ion o n C o mmuicatio ns ,1992,40(3);6162624.3981第5期刘阳美,余宁梅等:一种串行Vit erbi 译码器的F P G A 设计与实现8。
