一種適用于T-TCM系統的簡化的Log-Map算法

王建，李建平

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

1 引言

Turbo網格編碼調制(T-TCM)[1]把網格編碼調制[2，3]和Turbo編碼[4]結合在一起，它可以同時獲得卓越的編碼增益和頻帶效率，與此同時，它卻引入了更高的譯碼復雜度[5]。逐符號的Log-MAP算法把MAP算法引入對數域，它是高斯白噪聲環境下的最佳譯碼算法[6-8]。但是，對于Log-MAP算法來說，從一個巨大的對數表中查找數據是一個相當耗費時間的過程。MAX-Log-MAP(以后簡稱MLM)算法以其簡單的復雜度成了Log-MAP算法的一大候補，但是由于損失了大量性能增益，因此它是一種次優算法[9-11]。Improved MAX-Log-MAP[12]算法實現了在性能和復雜度上的折中，然而它卻引入了不能帶來性能增益的冗余計算，此外，在很多情形下，它和MAX-Log-MAP是等價算法。顯然，提出一種既能實現好的性能又能有效降低復雜度的算法是非常必要的。

在本文中，我們提出了一種簡化Log-MAP算法(以后簡稱SLM)，它可以用非常低的復雜度在硬件輕松實現。我們的算法是在improved MAX-Log-MAP(IMLM)算法基礎上對Log-MAP(LM)算法的一種改進，它可以提供和LM幾乎等價的性能。

文中其余部分按以下方式組織：在第二部分，我們介紹譯碼算法，包括傳統的譯碼方法和我們提出的譯碼方法；在第三部分，我們描述本中提出算法的詳細硬件實現過程；在第四部分，我們將描述實驗仿真結果，包括性能仿真和復雜度分析兩部分；最后，我們在第五部分得出結論。

2 T-TCM譯碼算法

2.1 傳統的譯碼算法

在這里，我們簡單介紹一下現存的幾種經典譯碼算法，詳細的算法描述可以參考文獻[12]。

Log-MAP算法的關鍵是計算信息比特xk的對數先驗概率(LLR)值，可以用以下公式計算：

(1)

在這里，R表示接收到的信息序列。

根據譯碼網格圖，(1)式可以修改為下式：

(2)

在這里，是發送的信息序列，s和s′分別代表在k時刻和k-1時刻的狀態。把 R分成三部分，我們可以得到如下表達式：

p(s′，s，R)=p(Rt>k|s)p(s，Rk|s′)p(s′，Rt

(3)

定義下面三式：

αk(s′)=p(s′，Rt

(4)

βk+1(s)=p(Rt>k|s)

(5)

γk(s′，s)=p(s，Rk|s′)，

(6)

我們可以把(3)式重寫為如下表達式：

p(s′，s，R)=αk(s′)γk(s′，s)βk+1(s)

(7)

這里α，β和γ分別表示前向度量、后向度量和分支度量。我們用下式對α，β和γ重新表示：

(8)

(9)

(10)

這里σk和σk+1分別表示在k時刻和k+1時刻的所有狀態的集合，Lc是信道置信度。

下式是雅克比變化式，利用它可以避免復雜的指數求和運算：

max*(x，y)=ln(ex+ey)

=max(x，y)+ln(1+e-|x-y|)

(11)

這里ln(1+e-|x-y|)是譯碼校正項，它的存在使Log-MAP算法有著最佳的性能。利用雅克比變換式，我們可以引入以下對數域度量：

(12)

(13)

γk(s′，s)=lnγk(s′，s)

(14)

隨后，我們利用上面三式利用前向遞歸和后向遞歸運算去計算α和β，這個過程可以參照圖1。

最后，LLR值可以通過下式計算：

(15)

LLR值同樣也是用遞歸運算計算，詳情見圖2。

圖1 式(12)的前向遞歸和式(13)的后向遞歸運算

圖2 LLR值得遞歸運算過程

MAX-Log-MAP算法以其簡單的復雜度而被廣泛使用，它通過修改雅克比變化式(11)得到。在這里，雅克比變化式中的對數項被省略，修改后如下：

max*(x，y)≈max(x，y)

(16)

最后，LLR被重寫為下式：

(17)

Improved MAX-Log-MAP算法利用了邁克勞林展開式，它把式(13)修改為下式[13]：

(18)

2.2 本文提出的算法

我們先看Log-MAP 算法，式(11)中的校正項ln(1+e-|x-y|)雖然使其成為最優算法，但是也帶來了許多問題。首先，把ln(1+e-|x-y|)的計算結果保存到對數表中會引入由截斷引起的量化錯誤；其次，對數表需要設定大范圍的信噪比，這樣會大大提高硬件花費；最后，從對數表中讀取數據也是一個非常耗時的過程。

顯然，如何用函數近似ln(1+e-|x-y|)是解決問題的關鍵。我們對式(18)進一步推導，過程如下：

令|x-y|=t，式(18)可等價為下式：

(19)

當t<1.3862時，我們可以對x和y進一步討論。

情況1：當x>y時，有：

(20)

情況2：當x

(21)

顯然無論x與y哪個值大，我們都可以得到以下恒等式

(22)

最后，式(19)可以用下式表示：

(23)

用式(23)計算前向度量αk(s)，后向度量βk(s)以及LLR值，我們得到了簡化的Log-MAP算法。由于我們是對校正項ln(1+e-|x-y|)進行數學逼近，因此我們的算法可以實現和Log-MAP算法幾乎等價的性能。同時，又由于式(23)和式(18)是恒等式，因此我們的算法可以實現與improved MAX-Log-MAP算法完全等價的性能。此外，由于算法中只有簡單的加法和乘除2運算，它可以用非常低的復雜度輕松在硬件實現。

3 硬件實現

圖3 不同狀態的節點計算單元

圖4顯示了計算αk(s)的詳細硬件實現過程，βk(s)和LLR也是用類似的方法實現。從圖4可以看出，我們提出的簡化算法的實現過程遠比Log-MAP算法和improved MAX-Log-MAP算法的實現過程簡單。

圖4 提出算法的詳細硬件實現過程

4 仿真結果

4.1 性能比較

我們分別在生成多項式g1=[7，5]和 g2=[11，13]兩種情形下做仿真實驗。在實驗中，我們把交織長度(記作N)設為1024，編碼效率(記作R)設成1/3，最大迭代次數設為6次。我們只考慮高斯白噪聲(AWGN)環境和BPSK調制方法。

圖5展示了生成多項式g1=[7，5]的仿真結果。四條線顯示了我們提出算法和LM，MLM以及IMLM的對比。圖6展示和圖5類似的仿真結果，但是它的生成多項式改為g2=[11，13]。

圖5 四種算法的BER性能比較，生成多項式g1=[7，5]，N=1024，BPSK調制，AWGN信道

圖6 四種算法的BER性能比較，生成多項式g2=[11，13]，N=1024，BPSK調制，AWGN信道

從圖5和圖6我們可以看出，和MLM算法相比，SLM，IMLM和LM算法在性能方面有著明顯的優勢，我們提出的簡化算法SLM比MLM算法額外獲得0.3db的性能增益。此外，從仿真結果我們還可以看出SLM和IMLM有著完全等價的性能，且這個性能非常接近LM。

4.2 復雜度分析

要想計算我們提出算法的復雜度，必須先計算αk(s)，βk(s)以及LLR在t位于不同區間時的概率。我們選擇5個信噪比做仿真實驗得到大量統計數據，然后分別計算在區間(0，1.3862)以及區間(1.3862，∞)的平均值，然后分別記作p1，p2，這兩個值如下式所示：

(24)

通過參考文獻[13]和文獻[14]，我們計算得到表1，表中的M是編碼器的約束長度。

從表1我們可以清楚地看出，SLM算法不需要進行復雜的對數運算，并且它的復雜度比IMLM算法降低了大約39%。

表1 四種譯碼算法的復雜度比較

5 結論

我們在文中提出了一種簡化的Log-MAP算法，該算法利用一種非常簡單的分段函數代替了對數校正項。從實驗仿真結果我們可以看出我們提出的算法實現了和Log-MAP非常接近的性能，并且它不用進行復雜的對數查表運算。和文獻[12]提到的improved MAX-Log-MAP算法相比，它再提供與其完全等價的性能的同時，降低了大約39%計算復雜度。文中提出的算法易于在硬件實現，它可以輕松地應用在T-TCM系統中。

[1]S Robertson，Worz T.Bandwidth-efficient turbo trellis-coded modulation using punctured component codes[J].IEEE J Sel Areas Commun，1998，16(2)：206-218.

[2]Ungerboeck G.Channel coding with multilevel/phase signalling[J].IEEE Trans Inf Theory，1982，25(1)：55-67.

[3]Sybis，Michal.Branch canceling technique for turbo TCM decoding[J].IEEE European Wireless Conference，2012，1-5.

[4]Ji Hoon Kim，In CheolPark.Bit-Level extrinsic information exchange method for double-binary turbo codes[J].IEEE Transactions，56(1)：81-85.

[5]Sybis S.Log-MAP equivalent Chebyshev inequalitybased algorithm for turbo TCM decoding，Electron Lett，2011，47(18)：1049-1050.

[6]D Mackay.Good error correcting codes based on very sparse matrices[J].IEEE Trans Inform Theory，vol 45，1999，399-431.

[7]L Bahl，J Cocke，J Jelinek，J Raviv，F Raviv.Optimal decoding of linear codes for minimizing symbol error rate[J]. IEEE Trans Inform.Theory，vol IT- 20，1974，284-287.

[8]Xiaoyi Li，Zhao Fang.Research on improved turbo-codes decoding algorithm [J].Computer 2009(25)：230-232.

[9]C Berrou，A Glavieux，P Thitimajshima.Near Shannon limit error-correcting coding and decoding：Turbo-codes[J].Proc ICC ’93，1993，1064-1070.

[10]Robertson P，Hoeher P，Villebrun E.Optimal and sub-optimalmaximum a posteriori algorithms suitable for turbo decoding[J].Eur Trans Telecommun，1997，8(2)：119-125.

[11]J P Woodard，L Hanzo.Comparative study of turbo decoding techniques：An overview[J].IEEE Trans Veh，Technol，49(6)：2208-2233，2000.

[12]S Talakoub，L Sabeti，B Shahrrava，M Ahmadi.An improved Max-Log-MAP algorithm for turbo decoding and turbo equalization[J].IEEE Trans.on Instrumentation and measurement，56(3)：1058-1063，2007.

[13]Park S J.Combined Max-Log-MAP and Log-MAP of turbo codes[J].Electron Lett，2004，40(4)：251-252.

[14]Robertson P，Villebrun E，Hoeher P.A comparison of optimal and sub-Optimal MAP decoding algorithms operating in the Log domain[J].IEEE International Conference on 1822，1995，1009-1013.

[15]S Lin，Daniel，J Costello.Error Control Coding (Second Edition)[M].Beijing：China Machine Press，2007，372-378，478-484 .