第五章 卷积码的译码算法.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)公有性能的提高，如果将前面例子中的Oi和6都变为0,1.和I；都变为1，则软判决的DMC就变为硬判决BSC信道(转移概率p=0.3),但经过Viterbi译码后，产生的信息序列不同，对软判决情况(Q=4),信息序列U=(I1.(X)(B,最后度Ifttf1.是139：俄判决情况(Q=2),0.序列U=(I1.(X)I),而这样的路径在四怆出信道中的度hi伯为135,很显然在软判决情况下并不是殿大似然路径，因为在现判决情况下它掩靛了软输出的区别.即时疑判决洋码器来说，Oi和我都一样,再多的软信息也没B1.5.2卷积码的性能界我们首先在BSC信道中对特定码字分析最大似然（Vitert>i）译码的性能，然后再推广到般伯道.假设发送式（5.1）所示（3.1.2）编码器中的全O码字，该编码器的IOWEF为:4(W.V.I)三x'wCI-XHKRX1A)=X'H1I+H1.(I*X21.A÷A,21.2)<514)"X'H1,d'+*杂N+V(""+Hu)即该码包含一个曳限为7的码字，它经过3个分支、由重1为I的信息序列产生的，一个常量为8的玛字，它经过4个分支、由取量为2的信息序列产生的，d如果全0路径（正确路径在t时刻与竞争路径（错误路径）的火拼中第一次被州除,就产生事件错误（第一次），如图56所示.时间一正确路径VH5.6*t时刻出现第一次事件错误错误路径必然是在前面从全。态分开、现在又首次仲1到全0态的某个路径，即它必然是码字WEFA（X）中枚举的个路径.假设它是条奴为7的那个路径,则正确路径和错误路径之间有7位比特不同,如果接收序列与错误路役在这7个位置处有不少于4个是相同的（即在这7个位置至少有4个1，就会发生错误任件。如果BsC的转移概率为p,则这个概率为：(5.15)?=尸7个位置至少有4个""|=c>假设重城为8的路径是错误路径，发生第一次事件错误的概率为:MW(S喏0"(j尸(5.16)因为如果正确路径和错误路径的度量值相同，则发生事件错误的概率为1.2o通常，如果错误路役的垂疑为d,则发生首次错误事件的概率为：;，("“二d是奇数Pj=I(5.17TQV"t步总楣数这样,在t时刻发生首次事件错误的概率号(丘，)可用一个界来表示，即为所有这些路径的惜误概率之和,如果符超过，个分支的错误路径也包括在内则这个界(较松)可表示为：P,(E,)<ZAjP<5.8)，“一其中A1.是垂量为d的码字数目(即码字WEFA(X)中重量为d的那一项的因子)。由于这个界与无关(在所有时刻都成立)，上式可写为：<5.I9）P,<ZW对上式还可进一步简化，当d是奇数时,<朗“八5羽（5.20）<,1(-pr=2，/”(1-“”州问样可证明,当d砧偶数时.仍会得到相同的结果.因此，P1.(E)<NAUKI-P7<5.21)对于卷积码，其码字WEF4V)=EyAdM，有,(GJX)Qr<52，)最后的译码路径可以和正确路径分开和合并多次即它可能会包含多个错设事件,如图5.7所示。在发生一次或多次枯误事件后,在全。态进行比较的两条路径都是常误路径，因为每个路径都至少包含一个以前的错误事件.错误路径正礴路径图5.7多个错设事件这样，在t时刻发生错误事件的概率P（E,r）PJE/）,由于它在所有时刻都成立，W此可写为：&£）<£4<4诉匚7</（现.烟；<522）由于P很小，这个界主要是由其第一项决定的，即自由距离顶，因此上式可近似为:P（E）2p（1.-pT"'52J*'2（5.23）例53：对于式（S.I）所示的（3,1,2）编码器，加=7,A1.=1.当P=10'1Bt.有：P（E）XE产=1.28XIOT对式（5.22）衣示的事件错误概率界进行惚改，就可寿到比特错误概率Pfi（K）的界.每个事件播送概率都会造成多个信息比特错误（错误路径的非0比特数），因此，如果每个事件倍以概率项先用重量为d的路径上的非0信息比特数进行加权（注意：理盘为d的路径可能不止一条），我们就可得到信息比特错误数的界,这个界再除以k（每个时间单元的信息比特数）,就可得到的界,为：虫£）<BFj（5.24）其中科是所有重录为d的路径上的非0信息比特总数除以每个时间单元的信息比特数k（即为比特WEF8*）=E,Bx中重玻为d的那一项的因子）.这样利用式（5.20）和式（5.24,可得:阜£）<tB<4口麻7'WY儿（525）同样，当P很小时，上式近似为：<5.26),J-）哺2加匚旷«%*例5.4：对于式<5.1）所示的（3.1.2编码器,加=1.综=I-','>=107时，有:P（E）2V2=1.28×IOs.与事件错误概率楣问.这就是说，当P很小时,1可能出错的事件是译码成重用为7的路径，因此引起一个信息比特错误.如果BSC是从AWGN信道、BPSK网制、最优相干检测、2-ary输出量化（便判决推导的，则P（E）B2J?/ME（5.28）1.由于每比特能技以士工.R是编码速率，这样上式改写为（对于较大EN）：*R(5.29)PAE)«%2'10/'*»3"叫(WiIhcoding)如果不使用编码，即R=1,E=E1,.BSC粒移概率P是误比特率尸/£）：W"(便卜"M(WithoutCodGg)（5.30）比较式（5.29）和式（5.30）,我们可看刎,对于给定的fiN>.指数部分相差一个因子RdZI2,由于当区/M较大时.指数项占主导地位,这个因子dB值）称为渐近编码增益(My11t<iccodinggain)Y(硬判决情况下)：注重:当SNR变小时，编码增益也变小。实际上，如果SNR(EN")降低到编码速率R大于信道容域C的那个点时，可挣通信已经不可能了，此时未编码系统反而会有更好的性能.对于二伯怆入、Qary输出的DMC信道.性能界为：P(E)<A(X)x.ai(5.32a)P,(E)<B(X)x.1.,t<5.32b)nj其中Q*X7P(0k1.)是信道转移概率的函数称为BhaUMharyya参数，当Q=2时.Da=2i-p),就是BSC信道.在二值脓入、连续输出的AWGN信遒情况下，暇设发送码字是全0码字v=(-i.-1.-I)映射关系I-+1和0-1】，现在来计算正确路径V在I时刻苜次被册除的概率Pj,其中V是在与错误路径v'(与V的Hamming距离是d)的PK中“牺牲”的.因为ViteIbi算法选择具有最大似然函数值的路径.在t时刻首次事件错误1«率为：C=PrA(r1.)>W(rv1.)J工时卜小卜叫=1.>rr4r*1>0)=内r,v；.方匕>0(5.33)IM1.XJ(w4.川N>。：Im，J其中rv表示！和V在前f个分支的内枳.很晶然.上式中只有d个位置不为0.假设I=1.2.”表示这些位里，因为寸v；=+1,I；=-1,式(5.33可表示为：<554)C-Pr(H(-)>-Prj2j>O>Prr;I/上式役示如果接攻伯元的伯在1.;HV1的d个位过上的累积和为正数,就会在t时刻发生首次错误事件.由于信道是无记忆的，发送码字v=(-1.-1.,-1),pt£/是d个独立高斯随机变盘的和,每个。是均值为一1、方差为NM2£,的高斯陆机变St(见式5.12),这样P是均值为一比方差为N"2E的高斯随机变疥，则式(534)可写为:iSO4展)即(535)进行变量代换J(/，,/上式变为:%2J"-G.e_W7'诉Ke(5.36)一。糕H停)将式(536)代入式(5.22)和式(5.25)的界，得到：值输入、连续输出AWGN信道下的事件错以概率和比特错误概率的界.为：P(GV4。单£)<ZB,Q如果用史松的界0X)Sge-%<G、x0.可得:,*,(fc><""=/(刈XF3八)(5.38a)一(£)<必、'=8(')Xyi,(538b)-一比较式(5.38和式(5.32),我们可知，对于连续输出AwGN信道，Bhanacharyya数Da=exp(-RE)NJ.当&/乂较大时，在比特WEF中的第一项决定了式(5.38b)的界，匕(E)近似为：P,(E)BqfMN(5.39)此时渐近编码增益(软判决为：YtIOIog1O(/?<w)dB(5.40>比较式(5.39).(5.40)和武(5.29)、(531),我们可看到软判决情况比硬判决情况多出3dB增益，这也就竟味着为了得到相同的错误概率，在BSC信道上传输的发射机的发射功率是AWGN信道下发射功率的2倍.(注：前面的分析是基于对特定码字的性能界.且只当片/N“较大时才有效，当用随机码进行分析H.SNR较小时，津码增益只有2dB左右，所以较判决相对硬判决有23UB的增益，代价是译码的笑杂度增加)。这个界通过下面的不等式还可以更紧.(?(E)MQ(Yr)e1.,C->(),z0)(5.41)修卜Qg-WW,.欣4号卷现在定义函数"x)=0(<5.43)<5.42)可写为：小乂卡卜号(华)最后.将式(5.44)代入式<522)和式(5.25)的界.道下的'H件错误概率和比特错误概率的界，为：(5.42)褥到二值输入、连续输出AWGN信V=2d,RE,!Nu,=2(d-d.)REJN0,式(5.36)可写为:6(d,RE牛(£)<M-E1.f,Z-0/如8/牛广r(笔加刈一我们从式(5.45)表示的紧界和式(5.38表示的界可知.该因子只依极于码字的自由距.(5.45a)(5.4)紧界有一个因子/(攵"上)例55计算AWGN信道的误比特率界(546)1.-2Yrz-2A,2X4Y=X'2XW-考虑式(Sj)所示<3.1.2)解超器，其IOWEFA(W.X,1.)见式614),其比特WEF可计算为：”Aax,M(-.<-.vr)1.aw可知.一码的自由叫Wr=7.利用上式可直接得到(5.38b)和(5.45b所示的界.如图5.8所示.图5.8卷积码的性能界从上图我们可看出.<5.45b)表示的紧界和itcrbi译码仿真非常拟合(SNRMdB),而式(5.38b)表示的界一H追随着仿真曲线,但不是很推近。该码的渐近编码增益(软判决为：Y=IO1.og10()=IO1.og1.1.1.(7/3)=3.68JB(5.47>这是与未编码BPSK系统性能相比的增益,从上图我们可以看出这一点.从上面的讨论我们可知.P(E)和Ph(E)RG%的增加指数下降,瓯%.和B,.的增加线性增加,因此首要准则是最大化自由距禹4中第二个准则是最小化儿,“和.通常来说,在高SNR时，%r起决定作用,在低SNR时.Aq和四&,起决定作用.表5.1列出了一些最优码：表5.1.（八）R=1/4的浅积码VG«。g,"g，：d*Y(dB)III33611.7625577IO13.983131315171325.124252733371646.025455367771836.5361171271551712026.9972573113373552217.40853357564771124I7.78911731325146717512738.29衣5.1.(b)R=1/3的卷积码VG,n,8a,VY(dB)11335I2.222577824.263131517IO35.2242533371256.0254753751316.3661171271551536.99722533136716I7.2785756237271817.7891167137515452038.23IO2325273137472278.65H57456471755324139.031223713725147332459.03表5.1.(c)R=1/2的卷积码VG,u,8"*dYidB)131311.76257513.9831317614.7742731725.4455375816.026117155IOI1.6.997247371IOI6.99856175312I1.7.789113115371217.78102473321714148.45H4325674715148.7512106271676516149.031327251373631619Q35.3软输出Viterbi算法（SOVA）5.3.1 SOVA基本原理对于卷枳码，Viierbi算法是业优的最大似然许码方法，译码输出为卷枳码的最优估计序列.但对于阿干级联卷积眄的TUrbo码而言传统的Viterb1.算法存在两个缺陷：首先,一个分fit译码器输出中存在的突发错误会影响另一个分量译码器的译码性能,从而使级联码的性能下降，其次，无论是软判决Vitcrbi豫法还是现判决Vitcrbi算法，共洋玛输出均为硬判决信若一个分房码果用Viterbi算法译码，则另一个分从洋码器只能以硬判决结果作为输入，无法实现软判决课码，从而性能会有所下降.因此,如果VitCrt>i译码港能够提供软侑息物出.则可以弥补上述两个缺陷,并且可以通过在分及洋码器之间软信息的交换使级联码的性能大大提高。为此，需要在传统的ViIerbi算法上iS行修正，使之提供软信息输出，相应的算法就称为软输出ViIetbi算法，记做SoVA(SoftoiHpuiVherbiAIgoriiI)In)o下面通过具体的实例来说明软怆出VitCrbi算法的软信息的生成.图5.9给出了在个4状态网格图实现SOVA译码的计算输出较信息的示意图，«®)j>(>(三)G)®yM(Sj)S"®Si®Q'0y'*Mds,)(Sy®.®检苍,0MHHNMt-It图5.9实现竞争路径和幸存路径可捷性估计的格图图5.9中的实线表示t时刻状态结点S“处的幸存路径(这里假设为最终的最大似然路径的一部分),虚线表示t时刻状态结点SU处的竞争路径.为使图看上去满是一些.就没有画出其他结点的幸存路径和竞争路径.标记，代&t时刻的状态I,标记(0,1)表示每个分支路径对应的二元判决tf1.,当前结点时刻的幸存路径对应的累计度员值记为Mda,).当前结点时刻的优争路钱对应的米计僮戊伯记为W,(&；).指定结点S.1的幸存路径的可能性度疑值,(SJ为上述两个累计度地值之差的绝对值.即,(S,)=v(51.i)-Mc(51j),这个俏越大,幸存路径是最大似然路径的可能性就越大,判决也越可就*这里假设幸存路径累计度量总是优F竞争路径累计度;匕后面就将A,(，)称为I时刻的SOVA详码输出的可常性侑.H然.根据,(SJ=IM(S3-计算得到的值可以作为先险信以辅助下一个分量译码器进行译码判决.此外，为降低发杂性,只需要计算Ai大似然幸存路径的可肱性伯(这里假设己知)，而其他幸存路径没有必要计算可皴性值,随着译码的进行,这些路径逐个被丢弃了.为说明可拳性的概忿，下面给出两个例子。在这些例子中，ViWbi整法选择累计废玳做小的路径作为幸存路径.在第一个例子中，状态结点SU处幸存路径累计股也值为MS(SU)=50,竞争路行累计ffttfiH(S1J=KX),选择这个幸存路径时相应的可靠性值为,(S1)=|v(S1.r)-Mf.(S,1.)=5()-I()C=50在第二个例子中,状态结点Su处幸存路径累计度量值M(SJ=50：竞争路径累计度HUiIWc(S1.1.)=75,选和这个幸存路径时相应的可考性值为,(S1)=|v(51,1)-Mc(51.f)=5O-75=25尽管在这两个例子中幸存路径的累计度量值相同.但幸存路径的可靠程度并不同.根据可靠性度量值的大小Ur以利定：第一个例子中提供的幸存路径比第二个例子中提供的幸存路径更可信-些.图5.10说明了使用幸存路径累汁度M值与竞争路径祟计度量值之差的绝对值作为UJ抑性时的示意图.M(SU7)=IOM(Sg)=50Mc(Sg)=20MC(SU=75AMSJ=IOAt区)=25图5.10不同幸存路径和竞争路径外部信尽的比较在图5.10中，状态的幸存路径和竞争路径在1-5时刻的状态结点SUS处开始分底，在1-2和14时刻幸存路径和竞争路径得到的比特判决值完全相反，如图中红色所示.为方便说明,假设在状态结点S1,1处竞毋路径依计度量低和幸存路轻累计度量值相等,且fv(5u)=Mc(S1.t)=KX).这意味着幸存路径和优争路径成为最终的最大似然路径的概率是相等的.此外,类似于图5.9,还假设在1-2和14时刻幸存路径泉计度量值优于竞争路径的累计度技值.为使图看上去清楚一些.这些时刻的竞毋路径没有而出.从图5.10可以在出.t时刻幸存路径相应的可戕件值为A(S,)=0.这意味着选择该路径作为幸存谿径没有任何可挑性.在t-2ftt-4时刻,幸存路径相应的可整性值均大于0<,.2(S1)=25，A-KSJ=10),这也想味者幸存路径的累计度M伯较好。但在时刻，由于幸存路径和竞争路径具干j相同的度疑，因此竞争路径也可以是幸存路径，这样，在不降低幸存路径的相关诃程性情况3在1-2和-4时刻存在完全相反的二元判决.为改善幸存路径的可独性值，Hagenauer等人提出了通过后向世踪更新可究性值的方法。这个更新过程嵌入到V1.tC1.bi算法中.得到的算法描述如下.对于格图中的状态结点&r(相应于t时刻的状态k)：存储可靠性A,(SJ=W,(S,)-M<(i,),如果存在不止一条竞争路径对应的可常性值,就将最小的一个存储到,(，).初始化状态S,的可靠性值为+8.比较状态Sm的拿存路径和竞争跖径，并存体反映两个路径的：元判决不同的相对时刻值到MEM,即与当前时刻的差值：按照下面的步骤更新这些MEM处的可就性战. 找到可靠性值没有更新过、满足MEM>0且值最小的MEM.记做MEM 用MEM=0和MEM=MEMx之间H、的可林性值来更新MEMk1.iv的可蒙:性假.继续前面的例子,状态结点SU处幸存路径和竞争路径之间比特判决相反的位置存储为MEM=2,4|,根据这个MEM信息，在图5.11和图5.12中给出了更新可推性值的过程，图5.11中给出了第一个可靠性度量值的更新过程.MEM>0且未更新可靠性值的量小MEMkw=2,在MEM=O和MEM=MEM2=2之间最小的可挣性值为,($)=0,这样相应的可整性值就由A(SJ=25更新为(，)=A(SJ=0。卜一个MEM>0且未更新可靠性值的最小MEM1.w=4,在MEM=0和MEM=MEMM=4之间最小的可能性值为.(51.)=0.这样相应的可IX性伯就更新为A,(SJ=1.(51.)=0.图5.12给出了第二个可绑性值更新的过程。研究表明,最后的可豫性值在送入F一个分里译码器之前应该经过归一化或者而效化处理，以M小由于可拳性值更新带来的影响，图5/11.2时刻路在改也E新过程图，.1214时刻路径度也更新过程5.3.2SOVA在级联洋码系统，通常一个洋码器会将其误码怆出的可靠度信息（软输出传递给第二个译码器，这样第二个译码零辘可以使用软判决译码.德峪处理从信道（或另一个译眄器传来的软输入俏，并将物输入值传递给处-个译码器，象这种译码器称为软输入软输出SISO.So1.1.-In.Sof1.-Ou1.）译码器。狄输出Vitcrbi。法（SOVA）是Hagcnaucr和HOeber在1989年提出的,我们主要讲解在.:值输入、连续添出AWGN信道卜编码速率为R=!n的卷枳码的SOVASOVA的基本运WqVitcrbi算法相同，唯一的区别在于对每个信息比特的硬判决输出附加一个可靠度的指示.这两者（硬判决徜出和可靠度指示）组合在一起就是蚊徜；1，假设信息比特的先验概率为M*I=0,1,-1.,在r时刻，部分接收序列为r,=（r1,r1,.r,.1）=部分路径度Ia必须最大化校用Vherbi算法）：W（rv1）三4rv1.）p（vr）（5.48）式（5.48）和式（5.13）的区别就在于包含了先验路每柢率p（v）【因为当信息比特的先抬概率不是等慨时，先脸路径概率也是不等概的】，注意：先股路径概率"（、1）就是相关的信息序列u,的先验概率,我们可以符部分路径度过按照=r时刻和时刻分开："In口、JWJ+nq111.'M'>)K0(5.49>-1111p(rJ%jp(M,)IM+Zn”力中R+n小叫对上式进行修正：将和式中的每4乘以2,并引入常数Cy和Q,为:、(5.51a)r21.nr<,')-C÷2np(w.)1.-C.J其中常数C/1三InJMry>IVy=+1.)+1.nz1.,)=_|)；=()j,./j-Q三In/Xmi=+1)+InXu,=-1)(551b)是独立于路径卜,这里的映射初一+1和。-1,类似地，对式5.