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

Turbo 码的各种译码算法及比较Turbo 码有一重要特点是其译码较为复杂，比常规的卷积码要复杂的多，这种复杂不仅在于其译码要采用迭代的过程，而且采用的算法本身也比较复杂。

这些算法的关键是不但要能够对每比特进行译码，而且还要伴随着译码给出每比特译出的可靠性信息，有了这些信息，迭代才能进行下去。

用于Turbo 码译码的具体算法有：MAP(Maximum A Posterori)、Max-Log-MAP 、Log-MAP 和SOV A(Soft Output Viterbi Algorithm)算法。

MAP 算法是1974年被用于卷积码的译码，但用作Turbo 码的译码还是要做一些修改；Max-Log-MAP 与Log-MAP 是根据MAP 算法在运算量上做了重大改进，虽然性能有些下降，但使得Turbo 码的译码复杂度大大的降低了，更加适合于实际系统的运用；Viterbi 算法并不适合Turbo 码的译码，原因就是没有每比特译出的可靠性信息输出，修改后的具有软信息输出的SOV A 算法，就正好适合了Turbo 码的译码。

这些算法在复杂度上和性能上具有一定的差异，系统地了解这些算法的原理是对Turbo 码研究的基础，同时对这些算法的复杂度和性能的比较研究也将有助于Turbo 的应用研究。

MAP 算法MAP 算法最初是用来估计无记忆噪声下的马尔可夫过程的，它是一种最优的算法。

Bahl 等人于1974年把它用于线性分组码和卷积码的译码中，在用于卷积码的译码时，对于给定接收序列Y ，它不像Viterbi 算法那样以栅格路径上的比特组错误最少为目的，而是以译码出来的符号i x 的错误最少为目的。

即，(){}arg max ii i x x P x Y = (1.1)不过在大多情况下，它和Viterbi 算法的作用是一致的。

由于在卷积码的译码中，MAP 算法要考虑栅格图中的所有可能路径，这样运算量就非常大，实际系统中很少用到。

这样虽然MAP 算法早在1974年就被提出，但一直未被得到充分利用，只有到了1993年Turbo 码被提出来，MAP 算法被用于Turbo 码的译码之后，这种算法才得到广泛的应用。

MAP 算法不仅能译出序列的比特值，在译码的同时还能输出关于每比特译出的可靠性信息。

这种特点正好符合了Turbo 码的迭代译码特性，所以才被用于Turbo 码的译码中。

下面我们来看看MAP 算法是如何用于二进制Turbo 码的译码的。

MAP 算法是要根据接收到的序列Y ，找出每信息比特k u 是“1+”(1)或“1-”(0)的概率，这等同于计算序列Y 下k u 的对数似然比值(LLR)()k L u Y ，如式1.2，()()()1ln 1k k k P u Y L u Y P u Y ⎛⎫=+= ⎪ ⎪=-⎝⎭(1.2)在栅格图中假设前一状态1k S s -'=和当前状态k S s =，输入比特k u 引起s s '⇒的状态转移，根据贝叶斯(Bayes)准则，可由式1.2得式1.3，()()()()()11,111,1,,ln ,,k k k k s s u k k k s s u P S s S s Y L u Y P S s S s Y --'⇒=+--'⇒=-⎛⎫'==⎪= ⎪'==⎝⎭∑∑ (1.3) 上式中(),1k s s u '⇒=+表示所有由1k u =+引起s s '⇒状态转移的集合；同样(),1k s s u '⇒=-表示由1k u =-引起的状态转移的集合。

接收序列Y 可以被分成三部分j k Y <、k Y 和j k Y >，分别表示k 时刻之前接收码字序列、当前接收码字和之后接收码字序列。

所以，()()11,,,,,,j k k j k k k P S s S s Y P s s Y Y Y <>--''=== (1.4) 利用贝叶斯公式可得式1.5，()()()()()()()()()()111,,,,,,,,,,,,j k k j k k k j k j k k j k k j k k k k P S s S s Y P s s Y Y Y P Y s P s s Y Y P Y s P s Y s P s Y s s s s βγα<>--><><-''==='=''=''= (1.5)式1.5中用了式1.6、1.7、1.8的定义，()()11,j k k k s P S s Y α<--''== (1.6)表示接收序列是j k Y <，1k -时刻状态是s '的概率，我们称之为前向概率。

()()j k k k s P Y S s β>== (1.7)表示k 时刻状态为s 且之后接收序列是j k Y >的概率，我们称之为后向概率。

()()1,,k k k k s s P S s Y S s γ-''=== (1.8)(),k s s γ'表示由给定状态s '转移到s 并且此时接收码字为k Y 的状态转移概率。

因此计算LLR 的式1.3可被分成前向概率转、状态转移概率和后向概率三部分，如式1.9所示，()()()()()()()()()()()()()11,111,11,11,1,,ln ,,,ln ,kk kk k k s s u k k k s s u k k k s s u k k k s s u P S s S s Y L u Y P S s S s Y s s s s s s s s αγβαγβ--'⇒=+--'⇒=--'⇒=+-'⇒=-⎛⎫'==⎪= ⎪'==⎝⎭⎛⎫''⋅⋅⎪= ⎪''⋅⋅⎝⎭∑∑∑∑ (1.9)可以看出，用MAP 译码算法译接收序列Y 的关键是要计算出和各时刻有关的所有的()1k s α-'、()k s β，还有所有可能的s s '⇒状态转移的概率(),k s s γ'。

()k s α、()k s β的计算仍旧非常复杂，在下面的推导中我们可以看到()k s α、()k s β的计算可以用递规的方法。

()k s α的计算根据()k s α的定义，有式1.10成立，()()()()11,,,,,,j k j k k k k k j k k k k alls s P S s Y P S s Y Y P S s S s Y Y α<+<<-'===='===∑(1.10)“all s '”表示所有的状态s '。

假设信道为无记忆信道，则(),k s Y 的概率只和前一状态s '有关，而和j k Y <无关。

并利用贝叶斯公式，有式1.11成立，()(){}{}()(){}()()()()11,,,,,,,,,j k k k k k alls kj kj kalls kj kalls k kalls s P Ss S s Y Y P s Y s Y P s Y P s Y s P s Y s s s ααγ<-'<<'<'-''===''=⋅''=⋅''=⋅∑∑∑∑ (1.11)由此看出()k s α可由()1k s α-'前向递归计算得出。

递归计算存在初始化的问题，初始状态()00S α由式1.12给出，()000010S S S α=⎧=⎨≠⎩ (1.12) ()k s β的计算类似()k s α的计算推导，后向概率()k s β也可以由递归计算得出，不过这次是后向递归，()()()()()()()()()11,,,,,j k j k k k j kj k k allsj k k allskkallss P Y s P Y Y s P Ys P Y Y s s P Y s P Y s s s s s ββγ>->->>>'''=='='='=⋅∑∑∑ (1.13)()k s β的初始状态()N N S β由式1.14给出， ()10N N N N S S S β=⎧=⎨≠⎩ (1.14)(),k s s γ'的计算(),k s s γ'计算可根据当前接收码字和先验信息(a-priori )计算得出。

设在编码k 时刻输入信息比特k u ，编码状态由s '转移到s ，并得到码字为k x ，经信道传输后接收到k y ，则()(){}()(){}()()()(),,,,k k k k k k s s P s Y s P Y s s P s s P Y s s P s s P y x P s s γ''''==⋅''=⋅'=⋅ (1.15)概率()P s s '直接由引起状态转移的输入比特k u 的先验概率决定。

定义k u 的先验概率对数似然比()k L u ，()()()1ln 1k k k P u L u P u ⎛⎫= ⎪ ⎪=-⎝⎭(1.16)当()1,1k p u s s '==，则()()()()()1ln ln 11k k k P s s P u L u P u P s s ⎛⎫'⎛⎫== ⎪ ⎪ ⎪ ⎪'=--⎝⎭⎝⎭(1.17) ()()()1k k L uL u e P s s e'=+ (1.18) 当()1,1k p u s s '==-时，则()()()11k k L uL u e P s s e'=-+ (1.19) 设()()/21k k L uL u e eρ=+，则 ()()()()()()/2/2/21,11,1k k k k L u k u L u L u k e p u s s P s s ee p u s s ρρρ⋅-⎧'==+⎪'==⎨'==-⎪⎩(1.20)比特k u 的先验信息()k L u ，一般从上一次译码输出信息中获得的；在第一次译码时，由于没有什么信息可以获得，只有先假设k u 为“1+”(1)或“1-”(0)的概率相同，即()0k L u =。

设信道噪声为高斯白噪声，方差为2σ，所要传输的信息比特的平均能量是b E ，编码速率为R (编码后每比特的平均能量为b E R )，则()k k P y x 可由式1.21计算，()()()22121k k b kl kl nkl kl l E R ny x l P y x P y x σ=⎛⎫-- ⎪⎝⎭===∏ (1.21)n 表示一个码字中信息位与校验位加在一起所有比特的数量。