一種低復雜度Turbo乘積碼自適應Chase譯碼算法

黨小宇 陶 靜虞湘賓 楊鵬程

(南京航空航天大學電子信息工程學院 南京 210016)

1 引言

Turbo 乘積碼(TPC)是由2維乘積碼構成的串行級聯碼，它是在Turbo碼的基礎上發展而來的[1,2]，采用行列交織[3]，可以達到與隨機交織同樣的性能。上個世紀90年代，Pyndiah等人[4,5]在Chase算法的基礎上進行修改，提出了TPC的軟輸入軟輸出迭代譯碼算法，這種譯碼方式采用了Chase譯碼器的軟輸出信息取代二進制硬判決信息[6]進行迭代譯碼，同時，Chase算法的軟輸出可以看作是對數似然比(LLR)對二進制判決信息的估計值。Chase算法是接近最大似然譯碼性能的一種次最優的、復雜度較低的譯碼算法。Chase算法可以分為Chase-I, Chase-II和Chase-III 3類，它們的主要區別是測試序列產生的方式和個數不同。其中， Chase-II是Chase-I和Chase-III算法在譯碼復雜度和譯碼性能兩方面的折中，因此，Pyndiah選用基于 Chase-II的 TPC迭代譯碼算法。

在信道編譯碼中，如何降低譯碼復雜度[7]，提高譯碼效率[8,9]和譯碼性能[10]一直是一個實際問題，很多專家學者都在研究。雖然在1994年，Pyndiah等人[11,12]驗證了新的分組 Turbo碼可以在誤碼率性能和復雜度性能之間取得折中，但是在降低復雜度方面，仍然存在提升的空間。在文獻[13]和文獻[14]中，已經有報道了TPC自適應譯碼算法，它們在譯碼過程中，都需要估計SNR的值，根據SNR的估計結果，改變每次迭代碼塊中不可靠位數(LRB)的值。

本文提出了一種全新的自適應Chase迭代譯碼算法，其思想是統計譯碼過程中TPC碼塊每一行/列代數譯碼后的序列與接收序列的相同最小歐氏距離的個數，根據統計分析結果自適應地降低譯碼中最不可靠位數的值，從而成倍降低2p個測試序列的個數和相應的歐式距離求解計算量。與現有的Pyndiah每次迭代譯碼采用固定不可靠位數值p的算法相比較，本文提出的算法能在譯碼性能略有降低的代價下，顯著減少了譯碼復雜度。

本文的內容安排如下：第2節，回顧TPC的編碼方法和傳統的Chase-II迭代譯碼方式；第3節，重點介紹自適應TPC譯碼的思想和步驟；第4節，給出不同門限值A的自適應 TPC誤碼率和復雜度曲線仿真結果，并且分析了其優越的性能；第5節，總結全文，給出結論。

2 TPC編譯碼方式

2.1 TPC編碼原理

Turbo乘積碼通常是由兩到三個線性系統碼組成的塊狀碼。如圖1所示，兩個系統碼和，其中分別表示信息位的數目、碼長和最小漢明距離。TPC編碼首先將個信息位排列在如圖1位置的左上角，然后進行行編碼得到矩陣，再進行列編碼得到矩陣[15]。編碼完成后的TPC碼塊表示為,C的參數如下，它最多可以糾正個隨機錯誤，體現了TPC碼很強的糾錯能力。編碼的時候，也可以先進行列編碼，然后進行行編碼，編碼效果相同。在通信系統傳輸過程中，可以逐行傳輸，也可以逐列傳輸。通常為了降低編譯碼的實現復雜度，但又不影響性能分析，Turbo乘積碼的兩個系統碼選擇相同，即。

圖1 TPC編碼結構圖

圖2 TPC譯碼流程圖

2.2 基于Chase-II的TPC譯碼原理

傳統TPC譯碼一般采用Chase-II 迭代譯碼算法，它既可以用于行譯碼又可以用于列譯碼?；驹硎牵簩邮盏降男盘枺糜才袥Q譯碼器，根據不同的試探序列產生候選碼字，然后把它們與接收序列對比，選擇一個與接收序列有最小軟距離的候選碼字作為譯碼器的輸出碼字。

C的歐氏距離定義為

在迭代譯碼過程中，Chase譯碼器產生判決碼字D和競爭碼字B，用來計算軟輸出信息[()]R'm 和外信息 []W m，進而產生新的軟輸入信息 []R m作為下一次迭代的輸入信息。其關系可表示如下：

大量仿真和工程實踐表明[4,5,11,12]，進行 4次迭代輸出最后的判決碼字可以達到比較理想的譯碼性能，同時也可以控制譯碼的復雜度。因此，為了統一比較標準，在后文的自適應譯碼仿真中均采用 4次迭代，并且該結果具有一般性。圖2為TPC譯碼流程圖，其中譯碼器復雜度與(自適應)行/列譯碼器模塊密切相關，所以本文采用自適應譯碼來降低譯碼復雜度和延遲。是用來調整譯碼過程中不可靠外信息對譯碼造成影響的比例因數。當最佳譯碼序列找不到時，()mβ是預先定義的值，用來表示判決碼字D的可靠性。

3 自適應TPC迭代譯碼算法

本文的自適應TPC譯碼算法是在Chase-II 迭代譯碼算法基礎上，通過觀察分析每次譯碼過程內部的規律，研究總結后提出的。

3.1 基于Chase II譯碼算法的結論

為了方便討論，文中采用擴展漢明碼作為TPC的子碼，擴展漢明碼可以糾正一個隨機錯誤，同時發現兩個隨機錯誤。雖然本文的結論和推導證明是在此前提下得到的，但是只需要以此類推，便可以拓展到其它更為一般的子碼。

在一個 TPC碼塊的一次迭代譯碼過程中，我們通常設定行/列譯碼的不可靠位數值p,可以產生2p個測試序列，經過代數譯碼后，產生2p個備選序列。接收序列R和備選序列的相應的歐氏距離記為，并且我們將歐氏距離集合中最小相同歐氏距離的序列個數用sN 來表示。

經過對 TPC碼塊接收序列錯誤發生在可靠位和非可靠位的深入分析推導，我們可以得到如下 3個重要的結論：

(1)在行(列)譯碼過程中，采用最不可靠位數p，可以產生2p個測試序列，經過代數譯碼后得到2p個備選序列。如果沒有錯誤或者有一個錯誤發生在p個不可靠位中，則備選序列中存在個相同的序列，它們與接收序列的歐氏距離最小。

(2)如果有一個錯誤發生在除了p個最不可靠位的其它位，雖然概率比較小，備選序列中只存在一個序列，它與接收序列的歐氏距離最小。

由于篇幅所限，上述3個結論的證明略。

3.2 自適應TPC譯碼步驟

基于上述重要結論和證明，本文提出了一種全新的自適應TPC迭代譯碼算法，通過調整不可靠位數的值p來進行自適應Chase譯碼。

步驟1 對接收到的一個TPC碼塊進行第1次Chase-II行譯碼。采用不可靠位數p，每一行譯碼輸出后得到該行軟輸入數據與代數譯碼后的序列的2p個歐氏距離。

步驟2 對步驟1中得到的2p個歐氏距離排序，記錄下該行的sN 。等到一個碼塊的所有行譯碼結束后，統計這個碼塊中的行數rN，如果，則p值減1，進行第2次行譯碼；如果，則p值不變。具體門限值A取決于TPC子碼的構造(下文仿真中給出A的取值)。

步驟 3 行列交織后對 TPC碼塊進行第 1次Chase-II列譯碼。列譯碼采用已經更新的不可靠位數值p進行譯碼，按照步驟 1的規則，統計一個碼塊中的列數，如果，則p值減1進行第2次列譯碼，如果，則p值不變。

步驟4 按照上述步驟1、步驟2、步驟3的規則進行第2次，第3次，第4次基于Chase-II塊譯碼，并統計相同最小歐氏距離的個數sN ，不可靠位數p驅動下的自適應TPC迭代譯碼，輸出最終譯碼結果。

圖3給出了TPC一個碼塊在一次迭代過程中，自適應譯碼與傳統Chase-II譯碼的對比流程圖，圖中虛線框為自適應TPC譯碼流程圖，可以清楚看到本文自適應譯碼算法的步驟及其與傳統譯碼算法的區別。上述3個重要的結論和步驟是自適應TPC譯碼的核心，后文將通過仿真實驗驗證其誤碼率和復雜度性能。

4 仿真分析

為了驗證本文提出的自適應 TPC譯碼算法的性能，仿真中選擇BPSK調制方式，通過加性高斯白噪聲信道傳輸TPC編碼后的信息。其中TPC子碼采用相同擴展漢明碼(128,120,4)進行行和列編碼。

圖4和圖5分別給出了TPC2(128,120,4)的誤碼率和復雜度性能仿真曲線。文中的復雜度是指在迭代譯碼過程中，根據不同的測試序列產生備選序列，平均每個信息塊需要采用的實數乘法運算(加法運算可忽略)的次數可以參考文獻[9]。需要指出的是，為了方便比較，圖5中縱坐標統一表示成歸一化后的復雜度。它將標準的Chase-II譯碼算法4次迭代采用固定的不可靠位數的值計算出來的實數乘法數目，作為復雜度參考值，并歸一化為單位 1，本文提出的自適應算法復雜度是在此基礎上進行比較并且歸一化得到的。

可以看出，誤碼率和復雜度性能將隨著不同門限值A的變化而變化。當門限值A接近子碼的長度時，誤碼率性能將和傳統的每次迭代p為固定值的性能幾乎相同，但是復雜度大幅度降低。當門限值A比較小時，雖然會損失一些誤碼性能，但是復雜度卻可以更低。

圖3 自適應TPC譯碼流程圖

圖4和圖5中包含了5個不同的門限值 96,A=82,62,42,22，從這兩幅仿真圖可以清楚地看出性能曲線隨著不同門限值的變化關系。例如，當 96 A=時，在誤碼率處，自適應算法相比傳統譯碼算法每次迭代采用固定不可靠位數的值p，只損失了0.08 dB的性能，但是平均復雜度降低了約40.4%；當 22A= 時，在誤碼率處，自適應譯碼的誤碼性能也只有近0.3 dB的損失，但是平均譯碼復雜度只有傳統譯碼的64%，約1/3。因此，我們可以選擇不同的門限值來滿足實際應用需要，在復雜度和誤碼率性能之間尋求折中。

圖4 不同門限值下的TPC誤碼性能曲線

5 結論

圖5 自適應TPC復雜度性能曲線

本文提出了一種全新的低復雜度自適應 TPC迭代譯碼算法，并且通過仿真驗證了本文算法的正確性和可行性。與傳統迭代譯碼采用不可靠位數p為固定值的Chase-II迭代譯碼算法相比，當采用編碼效率為0.879的擴展漢明碼時，在誤碼率為處僅損失約0.08 dB的性能，但是譯碼平均復雜度可降低約2/5，適用于通信譯碼實時性需求較高的場合。

[1] 詹明, 周亮. 一種基于對稱性的雙向雙二進制卷積Turbo碼譯碼結構研究[J]. 電子與信息學報, 2012, 34(5): 1179-1184.Zhan Ming and Zhou Liang. A bidireotional decoding architecture for double binary convolutional Turbo code based on symmetry[J]. Journal of Electronic ＆amp; Information Technology, 2012, 34(5): 1179-1184.

[2] 戴利云, 楊鴻文, 堯文元. 改進的Turbo類編碼的近似碼字錯誤率公式[J]. 電子與信息學報, 2012, 34(5): 1191-1195.Dai Li-yun, Yang Hong-wen and Rao Wen-yuan. An improved approximate formular for word error rate of Turbo-like codes[J]. Journal of Electronic ＆amp; Information Technology, 2012, 34(5): 1191-1195.

[3] Fonseka J P, Dowling E M, Brown T K, et al.. Constrained interleaving of Turbo product codes[J]. IEEE Communications Letters, 2012, 16(9): 1365-1368.

[4] Pyndiah R, Glavieux A, Picart A, et al.. Near optimum decoding of products codes[C]. IEEE Global Communications Conference, San Francisco, CA, 1994: 339-343.

[5] Pyndiah R. Near-optimum decoding of product codes: block Turbo codes[J]. IEEE Transactions on Communications,1998, 46(8): 1003-1010.

[6] Chase D. Class of algorithms for decoding block codes with channel measurement information[J]. IEEE Transactions on Information Theory, 1972, 18(1): 170-182.

[7] 柳昭, 魏延清, 張曉明. Turbo乘積碼譯碼算法的優化和改進[J]. 計算機應用, 2013, 33(2): 397-399.Liu Zhao, Wei Yan-qing, and Zhang Xiao-ming.Optimization and improvement for Turbo product code decoding algorithm[J]. Journal of Computer Applications,2013, 33(2): 397-399.

[8] Morero D A and Hueda M R . Efficient concatenated coding schemes for error floor reduction of LDPC and turbo product codes[C]. IEEE Global Communications Conference,Anacheim CA, 2012: 2361-2366.

[9] Dave S, Kim J, and Kwatra S C. An efficient decoding algorithm for block turbo codes[J]. IEEE Transactions on Communications, 2001, 49(1): 41-46.

[10] Chen Guo-tai, Cao Lei, and Zheng Hai-feng.Near-Log-MAP decoding for turbo product codes[C].International Conference on Wireless Communications,Networking and Mobile Computing (WiCOM), Wuhan, 2011:1-4.

[11] Pyndiah R. Iterative decoding of product codes: block turbo codes[C]. IEEE International Symposium on Turbo Codes＆amp; Related Topics, Brest, France, 1997: 71-79.

[12] Pyndiah R, Picart A, and Glavieux A. Performance of block turbo coded 16-QAM and 64-QAM modulations[C]. IEEE Global Communications Conference, Singapore, 1995, 2:1039-1043.

[13] Mahran A and Benaissa M. Adaptive Chase algorithm for block turbo codes[J]. Electronic Letters, 2003, 39(7): 617-619.

[14] Liu Xing-cheng, Zhang Wei, Wang Zhong-feng, et al.. An efficient adaptive decoding for block turbo codes[C].International Conference on Wireless Communications,Networking and Mobile Computing (WiCOM), Wuhan, 2006:1-5.

[15] Adde P, Pyndiah R, Raoul O, et al.. Block turbo decoder design[C]. IEEE International Symposium on Turbo Codes ＆amp;Related Topics, Brest, France, 1997: 166-169.

[16] Goalic A and Pyndiah R. Real-time turbo-decoding of product codes on a digital signal processor[C]. IEEE International Symposium on Turbo Codes ＆amp; Related Topics,Brest, France, 1997, 2: 624-628.