孫增友　李歡歡　王　蒙　王景芹

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

?

采用近似max*運(yùn)算的Log-MAP譯碼算法

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

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

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

Turbo碼Log-MAP算法ConstantLog-MAP復(fù)雜度

0　引　言

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

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

1　Turbo碼的譯碼方案

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

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

(1)

(2)

(3)

max*運(yùn)算，可以利用Jacobian算法定義為：

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

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

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

(4)

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

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

(5)

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

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

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

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

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

2.1近似的max*運(yùn)算

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

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

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

(6)

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

max*(x1+x2+…+xn)

(7)

由此所提出的改進(jìn)的Log-MAP算法的n輸入max*運(yùn)算為：

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*運(yùn)算的第一項(xiàng)是一個簡單的max運(yùn)算，第二項(xiàng)可以認(rèn)為是另一個校正功能的函數(shù)fc(·)。

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

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

(9)

2.2max*運(yùn)算中相關(guān)函數(shù)的實(shí)現(xiàn)

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

圖3　Log-MAP相關(guān)函數(shù)fc(x)和Constant Log-MAP算法的fc(x)

(10)

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

因?yàn)槭?9)中δ≥0，fc(δ)的實(shí)現(xiàn)可以更簡化。設(shè)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″(因?yàn)棣摹?，所以δp-1=″0″)，其中x任意表示為1或0， (即δj=′0′，2≤j≤p-2)。因此c0和c1僅當(dāng)δj=0,4≤j≤p-2時等于1，即：

(11)

圖4　改進(jìn)的結(jié)構(gòu)圖(灰色框?yàn)楦倪M(jìn)部分)

(a) 2輸入的MVG結(jié)構(gòu);(b)n輸入的近似max*運(yùn)算結(jié)構(gòu)

3　仿真結(jié)果與比較

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

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

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

由圖5可知，所提出的改進(jìn)的Log-MAP算法，總是能達(dá)到接近最優(yōu)的譯碼算法的BER性能，其譯碼復(fù)雜度接近Max-Log-MAP算法，而糾錯性能顯著優(yōu)于Max-Log-MAP算法。因?yàn)楦倪M(jìn)的Log-MAP算法是對ConstantLog-MAP算法的簡化，所以性能略差于ConstantLog-MAP算法，如在BER等于10-5時，相差不到0.1dB。在低誤碼率時，如10-6時，所提出的改進(jìn)的譯碼算法可以實(shí)現(xiàn)與ConstantLog-MAP算法和Log-MAP算法基本上相同的BER性能。

4　譯碼復(fù)雜度分析

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

表1　不同算法的硬件結(jié)構(gòu)空間及延遲比較

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

5　結(jié)　語

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

[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標(biāo)準(zhǔn)Turbo碼譯碼器設(shè)計及實(shí)現(xiàn)[D].北京郵電大學(xué),2013.

[4] 孫增友,張利杰,田勇.SF-MAX-Log-MAP并行譯碼算法及其在LTE中的應(yīng)用研究[J].東北電力大學(xué)學(xué)報,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碼原理與應(yīng)用技術(shù)[M].北京:電子工業(yè)出版社,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。國家自然科學(xué)基金項(xiàng)目(51077039)。孫增友，高工，主研領(lǐng)域：無線電通信。李歡歡，碩士生。王蒙，碩士生。王景芹，教授。

TP3TN911.22

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