一種新的聯(lián)合譯碼方案研究

石雅盟，李建平

(中國傳媒大學(xué)信息工程學(xué)院，北京100024)

1 引言

1993 年，Turbo碼由 C.Berrou 等人提出［1］，目前已經(jīng)被廣泛地應(yīng)用于許多通信系統(tǒng)標(biāo)準(zhǔn)中。Turbo碼的譯碼算法主要有三種:對數(shù)最大后驗譯碼算法(Log Maximum A Posteriori，Log-Map)，Maximum Log-Map(Max-Log-Map)算法和軟輸出維特比譯碼算法(Soft-Output Viterbi，SOVA)。Log-Map算法具有較低的誤碼率性能，Max-Log-Map是Log-Map的簡化。相比于Log-Map，后兩種算法具有較低的計算復(fù)雜度，但是Max-Log-Map在誤碼率為10-5時比Log-Map小0.5dB的編碼增益，SOVA則要比Log-Map小0.5-1.0dB的編碼增益?，F(xiàn)已有許多改進的算法來提高Max-Log-Map的性能［2，3］，但是需要增加一些必要的計算復(fù)雜度。本文不改變算法本身，提出一種新的聯(lián)合譯碼算法結(jié)構(gòu)，進一步提高Turbo譯碼的性能。

2 譯碼算法簡介

2.1 MAP譯碼算法

最大后驗概率算法(Maximum A Posteriori，MAP)，也稱BCJR 算法［4］，首次由 Bahl等人于1974年提出。在MAP算法提出后的將近20年時間里，由于其計算量大和硬件實現(xiàn)復(fù)雜性高而一直沒有得到重視。直到1993年Turbo碼的發(fā)明者在其最初的Turbo迭代譯碼方案中采用了修正的MAP算法，相應(yīng)的各種簡化算法也開始不斷出現(xiàn)。MAP算法是基于編碼網(wǎng)格圖的軟輸出譯碼算法，目的是使譯碼輸出比特錯誤概率最小。根據(jù)最大似然譯碼原理，譯碼器的主要任務(wù)就是計算在接收采樣條件下不同發(fā)送符號的概率，即P(uk=u|Y)。而后將接收采樣判決為概率值最大的信息符號，即

u＇=arg(maxu:ujεuP(uj=u|Y)) (1)現(xiàn)定義一個編碼網(wǎng)格圖中邊的概念，也叫做分支，如圖1:

圖1 網(wǎng)格圖中的邊

假設(shè)系統(tǒng)采用BPSK調(diào)制，則發(fā)送符號與碼字的關(guān)系為:

式中，Es為信號平均功率，k時刻譯碼輸出信息比特概率Pk(u;o)為

對于遞歸系統(tǒng)卷積碼編碼器，當(dāng)k時刻狀態(tài)SK已知時，k時刻以后發(fā)生的事件與之前的輸入無關(guān)，等效一個馬爾科夫源。因此，式(3)中聯(lián)合條件概率αk(s)和βk(s)可分別通過前向和后向遞推計算得到

其計算過程如圖2所示。

圖2 αk(s)和βk(s)計算過程

若編碼器的初始狀態(tài)S0和結(jié)束狀態(tài)SN均已知，則上述遞推初值可設(shè)定為

為了防止溢出，一般要將因子歸一化。

式(3)中?k(e)稱為邊度量或分支度量，利用貝葉斯公式，有

式中，第一項為網(wǎng)格圖中分支(邊)的狀態(tài)轉(zhuǎn)移概率，由信息比特的先驗信息La(uk)決定

式中，

第二項P(Xk|e)根據(jù)XK是否與邊e有關(guān)而取值為1或0;最后一項根據(jù)信道模型的不同而有所區(qū)別。例如對于AWGN信道上采用BPSK調(diào)制的傳輸系統(tǒng)，有

對于二元輸入，可以用對數(shù)似然比(LLR)作為判決函數(shù)

MAP算法根據(jù)L(uk)的值進行判決

2.2 Log-Map算法和MAX-Log-Map算法

上面介紹的MAP算法，由于它的運算復(fù)雜度很高，包含了大量的乘法運算，因此給實現(xiàn)帶來了較大困難。所以在實際應(yīng)用中采用的大都是MAP的對數(shù)域算法，可以化乘法為加法，可大大減少運算量如MAX-Log-Map 算法和 Log-Map 算法［5，6］。

在 Log-Map 算法中，Mk(e)、Ak(S)、Bk(S)與MAP 算法中 ?k(e)、αk(s)、βk(s)相對應(yīng)，它們之間滿足對數(shù)關(guān)系

分別代入對應(yīng)公式，最后得到

其中，在Log-Map算法中引入max*(.)操作，定義為

通常，可以對上述max*(.)操作進行變形，對于兩個量變的情況(x和y)，有

max(x，y)為最大值函數(shù)，fc(|x-y|)為修正函數(shù)。當(dāng)x與y的值相差較大時fc(|x-y|)值趨向于0，則上式可以進一步簡化為

此時Log-Map算法轉(zhuǎn)換為MAX-Log-Map算法，計算量進一步降低。

2.3 維特比算法

假設(shè)編碼器送出的碼序列C，經(jīng)過離散無記憶信道傳輸后送入譯碼器的是序列R=C+E，E是信道加上的噪聲序列。譯碼器根據(jù)接受序列R，按最大似然譯碼準(zhǔn)則力圖找出編碼器在網(wǎng)格圖上所走過的路徑，這個過程就是譯碼器計算、尋找最大似然函數(shù)

的過程，或者說譯碼器計算、尋找有最大度量路徑過程，即尋找

的過程。式中，M(R|Cj)=logbP(R|Cj)是Cj的自然函數(shù)，也稱為Cj的路徑度量。

可以將維特比算法步驟總結(jié)如下［7］:

第一步，在時間單元t=m開始，計算進入每一狀態(tài)的單個路徑的部分量度。存儲每一狀態(tài)下的路徑(幸存的)及其量度。

第二步，t增加1。將進入某一狀態(tài)的分支量度與前一時間單元有關(guān)的幸存路徑的量度相加，計算進入該狀態(tài)的所有2k路徑的部分量度。對每一狀態(tài)，比較進入該狀態(tài)的所有2k路徑的量度，選擇具有最大量度的路徑(幸存路徑)，存儲該路徑及其度量，并刪除其他所有路徑。

第三步，如果t＜h+m，重復(fù)步驟2;否則停止。維特比算法執(zhí)行的基本運算是步驟2中的加法、比較和選擇操作。作為一個實際考慮，對每個狀態(tài)，在步驟1和2中存儲的是對應(yīng)于幸存路徑的信息序列，而不是幸存路徑本身，因而當(dāng)算法結(jié)束時，不需要對估計碼字序列進行轉(zhuǎn)化以恢復(fù)估計信息序列。

3 新的譯碼結(jié)構(gòu)設(shè)計

在編碼及調(diào)制解調(diào)方面，均采用經(jīng)典編碼調(diào)制系統(tǒng)方案在譯碼部分，不同于傳統(tǒng)Turbo譯碼的兩個SISO譯碼器并行級聯(lián)結(jié)構(gòu)，我們采用三個譯碼器，前兩個依然按照并行結(jié)構(gòu)級聯(lián)，并且應(yīng)用Log-Map譯碼算法相互進行迭代;添加的第三個譯碼器的輸入有三個:第一個譯碼器輸出的校驗位估計軟值序列Lp1，第二個譯碼器輸出的系統(tǒng)位估計軟值序列Ls以及最后一次更新的外信息序列Le21。第三個譯碼器采用軟輸入軟輸出維特比譯碼算法。最后將譯碼器三的信息軟值序列進行硬判決輸出。譯碼結(jié)構(gòu)如圖3所示。

在此結(jié)構(gòu)中，輸入到譯碼器3的系統(tǒng)位、校驗位軟值已經(jīng)較為精準(zhǔn)，外信息也已多次更新。基于兩種算法的差異，即:Log-Map算法是逐比特譯碼，首先能獲得比較好的性能，維特比算法利用網(wǎng)格圖選擇最優(yōu)路徑譯碼，再將Log-Map中沒有譯出來的比特更正，結(jié)合兩者優(yōu)勢，聯(lián)合譯碼性能理論上可以獲得更低的誤碼率。

圖3 Log-Map與viterbi聯(lián)合譯碼結(jié)構(gòu)圖

4 仿真結(jié)果與分析

首先給出以信噪比為橫坐標(biāo)，交織長度為1024的Log-Map與聯(lián)合譯碼算法性能比較，生成多項式(7，5)如圖4所示。

圖4 Log-Map與聯(lián)合譯碼算法性能比較1

圖4所示分別為第1、3、5和10次兩種譯碼算法性能曲線。可以看出，在10次迭代以前，聯(lián)合譯碼性能能夠提高0.1-0.2db編碼增益。通過實驗進行10次及大于10次仿真，雖然譯碼器3仍可糾正Log-Map譯碼結(jié)果中個別比特錯誤，但此時Log-Map譯碼算法在10次迭代以后本身誤碼率較低，所以維特比譯碼進一步譯出的錯誤比特就更為稀少。如圖5所示為以迭代次數(shù)為橫坐標(biāo)的兩種譯碼結(jié)構(gòu)性能比較結(jié)果。

圖5 Log-Map與聯(lián)合譯碼算法性能比較2

在分析此實驗結(jié)果前先介紹Turbo譯碼過程的幾個經(jīng)典的動力學(xué)分析成果。Richardson［8］首先將Turbo譯碼過程視為一個動力學(xué)系統(tǒng)進行研究，并發(fā)現(xiàn)了不動點的存在。之后，Agrawal［9］進一步分析出這些不動點的唯一性和穩(wěn)定性，在此基礎(chǔ)上將整個SNR區(qū)域分為三個部分并發(fā)現(xiàn)了分岔現(xiàn)象。通過雅克比矩陣特征值的情況我們能夠判定出現(xiàn)分岔的具體類型。如果倍周期分岔出現(xiàn)，那么相應(yīng)的奇異區(qū)內(nèi)為周期二軌道。如果切分岔出現(xiàn)，那么Turbo譯碼算法不經(jīng)歷中間奇異區(qū)直接收斂到清晰不動點。最為復(fù)雜的是Neimark-Sacker分岔，奇異區(qū)內(nèi)首先出現(xiàn)的是準(zhǔn)周期軌道，緊接著周期三的出現(xiàn)預(yù)示著混沌軌道的存在。選取合適的交織長度N，將SNR從負(fù)無窮逐漸增大，就可以得到上述所提的三個區(qū)域，即不確定不動點、奇異區(qū)和清晰不動點。

簡單的來說，經(jīng)過大量實驗統(tǒng)計，Turbo譯碼在低信噪比時會出現(xiàn)三種譯碼結(jié)果:1、隨著譯碼迭代次數(shù)增加，錯碼個數(shù)逐漸收斂在一個清晰不動點上;2、由于譯碼算法本身的某種結(jié)構(gòu)特性，會使一些幀的個別比特十分難譯，這樣就造成了錯碼個數(shù)為那些難譯的比特數(shù)，即收斂在了一個不確定不動點上;3、除了以上兩種結(jié)果，還會有個別被稱為壞幀的情況存在。這些幀的錯碼個數(shù)不收斂，在一個不確定不動點周圍震蕩，錯碼個數(shù)較多，使得誤碼率較低。但是這種奇異區(qū)只出現(xiàn)在低信噪比條件下，當(dāng)信噪比升高，基本只出現(xiàn)前兩種情況。

聯(lián)合譯碼就是利用了在低信噪比時出現(xiàn)的奇異區(qū)，譯碼器三可以繼續(xù)將奇異區(qū)內(nèi)的錯碼糾正來使曲線降低。但當(dāng)譯碼次數(shù)增大或者信噪比更高時，聯(lián)合譯碼的性能就表現(xiàn)不突出了。即，如圖5，這是在0.7db下的仿真，可以看出在10次迭代左右，聯(lián)合譯碼即使能稍微降低Log-Map性能曲線，但由于此時奇異區(qū)壞幀少，而維特比又不能繼續(xù)譯出不確定不動點的錯誤比特，在數(shù)據(jù)量很大的時候，聯(lián)合譯碼所帶來的編碼增益只有0.03db。

5 結(jié)束語

本文首先介紹了三種重要的譯碼算法，然后在傳統(tǒng)Turbo譯碼結(jié)構(gòu)上進行改進，提出了一種新的聯(lián)合譯碼算法。實驗證明，在10次迭代以前，至少能夠獲得0.1dB的編碼增益，降低了誤碼平臺。

在對Log-Map譯碼算法的研究中，在低信噪比時發(fā)生的奇異區(qū)現(xiàn)象較為明顯，假設(shè)能在分析透徹算法的情況下，修改原有的算法，降低奇異區(qū)的誤碼率或者使其收斂是一個值得研究的課題。

［1］Berrou C，Glavieux A，Thitimajshima P.Near Shannon limit error-correction coding and decoding:Turbo-codes［C］.Proc IEEE Int Conf on Communications，Geneva，Switzerland，1993:1064-1070.

［2］Talakoub S，Sabeti L，Shahrrava B，Ahmadi M.An improved Max-Log-Map algorithm for Turbo decoding and Turbo equalization［J］.IEEE Trans Instrum Meas，2007，56(3):1058-1063.

［3］Park S J.Combined Max-Log-Map and Log-Map of Turbo codes［J］.IEE Electronics Letters，2004，40(4):251-252.

［4］Bahl L R，Cocke J，Jelinek F，Raviv J.Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate［J］.IEEE Trans Inform Theroy，1974，20(2):284-287.

［5］Erfanian J，Pasupathy S，Gulak G.Reduced Complexity Symbol Detectors with Parallel Structures for ISI Channels［J］.IEEE Transaction on Communication，1994，42(234):1661-1671.

［6］Pietobon SS.Efficient Implementation of Continuous MAP Decoders and A Synchronization Technique for Turbo Decoders［C］.Int Symp on Information Theory and Its Application，1996，Victorial，BC:586-589.

［7］Shu Lin，Daniel J.Costello，J.Error Control Coding［M］.晏堅，等，譯.北京:機械工業(yè)出版社，2007:343.

［8］Richardson.The Geometry of Turbo-Decoding Dynamics［J］.IEEE Trans Inform Theory，2000，46(1):9-23.

［9］Dakshi Agrawal，Alexander Vardy.The Turbo Decoding Algorithm and Its Phase Trajectories［J］.IEEE Trans.Informati on Theory，2001，47(2):699-722.