《第五章 卷积码的译码算法.docx》由会员分享,可在线阅读,更多相关《第五章 卷积码的译码算法.docx(37页珍藏版)》请在优知文库上搜索。
1、第五章卷积码的译码算法卷枳编码器自身具有网格结构,胫于此结构我们给出两种洋码算法:Viterbi译码算法和BeJR详码算法。葩于某种准则,这两种算法都是最优的,1967年,Vite1.bi提出了卷积码的Viterbi译码算法,后来Omura证明Viterbi译码算法等效于在加权图中寻找最优路役同鹿的一个动态规划(DynamicProgramming)解袂方案,由后,Fortiey证明它实际上是最大似然(M1.Maximum1.ike1.ihood)详码算法,即译码器选择输出的码字通常使接收序列的条件概率最大化.BCJR算法是1974年提出的,它实际上是最大后验假率(MAP,MaximumAPo
2、sterioripnbabi1.iy)译码算法。这两种算法的最优化目标略有不同:在MAP译码算法中,信息比特错误概率是最小的,而在M1.洋码算法中,码字错误微率是城小的,但两种洋码券法的性能在本吸上是相同的.由于Vitcrbi宛法实现更简单,囚此在实际应用比较广泛,但在迭代洋码应用中,例如逼近Shannon限的TUrbO码,常使用BCJRg法.另外,在迭代课码应用中,还有一种Vitcibi究法的变种:软输出Vitcrhi算法(SOVA,Soft-OutputVitcrbiA1.gorithm),它是H;WCnaUCr和HOChCr在1989年提出的.5.1Viterbi算法为了理解Viieib
3、i详码算法,我们需要将编码器状态图按时间展开(因为状态图不能反唉出时间变化情况),即在每个时间单元用一个分隔开的状态图来衣示,例如(3,1.2)非系统前惯编码落.其生成城即为:G(D)=+D1+0:1.+DD2J(八)01234567时间单元(b)IS5.1(aG.1.2)编码器(b网格图(h=5)假定信息序列长度为h=5,则刈格图包含有h+m+1=8个时间单元,JJOh+m-7来标识,如图5.1(b)所示,超设编码器总是从全。态SO开始,又I可到全0态,前m=2个时间单元对应于编码器开始从S1,“启程”,以后m=2个时间单元对应于向X“返航”。从图中我们也可以看到,在前m个时间单元或以后m个
4、时间单元,并不是所有状态都会出现,但在网格图的中央部分,在每个时间单元都会包含所有状态,且在年个状态都有2=2个分支离开和到达.离开每个状态的卜.而分支表示输入比特为I(即必=1.i表示第i个时间单元.下面的分支表示输入比特为0,每个分支的怆出Whn个比特组成,共有2*=32个码字,集个码字都可用网格图中的唯路径表示,码字长度N=n(h+m)=21.例如当信息序列为U=(I1.1.OI)时,对应的码字如图5.1b中红线所示,V=(III.010.001.110.100.101.011).在一般的n,k.v)编码器情况下,信息序列长度K*=kh,离开和进入傩个状态都有外个分支,有2*个不同路径通
5、过网格图,对应蓿2尸个码字,17设长度K*=M的俏息序列u=(u0,u1.U*“祓然码成长度为N=Mh+m)m字V=(v1),v,.va.m.,),在经过一个二进制输入、Qary输出的离放无记忆信道(DMC,Discretememory1.essChanne1.)后,接收序列为r=(1.,r。也可表示为;u=(m).m,.ma.i),V=(v1.V,.va,.i),r=(,r,.rf,.t),译码器对接收到的序列r进行处理.得到V的估计S.在禹敢无记忆信道情况下.最大似然详码据是按照我大化对数似然函数IOgArIV)作为选择&的准则“因为对于DMC*(rv)*11,(vJ-,(IvJ两边取对数
6、后为:hgP(rv)-Zog,(v,)-kgP(r1.v1.)(53)其中P化”是信道转移概率,当所有码字等概时,这是个以小错误概率译码准则。对数似然函数1.ogrIv).用M(I1.V)表示.称为路径度量(pathmetric):1.ogP(r,V,),称为分支度值(branchmetric),用M(IjVj)发示:1.ogPS1.以称为比特度盘(bimetric),用M匕旧)表示,这样(53)式可写为:(rv)Yt.W(vj三.V(jvJ(5.4)0*-A如果我们只考虑前t个分支.则部分路径度盘可表示为:/(rV)V(rvJ化IVj对于接收序列r.Viterbi算法就是通过网格图找到具有G
7、大度量的路径,即扑大似然路径(码字).在每付悯单元的衽个状态,都增加!个分支度量到以前存储的路径度显中函):然后对进入埒个状态的所有21个路径度量:进行比较(比),选择具有最大度城的路径(逸),最后存储每个状态的幸存路径及其度1出Vikrbi算法,StepI:在1.=m时间单元开始,计算进入每个状态的单个路径的部分度推,存储每个状态的路径(幸存)及其度RbStep2:1.1.+3对进入短个状态的所有2t个路径计算部分度量,并加上前一时间单元的度量,对于每个状态,比较进入该状态的所有2个路径底中,选择具有最大度量的路径.存储其度量,并删掉其他路径.Step3:如果tvh+m.返回StCP2:否则
8、,就停止.VUerbi算法的班本计算“加、比、选”体现在step2.注;实际工程中,在傩个状态存储(在SICPI和S1.eP2)的是对应于幸存路径的信息序列,而不是幸存路径自身,这样当算法结束时,就无需再通过估计码字&来恢笑信息序列而,从时间的元m到h.有2”个幸存路径,每个状态(共有2个状态)一个。随后,幸存路径数就会变少因为当潟码潺回到全0态时.状态数就会变少.最后,在时间单元h+m就只有一个状态(即全。态),因此,也就只有一个幸存路径了,究法中止.定叫!S.I:在ViIerbi算法中最后的幸存路径&是最大似然路径,即(rv)WrIv),forvV(5.6)从实现的角度看,用正整数度量来表
9、示要比用实际的比特度瑜表示更方便,比特度埴MgIVJ=IO亿旧)可用口1型打小,,)+I1.IIo2,11110(111)1101.a1.dj,IaOiIi)图S.4DMC信道卜的Viterbi算法每个状态上的数字表示幸存路径的度电,另一个路径就将被册除(绿线部分)。这样最后的码字(红线部分的输出)判决为:V=(II1.010.110.011.0.(XX),O(JO)(5.8)它对应的输入序列为6=(I1000),注意:同格图中最后的m=2个分支是清空寄存器的,不能算作为输入信息序列,在BSc信道情况下,转移概率为p1.2.接收序列r是2ry输出的,此时对数似然函数为:k)g*(r)=(r.v
10、)1.og-+,VIog(1.-p)I-P其中小r.V)是r和V之间的Hammmg距禹.It1.T1.og,0.且MOg(I河所有VI-P来说椰是一个常数,因此最大似然译码max1.ogP(rV)就是帔小化Hamming距窗(min(r.V).(r,v)-NdMeJ一5.10)因此,当我们将VnCrbi算法应用到BSC信道时,因也Vj成为分支度量,d(%)为比特度量,该算法就是寻找具有G小度求的路径,即与r汉明距离地近的路径。该除法运算仍然相同,只是用Hammmg距黑代替了似然函数作为度量,在每个状态的幸存路径是具有母小度Iik的路径。例5.2:BSC信道卜的Viterbi算法假设接收到的序列
11、为r=(IIO,IIO,IIO.111.010,101,101)5.10)r(110.110.110.i1.1.010.IUI.101)图5.5BSC信道下的VitCrbi算法域后的码字判决为:Q=(111.010.110.011.111.101,011)5.11)它所对应的信息序列为山=(110()1).以后的幸存路径收此伯为7,表示接收序列和判决码字之间有.7个对应位况不同,而其他路径所对应的码字和接收序列之间的位置不同数目都要大干7.在上图中紫色对应的线表示两条路径度量值相同,此时随便选其中-条就OK了。现在考虑二进制输入的AWGN信道,解调署输出不进行量化,即二值输入、连续输出信道.假
12、设信道输入O和1用BPSK信号士、二CoM2尸/“/)表示,其中映射关系1.J-E,0-JTr.考虑码字V=(vi,.vv.1),按照映射美系1一+1.f1.O-*-1.进行取值.即士归一化(用叵进行归一化的接收序列r=(应r,.r*)是实际值(未玳化.这样在给定发送比特丫:接收到n的条件概率密度函数(PdQ为;W很d中:.(5.12)其中NV,是噪声的归一化单边PSd.如果信道是无记忆的.发送码字为V,接收序列为r的似然函数为:V-I.W(rv)-1.nXrv)-np(firj-1.np(vjJSFJVF=-Tv3+v,n-An1.1.VrtFV1.NF(5.13)=r(2*+h*-1.n-
13、咦此斗”条=C1.(r.V)+C2其中G=;/乂和。2=-|5/乂)(|/-、)一(八,2加(,”、,):是常数.独立于码字V,rV我示接收向最r和码字V的内积(相关),由于G是正数,簸大化r.v的网格路径码字)同样也最大化对数似然函数1.nX门V),为应于码字V的路径虔/为W(rIV)=r.V,分支度量为1W(r,v,)=r1.v1.,I=0,1.,+-1,比特度显为Mr,I0=rf.vf,/=0,1,,NT,Vi1.erhiIZ法就是要找到与接收序列相关值最大的那条mt(码字。对于连续输出AWGN信道,最大化刖数似然函数等效为找到与接收序列r欧拉距禹最近的那个码字V.而在BSC信道,最大化对数似然函数等效力找到与接收序列r汉明距离最近的那个码字V前面也讨论了,软解调器判决2)相比硬判决(Q=2)公有性能