Turbo码的各种译码算法及比较

1Turbo码的各种译码算法及比较Turbo码有一重要特点是其译码较为复杂，比常规的卷积码要复杂的多，这种复杂不仅在于其译码要采用迭代的过程，而且采用的算法本身也比较复杂。这些算法的关键是不但要能够对每比特进行译码，而且还要伴随着译码给出每比特译出的可靠性信息，有了这些信息，迭代才能进行下去。用于Turbo码译码的具体算法有：MAP(MaximumAPosterori)、Max-Log-MAP、Log-MAP和SOVA(SoftOutputViterbiAlgorithm)算法。MAP算法是1974年被用于卷积码的译码，但用作Turbo码的译码还是要做一些修改；Max-Log-MAP与Log-MAP是根据MAP算法在运算量上做了重大改进，虽然性能有些下降，但使得Turbo码的译码复杂度大大的降低了，更加适合于实际系统的运用；Viterbi算法并不适合Turbo码的译码，原因就是没有每比特译出的可靠性信息输出，修改后的具有软信息输出的SOVA算法，就正好适合了Turbo码的译码。这些算法在复杂度上和性能上具有一定的差异，系统地了解这些算法的原理是对Turbo码研究的基础，同时对这些算法的复杂度和性能的比较研究也将有助于Turbo的应用研究。MAP算法MAP算法最初是用来估计无记忆噪声下的马尔可夫过程的，它是一种最优的算法。Bahl等人于1974年把它用于线性分组码和卷积码的译码中，在用于卷积码的译码时，对于给定接收序列Y，它不像Viterbi算法那样以栅格路径上的比特组错误最少为目的，而是以译码出来的符号ix的错误最少为目的。即，argmaxiiixxPxY(1.1)不过在大多情况下，它和Viterbi算法的作用是一致的。由于在卷积码的译码中，MAP算法要考虑栅格图中的所有可能路径，这样运算量就非常大，实际系统中很少用到。这样虽然MAP算法早在1974年就被提出，但一直未2被得到充分利用，只有到了1993年Turbo码被提出来，MAP算法被用于Turbo码的译码之后，这种算法才得到广泛的应用。MAP算法不仅能译出序列的比特值，在译码的同时还能输出关于每比特译出的可靠性信息。这种特点正好符合了Turbo码的迭代译码特性，所以才被用于Turbo码的译码中。下面我们来看看MAP算法是如何用于二进制Turbo码的译码的。MAP算法是要根据接收到的序列Y，找出每信息比特ku是“1”(1)或“1”(0)的概率，这等同于计算序列Y下ku的对数似然比值(LLR)kLuY，如式1.2，1ln1kkkPuYLuYPuY(1.2)在栅格图中假设前一状态1kSs和当前状态kSs，输入比特ku引起ss的状态转移，根据贝叶斯(Bayes)准则，可由式1.2得式1.3，11,111,1,,ln,,kkkkssukkkssuPSsSsYLuYPSsSsY(1.3)上式中,1kssu表示所有由1ku引起ss状态转移的集合；同样,1kssu表示由1ku引起的状态转移的集合。接收序列Y可以被分成三部分jkY、kY和jkY，分别表示k时刻之前接收码字序列、当前接收码字和之后接收码字序列。所以，11,,,,,,jkkjkkkPSsSsYPssYYY(1.4)利用贝叶斯公式可得式1.5，111,,,,,,,,,,,,jkkjkkkjkjkkjkkjkkkkPSsSsYPssYYYPYsPssYYPYsPsYsPsYssss(1.5)式1.5中用了式1.6、1.7、1.8的定义，311,jkkksPSsY(1.6)表示接收序列是jkY，1k时刻状态是s的概率，我们称之为前向概率。jkkksPYSs(1.7)表示k时刻状态为s且之后接收序列是jkY的概率，我们称之为后向概率。1,,kkkkssPSsYSs(1.8),kss表示由给定状态s转移到s并且此时接收码字为kY的状态转移概率。因此计算LLR的式1.3可被分成前向概率转、状态转移概率和后向概率三部分，如式1.9所示，11,111,11,11,1,,ln,,,ln,kkkkkkssukkkssukkkssukkkssuPSsSsYLuYPSsSsYssssssss(1.9)可以看出，用MAP译码算法译接收序列Y的关键是要计算出和各时刻有关的所有的1ks、ks，还有所有可能的ss状态转移的概率,kss。ks、ks的计算仍旧非常复杂，在下面的推导中我们可以看到ks、ks的计算可以用递规的方法。ks的计算根据ks的定义，有式1.10成立，11,,,,,,jkjkkkkkjkkkkallssPSsYPSsYYPSsSsYY(1.10)“alls”表示所有的状态s。4假设信道为无记忆信道，则,ksY的概率只和前一状态s有关，而和jkY无关。并利用贝叶斯公式，有式1.11成立，11,,,,,,,,,jkkkkkallskjkjkallskjkallskkallssPSsSsYYPsYsYPsYPsYsPsYsss(1.11)由此看出ks可由1ks前向递归计算得出。递归计算存在初始化的问题，初始状态00S由式1.12给出，00001000SSS(1.12)ks的计算类似ks的计算推导，后向概率ks也可以由递归计算得出，不过这次是后向递归，11,,,,,jkjkkkjkjkkallsjkkallskkallssPYsPYYsPYsPYYssPYsPYsssss(1.13)ks的初始状态NNS由式1.14给出，1000NNNNSSS(1.14),kss的计算,kss计算可根据当前接收码字和先验信息(a-priori)计算得出。5设在编码k时刻输入信息比特ku，编码状态由s转移到s，并得到码字为kx，经信道传输后接收到ky，则,,,,kkkkkkssPsYsPYssPssPYssPssPyxPss(1.15)概率Pss直接由引起状态转移的输入比特ku的先验概率决定。定义ku的先验概率对数似然比kLu，1ln1kkkPuLuPu(1.16)当1,1kpuss，则1lnln11kkkPssPuLuPuPss(1.17)1kkLuLuePsse(1.18)当1,1kpuss时，则11kkLuLuePsse(1.19)设/21kkLuLuee，则/2/2/21,11,1kkkkLukuLuLukepussPsseepuss(1.20)比特ku的先验信息kLu，一般从上一次译码输出信息中获得的；在第一次译码时，由于没有什么信息可以获得，只有先假设ku为“1”(1)或“1”(0)的概率相同，即60kLu。设信道噪声为高斯白噪声，方差为2，所要传输的信息比特的平均能量是bE，编码速率为R(编码后每比特的平均能量为bER)，则kkPyx可由式1.21计算，2212112kkbklklnklkllERnyxlPyxPyxe(1.21)n表示一个码字中信息位与校验位加在一起所有比特的数量。关于ks和ks的递归计算及其与,kss的关系，可由图1.1更直观的看出来。这是一个有4种状态的编码，图中的加粗线是在计算中所需要考虑的栅格路径。kS1kS2kS1kS2kS0S1S2S3S10k11k0k0k10k12k10,0k10,2k0,0k1,0k111111000,011,0000,020,2kkkkkkkkkk图1.1递归计算ks和ks的示意图用于迭代的MAP算法正如上章中看到，在Turbo码的译码迭代过程中，每个SISO译码模块输出的信息中一定要有一部分作为下次的先验信息输入，所以要从式1.9计算出kLuY分离出所需要的信息。如式1.22我们把它分成三部分，1,11,1,ln,kkkkkssukkkkssukcksekssssLuYssssLuLyLu(1.22)7其中cL为信道可靠度（置信度）。在双边带功率谱密度是0/2N的加性高斯白噪声信道下，04bcERLN(1.23)kLu被称为先验信息。接收到ksy，kskkyun(1.24)其中，kn是离散的加性高斯白噪声。ekLu被称为ku的外在(extrinsic)信息。1,11,1,ln,kkekkkckskkkssukkkssuLuLuYLuLyssssssss(1.25)其中，2,exp2nckklkllLssyx(1.26)由此看来所得到的后验概率kLuY被分成三部分：先验信息kLu、系统比特信息cksLy和外在信息ekLu：1、先验信息kLu，如上文所述，一般由前一次迭代译码输出获得，第一次迭代时，由于无先验信息可用，kLu为零。2、系统比特信息cksLy是从信道中直接获得的关于系统比特ku的信息，当系统的信噪比(0bEN)比较高时，ksy在kLuY中占用份量就越大，换句话说就是直接从信道中获得的信息就越可靠；反之，就越不可靠。3、ekLu可以被理解为除了上述两项和ku直接相关的信息之外的信息，由式81.25和式1.26可以看出，此信息在Turbo码的译码中被用作下一个成员译码器的先验信息输入。从式1.22可以看出，MAP译码算法实际上用上了所有和ku有关的信息（kLu，cksLy，ekLu）来计算ku的LLR。Max-Log-MAP与Log-MAP算法从上节中可以看到MAP算法非常复杂，运算量极大，运算中不仅有大量的乘法和加法，还有在数字电路中较难实现的指数和对数运算，这极大的影响了MAP算法的实用。Koch和Baier及Erfanian等人提出Max-Log-MAP算法，大大地简化了MAP算法的复杂性，由于计算中做了一定地近似，这种算法不是最优的。Robertson等人对Max-Log-MAP算法做了一定地修正，被称作Log-MAP算法。Max-Log-MAP对MAP所做的修改是直接在对数域里对ks、ks、,kss和kLuY进行计算，省去了许多指数和对数运算，大大简化了运算量。首先定义kAs、k