Turbo乘積碼譯碼算法的簡化

柳 昭，張曉明，韓月平，宋慶國

(山東航天電子技術研究所 山東 煙臺 264003)

1993年Berrou等學者提出了基于軟輸入軟輸出(Soft Input Soft Output，SISO)迭代譯碼算法的Turbo碼[1]。由于Turbo碼具有接近香農限的優異性能，使之成為信道編碼領域的研究熱點。1994年，Pyndiah將Turbo碼的子碼碼型拓展到線性分組碼，認為由分組碼串行級聯構造的Turbo碼同樣具較好的性能。Pyndiah還設計出可以實現SISO的迭代Chase譯碼算法[2]，并將其應用于乘積碼的譯碼，給出了一種譯碼方法類似Turbo碼的SISO迭代譯碼算法，從而提出了Turbo乘積碼(Turbo Product Code，TPC)的概念。

1998年Pyndiah針對TPC提出一種修正的Chase譯碼算法[3]，這是一種近似的最大似然譯碼，可以獲得接近Shannon極限的糾錯性能。但是這種算法需要大量的運算來尋找競爭碼字和計算軟輸出，因此譯碼復雜度高，延時大。近幾年來，有不少學者提出了TPC改進譯碼算法[4-5]，如梯度算法[6]、并行譯碼算法等。這些算法在一定程度上減少了運算量，降低了系統延時，但是由于在迭代譯碼中仍然需要尋找競爭碼字和計算軟輸出，所以算法的復雜度并未實質降低。

本文在傳統Chase算法的基礎上，提出了兩種新的簡化方法，這兩種方法不再需要尋找競爭碼字和計算軟輸出，大大減小了算法的計算量，提高了算法的譯碼速度。

1 傳統Chase算法

硬判決譯碼，即代數譯碼，先用一個固定的判決門限，把超過門限電壓的信號判為邏輯 ，把低于門限電壓的信號判為邏輯 ，然后利用校驗子結合奇偶校驗位進行糾錯。軟判決譯碼，是指先把解調器輸出的抽樣電壓進行Q進制（Q=2m,m＞1）電平量化，再送給譯碼器進行譯碼。Chase軟判決譯碼算法是一種軟輸入硬輸出(Soft Input Hard Output，SIHO)譯碼算法，譯出的碼字為硬輸出。

1.1 Chase算法

假設二進制信息碼元{0，1}通過分量碼都為線性分組碼（n,k,d） 的二維TPC編碼器，經BPSK調制后得到發送碼字E=（e1,e2, …,en），，再經AWGN信道中傳輸，N=（n1,n2, …,nn）信道噪聲 的均值為0，方差為σ2。接收碼字為R=（r1,r2, …,rn），三者滿足：R=E+N。Chase算法實現方法步驟[3]如下：

步驟1：對接收碼字R進行硬判決得到Y=（y1,y2, …,yn），yj∈{,}0 1 。

步驟2：確定Y的p=[d/2]個最不可靠位，記錄其位置。

確定最不可靠位是通過考察yj的可靠度得出的，碼元yj的可靠度定義如下：

p（ej= +1/rj）為信道的轉移概率，推導過程參考文獻[3]。經歸一化后，碼元yj的可靠度可通過考察|rj |得到， |rj |值越小，可靠度越低。

步驟3：構造測試圖樣T q。分別在p個不可靠位置上取'0'和'1' ，'0' 其它位置取 ，構造一個由2p個n維向量組成的測試圖樣T q。

步驟5：將Z q進行代數譯碼（即硬判決譯碼）。得到譯碼結果C i，將譯碼結果作如下映射：0映射成-1，1映射成+1，后歸入集合Ω 。

步驟6：計算集合Ω中的碼字C i與接收信號R間的歐氏距離，選出歐氏距離最小的碼字作為候選碼字D。歐氏距離的計算如下：

1.2 基于Chase算法的軟入軟出譯碼算法

上述Chase算法譯出的碼字為硬輸出，糾錯能力不能得到保證。為了提高TPC的譯碼性能，必須采用迭代譯碼方式，這就需要保證譯碼器的輸出為軟數據。下面直接給出譯碼器軟輸出值的計算公式，推導過程參考文獻[3]。譯碼器的軟輸出值為：

其中，R為接收序列，它是經過解調器解調和Q進制量化得到的軟數據；D為經過SIHO譯碼得到的候選碼字；C為D的競爭碼字，C滿足：與接收序列R的歐式距離最小，且Cj≠Dj。由于在候選碼字集合Ω中存在找不到競爭碼字C的可能，此時可用含可信度因子β(m)的式子來近似計算，β(m)≥0，在實際的工程實踐中，β(m)值主要通過仿真實驗來確定。用軟輸出值減去軟輸入值，就可以得到外部信息。

2 影響算法復雜度的關鍵因素分析

第1節中介紹的傳統Chase算法在硬件上實現比較復雜，主要原因是歐氏距離的計算以及尋找競爭碼字C需要大量的運算。歐氏距離的計算可以用相關值的計算進行簡化，歐氏距離最小等價于相關值最大[7]。尋找競爭碼字C就成為影響算法譯碼復雜度的關鍵因素。

競爭碼字C同時滿足兩個條件：1）與接收序列R的歐式距離最小；2）Cj≠Dj。傳統Chase迭代譯碼算法是將條件b放在前[3]，先判斷Cj≠dj，在候選碼字Ω集合中找到Cj≠dj的序列，把找到的序列放入子集Ω1中，Ω1Ω；然后在Ω1中找到與接收序列R有最大相關值的序列作為競

爭碼字C。用傳統方法尋找競爭碼字C半次迭代需要進行n2×(2p-1)次比較，動態構建n2個子集Ω1 ，進行n2次排序計算。傳統方法尋找競爭碼字C的過程相當繁瑣，逐行或逐列譯碼時每個碼元的競爭碼字C是動態變化的。

3 新的簡化譯碼算法

梯度算法的思想[6]是：為了簡化外部信息的計算，在迭代譯碼時，用前一次迭代得到的候選碼字D(m-2)來代替競爭碼字C，省去了尋找競爭碼字C的過程來降低譯碼復雜度。即當dj(m)≠dj(m-2)時，

當dj(m) =dj(m-2)時，

當m〈2時，仍應用Chase迭代譯碼算法進行譯碼，m≥2時用梯度算法進行譯碼， 為串行迭代譯碼的半迭代次數。由此可見，梯度算法盡管對傳統的Chase算法有所簡化，然而當m〈2時仍需繁瑣的尋找競爭碼字；當m≥2需要比對行和列的候選碼字，而且部分碼元的外部信息仍需通過公式（4）計算。因此，算法的復雜度仍然很大，并未實質減少。

在對梯度算法的研究中發現，行和列的候選碼字大部分都保持不變，即dj(m)=dj(m-2)，此時外部信息大部分都為β(m)dj。因此在梯度算法的基礎上提出兩種簡化方案。第一種簡化方案是：不找競爭碼字C，不再計算軟輸出，外部信息wj直接用經過SIHO譯碼得到的候選碼字D乘以β(m)得到，即wj=β(m)dj，dj∈ { - 1 , 1 } 。此處可信度因子β(m)是經過Q進制量化得到的。

4 性能仿真

使用MATLAB編程工具進行定點數仿真實驗，子碼選取（64,57）×（64,57）的擴展漢明碼構成二維TPC碼，編碼效率為0.793。調制方式為BPSK，傳輸信道為AWGN信道。不可靠碼元個數p=3，采用串行迭代，迭代次數為3次，8bit量化，縮放因子α(m)=[0.0,0.2,0.3,0.5,0.7,0.9]，可信度因子β(m)=[0.2,0.4,0.6,0.8,1.0,1.0],設定參與仿真的碼塊個數為10 000，誤碼率仿真圖如圖1和圖2所示。

由圖1可以看出，在BER為10-6時，傳統Chase算法譯碼可以獲得大約6.6 dB的信道編碼增益，相比硬判決譯碼，編碼增益明顯提高了大約2.5 dB。不找競爭碼字，外部信息用 簡化后，編碼增益比傳統Chase算法僅僅下降了0.5 dB，然而復雜度卻大大降低。同時，簡化算法比硬判決譯碼編碼增益提高了2 dB。

由圖2可以看出，在BER為10-6時，用β(m)簡化算法后相比已有的梯度算法[6]編碼增益下降了大約0.1 dB。若采用最大相關值的均值簡化算法后，此時編碼增益比梯度算法提高了大約0.1 dB，比傳統Chase算法僅僅下降了0.3 dB，然而兩種方法的譯碼過程比梯度算法和傳統Chase算法都簡單，復雜度大大降低。由上述分析可見，兩種簡化算法復雜度更低，實時性更好，而譯碼性能只是略微降低。

圖1 簡化后Chase算法譯碼性能Fig.1 Decoding performance of the simplified Chase algorithm

圖2 簡化后譯碼算法與梯度算法的對比Fig.2 Comparison of the simplified algorithm and gradient algorithm

5 結束語

文中在梯度算法的基礎上介紹了兩種新的TPC軟判決串行簡化迭代譯碼方法，以較小的性能代價換取了很大程度上譯碼復雜度的降低。用β(m)簡化算法后可以獲得大約6.1 dB的信道編碼增益，相比傳統Chase算法，編碼增益下降了大約0.5 dB；而用最大相關值的平均值簡化算法后可以獲得大約6.3 dB的信道編碼增益，相比傳統Chase算法，編碼增益僅僅下降了大約0.3 dB。兩種簡化算法能基本保持傳統Chase算法的譯碼性能，然而譯碼復雜度卻大大降低。這兩種低復雜度算法非常適合硬件實現高碼率實時譯碼，具有一定的工程實用參考價值。

[1]Berrou C,Glavieux A,Thitimajshima P. Near Shannon limit errorcorrecting coding and decoding :Turbo codes[C]// IEEE Int.Conf.Communications ICC’93.NewYork:IEEE,1993:1064-1071.

[2]Pyndiah P,Glavieux A,Picart A, et al. Near optimum decoding of product codes[C]//1994 IEEE GLOBECOM. New York: IEEE,1994:339-343.

[3]Pyndiah P. Near optimum decoding of product codes: block turbo codes[C]//IEEE Transaction on Communications. New York: IEEE,1998:1003-1010.

[4]黃小平，簡福斌，譚燕慶. 一種新的Turbo乘積碼簡化迭代譯碼算法[J].計算機應用研究,2011,28(2):689-691 .

HUANG Xiao-ping，JIAN Fu-bin，TAN Yan-qing. New simplified iterative decoding algorithm for Turbo product codes[J]. Application Research of Computers,2011,28(2):689-691 .

[5]Chen Y，Parhik K. A very low complexity block Turbo decoder composed of extended hamming codes[C]//Proc of IEEE Global Telecommunications Conference.New York: IEEE, 2001:171-175.

[6]徐進延，李紅信. Turbo乘積碼梯度譯碼算法[J].通信技術，2008, 41(12) :81-83.

XU Jin-ting, LI Hong-xin.Study of Gradient Algorithm for Turbo Product Codes[J].Communications Technology, 2008, 41(12) :81-83.

[7]王瑋，葛臨東，鞏克現. TPC基于相關運算的迭代譯碼算法[J]. 計算機應用，2010,30(7) :1760-1762.

WANG Wei，GE Lin-dong，GONG Ke-xian. Iterative decoding algorithm of TPC based on correlation computation[J]. Journal of Computer Applications,2010,30(7) :1760-1762.