PCCC码(Turbo码)的编码和译码算法

..目录概述1TOC\o"1-3"二、PCCC码的编码算法2三、PCCC码的译码算法13概述虽然软判决译码、级联码和编码调制技术都对信道码的设计和发展产生了重大影响,但是其增益与Shannon理论极限始终都存在2～3dB的差距。因此,在Turbo码提出以前,信道截止速率R0一直被认为是差错控制码性能的实际极限,shannon极限仅仅是理论上的极限,是不可能达到的。根据shannon有噪信道编码定理,在信道传输速率R不超过信道容量C的前提下,只有在码组长度无限的码集合中随机地选择编码码字并且在接收端采用最大似然译码算法时,才能使误码率接近为零。但是最大似然译码的复杂性随编码长度的增加而加大,当编码长度趋于无穷大时,最大似然译码是不可能实现的。所以人们认为随机性编译码仅仅是为证明定理存在性而引入的一种数学方法和手段,在实际的编码构造中是不可能实现的。在1993年于瑞士日内瓦召开的国际通信会议<1CC,93>上,两位任教于法国不列颠通信大学的教授C.Berrou、A.Glavieux和他们的缅甸籍博士生P.thitimajshima首次提出了一种新型信道编码方案——Turbo码,由于它很好地应用了shannon信道编码定理中的随机性编、译码条件,从而获得了几乎接近shannon理论极限的译码性能。仿真结果表明,在采用长度为65536的随机交织器并译码迭代18次情况下,在信噪比Eb/N0≥0.7dB并采用BPSK调制时,码率为1/2的Turbo码在AWGN信道下的误比特率≤10-5,达到了与Shannon极限仅相差0.7dB的优异性能〔1/2码率的Shannon极限是0dB。Turbo码又称并行级联卷积码<PCCC,ParallelConcatenatedConvolutionalCode>,它巧妙地将卷积码和随机交织器结合在一起,在实现随机编码思想的同时,通过交织器实现了由短码构造长码的方法,并采用软输出迭代译码来逼近最大似然译码。可见,Turbo码充分利用了Shannon信道编码定理的基本条件,因此得到了接近Shannon极限的性能。在介绍Turbo码的首篇论文里,发明者Berrou仅给出了Turbo码的基本组成和迭代译码的原理,而没有严格的理论解释和证明。因此,在Turbo码提出之初,其基本理论的研究就显得尤为重要。J.Hagenauer首先系统地阐明了迭代译码的原理,并推导了二进制分组码与卷积码的软输入软输出译码算法。由于在Turbo码中交织器的出现,使其性能分析异常困难,因此S.Benedetto等人提出了均匀交织<UI,Uniforminterleaver>的概念,并利用联合界技术给出了Turbo码的平均性能上界。D．Divsalar等人也根据卷积码的转移函数,给出了Turbo码采用MLD时的误比特率上界。对于Turbo码来说,标准联合界在信噪比较小时比较宽松,只有在信噪比较大时才能实现对Turbo码性能的度量。因此,T.M．Duman、I.Sason和D.Divsalar等人在Gallager限等已有性能界技术的基础上进行改进．扩展了Turbo码性能界的紧致范围。D.Divsalar等人还根据递归系统卷积码的特点提出了有效自由距离的概念,并说明在设计Turbo码时应该使码字有效自由距离尽可能大。L.C.Perez等人从距离谱的角度对Turbo码的性能进行了分析,证明可以通过增加交织长度或采用本原反馈多项式增加分量码的自由距离来提高Turbo码的性能。他们还证明了Turbo码虽然自由距离比较小,但其小重量码字的数目较少,从而解释了低信噪比条件下Turbo码性能优异的原因,并提出了交织器增益的概念。S.Dolinar的研究表明,Turbo码的最小距离码字主要由重量为2的输入信息序列生成,是形成错误平台的主要原因。为提高高信噪比条件下Turbo码的性能,就必须提高低重输入信息序列的输出码重。J.Seghers系统地分析了Turbo码的距离特性。由于交织器的存在,无法给出Turbo码自由距离的严格数学表示,相应地也出现了许多分析和计算Turbo码最小距离、重量分布和性能上限的方法。A．Ambroze还构造了Turbo码的树图,用来作为计算码字距离谱的工具。此外,、E.Offer和K.Engdahl分别从代数和统计的角度对Turbo码进行了分析。考虑到Turbo码的延时问题,E.K.Hall等人提出了面向流的Turbo码。也可以用其他系统模型采描述Turbo码及其迭代译码过程：T.Richardson把Turbo码作为一个动力学系统进行描述；A.K.Khandani则把Turbo码考虑成一个周期性的线性系统；J.Laertyy,X.Ge和F.R.Kschischang描述了Turbo码的图模型；在图模型的基础上,D．J．C．MaKay等人证明了Turbo码的校验矩阵与LDPC码的校验矩阵是等价的,从而可以将Turbo码看成一类特殊的LDPC。PCCC码的编码算法输入：信源消息u〔消息分组u输出：码字v处理：信源输出为一系列二进制数字0和1。在分组码中,这些二进制信息序列分成固定长度的消息分组〔messageblocks。每个消息分组记为u,由k个信息位组成。因此共有2k种不同的消息。编码器按照一定的规则将输入的消息u转换为二进制n维向量v,这里n>k。此n维向量v就叫做消息u的码字〔codeword、码字矢量或码向量〔codevector。因此,对应于2k种不同的消息,也有2k种码字。这2k个码字的集合就叫一个分组码〔blockcode。若一个分组码可用,2k个码字必须各不相同。因此,消息u和码字v存在一一对应关系。由于n符号输出码字只取决于对应的k比特输入消息,即每个消息是独立编码的,从而编码器是无记忆的,且可用组合逻辑电路来实现。定义：一个长度为n,有2k个码字的分组码,当且仅当其2k个码字构成域GF<2>上所有n维向量组成的向量空间的一个K维子空间时被称为线性〔linear<n,k>码。卷积码是把信源输出的信息序列,以k0个<k0通常小于k>码元为一段,通过编码器输出长为n0<≥k0>的码段。但是该码段的n0-k0个校验元不仅与本组的信息元有关,而且也与其他前m段的信息元有关,称m为编码存贮,因此卷积码用<n0,k0,m>表示。卷积码与分组码不同,在进行编码时,本组的校验元不仅与本组的信息元有关,而且还与以前各时刻输入至编码器的信息组有关。同样,在卷积码译码过程中,不仅从此时刻收到的码组中提取译码信息,而且还要利用以前或以后各时刻收到的码组中提取有关信息。正是由于在卷积码的编码过程中,充分利用了各组之间的相关性,因此,在与分组码同样的码率和设备复杂性条件下,无论从理论上还是从实际上均已证明卷积码的性能至少不比分组码差,且实现最佳和准最佳译码也较分组码容易。为简便起见,我们以<2,1,2>卷积码为例,对其进行说明。图1<2,1,2>卷积码编码器图3-2中给出了一个二进制卷积码的编码器,若每一时间单位输入编码器一个新信息元,且存储器内数据右移一位,则一方面将数据送入存储器,另一方面与刚才存储器中的两个数据按图中的规则进行运算,则此时刻得到两个输出码元、,组成一个子码送入信道。由图可知输入与输出的关系是<1-1>在每一时间单位送入编码器k0<这里为1>个信息元,编码器就送出相应的n0<这里为2>个码元组成一个子码cI送入信道。在卷积码中,这个码元组成的子码cI,也称为卷积码的一个码段或子组,上式中的"+"是模2和。由式<3-1>可知,输入与输出码元之间是线性关系,所以这类编码器输出的卷积码是线性码,称m为编码存储,它表示输入的信息组在编码器中存储的时间数,称m+1=N为编码约束度,说明编码过程中互相有约束关系的码元个数。同样,在卷积码译码过程中,不仅要根据此时刻输入到译码的子码,而且还要根据以后很长一段时间,如m’段时间内收到的各子码,才能译出一个子码的信息元,通常m’>m。称为译码约束度,称为译码约束长度,它们分别表示译码过程中互相有约束的码段或码元个数。从式<3-1>中还可看出,输出的码元中,不一定与输入的码元相等,所以这样的码是非系统码。当然,如果输出的码段中的某一位码元与输入的码元固定相等,则这样的码为系统码。总之,在卷积码的各码段之间,不论是编码还是译码,都不是每段各自处理,而是与前后或段有关,所以卷积码通常用表示,,称为卷积码的码率。Turbo码的编码Turbo码的编码结构可以分为并行级联卷积码〔PCCC、串行级联卷积码〔SCCC和混合级联卷积码〔HCCC三种,如图1所示。图1-1Turbo码的几种编码结构〔aPCCC〔bSCCC〔cHCCC-I〔dHCCC-II1993年,C.Berrou提出的Turbo码就是PCCC结构,主要由分量编码器、交织器、穿刺矩阵和复接器组成。分量码一般选择为递归系统卷积〔RSC码,当然也可以选择分组码、非递归卷积〔NRC码以及非系统卷积〔NSC码。通常两个分量码采用相同的生成矩阵〔也可不同。若两个分量码的码率分别为R1和R2,则Turbo码的码率为：R= <1-1>在AWGN信道上对PCCC的性能仿真证明,当BER随SNR的增加下降到一定程度时,就会出现下降缓慢甚至不再降低的情况,一般称为误码平台〔errorfloor。为解决这个问题,1996年,S.Benedetto提出了串行级联卷积码〔SCCC的概念,它综合了Forney串行级联码〔RS码＋卷积码和Turbo码〔PCCC的特点,在适当的信噪比范围内,通过迭代译码可以达到非常优异的译码性能。Benedetto的研究表明,为使SCCC达到比较好的译码性能,至少其内码要采用递归系统卷积码,外码也应选择具有较好距离特性的卷积码。若外码编码器和内码编码器的编码速率分别为RO和RI,则SCCC的码率R为：R=RO×RI〔1-2HCCC是将前两种方案结合起来,从而既能在低SNR下获得较好的译码性能,又能有效地消除PCCC的误码平台,称为混合级联卷积码。综合串行和并行级联的方案很多,这里只给出两种常见的方案,一是采用卷积码和SCCC并行级联的编码方案,如图1〔c所示；另一种是以卷积码为外码,以PCCC为内码的混合级联编码结构,如图1〔d所示。我们主要讨论PCCC结构的卷积码。为便于讨论,将PCCC编码结构重画为图1-2〔a所示。图1-2PCCC编码器基本结构系统包括输入信息序列u,两个〔2,1,v系统反馈〔递归卷积编码器,一个交织器〔用π表示。假设信息序列含有K*个信息比特以及v个结尾比特〔以便返回到全0态,其中v是第一个编码器的约束长度,因此有K＝K*＋v,信息序列可表示为：u=<u0,u1,…,uK-1>由于编码器是系统的,因此信息序列就等于第一个输出序列,即：u=v<0>=<v0<0>,v1<0>,…,vK-1<0>>第一个编码器输出的校验序列为：v<1>=<v0<1>,v1<1>,…,vK-1<1>>交织器对K个比特进行扰序处理,得到u’,第二个编码器输出的校验序列为：v<2>=<v0<2>,v1<2>,…,vK-1<2>>从而最终的发送序列〔码字为：v=<v0<0>v0<1>v0<2>,v1<0>v1<1>v1<2>,…,vK-1<0>vK-1<1>vK-1<2>>因此,对该编码器来说,码字长度N＝3K,Rt＝K*/N＝<K－v>/3K,当K比较大时,约为1/3。在图1-2〔b中,两个分量码都是〔2,1,4系统反馈编码器,具有相同的生成矩阵,为：G[D]=[1<1+D4>/<1+D+D2+D3+D4>]对于Turbo码来说,需要注意以下几点：〔1为了得到靠近Shannon限的系统性能,信息分组长度〔交织器大小K一般比较大,通常至少几千个比特。〔2对于分量码来说,一般选择相同结构,且约束长度较短,通常v≤4。〔3递归分量码〔由系统反馈编码器产生会比非递归分量码〔前馈编码器有更好的性能；〔4高码率可通过穿刺矩阵产生,如图1-2〔b中,可通过交替输出v<1>和v<2>得到1/2的编码速率。〔5通过增加分量码和交织器也可得到较低编码速率的Turbo码,如图1-3所示。图1-3速率R=1/4的Turbo码〔6最好的交织器能够对比特以伪随机的方式进行排序,传统的块交织器〔行-列在Turbo码中性能不好,除非block长度很短；〔7由于交织器只是对比特位置进行重新排序,因此,交织后的序列u’与原始序列u具有相同的重量；〔8对每个分量码来说,用BCJR〔或MAP算法作为SISO译码器能够获得最好的性能；因为MAP译码器使用了前向-后向算法,信息是以block的形式进行的,因此,对第一个分量译码器来说,附加v个0比特能够让它返回到全0态；但对于第二个译码器来说,由于交织器的作用,将不能返回到全0态。图1-2〔b所示的编码器,穿刺后得到1/2的码率。此时穿刺矩阵可以为P=,其输出就为v=<v0<0>v0<1>,v1<0>v1<2>,…>。当信息序列长度K＝65536比特,SISOMAP译码器经过18次迭代后,在0.7dB可以达到10-5的误比特率,与Shannon限只相差0.7dB。Turbo码有两个缺点：〔1较大的译码时延,这是由于block长度较大、译码需要多次迭代造成的。这样对于实时业务或高速数据的传输就非常不利；〔2BER在10-5后会出现误码平台,这是由于Turbo码的重量分布造成的。对于某些对BER要求较高的应用就不适合,当然通过交织器的设计能够提供码字的最小距离,从而降低误码平台。例1-1：用于QAM的8状态并行级联卷积码<PCCC,ParallelConcatenatedConvolutionalCode>。根据图1-4,这里的PCCC码将把K2个类型2的比特b2<1>,b2<2>,…,b2<K2>变成K3个类型3的比特b3<1>,b3<2>,…,b3<K3>。这K2个类型2的比特包含两组尾比特b2<K2–2>,b2<K2–1>,b2<K2>和b2’<K2–2>,b2’<K2–1>,b2’<K2>,目标是要使分量递归系统卷积码RSC<recursivesystematicconvolutional>编码器的最后状态归零。两个分量编码器的初始状态为零。正如图1-4a>用一个8状态递归系统卷积码RSC编码器〔图1-4中上面的那个RSC编码器实现1/2的码率的编码；b>用一个二次线汇内编码器对输入的K2–3个类型2的比特实现交织；c>用第二个8状态递归系统卷积码RSC编码器对已交织的比特实现等同于a>的1/2的码率的编码,并且只保留校验序列〔码；d>实现对两个递归系统卷积码RSC编码器输出的校验序列〔码的穿刺,以获得码率为K2/K3的8状态并行级联卷积码PCCC。这四步骤的通用描述分别列在[3]的和。编码率为2/3和1/2的8状态PCCC编码器的穿孔图样〔打孔图样、压缩图样的描述分别列在[3]的和。图1-4PCCC编码器.4.6编码率为2/3的PCCC编码器的穿孔图样t=6个穿孔系数为:P<1>=1,P<2>=2,P<3>=4,P<4>=7,P<5>=9,P<6>=10,而且i=j <8.30>.4.7编码率为1/2的PCCC编码器的穿孔图样t=8个穿孔系数为:P<1>=1,P<2>=2,P<3>=4,P<4>=6,P<5>=7,P<6>=8,P<7>=10,P<8>=12,而且i=j <8.31>各个PCCC码在TETRA信道编码方案中的使用方式由下面各图显示。图QAM纠错编码接口结构图QAM逻辑信道纠错结构框图QAM所用到的块交织结构在[3]的.3描述,其扰码结构与其他调制方式时相同,其描述列在8.2.5.PCCC码的译码算法输入：接收向量r输出：译码所得码字v*处理：下图表示了Turbo码解码器结构,S表示接收到的信息位,P1表示接收到的第一路校验位,P2表示接收到的第二路校验位。SISO表示软入软出的解码器〔MAP或者SOVA,解码器输出S的外信息和硬判决值。整个Turbo解码时串行迭代的过程。第一个SISO〔软入软出,SoftInSoftOut解码器以S和P1为输入,产生外信息E1。第二个解码器以P2和经过正交织的S和E1为输入,产生外信息E2。从而,完成一次完整的迭代算法。第二次迭代,第一个SISO以S’、P1和经过反交织的E2为输入,产生外信息E1,这样周而复始地迭代下去。图2-1Turbo码解码器整个解码过程就像涡轮机〔Turbo一样不断循环反复,在两个解码器之间交换外信息,因而这样级联方式的卷积码又被形象地称为Turbo码。图2-2汽车发动机的Turbo结构Turbo码译码原理香农信息论告诉我们,最优的译码算法是概率译码算法,也就是最大后验概率算法<MAP>。但在Turbo码出现之前,信道编码使用的概率译码算法是最大似然算法<ML>。ML算法是MAP算法的简化,即假设信源符号等概率出现,因此是次优的译码算法。Turbo码的译码算法采用了MAP算法,在译码的结构上又做了改进,再次引入反馈的概念,取得了性能和复杂度之间的折衷。同时,Turbo码的译码采用的是迭代译码,这与经典的代数译码是完全不同的。Turbo码的译码算法是最早在BCJR算法的基础上改进的,我们称以MAP算法,后来又形成Log-MAP算法、Max-Log-MAP以及软输入软输出<SOVA>算法。Turbo码的译码结构如图2-1所示。Turbo译码器有以下的特点：1>串行级联2>迭代译码3>在迭代译码过程中交换的是外部信息2.概率译码译码原理及结构译码时首先对接收信息进行处理,两个成员译码器之间外部信息的传递就形成了一个循环迭代的结构。由于外部信息的作用,一定信噪比下的误比特率将随着循环次数的增加而降低。但同时外部信息与接受序列间的相关性也随着译码次数的增加而逐渐增加,外部信息所提供的纠错能力也随之减弱,在一定的循环次数之后,译码性能将不再提高。Turbo码译码算法如前所述,turbo码需要一种软输入软输出的译码算法。软输出译码器的输出不仅应包含硬判决值,而且包括做出这种判断的可信程度。译码算法应该考虑到三方面的问题,及外信息的引入；如何在迭代译码中充分利用各类信息,防止简单正反馈的形成,确保算法收敛；充分利用码原件的相关信息。常见的算法有以下几种：a>标准MAP算法〔最大后验概率译码算法,maximum-a-posteriori,MAP,是对bahl软输出算法做一定修正后,通过除以先验分布来消除正反馈的算法。对于约束长度为M+1的卷积码,其运算量为每比特6×3M次乘法和5×2Mb>Log-MAP算法,实际上就是对标准MAP算法中的似然全部用对数似然度来表示,这样,乘法运算变成了加法运算。总的运算量成为6×2M次加法,5×2M次求最大运算和5×2M次查表。c>Max-Log-MAP算法,是在上述对数域的算法中,将似然值加法表示式中的对数分量忽略,使似然加法完全变成求最大值运算,这样除了省去大部分的加法运算外,最大的好处是省去了对信噪比的估计,使得算法更稳健。d>软输出维特比译码<Soft-outputviterbiAlgorithm,SOVA>,其运算量为标准维特比算法的两倍。维特比算法是最大似然序列估计算法,但由于在它的每一步都要删除一些低似然路径,为每一状态只保留一条最优路径,它无法提供软输出。为了给他输出的每个比特赋予一个可信度,需要在删除低似然路径是做一些修正,以保留必要的信息。其基本思想是利用最优留存路径和被删路径的度量差,这个差越小意味着这次算去的可靠性越好。然后用这个差去修正这条路径上各个比特的可信度。Turbo码性能仿真比较目前Turbo码的大部分研究致力于在获得次优性能的情况下减小译码复杂度和时延,从而得到可实现的Turbo码系统。几种主要译码算法的性能比较图2-3译码算法对Turbo码的影晌对MAP算法、Log-MAP算法、Max-Log-MAP算法和SOVA算法在加性高斯白噪声信道<AWGN>环境下进行仿真比较,系统采用的是BPSK调制方式,Turbo码的交织长度是1024,RSC子码的生成多项式为<37,21>,系统编码率为R=1/2,译码时迭代5次,结果以曲线图给出如图。仿真结果表明,四种算法中,MAP算法性能最好,Log-MAP算法的性能跟MAP算法在较低的SNRq时比较接近,高信噪比时差别则较大。Max-Log-MAP算法和SOVA算法的性能十分接近,一般情况下,Max-Log-MAP算法的性能,总是稍优于SOVA算法。它们跟MAP和Log-MAP相比,性能下降十分明显。从算法复杂度而言,MAP算法最为复杂,Log-MAP其次,之后是Max-Log-MAP,SOYA算法最简单。由此可以看出,性能优异的Turbo码译码算法十分复杂,如果要使得译码容易实现而对算法进行简化或者是采用简单的算法,往往需以性能的降低为代价。不同迭代次数对Turbo码性能的影响图2-4迭代次数对Turbo码的影响上图给出了在不同解码迭代次数下,码率为1/2的Turbo码的BER与Eb/N0的关系曲线。Turbo码的交织长度是1024,RSC子码的生成多项式为<37,21>,系统编码率为R=1/2。如Turbo码译码原理中所述,两个译码器之间互相交外部信息进行迭代。可以得到,迭代译码次数增大,译码性能增加。在第一次迭代的误比特性能都比较差,这是因为两个分量译码器之间的信息还没有被很好的相互利用。随着迭代次数的增加,两个分量译码器之间的外信息被更好的利用,对信息比特的估计更接近最大似然比,判决输出的正确性就越高。迭代次数达到一定数值时,译码性能趋于稳定,再增加新的迭代对性能的改善非常小。迭代增加了译码时延,在大帧编码时尤其如此。仿真中迭代次数增大时运行时间显著增加。由于达到一定迭代次数后,新增加的迭代对性能改善不大,而法代又极大地增加译码时延,所以在实际设计Turbo码系统时,需要选择适当的迭代次数,在允许的译码时延内,达到最佳的译码性能。这种预先规定迭代次数的方式是终止译码迭代次数的方法之一.当要求的信噪比比较大,误码率要求不太高的情况,往往经过很少的几次迭代就能达到译码要求正确译码。此时,如果预设迭代次数比较大,那么译码器会继续译码,一直进行到预设次数的迭代为止.后边的几次送代并没有明显地提高性能,是完全不必要的,而且多余的法代食给译码带来了额外的时延。不同编码约束度K对Turbo码性能的影响图2-5不同的约束度对Turbo码性能的影响采用不同子码的Turbo码的性能也有很大差别。Turbo码的设计中首先就是选择好的RSC子码。这里只对几种常用的、较好的采用不同约束长度的RSC做子码的Turbo码进行仿真,以分析约束长度对Turbo码性能的影响。可以看出,随着约束长度K增大,编码后的码元与更多个信息比特相关,因此译码纠错能力越强,误比特率BER就越小。当BER<10-2时,增加卷积码的约束度将会改善Turbo码BER性能。在交织器长度和码率一定时,约束度越大,Turbo码的BER性能越好。SISO解码算法在介绍SISO解码算法之前,首先进行符号的定义：以1/2码率的卷积码为例,假设：k时刻的编码码字,uk是k时刻的信息比特,是k时刻的校验比特;k时刻的接收码字,是k时刻接收的信息比特,是k时刻接收的校验比特;假设平坦瑞利衰落信道<FlatRayleighFadingchannel>和相干解调<CoherentDemodulation>,那么接收码字和编码码字存在下列关系式：其中,ak是k时刻的衰落乘性系数,而和分别是对于信息比特和校验比特的k时刻的加性高斯白噪声〔AWGN,假设其均值为零,方差为σ2。≡<Y1,Y2,…,Yk>为从1时刻到k时刻的接收码字序列。≡<Yn,Yn+1,…,Ym>为从n时刻到m时刻的接收码字序列。αk<s>≡P<sk=s,>为前向递推概率,表示k时刻卷积码编码器状态为s,且接收序列为的概率。βk<s>≡P</sk=s>为后向递推概率,表示k时刻卷积码编码器状态为s,且接收序列为的概率。γk<s’,s>≡P<Yk,sk=s/sk-1=s’>为转移概率,表示在k-1时刻的s’条件下到k时刻的s状态且接收码字为Yk的转移概率。L<uk>≡ln为似然比,表示k时刻的信息比特uk为1和为-1的概率比值的对数。L<uk/>≡ln=ln为后验概率的输出似然比,表示已知接收序列解码的条件下解码输出的k时刻的信息比特uk为1和为-1的概率比值的对数。Lc≡为信道补偿参数。如图所示,定义度量概率和。图2-6状态转移图MAP、Log_MAP和Max_Log_MAP算法图2-7MAP解码器MAP算法推导转移概率的推导γk<s’,s>≡P<Yk,sk=s/sk-1=s’> =P<s/s’>P<Yk/s,s’>=P<uk>P<Yk/CkL<uk>≡lnP<Yk/Ck>= =P<Yk/Ck>∝令Lc≡,则γk<s’,s>∝前向概率的推导αk<s>≡P<sk=s,>= = = =〔由马尔克夫性 =后向概率的推导βk-1<s>≡P<= = = =〔由马尔克夫性 =联合概率的推导 ===〔由马尔克夫性 =后验概率的推导L<uk/>≡ln=ln =lnα0<s>、βN<s>的初始化问题因为卷积码编码的初态为零,所以若卷积码归零,则若卷积码不一定归零,则sN任意state_num表示卷积码的状态数。信息的输出软判决输出：,用于本解码器的外信息输出,经过交织或者反交织传递给下一个解码器,并作为下一个解码器的先验信息的输入。硬判决输出：uk=sign<>是硬判决的双极性比特,其中sign表示取符号。从MAP算法的推导可知,马尔可夫性是其算法成立的前提和核心。对于任何满足马尔可夫性的编码方法,MAP算法都可以适用。MAP算法又称为BCJR算法〔BCJR是四个算法发现者名字的首字母或者前向-后向〔Forward-Backward算法。Log_MAP算法：与MAP算法等效,只是将α、β、γ转移到对数域中计算,并将乘法运算映射为加法运算,加法运算映射为E运算,便于硬件实现。<1>引入映射f:y=lnx<2><3>×→＋<4>＋→E<5>E运算的定义：aEb≡ln<ea+eb>=max<a,b>+ln<1+>E运算与加法运算一样满足交换律和结合律,所以：分支转移概率为：γk<s’,s>=前向概率的递推为：αk<s>=后向概率的递推为：βk-1<s’>=后验概率为：L<uk/>≡Max_Log_MAP算法：Max_Log_MAP算法是Log_MAP算法的简化,原理完全相同,仅仅简化了E运算。aEb≡ln<ea+eb>=max<a,b>+ln<1+>aEb≈max<a,b>所以,定义aEb=max<a,b>。Max运算与加法运算一样满足交换律和结合律,用它取代Log_MAP算法中的E运算即改造成Max_Log_MAP算法。所以,分支转移概率为：γk<s’,s>=前向概率的递推为：αk<s>=后向概率的递推为：βk-1<s’>=后验概率为：L<uk/>≡软判决〔外信息输出为：Max_Log_MAP解码算法的计算复杂度降低了,但差错性能〔误码率和误块率也变差了。这是由于Max_Log_MAP解码算法的外信息存在高估〔over_estimate问题,亦即Max_Log_MAP的外信息的绝对值通常高于Log_MAP的外信息的绝对值。为了缓解这一问题,可以将上述的外信息乘以一个常数η,0<η<1,所以：Lk<uk>new=ηLk<u通过仿真,我们发现一个合适的η推荐值为3/4,这个值特别适用于二进制的硬件实现：Lk<uk>new=Lk<uk>-Lk<除4可以用二进制的右移两位操作来实现,这样多增加一个简单的加减法操作就可以很好地改善Max_Log_MAP算法的性能。SOVA算法SOVA算法推导：转移概率的推导〔同上文度量概率的推导度量概率的选择如图2-6所示,k时刻s状态的度量概率为,其中,度量最大者称为幸存路径,余者称为伴随路径。计算度量差那么对k时刻s状态正确选择幸存路径的概率为:计算k时刻s状态的后验概率为：〔uk为幸存路径的编码比特后验概率的更新策略采用维特比解码通过回溯找到ML<最大似然路径>,设其k时刻的状态为sk,编码比特为uk,则k时刻的后验对数似然比概率为：但是上式的判断过于乐观,存在似然值高估的问题。因而采用如图所示的更新策略。其中,δ是解码延时窗。从i时刻<i∈[k+1,k+δ]>的最大似然路径上的伴随路径分支分别问题回溯,如果得到的k时刻的编码比特与k时刻最大似然路径上的信息比特uk不同,则取其中度量差的最小值更新。sksk+1sk+2sk+3图2-8更新策略图以图2-8为例,假设最大似然路径为全零路径,解码延时窗δ=3,网格图上的实线表示输入信息比特为-1,虚线表示信息比特为1。从k+1时刻最大输入路径的伴随式路径回溯到k时刻的信息比特是1,与k时刻的最大似然路径上的信息比特-1不同,所以相应的度量差是需要进行比较：而从k+2时刻最大似然路径的伴随路径回溯到k时刻的信息比特是1,与k时刻的信息比特相同,所以不需比较。同理,从k+3时刻回溯的信息比特是1,也不相同,所以相应的度量差也需要进行比较。综上上述,更新的度量差应取中的最小值,后验概率的输出似然比为：SOVA软判决〔外信息输出为：硬判决输出:uk=sign<>。同样,SOVA解码算法的外信息也存在高估〔over_estimate问题,亦即SOVA的外信息的绝对值通常要高于Log_MAP的外信息的绝对值。为了缓解这一问题,可以将上述的外信息乘以一个常数η,0<η<1,所以：Lk<uk>new=ηLk<u通过仿真,我们发现一个合适的η推荐值为3/4,这个值特别适用于二进制的硬件实现：Lk<uk>new=Lk<uk>-Lk<也可进一步改进成双向的SOVA算法：维特比解码可以从前向后解码,也可以从后向前解码。取两次解码度量差的最小者更新。双向的SOVA算法比单向算法性能有所改善,但是计