联合解调与Viterbi译码算法的改进

联合解调与Viterbi译码算法的改进 联合解调与Viterbi译码算法的改进 《电信交换》2006年第1期 ?无线通信 联合解调与Viterbi译码算法的改进 常萌,申敏 (重庆邮电学院通信学院重庆400065) 摘要:本文分析了在第三代移动通信系统中,将数据解调和卷积码译码结合 的译码方法,并与传统的Viterbi软判决译码和硬判决译码算法进行了比较.在 3GPP所规定使用的调制和编码方式下进行了仿真,结果表明,在不增加复杂度和 保持相同的误码率的条件下系统所需信噪比比Viterbi软判决译码降低1--2dB.本 文给出的方法也可推广到其它通信系统中. 关键词:8PSK联合判决Viterbi软判决Viterbi硬判决 一 ,前言 卷积码因其编码器简单,编码增益高,以及具有很强的纠错能力,在通信系统中得到 了广泛的应用.在第三代移动通信系统中,卷积码是信道编码方案之一.基于最大似然准 则的维特比算法(viterbi)是加性高斯白噪声(AWGN)信道下性能最佳的卷积译码算法, 也是常用的一种算法. Viterbi译码算法是由Viterbi于1967年提出的降低计算复杂度的算法.它是计算网格 图上在时刻t到达各个状态的路径和接收序列之间的相似度,或者说距离,去除不可能成 为最大似然选择对象的网格路径,即,如果有两条路径到达同一状态,则具有最佳度量的 路径被选中,称为留存路径.对所有状态都进行这样的选路操作,译码器不断在网格上深 入,通过去除可能性最小的路径实现判决,从而降低译码器的复杂性.Omura于1969年证 明了Viterbi算法实际上就是最大似然算法. 一 个典型的通信系统如图1所示: 图1典型通信系统模型 接收机将信号进行解调后输入到Viterbi译码器,译码器的输入信号有两类:一类为硬 一 34— 常萌,中敏:《联合解调与viterbi译码算法的改进》 判决信号,对应的Viterbi译码称为Viterbi硬判决译码;另一类为软判决解调,对应的 ?terbi译码称为Viterbi软判决译码.理论证明软判决输入的?terbi译码结果明显优于硬 判决输入的Viterbi译码[2l. 由于软判决信息的计算方法在高阶调制系统中比较复杂,采用近似方法又必将损失信 息,降低译码性能.因此本文将解调和译码结合,针对3GPP所规定的8PSK星座图和1/3 卷积编码器,对Viterbi译码器进行了改进,从而在不增加复杂度的条件下得到了比近似方 法更好的译码效果. 二,传统Viterbi译码算法 对于3GPP中所规定的8PSK高阶调制系统,在时刻k,8PSK星座图上的信号点用复 平面上的实数对{A^,B^}来表示,它是由3个比特{Uk,i},i=l,2,3映射得到的.8PSK信号 星座图如图2所示,映射为复平面上的8个点. Im 010110 ??y=x \66:6]/011\/cu ?\/'\//.\ c?/\c5001/\?\101 /.\/,1?L. 0oo.100 图28PSK星座图 对于硬判决解调,判断接收到的信号点与星座图上的哪个发送信号点之间的欧式距离 最小,该发送信号点即为解调器的输出.不难看出,硬判决解调的处理过程中损失了大量 的信息.这从后面的误码率曲线中也得到了验证. 对于软判决解调,使用对数似然比作为解调器的软判决输出.在高斯信道下,解调器 接收数据的同相支路和正交支路和可以表示为: = A^+ =+ (1) (2) 其中A和为发送信号,和Q是均值为0,方差为d的高斯噪声,且它们是相 互独立的.比特{,},i=1,2,3的对数似然比LLR(ithmofLikelih?dRatio) 定义为: 一 35— 常萌,中敏:<联合解调与Viterbi译码算法的改进> A(uk,i)=K薯,i=l'2,3(3) ^p—l ):舞 ~ — xp — {- N_ (x — k, 一 ai.)21 A(uK,i:1,2,3(4))=__—L—一,=,(4) exp{_2--~N(XkiIN,口0.)} 这里口1,i和口O,i分别表示当,f=1和,=0时A^在星座图上的值.同理可知,比特 +3的对数似然比只依赖于,且具有与(4)式类似的表达式,只需将墨换为,al,f和 ao ,i换为b1.i和60.f即可. 对于BPSK和QPSK调制的信号,分子和分母均为一项指数函数,所以式(4)可以大 大简化.对于8PSK等高阶调制,分子分母都是若干项指数函数的和,所以计算非常 复杂. uA(.f)一种较好的近似是(此时K=/2,P=3): A(uk,1)=墨 A(u^.f)=IA(uk,i-1)I+2,i=2,L,P一1 A(u^,户)=一I墨l+2户一 (5) 三,解调和译码联合判决的Viterbi算法 从上面的讨论中可知,解调无论是硬判决还是对数似然比软判决的近似方法都损失了 信息.所以,本文考虑将星座图和卷积码的网格图联合进行考察,以期在不增加复杂度的 情况下获得更大的编解码增益. 卷积码采用3GPP定义的(3,1,9)卷积码[?,如图3所示.此卷积码的编码速率为1/ 3,约束长度为9,卷积编码的初始状态位为全0,以后每输入一个数据符号则产生3个编 码符号(分支码字),最后输入8个0比特,将寄存器归零.具体的编码方式见[1]. _-1广一'1.rr_]rr__'1厂—1rr_—1r1.厂厂土土土 ,t,,t, ,', 'r1r1r1r L,,, ,工,,, 1 1r' 输出0 Go=557(octa1) 输出1 Gl=663(octa1) 输出2 G=7l1(octa1) 图3(3.1,9)卷积编码器 Viterbi译码算法的译码过程就是根据接收到的数据符号,按最大似然准则找到编码器 一 36— 常萌,申敏:《联合解调与Viterbi译码算法的改进》 在网格图上所走过的路径,网格图如图4: S(汁1) s(u2) +21 图4卷积编码器网格图 其中,i=0,2,4,L,2K一一2,K为约束长度,这里K为9.每一个符号时间间隔内有2s= 256种状态,可构成128个图4所示的蝶形图.S(i/2)和S(i/2+2k-2分别为本地编码器. 当输入为0和1时,状态S(i),s(i+1)往上和往下分支转移的转移状态,路径度量的运算可 以用下式表示: ,, fdo(i+1)+1d0(i+1)+5>5.)+5?,,' do(i)+d(0)d.(+1)+d{<dl0)+d(0)(6) (i/2+2K-1)=do(+1)+dll+)l>d5'+d5' .(+1)+5l+)l<5'十1)(7) 其中,d(.『)表示更新状态的路径度量,do()表示原状态为的路径度量,d5)表示输 入为i时,由状态出发接收码元与分支码字(或本地编码.)的分支度量,其计算方法见[2]. 即首先累加进入更新状态的两条路径的分支度量,然后比较两个分支度量,最后选出分支度 量最小的一条作为留存路径. 调制方式采用上述的8PSK星座图调制,3个比特映射为星座图上的一个点,如果将编 码器和调制器联合起来看,则3个信息比特经过编码调制后,映射为星座图上的3 个信号 点.解调和译码联合判决就是将接收到的星座图上的3个信号点进行联合解调判决得出3 个信息比特. 那么,联合判决意味着每接收到星座图上的i个信号点就译出i个信息比特.这只要 求每接收到一个信号点,就在网格图上进行1步路径搜索,然后进行比较,选取度量较小 的路径.编码器从零状态开始编码.经过信道后,接收到的复信号点序列为A0,A1,A2,K. 观察网格图上的两条路径,它们从初始状态S0经过2个状态转移分别到达S0状态和S128, 这两条路径对应的输入比特为0和1,输出比特序列为000和111,它们分别调制为8PSK星 座图上的两个信号点C0和C7(见图2).这两条路径对应的度量就是此时星座图上接收到的 信号点A0与C0和C7的欧式距离: 50)=d(A0,Co) )=d(Ao,C7) 一 37— 常萌,申敏:《联合解调与Viterbi译码算法的改进> 即从状态S0出发,输入为0和1时的两条路径的分支度量分别为星座图上接收到的信 号点A.和发送的信号点C0和C7之间的欧式距离.再看下一步网格图的变化,两条路径 从状态S0出发经过一次状态转移分别到达S0和Sl28,另两条路径从状态S~2sfl5发经过一 次状态转移分别到达S64和Sl93,此时对应的输出比特序列分别为101和110,它 们分别调 制为8PSK星座图上的信号点C5和C6(见图2).这两条路径对应的分支度量就是星座图 匕接收到的信号点A与C5和C6的欧式距离: i箍=d(Al,C5) = d(Al,C6) 因此,从状态S0出发,经过两步状态转移对应四条路径的度量为: d(0)=d(A0,C0)+d(Al,Co) d(64)=d(Ao,C7)+d(At,Cs) d(128)=d(Ao,Co)+d(Al,C7) d(193)=d(A0,C7)+d(Al,C6) 依此类推,与传统的Viterbi译码类似,将进入每一状态的所有分支度量,和同这些分 支相连的前一时刻的留存路径的度量相加,得到了此时刻进入每一状态的分支度量,选取 加以存储并删去其它所有路径,因此留存路径延长了一个分最小的作为留选路径, 支.每 个状态作为其中?条路径的终点,并且每条留存路径都有自己的度量.随着以后每一时间 间隔中新信号的接收,在网格图中的每个状态都要更新自己的度量和留存路径. 不难看出,这种将解调和译码联合进行的Viterbi算法每接收到一个信号点,在网格图 上只需要进行1步搜索,对应的计算一次度量,译出1个比特,需要计算的路径度量数目 为256.而传统的Viterbi算法(包括软判决和硬判决)也是每次进行1步搜索,对应的计 算一次度量,译出1个比特,需要计算的路径数目度量也为256.因此,从搜索的路径数目 来看,二者是一样的.但是,这种联合判决算法没有损失任何信息.因此,它应该优于上 面介绍的先近似软判决解调(损失了信息),再进行viterbi译码的算法. 四,计算机仿真结果 为验证该联合解调和译码的Viterbi算法的有效性,在ccss平台上搭建仿真链路.采用 3GPP中规定的(3,1,9)卷积编码器和8PSK调制方式.r 为了进行比较,这里对Viterbi硬判决,Viterbi软判决和解调与译码联合判决3种算法 进行了测试.在高斯信道下的误码率曲线见图5.其中横坐标是信号平均功率和噪声功率的 比值().r 从图中可以看出.软判决译码性能要比硬判决性能好2--3dB,而解调和译码联合判决 算法又比软判决译码算法性能要好1--2dB左右. 在算法复杂度方面,3种算法需要计算的路径度量数和需要选择的路径数是相同的,但 一 38— 常萌,申敏:《联合解调与Viterbi译码算法的改进》 是在计算路径度量方面有所不同,对于硬判决译码,这个度量标准是Hamming距离,计算 较为简单;对于软判决译码,度量标准是解调器输出的对数似然比U(近似);对于解调 和译码联合判决,度量标准是欧式距离,计算相对复杂一些. 高斯倍道下联合8PSK~调各种Vi~bi算法性能比较 2.E.0l 1.E.0l 5.E-02 2.E.02 5.E.03 2.E-03 1.E.03 5.B04 2.E.04 1.E.04 5.E.05 2.B05 1.E-05 5.B06 7.4 ? 苦 l 塞 ::: .=. :'.'... iliIlI悖l-I--?---?--? ??---????--- ???-?-?-?--- -----?----?- iliIiI?Illl ??----?-?--- ---?i?i??ii- IIIIIIIIIIIlii-i?_???iii i-iii--???ii ?l?IIIIIII-----???---- ----?-?----? ---??-?---?? !!!!!!,l!!!! --?--?------ --????-…-? ---????-?--- ___ I = : - _ I = : - , l = : - _____囊I___??______ I - - - = : _ _ : : - I??? 葛_, ?? I = : I = : - I = : - IlIlllIIIII =:====;=== ? ! } i !! :: -- :: 0 sNR 图5高斯信道下基带系统中3种算法的误码率曲线图 4 五,结论 从上面的仿真结果来看,解调和译码联合判决算法要优于viterbi(近似)软判决算法, 并且复杂度没有太大提高.解调和译码联合判决算法的实现依赖于特定的解调器,也就是 说,不同的解调器需要对联合判决算法的一些细节进行修改.该方法还可以用于更高阶的 调制系统,如O.AM调制. [1] [2] [3] [4] [5] [6] 参考文献 3GS25.222:"Multiplexingandchanndcoding(11]D)" JohnG.Proa~着,张力军等译.数字通信(第四版),电子工业出版社,2003年,北京[M] A.J.Viterbi,"ErrorboundsforconvolutioneodesandanasymptoticallyoptimumdecodingaI 一 rithm"IEEETram.InformationTheory.vo1.IT一13,PP.260—269,1967 C.Y.HuangandH.Chalmers."Viterbidecoderandperformanceevaluationformobilesatellit e fadingchannels"COMSATCorFa'ationClarksbm'g,Maryland20871—9475 JimK.Omura"OntheViterbiDectxtingAlgorithm",StanfordResearchInst.MenloPark,Cal if. 94025 HenryHendrix,ViterbiDecodingTechniquesintheTMS320C54xFamily,SPRA071,June1 996A 一 39一 I_,--I-=--,??=-.- ?-.蕾--._-?-.--.--?.-----?,一,???l3_.,?-S,一.--? --?=---I...---?=-?. _I=..---?-??---?=--? ??=?.-I薯---I=:-. --?-?-?-??------?.-??- --?-...-I?=.---_....- ?=:_-I=_--I=:.- .I--?-?=--l=---I=----?=-----_...-- ..一?==:..?=::lI?===.. 一.I_f.^_十I.+.^萃—十}..—霹x.I.1. ---????-?--?--??---?-------??---- ,?-jJJ?I,?,???I{,??_,?J? 梓慕啦聋筮