SF-MAX-Log-MAP并行譯碼算法及其應用研究

孫增友，張利杰，田 勇

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

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

文章在闡述Turbo碼的串行和并行譯碼結構的同時，探討了SF-MAX-Log-MAP算法的優越性，將其應用于分塊并行的Turbo譯碼算法中，并在LTE系統中進行了分析。

1 串行譯碼結構

1.1 Turbo 譯碼結構

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

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

圖1 Turbo譯碼器結構

1.2SF-MAX-Log-MAP 算法

Forney等人證明了最優的軟輸出譯碼器是后驗概率(APP)譯碼器［2］，其中MAP(最大后驗概率)算法最為經典。最大后驗概率(MAP)譯碼算法是1974年由Balh，Cocke，Jelinek和Raviv共同提出的，因此也稱為BCJR算法［3］。它是基于網格的軟入軟出譯碼算法，譯碼準則是在噪聲信道下對馬爾可夫過程的狀態及輸入輸出進行逐一估計。它可以準確地計算每一信息比特的后驗概率，但由于MAP算法包含了大量的指數和乘法運算，難以實現。若將其轉換到對數域，可變乘法為加法。后來在對數域對MAP算法進行了修正。一種為Log-MAP算法，另一種為MAX-Log-MAP算法。

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

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

此算法即為SF-MAX-Log-MAP算法。它使Turbo碼在較小的譯碼復雜度情況下，達到與Log-MAP算法接近的誤碼率性能。這一性能改進具有現實的意義。

2 并行譯碼結構

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

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

圖2 子塊重疊的并行譯碼結構

3 改進的并行譯碼算法——SF-MAX-Log-MAP并行譯碼算法

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

下面對SF-MAX-Log-MAP并行譯碼算法進行了簡單闡述。

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

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

外信息輸出為:

最大似然函數值為:

4 性能仿真

通過MATLAB仿真，驗證了此改進算法的有效性。并就LTE系統中Turbo碼的誤碼率性能進行了研究，分析了其關鍵參數(交織長度、并行度、交疊長度)對譯碼性能的影響。仿真相關信息如下:

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

其中分量碼為8狀態遞推系統卷積碼，生成多項式為［D3+D2+1，D3+D2+D+1］，碼率為1/3，

調制方式:BPSK

信道模型:AWGN

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

迭代次數:2

4.1 譯碼算法比較

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

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

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

4.2 交織長度的影響

圖4所示仿真圖可以看出:在譯碼并行度為4，交疊長度為32的并行譯碼過程中，交織長度為2 048的碼塊比交織長度為1 024的誤碼率低，譯碼性能好。因此，在相同的并行度和交疊長度條件下，交織長度越長，譯碼性能越好。這是因為在并行度不變的情況下，交織長度越長，編碼器輸出的碼間自由距離越大，碼抵抗突發錯誤的能力越強，譯碼性能也就越好。

4.3 并行度的影響

圖4 交織長度對Turbo碼誤碼性能的影響

圖5 并行度對Turbo碼誤碼性能的影響

圖6 交疊長度對譯碼性能的影響

圖5所示:在交織長度為2 048和交疊長度為32的并行譯碼過程中，若采用的并行度分別為8和4，則兩情況的誤碼率基本吻合。考慮到并行度越大，系統的復雜度越大，費用越高，采用并行度為4的譯碼器比較合適。因此，LTE采用并行譯碼方案時，不僅應考慮譯碼效率還需考慮占用的硬件資源及系統的復雜性。

4.4 交疊長度的影響

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

5 結 論

在Turbo碼的Log-MAP并行譯碼算法和SF-MAX-Log-MAP算法的基礎上，對它們進行了結合，提出了SF-MAX-Log-MAP并行譯碼算法。通過仿真表明:此算法在減少了大量運算量的同時，保持了Log-MAP并行算法的譯碼性能。在LTE系統中，當Turbo碼長較大時，選擇合適的并行譯碼算法可以降低譯碼時延。此并行譯碼算法需確定合適的并行度、交疊長度，且在滿足誤碼率和時延要求的情況下，需兼顧考慮譯碼系統占用的硬件資源，以降低Turbo譯碼系統費用及復雜度。

［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碼在無線移動通信系統中的應用［J］.廣東通信技術，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］陳雷，田曉燕.時延改進的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，FINGER.AN Improving the Max-Log-MAP Turbo decoding［J］.Electronics Letters，2000，36(23):1937 -1939.

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