一種新的聯合Turbo譯碼算法

茹玉年，李建平

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

1 引言

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

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

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

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

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

2 Turbo譯碼介紹

迭代譯碼是Turbo碼具有接近香農限的性能的一個重要因素，可以將其視為一種動態反饋系統。若要在Turbo碼中使用其最優的譯碼方法最大似然譯碼，那么計算復雜度將非常的大難以實現，所以C.Berrou等人將其譯碼簡化成次優譯碼算法(最大后驗概率譯碼)的迭代過程。因此分量碼譯碼必須采用SISO(soft－input soft－output)軟信息輸入輸出算法，從而實現迭代譯碼過程中軟信息在分量譯碼器之間的交換。圖1是Turbo譯碼器的結構，Turbo碼譯碼過程如下:第一個分量譯碼器SISO1產生軟判決信息L1(u)和外部信息Le1(u)，Le1(u)再經過交織器進行交織后傳給第二個譯碼器，作為第二個譯碼器的先驗信息。第二個分量譯碼器也產生軟判決信息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的對數似然比(loglikelihood ratio)如公式(2)所示［1］。

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

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

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

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

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

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

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

表1 不同譯碼算法使用的校正函數

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

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

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

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

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

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

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

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

2 迭代停止準則介紹

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

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

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

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

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

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

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

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

即在

時停止迭代。

3 新的聯合譯碼算法

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

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

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

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

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

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

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

4 仿真環境和結果

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

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

圖3 三種譯碼算法平均迭代次數

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

從圖2、3可以得出:

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

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

表2中為不同信噪比下需使用Log－MAP譯碼的數據幀數(實驗中總的數據幀數為10000)?？梢娫谄俨紖^內，只需要對少量的數據幀進行性能更優的Log－MAP算法譯碼就可以有效的提高譯碼的性能，同時，相對于10000幀的數據，少量幀使用Log－MAP譯碼所帶來的運算量可以忽略不計，所以新方法的平均迭代次數幾乎和常數法的相同。

5 結論

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

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

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

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

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

［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 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，Fossorier 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).