第五章 卷积码的译码算法.docx

第五章卷积码的译码算法卷枳编码器自身具有网格结构，胫于此结构我们给出两种洋码算法：Viterbi译码算法和BeJR详码算法。葩于某种准则，这两种算法都是最优的,1967年，Vite1.bi提出了卷积码的Viterbi译码算法，后来Omura证明Viterbi译码算法等效于在加权图中寻找最优路役同鹿的一个动态规划(DynamicProgramming)解袂方案，由后，Fortiey证明它实际上是最大似然(M1.Maximum1.ike1.ihood)详码算法，即译码器选择输出的码字通常使接收序列的条件概率最大化.BCJR算法是1974年提出的，它实际上是最大后验假率(MAP,MaximumAPosterioripn>babi1.i<y)译码算法。这两种算法的最优化目标略有不同：在MAP译码算法中，信息比特错误概率是最小的，而在M1.洋码算法中，码字错误微率是城小的,但两种洋码券法的性能在本吸上是相同的.由于Vitcrbi宛法实现更简单，囚此在实际应用比较广泛，但在迭代洋码应用中，例如逼近Shannon限的TUrbO码,常使用BCJRg法.另外，在迭代课码应用中，还有一种Vitcibi究法的变种：软输出Vitcrhi算法(SOVA,Soft-OutputVitcrbiA1.gorithm),它是H;WCnaUCr和HOChCr在1989年提出的.5.1Viterbi算法为了理解Viieibi详码算法，我们需要将编码器状态图按时间展开(因为状态图不能反唉出时间变化情况),即在每个时间单元用一个分隔开的状态图来衣示,例如(3,1.2)非系统前惯编码落.其生成城即为：G(D)=+D1+0：1.+D÷D2J<5.1>（八）01234567时间单元(b)IS5.1(a>G.1.2)编码器(b>网格图(h=5)假定信息序列长度为h=5,则刈格图包含有h+m+1=8个时间单元,JJO¾h+m-7来标识，如图5.1(b)所示，超设编码器总是从全。态SO开始，又I可到全0态，前m=2个时间单元对应于编码器开始从S1,“启程”，以后m=2个时间单元对应于向X“返航”。从图中我们也可以看到，在前m个时间单元或以后m个时间单元，并不是所有状态都会出现,但在网格图的中央部分，在每个时间单元都会包含所有状态,且在年个状态都有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*个不同路径通过网格图，对应蓿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=(v<1.V,.va,.i),r=(,r,.rf,.t),译码器对接收到的序列r进行处理.得到V的估计S.在禹敢无记忆信道情况下.最大似然详码据是按照我大化对数似然函数IOgArIV)作为选择&的准则“因为对于DMC*(rv)*11,(vJ-,(IvJ<52>两边取对数后为：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(r"vJ"£"化IVj<5.5>对于接收序列r.Viterbi算法就是通过网格图找到具有G大度量的路径，即扑大似然路径(码字).在每付悯单元的衽个状态，都增加！个分支度量到以前存储的路径度显中函)：然后对进入埒个状态的所有21个路径度量:进行比较(比)，选择具有最大度城的路径(逸),最后存储每个状态的幸存路径及其度1出Vikrbi算法，StepI:在1.=m时间单元开始，计算进入每个状态的单个路径的部分度推，存储每个状态的路径(幸存)及其度RbStep2:1.÷1.+3对进入短个状态的所有2t个路径计算部分度量，并加上前一时间单元的度量，对于每个状态，比较进入该状态的所有2'个路径底中，选择具有最大度量的路径.存储其度量,并删掉其他路径.Step3:如果tvh+m.返回StCP2：否则，就停止.VUerbi算法的班本计算“加、比、选”体现在step2.注；实际工程中，在傩个状态存储(在SICPI和S1.eP2)的是对应于幸存路径的信息序列，而不是幸存路径自身，这样当算法结束时，就无需再通过估计码字&来恢笑信息序列而，从时间的元m到h.有2”个幸存路径,每个状态(共有2'个状态)一个。随后，幸存路径数就会变少因为当潟码潺回到全0态时.状态数就会变少.最后,在时间单元h+m就只有一个状态(即全。态),因此,也就只有一个幸存路径了，究法中止.定叫！S.I：在ViIerbi算法中最后的幸存路径&是最大似然路径，即(rv")WrIv),forvV(5.6)从实现的角度看，用正整数度量来表示要比用实际的比特度瑜表示更方便，比特度埴MgIVJ=IO亿旧)可用口1型打小，,)+<%代耕,其中5是任意实数,。是任意正实数。Ur证明，如果路径V报大化Wr、厂E：W(*)=,0(r,v1.),则它也最大化Q10gP(r1.Vf)+CJ因此可以使用修正的度fit且不影响V,tcrb算法的性能.如果选择5使最小度此为。,则。可选择为使所有度肽近似为整数.这样,由于用整数来近似灰示度htVitcrbi灯法的性能变成了次最优算法，但通过选择G和6可使得这种性能降低非常小.例5.1：对千二输入、4-arj输出的DMC信道下的Vikrbi"法.输入、4ary输出的DMC如图5,2所示。该信道的比特度城如图53(a所示(按照底为IO的对数计算)，选择Ci=1.s=173,得到整数度量表如图53(b)所示。图5.2二输入、4-ary输出DMC信道模型O1O2IzIi0-0.4-0.52-0.7-1.01-1.00.70.520.4O1O2Ii0IO8S0105KIO（八）(b)图S.3度量表假设图5.1中的一个码字在这样的信道中传输，接收到的序列为：r=(1.1.1.1.1.1.Q2,1.1.0oIiIiIi.0h0,A1mIi(Mi)(5.7)对该序列进行Viteibi洋码如图5.4所示。r=(11IjOi>I1.IIo2,11110(111)1101.a>1.dj,IaOiIi)图S.4DMC信道卜的Viterbi算法每个状态上的数字表示幸存路径的度电，另一个路径就将被册除(绿线部分)。这样最后的码字(红线部分的输出)判决为：V=(II1.010.110.011.0.(XX),O(JO)(5.8)它对应的输入序列为6=(I1000),注意：同格图中最后的m=2个分支是清空寄存器的，不能算作为输入信息序列，在BSc信道情况下,转移概率为p<1.2.接收序列r是2ry输出的，此时对数似然函数为：k)g*(r)=(r.v)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算法假设接收到的序列为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信道，解调署输出不进行量化，即二值输入、连续输出信道.假设信道输入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=-T"v3'+v,n-An1.1.VrtFV1.NF(5.13)=r(2*+h*-1.n-咦此斗”条=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,I»0=rf.vf,/=0,1,，NT，Vi1.erhiIZ法就是要找到与接收序列相关值最大的那条mt(码字。对于连续输出AWGN信道，最大化刖数似然函数等效为找到与接收序列r欧拉距禹最近的那个码字V.而在BSC信道，最大化对数似然函数等效力找到与接收序列r汉明距离最近的那个码字V前面也讨论了，软解调器判决<Q>2)相比硬判决(Q=2)公有性能