-2-1-7-维特比译码器结构优化设计与实现(1)

第15卷第2期电路与系统学报Vol.15No.22010年4月JOURNALOFCIRCUITSANDSYSTEMSApril,2010文章编号：1007-0249(2010)02-0128-06(2,1,7)维特比译码器结构优化设计与实现*董时华1，乔庐峰1，胡庆生2，王志功2，章丽2（1.中国人民解放军理工大学通信工程学院，江苏南京210007；2.东南大学射频与光电集成电路研究所；江苏南京210096）摘要：对于维特比译码器设计与实现时速度的制约问题，通过优化加、比、选各单元模块结构，采用模归一化路径度量值和全并行的ACS结构，简化了ACS硬件实现的复杂度并极大地提高了运算速度，为了提高数据吞吐率，幸存路径存储与回溯单元使用4块SRAM优化数据的存储、回溯和译码。利用TSMC0.18逻辑工艺，实现了一种回溯度为64、3bit软判决的(2,1,7)维特比译码器，在1.98V，125℃操作环境下，使用DesignCompiler逻辑综合后静态时序分析，显示数据最大吞吐率为215Mb/s,Astro自动布局布线后的译码器芯片内核面积为1.56mm2，功耗约为103mW。关键词：维特比译码器；加比选；蝶形单元；模归一化；回溯；单端口存储器中图分类号：TN722文献标识码：A1引言随着现代通信技术的高速发展，对数据传输质量的要求在不断提高，为了提高信号在传输过程中抵御各种信道损伤（如噪声、干扰以及衰落等）的能力，就需要对信号进行差错控制编码。差错控制编码可分为卷积码和分组码两种，与线性分组码相比，卷积码充分利用了各组码间的相关性，具有信息位和码长较小的优点。卷积码的译码方法有基于码的代数结构的代数译码和概率译码，概率译码不仅基于码的代数结构，而且还利用了信道差错的统计特性，因而能充分发挥卷积码的特点，使译码错误概率最小。维特比译码是在1967年由Viterbi提出的一种最大似然译码算法。在码的约束度较小时，效率高、速度快而且译码简单，在实践中得到了极广泛的使用。2卷积码编码和维特比译码一个(n,k,N)卷积码编码器，如图1所示包括N段每段k级组成的移位寄存器，共Nk位寄存器，对应于每段k个信息比特，输出n个比特，在任意给定的时间单元时刻，编码器输出的n个比特，不仅与此刻输入的k个比特有关，而且与前面连续的N-1个时刻输入的信息比特有关，此时编码器共有2Nk个状态，如果输入的信息序列长度为Lk+Nk（后Nk个码元全0），则进入和离开每一个状态各有2k条分支，2Lk条不同的路径[1]。维特比译码是一种最大似然译码算法，相比其它译码方法，其的优越性在于它不是一次性比较所有可能的路径，而是接收一段，计算、比较一段，选择一段最可能的分支，从而达到整个码序列是一个最大似然函数的序列。本设计选用的(2,1,7)卷积码纠错性能优异而且实现复杂度适中，在实践中得到比较广泛的使用。(2,1,7)卷积码编码的生成多项式选择(171,133)8，如图2所示(2,1,7)卷积码编码结构图。对卷积码编码过程的分析常采用网格图进行，图3以(2,1,3)卷积码为例介绍了网格图结构，(2,1,7)*收稿日期：2009-12-04修订日期：2010-01-112k12k12k12n12N输入序列M输出序列X图1卷积码编码器一般形式S0S1S2S3S4S5S6输入序列x0x1图2(2,1,7)卷积码编码器第2期董时华等：(2,1,7)维特比译码器结构优化设计与实现129网格图原理类似。图中实线表示输入为0，虚线表示输入为1，线上数字表示期望的编码序列。图中自上而下4个节点分别为a,b,c和d四个状态，每个状态左边为低位输入码元，右边位为高位输入码元。3维特比译码算法与电路结构Viterbi译码器的结构主要包含4个基本组成部分[2]：分支度量单元（BMU：BranchMetricUnit）、加比选单元（ACS：AddCompareSelect）、幸存路径存储单元（SPM：SurvivorPathMemory）和回溯单元（TB：TraceBack）。下面将依次描述这些电路单元的具体实现方法和结构。3.1分支度量单元（BMU）的设计路径度量单元用于计算实际接收到的码元与期望码元之间的差值。采用欧几里得距离度量[3,4,9]时，如果在时刻n译码器接受到的软判决数据为yn，卷积码编码输出为Cij，则分支度量值表示为：222,,2)(ijijnnijnjinCCyyCyB+−=−=（1）式（1）中n为时间节点，i，j为n时刻任意的两种状态。因为维特比算法中决定幸存路径输出的是度量值间的差值，度量值同时加减一个常量都不会改变度量值间的差值，所以只需关注度量值之差即可。而对给定的时间节点n，接收的输入码序列yn一定，只需考虑编码输出Cij的二进制表示情况。当卷积码编码输出Cij表示为a和-a形式时，分支度量值差值可以表示为：⎪⎩⎪⎨⎧≠+−==−kjijijnijnkjijjknjinCCCyCyCCBB;22;0,,,,（2）去掉式（2）中公因子2，分支度量值可简化为：⎪⎩⎪⎨⎧−=+=−⇒−=aCyaCyCyBijnijnijnjin;;,,（3）此时仅剩下一个负号，实际算法时可以不用计算负号，而直接将求路径度量值的最小值改为求欧几里得距离的最大值即可。此时度量值表示为：ijnjinCyB=,,（4）最终简化后的式（4）是具体实现电路的分支度量计算式，当a取值1时，即使用+1和-1分别表示0和1。采用3bit软判决量化，将由于信道干扰，到达译码器的信号二进制编码011、010、001、000、111、110、101、100所对应的量化电平分别定义为3、2、1、0、-1、-2、-3、-4。此时支路度量值范围为：-8~+8，需要5bit符号数表示分支度量，设计时，所有状态分支度量的计算采用统一的运算单元并行完成。3.2加比选单元（ACS）的设计加-比-选单元是整个译码的核心，需要完成每个状态累加度量值的计算，比较并选出幸存路径信息和相应新的幸存路径度量值。在完成状态度量的计算和幸存路径的更新功能时，它的蝶型运算[5]单元包含了旧状态和新状态，四条相互关联的分支。蝶型运算的结构如图4所示，当输入比特为‘0’时，那么状态i和j都走实线表示的上支路（BMi0，、BMj0）到达状态p，当输入比特为‘1’时，那么状态i和j则都走下支路（BMi1、BMj1）到达状态q。SMx：表示状态x的状态度量值，在这里x为i、j、p、q。BMxk：表示输入比特为k（k为0或l）时，状态x的分支度量。这里x为i或者j。abaabdcabdcabdcabdca00b01c10d110100110110t1t2t3t4t5t600000000000000111111111010100101010101101010111111图3(2,1,3)卷积码网格图ijpqSMiSMjBMi0BMi1BMj0BMj1SMpSMqt-1t图4蝶形单元130电路与系统学报第15卷蝶形单元关系如下：（1）状态i来说，蝶型的状态转移关系为：12;2;22+==+=−iqipijN（5）（2）对于分支度量值：01010~;~iijjiBMBMBMBMBM===（6）（3）对于状态度量值：];),[(];),[(1100jjiiqjjiipBMSMBMSMMinSMBMSMBMSMMinSM++=++=（7）通过图4所示蝶形单元和各量间关系，所有状态随时序进行加-比-选。通过对状态度量值累加过程进行分析，发现路径度量值在参与每次累加过程中是不断增加的，然而在硬件实现时其值是存储在有限位长的寄存器中，就需要对度量值进行归一化运算，以防止在累加过程中发生数据溢出。一般采用的方法是在每一步运算后将各个状态的路径度量减去前一步所有状态路径度量的最小值，从而使调整后的当前状态最小度量为0。然而这个方法的主要缺点是路径度量最小值的选取工作在N比较大时（如N=7）消耗的硬件开销成指数倍增大，功耗也会随之增加，同时整个过程不能并行完成，降低了数据吞吐率。此时可以采用求模归一化[6]运算方法。求模归一化的基本理论依据是Viterbi算法有两个特性：（1）译码输出只与路径度量值之差有关；（2）路径度量值之差是有界的。可以证明每一时刻计算出的状态度量值的最大值和最小值间满足关系：mBSMSM≤−=||minmaxmax∆（8）对于(2,1,7)维特比译码器而言，61-==Nm，14727=×=×=nB，则12884max=∆。模归一化方法中，将状态j的路径度量值mj模归一化为：2)mod(2),mod(CCCmCmjjj−⎟⎠⎞⎜⎝⎛+≡=m（9）其中C值是选定的模值，路径度量值mj归一化为度量值jm的过程，可以按照图5所示来描述，将mj视为起点为0，终点无限延伸的射线，射线的无限延伸表示度量值无界的增长，将射线盘绕成一个周长为C、直径为π/C的圆，每个mj对应圆周上的点jm，而点jm对应圆周上的角度为Cmj/2π。度量值m1和m2间的差值满足2||21Cmm≤−，且2maxC≤∆。此时当max2∆≥C取值C=256时，度量值归一化就等同于用8比特补码表示度量值，可以不用考虑度量值溢出问题。加-比-选单元优化后的结构图和比较器结构图[7]分别如图6和图7所示，将符号位的异或运算和去掉符号位的数值比较运算分开并行实现，可以减少单纯补码减法实现的复杂度，并且运算速度更有优势。在图7中，ppmm21,分别为21mm、最高位即符号位，ppmm21,则为去掉符号位后的数值部分，满足：0m1m20α1m2m1m2m2C−图5模归一化运算示意图SMpSp2'sComplementAdder2'sComplementAdderModifiedComparatorBMi0SMiBMj0SMj558888888188MUX)(21mm、z1m2m图6设计使用的ACS结构图unsignedcomparator118888111Spm1pm2pm1pm2),(21mmy)(21mm、z1m2m图7Modifiedcomparator结构图第2期董时华等：(2,1,7)维特比译码器结构优化设计与实现131⎪⎩⎪⎨⎧+=0;20;jjjjjCmmmmm（10）无符号数比较器（unsignedcomparator）的输出满足：⎪⎩⎪⎨⎧=212121,0,1),(mmmmmmy（11）改进的比较器（ModifiedComparator）的输出为：),()(212121mmyz⊕⊕=mmmm、（12）满足：⎩⎨⎧=212121,0,1)(mmmmzmm、（13）3.3幸存路径存储单元和回溯单元设计幸存路径存储单元用来存储每个时间节点的所有状态的幸存路径，供回溯单元回溯和译码输出。由Viterbi算法可知，在网格图上经过大约5倍约束长度之后[4]（本设计选用的回溯深度L为64）所有的幸存路径都会收敛为一条。具体回溯的步骤[8]为：（1）当计算的级数t达到了译码深度L之后，控制单元产生回溯使能，开始回溯，回溯的起始状态设为状态000000；（2）从幸存路径存储器中获得与当前回溯状态对应的幸存路径值；（3）将回溯状态右移一位，用幸存路径值取代最高位，得到相邻的上一级回溯状态值；（4）重复步骤（2），继续计算直到Lt-级。回溯的目的是为了译码，将在网格图中发散的路径根据最大似然准则，选取每个时间节点处度量值最小的状态，当回溯达到要求的回溯深度L后路径便会收敛为一条，此条路径就是要找的译码路径，具体的译码步骤为：（1）将回溯完L级后的最后一个状态设为译码的起始状态；（2）从幸存路径存储器中获得与译码状态对应的幸存路径值，并输出；（3）将译码状态右移一位，用幸存路径值取代最高位，得到相邻上一级的译码状态值；（4）重复步骤（2），继续计算直至译码结束。实现时路径存储、回溯和译码是同步进行的，参考文献[2,10,11]流水线回溯译码思想，结构如图8(a)所示，由四块64×64的单端口SRAM组成的数据存储、回溯和译码结构图。其中①表示开始将幸存路径写入SRAM2的同时对SR