Turbo譯碼器基于組合邏輯電路的低復雜度Log-MAP算法

王　東，李秀朋

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

0　引言

Turbo編碼作為第一種接近香農極限的信道編碼方式，已經在包括LTE(Long Term Evolution)、CCSDS(Consultative Committee for Space Data System)、DVB-RCS(Digital Video Broadcasting - Return Channel via Satellite)等在內的大量無線通信標準中得到應用。Log-MAP算法是一種簡化版的最大后驗概率(MAP)算法，廣泛應用于Turbo譯碼器中。盡管通過將對數域引入MAP算法已經去除了大部分的指數和乘法運算，但剩余的指數和對數運算在實現上仍然比較困難。

1　Log-MAP算法

在文獻[1]中，Log-MAP算法的核心max*運算定義如下：

max*(x1,x2)=max(x1,x2)+ln(1+e-|x2-x1|)=

max (x1,x2)+fc(-|x2-x1|)，

(1)

式中，fc=ln(1+e-|x2-x1|)通常被稱為修正因子。Log-MAP是SISO(Soft Input Soft Output)迭代譯碼的最優算法，然而fc較高的復雜度使得該算法實現起來十分困難[2-4]。為了解決這一問題，在文獻[5-11]中已經出現了一系列簡化的Log-MAP算法。

Max-Log-MAP算法[5]直接忽略了修正因子fc，在這種情況下，max*運算可以僅用一個比較器實現。然而，伴隨著復雜度的降低，性能也有相對較大的下降。通過舍棄fc，Max-Log-MAP算法在所有簡化的Log-MAP算法中取得了最低的復雜度和最差的BER性能。SF-Log-MAP算法[6]通過將外部信息乘以一個縮放系數(Scaling Factor，SF)，在小幅增加復雜度的情況下改善了Max-Log-MAP算法的BER性能。然而該算法性能的提升十分有限，依然不能滿足實際應用的需求。

Linear-Log-MAP[7]和Constant-Log-MAP[8]等一系列算法采用了線性函數完成對fc的近似。這些算法將fc分為若干部分，每一部分都使用特定的線性函數對fc進行近似。特別的，在Constant-Log-MAP算法中使用的線性函數是一個常量。這些線性近似算法取得了更好的BER性能，也引入了更高的復雜度[9]。一些算法使用了非線性函數[10]來計算fc，也可以在理論上獲得更好的BER性能。然而在實際應用中，為了方便硬件實現，通常將非線性函數修正為分段的線性函數。從這一點來看，這些方法也可以歸為線性近似。

就目前來看，大多數研究人員都遵從了下面這些步驟來實踐Log-MAP算法的簡化。首先，確定一個簡單的函數來近似fc。之后，使用比較器、加法器和移位器等實現比較及其他算術運算。

這些方法的局限性也是顯而易見的。一方面，隨著復雜度的提升，函數分段的數量不可能無限制地增加。這樣對fc的粗略估計直接導致了BER性能的下降。另一方面，作為最基本的運算，比較器、加法器和移位器在實現上引入的復雜度無法進一步降低。

文獻[11]提出了一種Constant-Log-MAP算法的新的實現方法很值得關注。這個方法使用適當的數字電路替換掉了fc，然而簡化效果需通過觀察發現，且該方法無法應用在其他算法中。受文獻[11]的啟發，本文提出了一種完整的簡化Log-MAP算法實現方案。該方案適用于包括最前沿算法在內的所有Log-MAP相關算法。第二部分將闡明Constant-Log-MAP算法是本文提出方案的一個特例，且可以通過特定的步驟推導得出，而無需依賴觀察。

2　基于CLC的簡化實現

Log-MAP算法的流程如圖1所示，其中虛線標識的模塊完成修正因子fc的計算。表1展示了幾種典型的簡化算法。考慮到硬件實現，|x2-x1|和fc均為有確定位寬的定點數據。這樣，用來計算fc的模塊可以看作是一個系統或者一個組合邏輯電路，其輸入為|x2-x1|，輸出為fc。fc中的每一位可由|x2-x1|經邏輯運算得出。之后，將該模塊的系統函數由一個算術表達式變換為N個邏輯表達式，其中N為fc的位寬。最終，加法器、比較器和移位全部被邏輯電路替換。本文提出的實現方法的各個步驟將在下面進一步描述。

圖1　簡化Log-MAP算法流程

表1適合定點和浮點算法的fc近似

算法Max?Log?MAPConstant?Log?MAPLinear?Log?MAP參考文獻[9]fc00．375x2-x1<20x2-x1≥2{-0．25×(x2-x1-2．5)x2-x1<2．50x2-x1≥2．5{max(0，ln2-0．5×x1-x2)

表23位有效位定點算法的fc近似

x2-x100．1250．250．3750．50．6250．750．87511．1251．251．3751．51．6251．751．875fc0．6250．6250．50．50．3750．3750．250．250．250．250．250．250．1250．1250．1250．125定點101101100100011011010010010010010010001001001001

2.1　選擇fc的近似方案

如前文所述，|x2-x1|和fc均為有確定位寬的定點數據，也可以說是有確定步長的離散值。在這一部分，應對每一個|x2-x1|對應的fc的值進行清晰的定義，既可以通過現有的簡化算法計算得出，也可以由研究人員直接確定。本文中|x2-x1|和fc分別采用[8.3]和[0.3]定點結構，其中[m.n]表示該定點數據有m位整數位和n位小數位。幾種簡化Log-MAP算法對fc的近似如圖2所示。在本文對fc進行近似的Example(2)中，令δ=|x2-x1|，

(2)

式中，T(·)表示表2定義的查找表，?x?為不大于x的最大整數。顯然式(2)無法通過一個簡單的函數進行描述，進而在傳統觀點上被認為難以進行實現。在下一部分，本文將介紹如何通過CLC架構完成對這種fc近似的實現。

圖2　幾種簡化Log-MAP算法對fc的近似

2.2　確定最大項/最小項方程

當輸入和輸出的映射關系確定之后，它們之間的邏輯關系可以通過數字電路得到。最大項或最小項[12-13]能夠首先確定。令c和u分別表示|x2-x1|和fc，又令c=cm-1…c0，u=un-1…u0分別表示他們的定點形式。這樣，式(2)的最小項可以確定為：

u0=∑c(0,1,4,5,12,13,14,15)，

u1=∑c(4,5,6,7,8,9,10,11)，

u2=∑c(0,1,2,3)。

(3)

方程(3)準確地給出了fc和|x2-x1|間的邏輯關系。然而，從實現的角度來看，該表達式并非最簡的。為了進一步降低硬件復雜度，必須對其進行簡化[12]。

2.3　確定最簡表達式

代數方法和卡諾圖[13-14]是簡化數字電路邏輯表達式的兩條主要途徑。根據最小項(3)，卡諾圖很容易設計，如圖3所示。其中，“1”表示最小項方程中包括該項。

圖3　與公式(3)對應的卡諾圖

通過卡諾圖，可以進一步簡化(3)，

(4)

顯然，本文提出的架構適用于任意一種fc的近似，只需知曉fc與|x2-x1|之間的映射表即可。特殊地，文獻[11]中的簡化方案作為本架構的一個特例，可以通過上面的步驟得到。Example(2)中基于CLC的fc計算模塊的組成如圖4所示。

3　仿真與硬件實現

本文針對CCSDS和LTE標準對AWGN信道[15]下Turbo譯碼器的BER性能進行了仿真，仿真參數如表3所示[15-16]。fc與|x2-x1|在仿真中分別以[8.3]和[0.3]的定點數據呈現。圖5和圖6分別給出了CCSDS和LTE兩種標準下的BER性能與Eb/N0的關系。為了保證結果的準確性，針對每一個Eb/N0至少要仿真5×104個幀[17-19]。

表3圖5和圖6所使用的仿真參數

標準碼長碼率迭代調制方式CCSDS17841/610BPSKLTE35201/310QPSK

圖5　CCSDS標準下幾種簡化算法的BER性能

圖6　LTE標準下幾種簡化算法的BER性能

從仿真中可以得出，Max-Log-MAP和SF-Log-MAP會造成0.15～0.5 dB的BER性能惡化。其他3種算法性能十分接近，其中Linear-Log-MAP和Example(2)性能略高于Constant-Log-MAP。表4和表5分別給出了CCSDS和LTE兩種標準下LINEAR-LOG-MAP、使用CLC的LINEAR-LOG-MAP和使用CLC的(2)的幾種算法占用硬件資源情況。實現平臺為Xilinx ML605評估板和ISE Design Suit 13.4開發環境。

表4CCSDS標準下幾種算法復雜度對比

算法寄存器查找表觸發器對RAM18Linear?Log?MAP2396(100%)7462(100%)7694(100%)180(100%)使用CLC的Linear?Log?MAP2629(110%)5578(74．8%)5789(75．2%)180(100%)使用CLC的(2)2622(109．4%)5495(73．6%)5678(73．8%)180(100%)

表5LTE標準下幾種算法復雜度對比

算法寄存器查找表觸發器對RAM18Linear?Log?MAP1654(100%)4452(100%)4659(100%)75(100%)使用CLC的Linear?Log?MAP1597(96．6%)3137(70．5%)3328(71．4%)75(100%)使用CLC的(2)1639(99．1%)3084(69．3%)3292(70．7%)75(100%)

對比傳統的Linear Log-MAP架構，基于CLC的架構能夠減少約30%的查找表和觸發器對，與此同時寄存器的數量基本持平或僅需小幅增加。正如我們所看到的，盡管式(2)無法使用一個簡單的函數描述，但使用基于CLC的架構對其進行實現的復雜度仍然低于Linear Log-MAP。從這一點來看，研究人員可以跳過目前廣泛采用的函數近似或曲線擬合，而直接設計fc與|x2-x1|之間的映射。文獻[11]中也給出了一些關于基于CLC的實現和傳統的Constant Log-MAP之間的對比，可以看作是本文提出的架構的一個特例。

4　結束語

本文提出了一種基于CLC的簡化Log-MAP算法，并給出了其有效的硬件實現。相對于傳統的簡化Log-MAP算法，本文提出的架構可以降低高達30%的復雜度并保持相同的BER性能。特別地，基于CLC的架構無需關注fc是否能用一個簡單的函數描述即可硬件實現Log-MAP算法。本文提供了一個新的途徑來幫助研究人員設計更具靈活性、更高BER性能和更低復雜度的Log-MAP簡化算法。

[1]Robertson P,Villebrun E,Hoeher P.A Comparison of Optimal and Sub-optimal MAP Decoding Algorithms Operating in the Log Domain[C] ∥in proc.IEEE Int.Conf.Commun.,1995,2:1009-1013.

[2]Classon B,Blankenship K,Desai V.Channel Coding for 4G Systems with Adaptive Modulation and Coding[J].IEEE Wireless Commun.,2002,9( 2): 8-13.

[3]Consultative Committee for Space Data Systems (CCSDS):Telemetry Channel Coding[DB/OL].Avaliable: (2002).http://public.ccsds.org/publications/archive/101x0b6s.pdf.

[4]Digital Video Broadcasting (DVB): InteractionChannel for Satellite Distribution Systems [DB/OL].Avaliable: (2009).http://www.etsi.org/deliver/etsi_en/301700_301799/301790/01.05.01-60/en_301790v010501p.pdf.

[5]Erfanian J,Pasupathy S,Gulak G.Reduced Complexity Symbol Detectors with Parallel Structure for ISI Channels[J].IEEE Trans.Commun.,1994,42(234):1661-1671.

[6]Vogt J,Finger A.Improving the Max-Log-MAP Turbo Decoder[J].IEE Electron.Lett.,2000,36(23):1.

[7]Cheng J F,Ottosson T.Linearly Approximated Log-MAP Algorithms for Turbo Decoding[C]∥in proc.IEEE.Veh.Technol.Conf.,2000,3:2252-2256.

[8]GrossW J,Gulak P G.Simplified MAP Algorithm Suitable for Implementation of Turbo Decoders[J].IET Electron.Lett.,1998,34(16):1577-1578.

[9]Talakoub S,Sabeti L,Shahrrava B,et al.An Improved Max-Log-MAP Algorithm for Turbo Decoding and Turbo Equalization[J].IEEE Trans.Instrum.Meas.2007,56(3):1058-1063.

[10] Wang H,Yang H,Yang D.Improved Log-MAP Decoding Algorithm for Turbo-like Codes[J].IEEE Commun.Lett.,2006,10(3):186-188.

[11] Martina M,Papaharalabos S,Mathiopoulos P T,et al.Simplified Log-MAP Algorithm for Very Low-complexity Turbo Decoder Hardware Architectures[J].IEEE Trans.Instrum.Meas.2014,63(3):531-537.

[12] Das S R,Choudhury A K.Maxterm Type Expressions of Switching Functions and Their Prime Implicants[J].IEEE Trans.Electron. Comput., 1965,EC-14(6):920-923.

[13] Wakerly J F.Digital Design Principles and Practices[M].3rd ed.Englewood Cliffs,NJ,USA:Prentice Hall,2000.

[14] Karnaugh M.The Map Method for Synthesis of Combinational Logic Circuits[J].AIEE,Trans.Commun.Electron.,1953,72(5):593-599.

[15] 許文龍,文運豐,鄧曉平,等.無人飛行器通信中聯合信道估計和Turbo均衡[J].無線電工程,2016,46(1):46-49.

[16] 郭曉東,陳衛東.高誤碼率下雙二進制Turbo碼交織器的識別算法[J].無線電工程,2017,47(2):69-73.

[17] 郝亞男,杜克明,馮昊軒.一種用于LTE的提前終止Turbo碼算法仿真[J].無線電工程,2017,47(4):24-27.

[18] 高紅山,高凡琪.瑞利信道下基于Turbo-BICM-ID的DFT-S-OFDM性能研究[J].無線電工程,2017,47(9):38-43.

[19] 張亞林,樹玉泉,張金濤,等.一種多進制LDPC編譯碼器硬件的實現方法[J].無線電工程,2018,48(1):72-79.