采用近似max*運算的Log-MAP譯碼算法

孫增友　李歡歡　王　蒙　王景芹

1(東北電力大學信息工程學院　吉林 吉林 130012)2(河北工業大學電氣工程學院　天津 300130)

?

采用近似max*運算的Log-MAP譯碼算法

孫增友1李歡歡1王蒙2王景芹2

1(東北電力大學信息工程學院吉林 吉林 130012)2(河北工業大學電氣工程學院天津 300130)

為有效降低Turbo碼譯碼的硬件存儲消耗，提出一種基于近似max*運算的改進的Log-MAP算法。并通過設計合適的數字電路來找出一組數據中最大的兩個值嵌入到其相關函數項中，有效實現了低復雜度的Turbo譯碼器的硬件結構。實驗結果表明，所提出的結構比ConstantLog-MAP算法結構平均簡化了30%，達到了與Log-MAP幾乎相同的誤碼率(BER)性能，降低譯碼的復雜度，便于實際工程應用。

Turbo碼Log-MAP算法ConstantLog-MAP復雜度

0　引　言

Turbo碼是在信道編碼領域最大的成就之一。Turbo碼編碼方式以其接近香農極限的優越性能[1]，自1993年提出以來，受到了人們的廣泛關注。Turbo碼主要應用于無線通信領域。

Turbo編碼通常指的是并行級聯卷積碼的結構，可以通過MAP算法、Log-MAP算法、Max-Log-MAP算法、SOVA算法等進行迭代譯碼。為降低譯碼過程中的計算復雜度，人們提出的各種算法均旨在簡化Turbo譯碼算法Log-MAP算法中的max*運算，包括：改進的Max-Log-MAP算法、ConstantLog-MAP算法[5]、LinearLog-MAP算法等。這些次優算法采用近似的方法使得譯碼算法簡化，但性能與最優算法相比略有損失。為了減少性能的損失，本文提出了一種基于近似的max*運算的Log-MAP譯碼算法。這種近似方法可以很好地降低每個譯碼步驟運算的復雜度，相對于傳統的Log-MAP算法，性能降低很小。

1　Turbo碼的譯碼方案

圖1　Turbo碼的迭代譯碼示意圖

假設u是N比特的信息塊。經過Turbo編碼和BPSK調制，通過AWGN信道，接收的信息序列為y。在Turbo譯碼之前先進行軟解調。設由輸入引起的柵格由K-1時刻的狀態S′轉移為K時刻狀態S。前向遞歸和后向遞歸可以遞歸計算為：

(1)

(2)

(3)

max*運算，可以利用Jacobian算法定義為：

max*(x1,x2)=ln(expx1+expx2)

=max(x1,x2)+ln{1+exp(-|x2-x1|)}

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

(4)

式中：fc(·)為相關函數。如果忽略相關函數的值，采用這種簡化方法得到的就是Max-Log-MAP算法[7]。即令fc(|x2-x1|)=0，則：

max*(x1,x2)=max(x1,x2)

(5)

這種近似雖然大大簡化了Max-log-MAP算法，也造成了性能上的損失。

SOVA算法是最大似然序列估計算法，最簡單，同時性能也最差。而Log-MAP算法的復雜性約是SOVA的兩倍左右。

三種不同譯碼算法BER性能仿真如圖2所示。圖2是基于MATLAB環境下，使用隨機輸入數據，編碼器的RSC子碼采用(13,15)碼，碼率為1/3，幀長為400，交織方式為隨機交織，迭代5次，在高斯信道下采用BPSK調制。可以看出Log-MAP算法性能最好，Max-Log-MAP算法性能介于Log-MAP算法和SOVA算法之間，SOVA算法性能最差，比Log-MAP算法約差了0.8dB。

圖2　三種不同譯碼算法的BER性能比較

2　Log-MAP算法的近似譯碼算法

2.1近似的max*運算

max*運算是Log-MAP算法的計算核心。當Turbo碼編碼器中寄存器個數為M時，譯碼器中存在2M個變量的max*運算，根據式(4)可知，多變量max*需要遞歸計算，當M≥3時硬件實現復雜，這也是硬件實現時少采用Log-MAP算法的關鍵原因，而采用Max-Log-MAP性能又有不少下降，因此提出一種改進的Log-MAP算法。

從式(3)中可以看出在Log-MAP算法中計算ln(expx1+…+expxn)表達式很必要。常規的Log-MAP算法采用式(4)中的max*運算。為了得到2個變量以上的max*運算，應用了遞歸Jacobian算法，如：

max*(x1,x2,x3)=max*{max*(x1,x2),x3}

(6)

為了降低對n個輸入變量參數的max*運算近似算法的復雜度，針對這個問題，采用Chebyshev不等式，所提出的改進的Log-MAP算法的n輸入max*運算為：

max*(x1+x2+…+xn)

(7)

由此所提出的改進的Log-MAP算法的n輸入max*運算為：

max*(x1,x2,…,xn)≈y1+ln[(1+K1exp{-δ})]+K2

(8)

式中：y1=max{x1,x2,…,xn}n個輸入值中第一個最大值，y2=max{x1,x2,…,xn/y1}是第二個最大值，δ=y1-y2，K1=(n-1)/n，K2=ln[2n/(n+1)]。近似的max*運算的第一項是一個簡單的max運算，第二項可以認為是另一個校正功能的函數fc(·)。

式(8)中，K2是一個正常數，在迭代譯碼過程中可以忽略，當n的值很大時，K1≈1，所以式(8)可以簡化為：

max*(x1,x2,…,xn)≈y1+ln(1+exp{-δ})=y1+fc(δ)

(9)

2.2max*運算中相關函數的實現

式(9)的實現需要設計合適的數字電路[8]找出y1和y2，計算出δ，然后應用于相關函數fc(·)。本文應用了ConstantLog-MAP算法的相關函數項，并在硬件實現的過程中做進一步改進，有效地將譯碼復雜度進一步降低，其相關函數曲線如圖3所示。Log-MAP算法中的max*運算中相關函數fc(x)=ln{1+exp(-x)}，其中，x=|x1-x2|，函數曲線如圖3所示。

圖3　Log-MAP相關函數fc(x)和Constant Log-MAP算法的fc(x)

(10)

ConstantLog-MAP中的fc(x)是對Log-MAP中fc(x)的近似，在硬件實現Turbo碼譯碼器時，可以通過ConstantLog-MAP算法的相關函數fc(x)進一步降低其復雜度。

因為式(9)中δ≥0，fc(δ)的實現可以更簡化。設c是給定δ=δp-1…δ0時fc(δ)的取值，且c=cp-1…c0。可以看出：

1) 如果c=3/8，那么cp-1…c0=″0…0.011″，或cp-1…c0=″0…0.000″，(即，c0=c1且ci=″0″，2≤i≤p-1)。

2) 如果δ<2，那么δp-2…δ0=″0000x.xxx″(因為δ≥0，所以δp-1=″0″)，其中x任意表示為1或0， (即δj=′0′，2≤j≤p-2)。因此c0和c1僅當δj=0,4≤j≤p-2時等于1，即：

(11)

圖4　改進的結構圖(灰色框為改進部分)

(a) 2輸入的MVG結構;(b)n輸入的近似max*運算結構

3　仿真結果與比較

將所提出的近似max*運算方法，應用于Turbo譯碼中，對應信噪比下(Eb/N0)的BER(誤碼率)性能仿真如圖5所示。其中，對4種譯碼算法進行仿真分析：①ConstantLog-MAP算法[5]，② 所提出的改進的Log-MAP算法，用Log-MAP-max*表示，③Log-MAP算法，④Max-Log-MAP算法。

仿真的Turbo碼參數為移位寄存器具有16個狀態，碼率為R=1/2，生成多項式為(1,33/23)o分別代表前饋多項式和反饋多項式。信息序列N=103的比特，傳輸幀總數為106。為了保證仿真結果性能的準確性，每個性能仿真實驗中至少引入了100個位錯誤。使用了偽隨機Turbo交織器，在接收端最多進行10次迭代，采用BPSK調制，應用于CCSDS標準[3]中。

圖5　不同譯碼算法的性能仿真比較

由圖5可知，所提出的改進的Log-MAP算法，總是能達到接近最優的譯碼算法的BER性能，其譯碼復雜度接近Max-Log-MAP算法，而糾錯性能顯著優于Max-Log-MAP算法。因為改進的Log-MAP算法是對ConstantLog-MAP算法的簡化，所以性能略差于ConstantLog-MAP算法，如在BER等于10-5時，相差不到0.1dB。在低誤碼率時，如10-6時，所提出的改進的譯碼算法可以實現與ConstantLog-MAP算法和Log-MAP算法基本上相同的BER性能。

4　譯碼復雜度分析

表1給出了所提出的n輸入近似max*算法結構(用C表示)在空間(用A表示)和延遲(用D表示)兩個方面與兩種基于樹結構的算法進行比較：① 基于3比特LUT的2輸入的Log-MAP算法結構(用A表示)；② 2輸入的ConstantLog-MAP算法結構[5](用B表示)。

表1　不同算法的硬件結構空間及延遲比較

實驗均表明，所提出的算法結構C不但比算法結構A和算法結構B的空間大大減小，而且具有較低的延遲。如表1中，假設n=16，p=16時，所提出的算法結構C需要5768個等同的門，最小延遲為2 ns，而算法結構B需要7312個等同的門，最小延遲為2.8ns。因此所提出的算法結構空間減少了21%，延遲降為算法結構C的28.5%。在具有與ConstantLog-MAP算法(B)相同的延遲時(DB)作更近一步比較，對應的比較結果如表1中最后一列所示。可以看出，此時與算法B硬件復雜度相比，所提出的結構平均節省了大概30%的空間。

5　結　語

在Log-MAP譯碼算法中，對其譯碼過程中的max*運算進行新的近似。max*運算是廣義上的對n個輸入值計算的簡化，將max*運算近似為簡單的max運算和相關函數的計算。仿真結果表明，這種方法相對于Log-MAP譯碼算法，性能有很小的損失，從實踐的角度來看，新的改進算法的優勢是顯著降低了每個譯碼步驟的譯碼復雜度，有利于譯碼器的硬件實現。

[1] Berrou C,Glavieux A,Thitimajhima P.Near Shannon limit error-correcting coding and decoding:Turbo codes[C]//Proc.ICC’93,1993:1064-1070.

[2] Bahl L R,Cocke J,Jelinec F,et al.Optimal decoding of linear codes for minimizing symbol error rate[J].IEEE Trans.Inform.Theory,1974,20(2):284-287.

[3] 張凱.CCSDS標準Turbo碼譯碼器設計及實現[D].北京郵電大學,2013.

[4] 孫增友,張利杰,田勇.SF-MAX-Log-MAP并行譯碼算法及其在LTE中的應用研究[J].東北電力大學學報,2012,32(4):35-39.

[5] Gross W J,Gulak P G.Simplified MAP algorithm suitable for implementation of turbo decoders[J].IET Electron.Lett.,1998,34(16):1577-1578.

[6] Papaharalabos S,Sweeney P,Evans B G.SISO algorithms based on Log-MAP and Max-Log-MAP turbo decoding[J].IET Proc.Commun,2007,1(1):49-57.

[7] 劉東華.Turbo碼原理與應用技術[M].北京:電子工業出版社,2004.

[8] Amarù L G,Martina M,Masera G.High speed architectures for finding the first two maximum/minimum values[J].IEEE Trans.Very Large Scale Integr.(VLSI) Syst.,2012,20(12):2342-2346.

LOG-MAPDECODINGALGORITHMUSINGAPPROXIMATEMAX*OPERATION

SunZengyou1LiHuanhuan1WangMeng2WangJingqin2

1(School of Information Engineering,Northeast Dianli University,Jilin 130012,Jilin,China)2(School of Electrical Engineering,Hebei University of Technology,Tianjin 300130,China)

InordertoeffectivelyreducetheconsumptionofTurbodecodinghardwarestorage,inthispaperweproposeanimprovedLog-MAPalgorithmwhichisbasedonapproximatemax*operation,andfindouttwomaximumvaluesinasetofdatathroughdesigninganappropriatedigitalcircuitandembedthemintotheircorrelatedfunctionterms,thuseffectivelyimplementthehardwarearchitectureofTurbodecoderwithlowcomplexity.Experimentalresultsshowthattheproposedarchitectureissimplerby30%onaveragethanthearchitectureofConstantLog-MAP,itreachestheBERperformancealmostthesameasLog-MAP’s,reducesthedecodingcomplexity,andisconvenientforpracticalengineeringapplication.

TurbocodesLog-MAPalgorithmConstantLog-MAPComplexity

2014-05-13。國家自然科學基金項目(51077039)。孫增友，高工，主研領域：無線電通信。李歡歡，碩士生。王蒙，碩士生。王景芹，教授。

TP3TN911.22

ADOI:10.3969/j.issn.1000-386x.2016.03.060