茹玉年，李建平

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

1 引言

1993年，一個新的前向糾錯碼Turbo碼由Berrou，Glavieux和 Thitimajashima 提出［1］。Turbo碼通過交織器和迭代譯碼使得譯碼性能非常接近香農限。但是Turbo碼迭代譯碼算法計算量大、耗時長，因此，研究和探求一種性能良好而且高效率的Turbo譯碼算法具有重要的現(xiàn)實意義。

公開發(fā)表的Turbo碼譯碼算法主要有三種，一種是Turbo碼發(fā)明者 Berrou最早給出的改進型BCJR迭代算法，一般稱為標準MAP(最大后驗概率)算法［2］;第二種是基于對數(shù)域的 BCJR迭代算法，即 Log－MAP算法［3］;第三種是軟輸出 Viterbi算法(SOVA)算法［4］。

由于MAP算法譯碼復雜度高，SOVA算法譯碼性能差，所以算法中Log－MAP算法最為常用，它又分為線性近似 Log － MAP［5］、常數(shù) Log － MAP［6］和Max－Log－MAP三種。這三種Log－MAP的簡化算法通過不同的逼近函數(shù)，減少了Log－MAP中的指數(shù)和對數(shù)運算，因此譯碼效率比Log－MAP算法有了較大提高，但是帶來了譯碼正確率的下降。

本文在研究以上Turbo碼譯碼算法的基礎上，結合實驗觀測現(xiàn)象，提出了一種新的聯(lián)合譯碼算法，這種算法聯(lián)合了常數(shù)Log－MAP譯碼算法和Log－MAP譯碼算法:譯碼初始階段使用算法復雜度較低的常數(shù)譯碼算法;第二個階段對常數(shù)譯碼算法達到最大迭代次數(shù)時依然未能滿足停止迭代準則的數(shù)據(jù)幀使用譯碼性能更好但是復雜度更高的Log－MAP算法，以提高譯碼正確率。

新的聯(lián)合譯碼方法的到了較好的性能和效率的折中。只增加了較少的計算量，使得常數(shù) Log－MAP達到了近似Log－MAP的糾錯性能。

2 Turbo譯碼介紹

迭代譯碼是Turbo碼具有接近香農限的性能的一個重要因素，可以將其視為一種動態(tài)反饋系統(tǒng)。若要在Turbo碼中使用其最優(yōu)的譯碼方法最大似然譯碼，那么計算復雜度將非常的大難以實現(xiàn)，所以C.Berrou等人將其譯碼簡化成次優(yōu)譯碼算法(最大后驗概率譯碼)的迭代過程。因此分量碼譯碼必須采用SISO(soft－input soft－output)軟信息輸入輸出算法，從而實現(xiàn)迭代譯碼過程中軟信息在分量譯碼器之間的交換。圖1是Turbo譯碼器的結構，Turbo碼譯碼過程如下:第一個分量譯碼器SISO1產(chǎn)生軟判決信息L1(u)和外部信息Le1(u)，Le1(u)再經(jīng)過交織器進行交織后傳給第二個譯碼器，作為第二個譯碼器的先驗信息。第二個分量譯碼器也產(chǎn)生軟判決信息L2(u)和外部信息Le2(u)。Le2(u)通過解交織器解交織后傳給SISO1，作為第一個譯碼器的先驗信息。第一個譯碼器的先驗信息初始值為0。如上所述外部信息在兩個分量譯碼器之間傳遞來提高譯碼性能直到滿足迭代停止準則，停止譯碼。最后再對L2(u)進行硬判決得到譯碼輸出，即逐個對信息序列u=(u1，u2，…，uN)的 L(u)值進行判定，如公式(1)所示。

圖1 Turbo碼譯碼結構框圖

Turbo碼的分量譯碼器采用了逐比特最大后驗概率似然比譯碼算法計算L(u)。下面將簡要介紹Log－MAP算法以及其計算是重要的三個變量:前向度量、分支度量、后向度量的計算方法。

時刻k，計算接收比特uk的對數(shù)似然比(loglikelihood ratio)如公式(2)所示［1］。

其中s’表示示存儲器前—狀態(tài)，s表示存儲器下—狀態(tài)。前向度量αk(s)和后向度量βk(s)可以通過下面的遞推公式(3)(4)計算:

分支度量和編碼器的狀態(tài)轉移概率以及信道的轉移概率有關:

公式(5)中Lc是信道置信度，表示信道干擾下接收到的可信度，L(uk)是先驗信息，C可以認為是一個常數(shù)，x是系統(tǒng)信息，y是校驗信息。Max*是雅可比變換式。

其中稱f(|a－b|)為校正函數(shù)。

根據(jù)對校正函數(shù)的不同逼近方式的選擇Log－MAP算法又可以簡化成以下復雜度較低的算法［7］。

Max－Log－MAP算法，它忽略校正函數(shù)，所以僅僅做了求最大值運算。這樣就使得計算復雜度有了大幅的減小，但是因為沒有計算校正函數(shù)將會對其譯碼性能造成較大影響。常數(shù)Log－MAP算法:在區(qū)間(0，2)內校正函數(shù)的值取0.375，其他區(qū)域的值取零，這樣明顯減少了運算復雜度。線性Log－MAP算法:使用了線性函數(shù)對原來的校正函數(shù)進行了逼近，取了麥克勞林展開式的常數(shù)項和一次項。

Log－MAP算法的性能幾乎接近香濃理論極限，但譯碼過程中需要計算校正函數(shù)，存在指數(shù)和對數(shù)運算，復雜度較高。Max－Log－MAP算法線性逼近、常數(shù)逼近Log－MAP等方法使用了復雜度較低的算法代替，這樣使得計算復雜度大幅減小，但是也帶來了性能上的損失，見表1。

表1 不同譯碼算法使用的校正函數(shù)

Turbo碼采用迭代譯碼來提高譯碼性能。通過觀測譯碼性能、迭代次數(shù)和外部信息的收斂，可以將Turbo碼的 BER性能曲線劃分成三個典型的區(qū)域［8］。

(1)BER區(qū)域 I(BER≥10－2)

對應較低的信噪比;在這個區(qū)域誤碼率幾乎不隨迭代次數(shù)的增加而降低。對于這樣的誤比特率，一般的通信系統(tǒng)都是難以接受的。

(2)BER 區(qū)域 II(10－5≤BER ≤10－2)，

對應中信噪比;在這個區(qū)域誤碼率隨迭代次數(shù)的增加而降低，所以譯碼收斂到較低的誤碼率是可能的，但是收斂速度較慢。這個區(qū)間又被稱作瀑布區(qū)(Waterfall Region)。在這個區(qū)域Turbo碼的性能遠遠優(yōu)于其它糾錯碼。

(3)BER區(qū)域 III(BER≤10－5)

對應較高的信噪比;在這個區(qū)域誤碼率隨迭代次數(shù)的增加迅速降低，而軟判決信息也能迅速收斂。一般迭代2－3次后趨于收斂，繼續(xù)進行迭代性能無改善，這個區(qū)間也被稱作錯誤平層區(qū)(BER Floor Region)，可以認為是近似無差錯的數(shù)據(jù)傳輸。

Turbo碼譯碼對于絕大多數(shù)的幀信息，經(jīng)過很少的幾次迭代后，就會很快收斂到平穩(wěn)狀態(tài)，若采用預設一個迭代次數(shù)，會產(chǎn)生不必要的延時;若信息比特幾次迭代收斂，但更多迭代時，似然比將會下降呈振蕩形式，信息比特的譯碼將出現(xiàn)誤碼。因此譯碼過程中，在不降低譯碼性能情況下，運用迭代停止判決，可以降低譯碼的延時，并且防止由于振蕩時所帶來不必要的性能下降。所以在迭代譯碼時需要使用停止判決方法，來動態(tài)的控制迭代譯碼的次數(shù)，即在滿足一定條件后就停止譯碼。這樣既能減少譯碼所需的計算量，還能降低譯碼延時，同時還能保證譯碼的性能。下面介紹了一些典型的迭代停止準則。

2 迭代停止準則介紹

(1)交叉熵最小化CE(Cross Entropy)迭代停止準則［9］

兩個分布之間的交叉熵是大于零的，當他們同分布時，交叉熵等于零。根據(jù)Turbo碼迭代譯碼的特性可知:兩個分量譯碼器的輸出概率分布隨著譯碼迭代次數(shù)的增加而趨近于相近。所以，兩個分量譯碼器輸出的交叉熵值將隨著迭代次數(shù)的增加而趨近于零。所以可以使用交叉熵來表征譯碼的程度。

兩個分量譯碼器的輸出對數(shù)似然比的概率分布PDEC1(u|y)和PDEC2(u|y)，則二者之間的交叉熵可以表示為:

隨著迭代次數(shù)的增加，PDEC1(u|y)和PDEC2(u|y)之間的交叉熵逐漸減小，當交叉熵達到最小值時，就實現(xiàn)了最佳譯碼，迭代即可停止。

(2)符號改變率SCR(Sign Change Ratio)迭代停止準則［10］

由于連續(xù)兩次迭代進程里中各元素符號正負的改變個數(shù)直接與兩次迭代輸出間的交叉熵有關，由此由這種關系引出了另外一種停止準則:SCR準則。在迭代進程中，當改變個數(shù)滿足u(i)≤(0.005－0.03)N時，停止迭代。所以門限值值越小，迭代次數(shù)越多，性能下降越小。SCR準則并不需要CE準則中的指數(shù)運算，也無需計算交叉熵，只需要儲存每個外信息值的符號并作比較即可?？梢奡CR準則相對以CE準則只需更少的存儲空間和計算復雜度。

(3)輔助硬判決法HDA(Hard Decision Aided)

HDA準則是一種比較簡單的硬比特判決準則。通過觀察迭代譯碼過程可以發(fā)現(xiàn):迭代次數(shù)的增加，譯碼器輸出的信息比特對數(shù)似然比值不斷增大，成功譯碼的情況下數(shù)據(jù)幀中的每個比特的軟值都達到收斂。但最終的譯碼判決都是根據(jù)每個比特似然比值的正負符號來進行判決的。它是基于在第k次與第k－1次迭代時硬判決相比較，又因為迭代譯碼收斂時，第k次與第k－1次迭代時的硬判決是一致的，所以在HDA準則中，我們只需存儲前一次迭代中對信息比特的硬判決輸出，然后用它與本次迭代中的信息比特的硬判決輸出相比較，假若在整個數(shù)據(jù)幀中兩次的硬判決輸出完全相同，則停止迭代。

即在

時停止迭代。

3 新的聯(lián)合譯碼算法

經(jīng)過大量的實驗和觀察發(fā)現(xiàn):在中高信噪比(1db－3db)時，數(shù)據(jù)的軟判決信息值會隨著迭代次數(shù)的增加而呈現(xiàn)出如下的三種狀況:

大量的數(shù)據(jù)幀只需要使用復雜度較低的常數(shù)Log－MAP譯碼算法，經(jīng)過迭代之后，軟判決信息的值就可以很快收斂且正負號固定不變，譯碼成功。

少量的數(shù)據(jù)幀在常數(shù)Log－MAP譯碼算法下經(jīng)過多次迭代依然無法成功譯碼，軟判決信息處于震蕩狀態(tài)很難收斂，正負號也不斷地跳變。但是使用復雜度較高的Log－MAP算法經(jīng)過有限次迭代就可以成功譯碼。

還有一少部分數(shù)據(jù)幀，在常數(shù)Log－MAP譯碼算法下經(jīng)過多次迭代無法成功譯碼，即使使用Log－MAP算法依然無法成功譯碼。

本文根據(jù)上述實驗觀察，結合常數(shù)Log－MAP譯碼算法和Log－MAP算法和停止迭代準則，提出了一種新的聯(lián)合譯碼算法:

步驟一:譯碼開始時使用復雜度較低的常數(shù)Log－MAP譯碼算法，使用停止判決準則HDA準則判決。

步驟二:對達到最大迭代次數(shù)時依然未能滿足停止迭代準則的數(shù)據(jù)幀使用譯碼性能更好但是復雜度更高的Log－MAP算法。

4 仿真環(huán)境和結果

仿真環(huán)境:仿真是在AWGN信道上采用BPSK調制。交織器采用交織長度N=512的偽隨機交織器，Turbo碼的生成多項式為(7，5)，碼率為 1/3，HDA的最大迭代次數(shù)設定為10次，每個信噪比下用10000幀數(shù)據(jù)幀。

圖2 三種譯碼算法的BER性能

圖3 三種譯碼算法平均迭代次數(shù)

表2 不同信噪比下需使用Log－MAP譯碼的數(shù)據(jù)幀數(shù)

從圖2、3可以得出:

在信噪比為0.6db到0.9db時，新的譯碼算法在譯碼性能上非常接近Log－MAP算法，好于常數(shù)Log－MAP算法。但是平均迭代次數(shù)大于常數(shù)法。

在信噪比為0.9db到1.6db時，新的譯碼算法不僅譯碼性能上非常接近Log－MAP算法，明顯好于常數(shù)Log－MAP算法;而且平均迭代次數(shù)和常數(shù)Log－MAP算法幾乎相同?？梢赃_到幾乎使用常數(shù)法的復雜度就可以達到Log－MAP的譯碼性能。

表2中為不同信噪比下需使用Log－MAP譯碼的數(shù)據(jù)幀數(shù)(實驗中總的數(shù)據(jù)幀數(shù)為10000)。可見在瀑布區(qū)內，只需要對少量的數(shù)據(jù)幀進行性能更優(yōu)的Log－MAP算法譯碼就可以有效的提高譯碼的性能，同時，相對于10000幀的數(shù)據(jù)，少量幀使用Log－MAP譯碼所帶來的運算量可以忽略不計，所以新方法的平均迭代次數(shù)幾乎和常數(shù)法的相同。

5 結論

本文提出了一種新的Turbo譯碼算法，并且將它和常數(shù)Log－MAP和Log－MAP算法和做了對比。經(jīng)過仿真可以得到:

在BER 區(qū)域 I(0.6dB －0.9dB)，即低信噪比下:新的方法不能很好地適應，主要是因為在低信噪比的條件下，常數(shù)法真確譯碼的數(shù)據(jù)幀少，數(shù)據(jù)還需經(jīng)過Log－MAP算法繼續(xù)譯碼，所以導致平均迭代次數(shù)高于常數(shù)法和Log－MAP譯碼算法。

在BER 區(qū)域 II(0.9dB－1.6dB)，即在瀑布區(qū)，新的方法幾乎與常數(shù)法的迭代次數(shù)相同。這也說明了，在瀑布區(qū)較多的數(shù)據(jù)幀只需要使用常數(shù)Log－MAP算法，就可以通過停止迭代準則在10次迭代之內成功譯碼，因此也只有少量的數(shù)據(jù)幀10次迭代之后任未成功譯碼，需要用譯碼準確度更高的Log－MAP算法繼續(xù)譯碼，這樣就可以將其性能提高到采用Log－MAP譯碼算法的性能。

總體來說，新的方法在瀑布區(qū)可以用幾乎和常數(shù)法相同的復雜度來達到Log－MAP譯碼算法的精度。

新的譯碼算法還可使用不同的停止準則來判定哪些數(shù)據(jù)幀需要繼續(xù)采用Log－MAP算法來進一步準確譯碼，因此也會產(chǎn)生不同的對性能和效率的折中，以適應不同的實際譯碼需求。

［1］Berrou C，Glavieux A.Near－optimum error－ correcting coding and decoding:Turbo － codes［J］.IEEE Trans Commun，1996，44:1261 －1271.

［2］Berrou C，Glavieux A，Thitimajstiima P.Near Shannon limit error－correcting coding and decoding［C］.IEEE Int Conf on Communications 1993，Geneva，1993:1064 －1070.

［3］Obertson P，Villebrnn E，Hoecher P.A comparison of optimal and sub－optimal MAP decoding algorithms operation in the Log Domain［C］.Int Conf Oil Communications 1995，Seattle，Gateway to Globalization，1995:1009 －1013.

［4］Francisco Blanquez－ Casado，F(xiàn) Javier Martin －Vega，David Morales － Jimenez，et al.Adaptive SOVA for 3GPP －LTE Receivers［J］.IEEE communications letters，2014，18(6).

［5］Cheng J F，Ottosson T.Linearly approximated Log－ MAP algorithms for turbo decoding［C］.IEEE Vehic Techn Conf(VTC)，Tokyo，Japan，May 2000:2252－2256.

［6］Gross W J，Gulak P G.Simplified MAP algorithm suitable for implementation of turbo decoders［J］.IEEE lectron Lett，1998，34(16):1577 －1578.

［7］Stylianos Papaharalabos，Takis Mathiopoulos P，Guido Masera，Maurizio Martina.On Optimal and Near－Optimal Turbo Decoding Using Generalized max*Operator［J］.IEEE communication letters，2009，13(7).

［8］許可.Turbo均衡關鍵技術研究［D］.長沙:國防科技大學，2011.

［9］Moher M.Decoding via cross entropy minimization［C］.IEEE Globecom Conf，Houston，TX，Dec 1993:809－813.

［10］Shao R Y，Lin Shu，F(xiàn)ossorier M C.Two Simple Stopping Criterion for Turbo Decoding［J］.IEEE Trans on Comnaunication，1999，47(8):1117 －1120.

［11］Yuejun Wei，Yuhang Yang，Lili Wei，Wen Chen.A New Parity－Check Stopping Criterion for Turbo Decoding［J］.IEEE communications letters，2012，16(10).