SF-MAX-Log-MAP并行譯碼算法及其應(yīng)用研究

孫增友，張利杰，田 勇

(東北電力大學(xué)信息工程學(xué)院，吉林吉林132012)

Turbo碼誕生于1993年，是由法國(guó)的Berrou［1］等人首次提出的。由于其解碼性能非常接近于Shannon理論極限，Turbo碼成為了第三代移動(dòng)通信的信道編碼方案之一。為滿足移動(dòng)用戶的需求以及應(yīng)對(duì)其他通信技術(shù)的挑戰(zhàn)，3GPP提出了從WCDMA、HSPA到LTE的演進(jìn)方案。由于3GPP LTE支持高達(dá)100 Mbps的峰值速率，而Turbo最大碼塊長(zhǎng)達(dá)6 144 bit。當(dāng)碼塊較長(zhǎng)時(shí)，若采用串行譯碼方式，其實(shí)現(xiàn)的復(fù)雜度高，延時(shí)大，采用并行譯碼不失為一種較好的選擇。

文章在闡述Turbo碼的串行和并行譯碼結(jié)構(gòu)的同時(shí)，探討了SF-MAX-Log-MAP算法的優(yōu)越性，將其應(yīng)用于分塊并行的Turbo譯碼算法中，并在LTE系統(tǒng)中進(jìn)行了分析。

1 串行譯碼結(jié)構(gòu)

1.1 Turbo 譯碼結(jié)構(gòu)

Turbo譯碼需采用遞歸迭代方法。為使Turbo碼達(dá)到較好的性能，分量譯碼器必須采用SISO算法，從而實(shí)現(xiàn)迭代譯碼過(guò)程中軟信息在分量譯碼器之間的交換。

如圖1所示:Turbo譯碼器的串行結(jié)構(gòu)，在第一次迭代過(guò)程中，子譯碼器1由信息位xs和校驗(yàn)位sp作為輸入，外信息Le(dk1)作為輸出，子譯碼器2以經(jīng)過(guò)交織的信息位xs'、xp2和經(jīng)過(guò)正交織的E12作為輸入，外信息Le(dk2)和硬判決值作為輸出。在第二次迭代過(guò)程中，信息位xs、校驗(yàn)位xp1和經(jīng)過(guò)反交織的Le(dk2)作為輸入，這樣周而復(fù)始進(jìn)行下去，直到達(dá)到最大迭代次數(shù)。此時(shí)子譯碼器2得到對(duì)最大似然函數(shù)值(LLR)的硬判決輸出值s'。

圖1 Turbo譯碼器結(jié)構(gòu)

1.2SF-MAX-Log-MAP 算法

Forney等人證明了最優(yōu)的軟輸出譯碼器是后驗(yàn)概率(APP)譯碼器［2］，其中MAP(最大后驗(yàn)概率)算法最為經(jīng)典。最大后驗(yàn)概率(MAP)譯碼算法是1974年由Balh，Cocke，Jelinek和Raviv共同提出的，因此也稱為BCJR算法［3］。它是基于網(wǎng)格的軟入軟出譯碼算法，譯碼準(zhǔn)則是在噪聲信道下對(duì)馬爾可夫過(guò)程的狀態(tài)及輸入輸出進(jìn)行逐一估計(jì)。它可以準(zhǔn)確地計(jì)算每一信息比特的后驗(yàn)概率，但由于MAP算法包含了大量的指數(shù)和乘法運(yùn)算，難以實(shí)現(xiàn)。若將其轉(zhuǎn)換到對(duì)數(shù)域，可變乘法為加法。后來(lái)在對(duì)數(shù)域?qū)AP算法進(jìn)行了修正。一種為L(zhǎng)og-MAP算法，另一種為MAX-Log-MAP算法。

MAX-Log-MAP算法相比較與MAP算法實(shí)現(xiàn)比較簡(jiǎn)單，但是卻存在著性能差距。根據(jù)文獻(xiàn)［4］由于MAX-Log-MAP算法在計(jì)算過(guò)程中對(duì)Jacobian Logarithm算法，式(1)進(jìn)行了近似，忽略了修正函數(shù)

(1+e-|y-x|)，放大了子譯碼器的外信息，為改善MAX-Log-MAP算法的性能，可以在MAX-Log-MAP算法中對(duì)子譯碼器外信息乘以一個(gè)尺度因子Sp(0＜Sp＜1)，使得子譯碼器外信息逼近MAP算法中的子譯碼器外信息LeMAP(dk)，且當(dāng)Sp=0.7時(shí)，譯碼性能最好。此時(shí)外信息為:

此算法即為SF-MAX-Log-MAP算法。它使Turbo碼在較小的譯碼復(fù)雜度情況下，達(dá)到與Log-MAP算法接近的誤碼率性能。這一性能改進(jìn)具有現(xiàn)實(shí)的意義。

2 并行譯碼結(jié)構(gòu)

由Turbo碼的串行譯碼過(guò)程可以看出，Turbo碼的譯碼時(shí)延主要由兩部分［6］:一是譯碼等待時(shí)延，串行譯碼器要等到整個(gè)數(shù)據(jù)塊結(jié)束后方可譯碼，二是譯碼計(jì)算時(shí)延，計(jì)算量越大，時(shí)延也就越大。為減小時(shí)延，S.Yoon等人提出了一種通過(guò)子塊間交換信息來(lái)提高譯碼性能的分塊并行譯碼算法［7］。該算法中，若信息幀長(zhǎng)為N，各個(gè)子塊長(zhǎng)為W，則所分子塊數(shù)為M，。與M組子譯碼器相對(duì)應(yīng)，每個(gè)子譯碼器進(jìn)行獨(dú)立譯碼，M為譯碼并行度。這種簡(jiǎn)單的分塊并行譯碼算法的譯碼時(shí)間縮短為串行譯碼的，但由于在譯碼過(guò)程中，各子塊之間相互獨(dú)立，沒(méi)有充分利用碼元之間的外信息，與串行碼相比，譯碼性能有很大損失。

為充分利用碼元之間的信息，J.KIM，H.PARK等人提出一種通過(guò)子塊間重疊一部分碼元來(lái)提高譯碼性能的算法［8］，該算法將長(zhǎng)度為N的碼塊分解為M個(gè)子塊，N=M×W，相鄰子塊之間有2V碼元相互重疊。其譯碼結(jié)構(gòu)如框圖2。從圖2可發(fā)現(xiàn)，在整個(gè)碼塊中，子塊1和子塊M的長(zhǎng)度為W+V，其余子塊長(zhǎng)度為W+2V。以子塊2為例，重疊算法中子塊長(zhǎng)度比簡(jiǎn)單分塊并行譯碼算法延長(zhǎng)了2V碼元，每次迭代中，對(duì)這2V碼元進(jìn)行計(jì)算都有利于提高前后向遞推變量的計(jì)算。V越大，計(jì)算量越大，計(jì)算出的前向和后向遞推量越準(zhǔn)確，譯碼性能也就越好。

圖2 子塊重疊的并行譯碼結(jié)構(gòu)

3 改進(jìn)的并行譯碼算法——SF-MAX-Log-MAP并行譯碼算法

MAP算法計(jì)算量較大，Log-MAP算法把乘法運(yùn)算轉(zhuǎn)換為對(duì)數(shù)域的加法運(yùn)算，比MAP算法更有利于實(shí)現(xiàn)。盡管如此，進(jìn)一步簡(jiǎn)化Log-MAP算法和降低Log-MAP對(duì)存儲(chǔ)空間的要求對(duì)算法的實(shí)現(xiàn)具有重要意義。MAX-Log-MAP算法則進(jìn)一步簡(jiǎn)化了計(jì)算量，但系統(tǒng)誤碼率變大了，在誤碼率為10-6時(shí)編碼增益比MAP算法降低了0.3～0.4 dB［9］。改進(jìn)的SF-MAX-Log-MAP算法在相同的誤碼率情況下編碼增益只比MAP算法相差0.1 dB，編碼增益大約提高了0.22 dB［10］，更好的實(shí)現(xiàn)了譯碼性能和計(jì)算量的折中。若是將SF-MAX-Log-MAP算法替代Log-MAP并行譯碼算法中的Log-MAP算法，則可實(shí)現(xiàn)譯碼時(shí)延小，計(jì)算量小，誤碼率低，滿足LTE系統(tǒng)對(duì)誤碼率低和延遲小的要求。

下面對(duì)SF-MAX-Log-MAP并行譯碼算法進(jìn)行了簡(jiǎn)單闡述。

首先根據(jù)圖2，將幀長(zhǎng)為N的輸入數(shù)據(jù)分割為M個(gè)子塊，相鄰子塊重疊長(zhǎng)度為V。由對(duì)數(shù)據(jù)的分塊處理情況可知，第一子塊的前向遞推初始值和最后一個(gè)子塊的后向遞推初始值是確定的，分別為:

然后，按照以下SF-MAX-Log-MAP算法計(jì)算前向、后向遞推公式以及分支轉(zhuǎn)移概率，最后對(duì)最大似然函數(shù)值進(jìn)行硬判決，輸出譯碼結(jié)果。

外信息輸出為:

最大似然函數(shù)值為:

4 性能仿真

通過(guò)MATLAB仿真，驗(yàn)證了此改進(jìn)算法的有效性。并就LTE系統(tǒng)中Turbo碼的誤碼率性能進(jìn)行了研究，分析了其關(guān)鍵參數(shù)(交織長(zhǎng)度、并行度、交疊長(zhǎng)度)對(duì)譯碼性能的影響。仿真相關(guān)信息如下:

編碼方案:LTE中的Turbo碼編碼方案

其中分量碼為8狀態(tài)遞推系統(tǒng)卷積碼，生成多項(xiàng)式為［D3+D2+1，D3+D2+D+1］，碼率為1/3，

調(diào)制方式:BPSK

信道模型:AWGN

譯碼算法:SF-MAX-Log-MAP并行譯碼算法

迭代次數(shù):2

4.1 譯碼算法比較

如圖3(a)所示:為并行度為2和重疊長(zhǎng)度L=32的情況下，三種并行譯碼算法的性能比較。在三種并行譯碼方式中Log-MAP并行譯碼算法性能最好，MAX-Log-MAP并行譯碼算法性能與它有較大的差距，而SF-MAX-Log-MAP并行譯碼算法改善了這種性能差距。因此提出的SF-MAX-LOG-MAP并行譯碼算法是可行的。

圖3 不同譯碼算法的譯碼性能比較

如圖3(b)所示為:交織長(zhǎng)度(碼長(zhǎng))為1 024的情況下，分別采用串行和并行方式進(jìn)行譯碼時(shí)，Turbo碼的誤碼率性能。從此圖中可以看出，采用并行譯碼結(jié)構(gòu)，Turbo碼的性能有一定的損失。但這種損失非常小，因此在LTE系統(tǒng)中采用并行譯碼結(jié)構(gòu)是可行的。

4.2 交織長(zhǎng)度的影響

圖4所示仿真圖可以看出:在譯碼并行度為4，交疊長(zhǎng)度為32的并行譯碼過(guò)程中，交織長(zhǎng)度為2 048的碼塊比交織長(zhǎng)度為1 024的誤碼率低，譯碼性能好。因此，在相同的并行度和交疊長(zhǎng)度條件下，交織長(zhǎng)度越長(zhǎng)，譯碼性能越好。這是因?yàn)樵诓⑿卸炔蛔兊那闆r下，交織長(zhǎng)度越長(zhǎng)，編碼器輸出的碼間自由距離越大，碼抵抗突發(fā)錯(cuò)誤的能力越強(qiáng)，譯碼性能也就越好。

4.3 并行度的影響

圖4 交織長(zhǎng)度對(duì)Turbo碼誤碼性能的影響

圖5 并行度對(duì)Turbo碼誤碼性能的影響

圖6 交疊長(zhǎng)度對(duì)譯碼性能的影響

圖5所示:在交織長(zhǎng)度為2 048和交疊長(zhǎng)度為32的并行譯碼過(guò)程中，若采用的并行度分別為8和4，則兩情況的誤碼率基本吻合?？紤]到并行度越大，系統(tǒng)的復(fù)雜度越大，費(fèi)用越高，采用并行度為4的譯碼器比較合適。因此，LTE采用并行譯碼方案時(shí)，不僅應(yīng)考慮譯碼效率還需考慮占用的硬件資源及系統(tǒng)的復(fù)雜性。

4.4 交疊長(zhǎng)度的影響

圖6中所示為:在交織長(zhǎng)度和并行度相同的情況下，交疊長(zhǎng)度分別為12、32和64的誤碼性能仿真。從仿真圖中可以看出:當(dāng)交疊長(zhǎng)度L=12時(shí)譯碼性能最差，L=32和L=64時(shí)譯碼性能基本吻合。由此，當(dāng)交疊長(zhǎng)度較小時(shí)，增大交疊長(zhǎng)度可以改善譯碼性能，但當(dāng)增到一定程度時(shí)，并不能改善譯碼性能。因此，在并行譯碼過(guò)程中應(yīng)選擇較合適的交疊長(zhǎng)度，若交疊長(zhǎng)度太小，譯碼性能不理想;交疊長(zhǎng)度過(guò)大，計(jì)算量也越大，不利于降低譯碼時(shí)延。

5 結(jié) 論

在Turbo碼的Log-MAP并行譯碼算法和SF-MAX-Log-MAP算法的基礎(chǔ)上，對(duì)它們進(jìn)行了結(jié)合，提出了SF-MAX-Log-MAP并行譯碼算法。通過(guò)仿真表明:此算法在減少了大量運(yùn)算量的同時(shí)，保持了Log-MAP并行算法的譯碼性能。在LTE系統(tǒng)中，當(dāng)Turbo碼長(zhǎng)較大時(shí)，選擇合適的并行譯碼算法可以降低譯碼時(shí)延。此并行譯碼算法需確定合適的并行度、交疊長(zhǎng)度，且在滿足誤碼率和時(shí)延要求的情況下，需兼顧考慮譯碼系統(tǒng)占用的硬件資源，以降低Turbo譯碼系統(tǒng)費(fèi)用及復(fù)雜度。

［1］C BERROU，A.Glavieux and P.Thitimajshim.Near Shannon Limit Error-Correcting Coding and Decoding:Turbo-Codes［C］.IEEE Int.Conf.on Communications，1993:1064 - 1070.

［2］劉東華.Turbo碼在無(wú)線移動(dòng)通信系統(tǒng)中的應(yīng)用［J］.廣東通信技術(shù)，2001，21(2):38-42.

［3］BAHL L R，COCKE J，JELINEK F，et al.Optimal decoding of linear codes for minimizing symbol error rate［C］.IEEE Transactions on Information Theory，1974:284 -286.

［4］L.PAPKE.P.ROBERTSON，and E.VILLEBRUN.’Improved decoding with the SOVA in a parallel oncatenated(Turbo-code)scheme，’in Proc，IEEE Intenarional Conference on Communications(ICC’96)［C］，Dallas，Tex，USA，June，1996(1):102 -106.

［5］J.KIM，H.PARK，B.KIM and S.PARK.Mod ed enhanced max-log-maximum aposteriori algorithm using variable scaling factor［C］.IET Commitafion，2007:1061 -1066.

［6］陳雷，田曉燕.時(shí)延改進(jìn)的Turbo碼譯碼算法［C］.1944-2011 China Academic Journal Electronic Publishing House.

［7］YooN S，BAR-NESS Y.A parallel MAP algorithm for low latency Turbo Decoding［J］.IEEE ommuncate，2002，6(7):288 -299

［8］H SU，I WANG C.A Parallel decoding scheme for Turbo codes［C］.Proc ISCCA98，1998，4(6):445 -448.

［9］VOGT J，F(xiàn)INGER.AN Improving the Max-Log-MAP Turbo decoding［J］.Electronics Letters，2000，36(23):1937 -1939.

［10］汪汗新，葉俊民.基于Turbo碼的Max-Log-MAP譯碼算法的改進(jìn).現(xiàn)代電子技術(shù)［J］.2003，160(16):39-41.