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

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算法那样以栅格路径上的比特组错误最少为目的，

%而是以译码出来的符号xi的错误最少为目的。即，

%xiargmaxPxiY(1.1)

xi不过在大多情况下，它和Viterbi算法的作用是一致的。

由于在卷积码的译码中，MAP算法要考虑栅格图中的所有可能路径，这样运算量就非常大，实际系统中很少用到。这样虽然MAP算法早在1974年就被提出，但一直未

被得到充分利用，只有到了1993年Turbo码被提出来，MAP算法被用于Turbo码的译码之后，这种算法才得到广泛的应用。

MAP算法不仅能译出序列的比特值，在译码的同时还能输出关于每比特译出的可靠性信息。这种特点正好符合了Turbo码的迭代译码特性，所以才被用于Turbo码的译码中。下面我们来看看MAP算法是如何用于二进制Turbo码的译码的。

MAP算法是要根据接收到的序列Y，找出每信息比特uk是“1”(1)或“1”(0)的概率，这等同于计算序列Y下uk的对数似然比值(LLR)LukY，如式1.2，

Puk1YLukYln(1.2)

Puk1Y在栅格图中假设前一状态Sk1s和当前状态Sks，输入比特uk引起ss的状态转移，根据贝叶斯(Bayes)准则，可由式1.2得式1.3，

s,suk1PSk1s,Sk1s,Y(1.3) LukYlns,su1PSk1s,Sk1s,Yk上式中s,suk1表示所有由uk1引起ss状态转移的集合；同样

s,suk1表示由uk1引起的状态转移的集合。

Yk和Yjk，接收序列Y可以被分成三部分Yjk、分别表示k时刻之前接收码字序列、

当前接收码字和之后接收码字序列。所以，

PSk1s,Sk1s,YPs,s,Yjk,Yk,Yjk(1.4) 利用贝叶斯公式可得式1.5，

PSk1s,Sk1s,YPs,s,Yjk,Yk,YjkPYjksPs,s,Yjk,YkPYjksPs,YksPs,Yjkksks,sk1s(1.5)

式1.5中用了式1.6、1.7、1.8的定义，

k1sPSk1s,Yjk(1.6)

表示接收序列是Yjk，k1时刻状态是s的概率，我们称之为前向概率。

ksPYjkSks(1.7)

表示k时刻状态为s且之后接收序列是Yjk的概率，我们称之为后向概率。

ks,sPSks,YkSk1s(1.8)

ks,s表示由给定状态s转移到s并且此时接收码字为Yk的状态转移概率。

因此计算LLR的式1.3可被分成前向概率转、状态转移概率和后向概率三部分，如式1.9所示，

s,su1PSk1s,Sk1s,YkLukYlns,su1PSk1s,Sk1s,Yk(1.9)

s,su1k1sks,sksklns,su1k1sks,sksk可以看出，用MAP译码算法译接收序列Y的关键是要计算出和各时刻有关的所有的k1s、ks，还有所有可能的ss状态转移的概率ks,s。

在下面的推导中我们可以看到ks、ks的ks、ks的计算仍旧非常复杂，计算可以用递规的方法。

ks的计算

根据ks的定义，有式1.10成立，

ksPSks,Yjk1PSks,Yjk,YkallsPSk1s,Sks,Yjk,Yk(1.10)

“alls”表示所有的状态s。

假设信道为无记忆信道，则s,Yk的概率只和前一状态s有关，而和Yjk无关。并利用贝叶斯公式，有式1.11成立，

ksallPSssk1s,Sks,Yjk,YkkjkjkallPs,Ys,YPs,YPs,YsPs,Ykjks(1.11)

allallss,sk1ks由此看出ks可由k1s前向递归计算得出。

递归计算存在初始化的问题，初始状态0S0由式1.12给出，

0S010S00(1.12) S00ks的计算

类似ks的计算推导，后向概率ks也可以由递归计算得出，不过这次是后向递归，

k1sPYjk1sPYjk,YksallPYsjksPYjk,Yk,ssallPYjksPYk,sskk(1.13)

sallss,ssks的初始状态NSN由式1.14给出， NSN10SN0 SN0(1.14)

ks,s的计算

ks,s计算可根据当前接收码字和先验信息(a-priori)计算得出。

设在编码k时刻输入信息比特uk，编码状态由s转移到s，并得到码字为xk，经信道传输后接收到yk，则

ks,sPs,YksPYks,sPssPYks,sPssPykxkPss(1.15)

概率Pss直接由引起状态转移的输入比特uk的先验概率决定。定义uk的先验概率对数似然比Luk，

Puk1Luk@lnPu1(1.16)

k当puk1s,s1，则

PssPuk1Luk@lnln(1.17) Pu1k1PssekPss(1.18) Luk1eLu当puk1s,s1时，则

ekPss1(1.19) Luk1eLuek设，则 Luk1eLu/2Luk/2ePssLu/2kepuk1s,s1puk1s,s1eukLuk/2(1.20)

比特uk的先验信息Luk，一般从上一次译码输出信息中获得的；在第一次译码时，由于没有什么信息可以获得，只有先假设uk为“1”(1)或“1”(0)的概率相同，即

Luk0。

设信道噪声为高斯白噪声，方差为2，所要传输的信息比特的平均能量是Eb，编码速率为R(编码后每比特的平均能量为EbR)，则Pykxk可由式1.21计算，

PykxkPyklxkll1nnl11e2EbR22yklxkl2(1.21)

n表示一个码字中信息位与校验位加在一起所有比特的数量。

关于ks和ks的递归计算及其与ks,s的关系，可由图1.1更直观的看出来。这是一个有4种状态的编码，图中的加粗线是在计算中所需要考虑的栅格路径。

图1.1递归计算ks和ks的示意图

用于迭代的MAP算法

正如上章中看到，在Turbo码的译码迭代过程中，每个SISO译码模块输出的信息中一定要有一部分作为下次的先验信息输入，所以要从式1.9计算出LukY分离出所需要的信息。如式1.22我们把它分成三部分，

s,su1k1sks,skskLukYlns,su1k1sks,sks(1.22)

kLukLcyksLeuk其中Lc为信道可靠度（置信度）。在双边带功率谱密度是N0/2的加性高斯白噪声信道下，

Lc4EbR(1.23) N0Luk被称为先验信息。接收到yks，

yksuknk(1.24)

其中，nk是离散的加性高斯白噪声。

Leuk被称为uk的外在(extrinsic)信息。

LeukLukYLukLcykss,suk1k1sks,sks(1.25)

lns,su1k1sks,sksk其中，

Lks,sexpc2yxklkl(1.26) l2n由此看来所得到的后验概率LukY被分成三部分：先验信息Luk、系统比特信息Lcyks和外在信息Leuk：

1、

先验信息Luk，如上文所述，一般由前一次迭代译码输出获得，第一次迭代时，由于无先验信息可用，Luk为零。

2、

系统比特信息Lcyks是从信道中直接获得的关于系统比特uk的信息，当系统的信噪比(EbN0)比较高时，yks在LukY中占用份量就越大，换句话说就是直接从信道中获得的信息就越可靠；反之，就越不可靠。

3、

由式Leuk可以被理解为除了上述两项和uk直接相关的信息之外的信息，1.25和式1.26可以看出，此信息在Turbo码的译码中被用作下一个成员译码器的先验信息输入。

从式1.22可以看出，MAP译码算法实际上用上了所有和uk有关的信息（Luk，

Lcyks，Leuk）来计算uk的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所做的修改是直接在对数域里对ks、ks、ks,s和

LukY进行计算，省去了许多指数和对数运算，大大简化了运算量。

首先定义Aks、Bks和ks，

Aks@lnks(1.27)

Bks@lnks(1.28) ks,s@lnks,s(1.29)

在Max-Log-MAP要用到一重要的近似等式1.30，

lnex1ex1Kexnmaxxi(1.30)

i1Lnmaxg表示取最大值。则，

Aks@lnkslnk1sks,sallslnexpAk1sks,sallsmaxAk1sks,ss(1.31)

Bk1s@lnk1slnksks,sallslnexpBksks,sallsmaxBksks,ss(1.32)

根据式3.15和3.21，ks,s在对数域的计算如式3.33，

L1ks,s@lnks,sCukLukc22yl1nklklx(1.33)

式中C为常数。称ks,s为栅格图中的分支度量(branchmetrics)。

LukY的计算变为加减法运算，如式3.34

s,su1k1sks,skskLukYlns,su1k1sks,sks(1.34) kmaxAk1sks,sBksmaxAk1sks,sBkss,suk1s,suk1可以看出Max-Log-MAP在译uk时，把所有可能的ss的状态转移路径分成两部分：一部分是uk1引起的，一部分是uk1引起的。并在这两部分中分别找出

Ass,sBs为最大值的路径，LLR的计算就是比较这两条路径的差。

k1kk总结Max-Log-MAP的计算步骤就是：通过前向递归计算出Aks（式1.31）；后向递归计算出Bks(式1.32)；用式1.33计算出分支度量ks；再通过式1.34就可计算出比特的LLR。

Max-Log-MAP译码过程极象Viterbi算法，都是要在栅格图中寻找最优路径，不过它还要多寻找一条最有竞争力的次优路径，这条次优路径在k时刻和最优路径给出完全不同的关于uk的判决。

Log-MAP

Log-MAP是对Max-Log-MAP作了一定的修正，由式1.35给出修正方法，

lnex1ex2maxx1,x2ln1ex1x2maxx1,x2fcx1x2其中定义修正函数，

fcx@ln1e(1.35)

x(1.36)

图3.2修正函数fcx的曲线图

fcx的函数图如图1.2所示，

可以看出fcx关于x＝0偶对称，在x5或x5时，fcx非常小。因此在实际计算中可通过查表法完成，Robertson指出只要在这个表中存储8个数据即可，x的范围是0～5，过多的数据存储对译码结果并没有太大的改善。由此看来，Log-MAP算法仅仅比Max-Log-MAP算法多了些查表和加法运算，复杂度仅仅多了一点点，而性能却有较大提高，这将在后续小节的各种译码算法性能比较中看到。

SOVA算法

Viterbi算法也是一种估计无记忆噪声中马尔可夫过程最优的算法，它不同于MAP算法的特点在于其最优的准则不同，它是给定接收序列Y，

%argmaxPXY(1.37) Xx%。 Viterbi算法找出了错误最少的发送序列XSOVA(SoftOutputViterbiAlgorithm)是对原Viterbi算法做了一定的修改，使其适合于Turbo码的迭代译码。所作的修改主要有两个方面：

1、在栅格图中选择最大似然路径时要把先验信息考虑进去；

2、不仅要把每个比特uk是＋1或－1译码出来，同时也要给出uk译码的可靠度，以LLR形式给出LukY，作为“Softoutput”，从中可以获得一些关于uk的先验信息，为下次迭代所使用。这正是此算法被命名为SOVA的原因。

设接收到的码字序列为Yjk，Sk是栅格图中某条路径所经过的所有状态组成的序列，且在k时刻到达状态Sks，Viterbi算法的出发点就是要寻找pSkYjk为最大的路径，被称为幸存路径。选取某条路径的概率是，

sspSkYjkspSk,YjkpYjks(3.38)

s显然pYjk对于所有的路径均一样。因此寻找pSkYjk最大的路径等价于寻找

pSk,Yjk为最大的路径。

s根据贝叶斯公式和s,s的定义式1.8，有

ssspSk,YjkpSk1,Yjkps,YkspSk1,Yjks,s(1.39)

定义分支度量(metric)MSk为，

MSk@lnpSk,YjksssMSlns,s(1.40)

sk1由此看来MSk可以利用前向递规的方法求得，类似于Max-Log-MAP算法中的

sAks的计算。

L1lnks,sCukLukc22yl1nklklx(1.41)

C为常数，计算中可以省去。因此，

MSMSsksk1L1ukLukc22xl1nklykl(1.42)

1比传统的Viterbi算法多了等式右边的第二项ukLuk，利用上了uk的先验信息。

2下面来看一下SOVA算法对Viterbi算法的所作的第二项修改。

°是栅格图中不同于幸存路径的另外一条路径，它也在k时刻到达状态Ss，设Skk换句话说就是在k时刻重合于幸存路径。由于幸存路径是到达状态Sks的累计分支度量最大的路径，所以有式1.43成立，

ss°s0(1.43) kMSkMSks称k为两路径的差异度。

ss°s的正确可靠度，在Sks状态下我们选择路径Sk作为幸存路径而丢弃S可用下面的k概率P(幸存路径,Sks)表示，

P幸存路径,Sks°PSPSPSkssksk(1.44)

需要注意的是，这里假设了编码速率是1/n，即在栅格图中进入每个状态的路径只有两条。当进入每个状态的路径不止两条时，需要从所有非幸存路径中选择度量最大的那一条路径。

根据MSk的定义，并把式1.43带入，则

sP幸存路径,SksesMSksMSksk1eMSeek1esks(1.45)

s由此看来，k时刻正确判决的LLR仅有一个参数k决定。

在Viterbi译码过程中，某时刻2所有的幸存路径一般都是从前某个时刻1的同一路径中分支出来，一般某时刻2与某时刻1的间隔一般最多不超过5～6倍的m个时间单位，其中m为卷积码的约束长度。而这条同一路径正是最大似然路径。因此译比特uk时要等到k5m时刻才作判决，在这5m时间内有许多幸存路径又回归到了最大似然路径上去并随后消失了，而这些路径在k时刻给出uk的判决和最大似然路径给出的判决

有相同的，也有不同的。这些不同的判决影响着我们在最大似然路径上对uk判决的可靠度，因此在求uk的LLR时要把它们考虑进去。可由式1.46来近似计算LukY，

LukYukminisi(1.46)

ik...kiukuk其中uk是最大似然路径上所做的判决值。在i(其中ik...k)时刻重合于最大似然路径的幸存路径在k时刻给出的判决为uki，isi是这些将要消失的幸存路径与最大似然

iuk那些isi当中最小的一个决定。 路径之间的差异度。Hagenauer指出LukY是由uk通过图1.3可以更好的理解关于计算LukY的过程。

图1.3SOVA算法中计算LukY示范图

在图1.3中假设最上面的粗虚线是最大似然路径，可以看出有5条路径（分别标示了数字）都在一定时刻汇合于最大似然路径。现在我们要计算k时刻的LukY，可以看出，最大似然路径对uk的判决是1，而路径1、2、4、5这4条路径对uk的判决是1，路径3对uk所作的判决和最大似然路径的判决是一样。这样在计算LukY时，需要考虑这4条路径，而第3路径就不在考虑之列了。这四条路径和最大似然路径的差异度分

000别是0k、k1、k3、k4，从中找出最小值并乘以1就是要计算的LukY。

3.5各种算法的比较

为了更好地理解这四种算法，在这一节中对这些算法进行比较研究。下面是这些算法的相同点和不同点：

相同点：1、这些算法都接收信道传来的软判决信息和信息比特uk的先验信息作为译码输入，译码输出不仅可以给出判决，而且也可以给出uk的后验概率LLR值(LukY)，可以统称它们为SISO(softinsoftout)算法。

2、从单次译码结果来看，Max-Log-MAP和SOVA都是在栅格图中寻找到了最大似然路径，二者在一定程度上具有一致性。

3、MAP算法和Log-MAP算法在理论基础上是一致的，都是在栅格图中考虑了所有的可能路径。而MAX-Log-MAP是在Log-MAP算法上做了近似，从而省去了大量加法运算。

不同点：1、MAP算法是Turbo码成员编码器的最优的译码算法，Log-MAP算法是把MAP算法转移到对数域内进行计算，这样极大的降低了译码的复杂度。译码过程中，对于每个信息比特uk，它们把栅格图所有可能的路径分成两类，一类为1路径，一类为1路径，所有1路径概率之和与所有1路径概率之和的比值的对数就是要求的uk的后验概率LukY；同样，在计算ks和ks时也要考虑所有可能存在的状态转移。

2、Max-Log-MAP算法的复杂度又比Log-MAP低一些。二者主要区别在于修正函数上。在计算uk的后验概率时，它只考虑两条路径，一条是最大概率的1路径，一条是最大概率的1路径，二者之中有一条是最大似然路径，另一条我们暂时可称其为最具竞争力路径；在译不同时刻的uk时，最大似然路径一般都会不变，只是继续地向后延伸，而最具竞争力路径会不停的改变。在计算Aks和Bks时，也只考虑了最有可能的一种状态转移。

3、SOVA的译码复杂度最低，它的目的很明确，就是要寻找最大似然路径。其计算Aks的方法和Max-Log-MAP一致，不过它不计算Bks。它所比较的两条路径，一条是最大似然路径，但另一条不一定是最具竞争力路径，而是一条给出判决不同于最大似然路径的且会重合于最大似然路径的路径，那些比这更具有竞争力的路径可能在译码

过程中被丢弃了，所以它给出的LukY不如Max-Log-MAP精确，在迭代译码过程中，这样不利于后续比特的译码，这正是SOVA的译码性能比Max-Log-MAP降低的原因。

图1.4给出了这些算法在栅格图中的译码过程，从中可以看出它们的异同点，图中加粗的线条为译码中选择的路径。

图1.4Turbo码各种算法译码示意图

另外，在表1.1中给出了三种算法计算复杂度的比较。MAP由于过于复杂，一般实际中都不大使用，常用Log-MAP算法来替代。Log-MAP算法中的修正函数是由上文中所述的查表法获得，只在表中存了0～5之间的8个数据。表1.1中的M指Turbo码成员编码器的寄存器的长度。表中比较的是译每比特的运算量。

运算 比较 加法 乘法 位比较 查表 Log-MAP 5×2M－2 15×2M＋9 8 5×2M－2 MAX-Log-MAP 5×2M－2 10×2M－11 8 SOVA 3(M+1)+2M 2×2M＋8 8 6(M+1) 表1.1Turbo码各种算法复杂度比较表

从表1.1可以看到，在每比特译出的计算中，Log-MAP算法最复杂，它不仅比MAX-Log-MAP算法多了一些查表的运算，而且也多了一些加法运算。而SOVA算法最简单，但它有一些特殊的运算如位比较运算，这在数字电路里非常容易实现。

图1.5帧长为1648的Turbo码各种译码算法译码性能比较

图1.5示出了帧长是1648的Turbo码在各种算法下的译码性能。从图中可以看出，MAP算法最好，Log-MAP稍微有些差，它和MAP算法的差异很小，有0.1dB左右；Max-Log-MAP算法比MAP算法大概有0.3dB的恶化，而SOVA性能最差，比MAP有0.6dB的差异。

结论

本节给出了各种译码算法的原理，然后对这些算法进行了详细的比较研究。从图1.4中可以清楚的了解到各种算法的工作过程和它们的异同点。通过译码复杂度的比较，得出MAP算法最为复杂，Log-MAP次之，Max-Log-MAP较为简单，SOVA最简单的结论。从仿真结果上看性能比较，MAP算法最好，Log-MAP稍微有些差，Max-Log-MAP算法大概有0.3dB的恶化，而SOVA比MAP有0.6dB的差异。因此在实际运用中，需要对性能和运算量上进行折中考虑，从而决定使用何种算法。