馬媛媛 彭娜

摘要：本論文旨在研究Turbo碼的幾種迭代譯碼算法，包括Log-MAP譯碼算法和Max-Log-MAP譯碼算法。在介紹Turbo碼基礎(chǔ)并推導(dǎo)Turbo碼的各種譯碼算法（Max-Log-MAP算法、Log-MAP算法和SOVA算法）的原理后，通過性能仿真，我們分析了迭代次數(shù)、交織長度等參數(shù)對Turbo碼的糾錯能力的影響，并橫向比較了三種算法的性能，從而得出結(jié)論。

關(guān)鍵詞：級聯(lián)碼;Turbo碼;交織器;Log-MAP算法;Max-Log-MAP算法

中圖分類號：TN929 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2018）12-0110-03

1 Turbo碼的譯碼器

一般情況下，在單個傳統(tǒng)編碼的譯碼器的最后獲取到的是硬判決譯碼比特，但是Turbo碼譯碼算法不局限于在譯碼器中通過的是硬判決[1]。Turbo碼一般是由兩個分量碼經(jīng)過不同交織后對同一信息序列進(jìn)行編碼，所以譯碼算法采用軟判決信息代替了硬判決可以更好的利用譯碼器之間的信息。

本文推導(dǎo)Turbo碼的各種譯碼算法（Log-MAP算法、Max-Log-MAP算法和SOVA算法）的原理，通過性能仿真，分析迭代次數(shù)、交織長度等參數(shù)對Turbo碼的糾錯能力的影響，對不同算法進(jìn)行性能仿真對比，對采用那種算法更優(yōu)得出結(jié)論。

2 譯碼算法

2.1 Log-MAP算法

MAP算法將Turbo碼的兩個編碼器一起使用反饋碼的結(jié)構(gòu)還利用性能優(yōu)異的卷積碼，并且達(dá)成軟輸入軟輸出和遞推迭代譯碼。MAP算法實施工程量大，為了避免復(fù)雜操作的數(shù)目和數(shù)字表示問題[2]，Log-MAP算法對MAP修改直接在對數(shù)域里對對，，和進(jìn)行計算，去除了大量的指數(shù)和對數(shù)運算，很大程度上減少了計算復(fù)雜度，提高了運算速率。

=2

（1）

對q（·）=1得到下面的表達(dá)式：

=++

+K? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

可以忽略常數(shù)K。

對于lnαk（sk），我們得到：

lnαk（Sk）=

-

（3）

對dk一個先驗的對數(shù)似然比（LLR）簡稱為L（dk）。在式（2）中確定一個先驗信息。

如果：

q（dk=1|Sk，Sk-1）=1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（4）

那么：

L（dk）==? ? ? ? ? ? ? （5）

所以：

=? ? ? ? ? ? ?（6）

對的近似可以在式（12）中找到引用：

≈? ? ? ? ? ? （7）

如果：

（8）

那么：

L（dk）==? ? ? ?（9）

因而，

=? ? ? ? ? ? ? ? ? ? ? （10）

類似地，

≈? ? ? ? ? ? ? ? ? ? （11）

由于近似的算法，Log-MAP算法比起MAP算法是次優(yōu)的，其產(chǎn)生的是一個較低的軟輸出。

=max（δ1，δ2）+=max （δ1，δ2）+? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（12）

其中，定義是修正函數(shù)。由此，

==

+=max（δ，δn）+? ? ? ? ? ?（13）

其中，Δ==eδ.通過計算fc（x），失去了一些Max-Log-MAP的低復(fù)雜度[3]。

2.2 Max-Log-MAP算法

Log-MAP算法仍然需要很大的計算量，通過下面的表達(dá)式再次減少計算量：

（14）

可以通過連續(xù)使用n-1個最大函數(shù)只計算兩個值。定義：

=? ? ?（15）

，? ? ? ? ? ? （16）

得到：

≈

-+? ? ? ? （17）

類似地，

≈

-? ? ? ? ?（18）

這就是更進(jìn)一步簡化了Log-MAP算法的Max-Log-MAP算法。

類似的：

≈

-+? ? ? （19）

2.3 SOVA算法

維特比算法（Viterbi）也是一種估計在無記憶噪聲條件下馬爾科夫過程最優(yōu)的算法，它區(qū)別于MAP算法的特點在于最優(yōu)的準(zhǔn)則不同它是給定接收序列，維特比算法找出了錯誤最少的發(fā)送序列[10]。SOVA（Soft output Viterbi Algorithm）是對原維特比算法做了一些修改，使其適合于Turbo碼的迭代譯碼。所做的修改主要是以下兩個方面：

第一，選擇柵欄圖中的最大似然路徑時要考慮先驗信息;

第二，再把每個比特uk是“+1”（1）或“-1”（0）譯碼出來的同時，給出uk譯碼的可靠度，即，以LLR形式給出L（uk），作為軟輸出，從中可以獲取關(guān)于uk的先驗信息，為下次迭代所使用。

3 性能仿真

3.1 不同迭代次數(shù)下性能的仿真

Turbo碼的譯碼性能極其優(yōu)異主要歸結(jié)于Turbo碼的循環(huán)迭代譯碼結(jié)構(gòu)。各個譯碼單元彼此之間傳遞外信息，該外信息作為先驗概率交付于下一次迭代譯碼。以Max-Log-MAP算法為例，在交織長度為640，采用隨機交織器，并且刪余后碼率為1/2的條件下，采用控制變量法仿真對比不同迭代次數(shù)下的性能差異。結(jié)果如圖1所示。

由仿真結(jié)果中分析對比可知，最初幾次迭代次數(shù)的增加很大程度上提高了Turbo碼的譯碼性能，然而從增加到五次迭代以后，再增加迭代次數(shù)增益就變得很小，如圖中第五次和第七次的譯碼性能差不多。在硬件流水線結(jié)構(gòu)中，迭代次數(shù)很大程度上決定了硬件規(guī)模，迭代次數(shù)越多，所用硬件規(guī)模越大，綜合考慮應(yīng)該選擇5次迭代才能達(dá)到更好的譯碼性能。

3.2 不同交織長度下譯碼性能的仿真

從Turbo碼的性能分析得到，交織長度也是影響Turbo碼譯碼性能的重要原因之一。交織長度增加使得Turbo碼的性能就越接近Shannon極限。同樣Max-Log-MAP算法為例以再次采用控制變量法仿真對比不同交織長度的性能差別得出結(jié)論。在迭代次數(shù)為5，采用隨機交織器，并進(jìn)行刪余，碼率為1/2的條件下，得出結(jié)果如圖2所示。

從圖2中對比分析可知，加長交織長度能夠明顯的提高Turbo碼的性能，如圖2中所示，交織長度為120的曲線明顯高于其他曲線，即性能遠(yuǎn)差于其他。

3.3 不同譯碼算法性能比較

為了更詳細(xì)的了解MAX-Log-MAP、Log-MAP和SOVA這三種算法，下面對這些算法進(jìn)行研究討論，具體來研究這些算法的相同點與不同點：

相同點：

（1）四種算法的譯碼輸入都是從接收信道傳來的軟判決信息與信息比特uk的先驗信息，而其譯碼輸出可以做出判決的同時給出uk的后驗概率LLR的值（L（uk）），這可以統(tǒng)稱它們?yōu)镾ISO（soft in soft out）算法[8]。

（2）單次譯碼結(jié)果中，Max-Log-MAP算法和SOVA算法都是尋找在柵欄圖中的最大似然路徑。

（3）為減少大量的加法運算量，MAX-Log-MAP算法在Log-MAP算法上做了近似。在理論的基礎(chǔ)上二者基本相同，都是在柵欄圖中考慮所有有可能的路徑。

不同點：

（1）在Turbo碼譯碼中，MAP算法是其最優(yōu)的譯碼算法，Log-MAP算法在對數(shù)域內(nèi)計算法MAP算法很大程度減少了譯碼的運算量。

（2）Max-Log-MAP算法復(fù)雜度比Log-MAP低主要在于修正函數(shù)上。在計算uk的后驗概率時，Max-Log-MAP算法只考慮兩條路徑，其中一條是最大概率的-1路徑，另一條是最大概率的+1路徑，在計算αk（Sk）和βk（Sk）的時候，只考慮到了最有可能的一種狀態(tài)轉(zhuǎn)移。

（3）SOVA算法尋找到最大似然路徑的譯碼所以復(fù)雜度相對來說最低。它計算方法αk （Sk）的方法和Max-Log-MAP算法是一致，但不同的是，它不計算βk（Sk）。

在參數(shù)相同的條件下，仿真這三種算法，圖3所示在交織長度是1024，采用隨機交織器，刪余后碼率為1/2的條件下，Turbo碼三種譯碼算法性能比較。

從仿真結(jié)果進(jìn)行性能比較，性能從優(yōu)到次為Log-MAP，Max-Log-MAP，SOVA。通過譯碼復(fù)雜度（仿真運算時間）則正好相反。由此看來，Log-MAP算法只是比Max-Log-MAP算法多了些查表和加法運算，增加了計算量，而性能也有較大的提高。

4 結(jié)語

本文推導(dǎo)出了各種譯碼算法的原理，通過在這些算法下性能的仿真可知，迭代次數(shù)初始增加迭代性能改善，迭代到5次之后性能相差不大。增大交織長度可改善Turbo碼的性能。最后對比各種算法的工作過程和異同點，從仿真結(jié)果上看性能比較從優(yōu)到次依次為，Log-MAP，Max-Log-MAP，SOVA。譯碼復(fù)雜度（仿真運算時間）則正好相反。綜上所述，在實際運用中決定使用何種算法，需要折中考慮其性能和運算量。

參考文獻(xiàn)

[1]王視環(huán).LTE中Turbo碼內(nèi)部交織器的研究[J].南京郵電大學(xué)學(xué)報（自然科學(xué)版），2010，30（4）：90-94.

[2]Patrick Robertson， Emmanuelle Villebrun ，Peter Hoeher， A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain， IEEE International Conference on Communications （ICC'95）[C].1995：1009-1013.

[3]Jason P. Woodard and Lajos Hanzo. Comparative Study of Turbo Decoding Techniques： An Overview[J].IEEE Transactions on Vehicular Technology，2000， 49（6）：2208-2233.

[4]Patrick Robertson. Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic （Turbo） Codes[C]. Global Telecommunications Conference （GLOBECOM '94），1994：1298-1303.

[5]賴克中.CDMA2000家庭基站與Turbo編碼技術(shù)研究[J].移動通信.2009（5）：50-53.

[6]何海建.基于OFDM技術(shù)電力線通信系統(tǒng)的編碼方案的研究[D]. 東南大學(xué)碩士學(xué)位論文.2006.

[7]王育民，李暉，梁傳甲.信息論與編碼理論[M].北京：高等教育出版社，2005.

[8]武冬冬，趙剛.Turbo碼的幾種譯碼算法及性能比較[J].儀器儀表用戶，2008（3）：98-100.

Encoding and Decoding of Turbo Code and Its Performance Simulation

MA Yuan-yuan， Peng Na

（Information Engineering school， Changan University， Xian Shaanxi 710064）

Abstract：This article is to study several iterative decoding algorithms of Turbo code， including LOG-MAP decoding algorithm and MAX-LOG-MAP decoding algorithm. After introducing the fundamentals of Turbo code and deriving various decoding algorithms （Max log map algorithm， log map and SOVA algorithm） of turbo code， simulations of these decoding algorithms are performed. Based on the simulation results， we analyze the impact of iteration number and interleaver length on the error correcting capabilities of Turbo codes. Horizontal comparisons of the performances of these three kinds of decoding algorithms are also made， and get the conclusions。

Key words：concatenated code; Turbo code， interleaver; Log-MAP algorithm; Max-Log-MAP algorithm