一種低復(fù)雜度Turbo乘積碼自適應(yīng)Chase譯碼算法

黨小宇 陶 靜虞湘賓 楊鵬程

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

1 引言

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

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

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

本文的內(nèi)容安排如下：第2節(jié)，回顧TPC的編碼方法和傳統(tǒng)的Chase-II迭代譯碼方式；第3節(jié)，重點(diǎn)介紹自適應(yīng)TPC譯碼的思想和步驟；第4節(jié)，給出不同門限值A(chǔ)的自適應(yīng) TPC誤碼率和復(fù)雜度曲線仿真結(jié)果，并且分析了其優(yōu)越的性能；第5節(jié)，總結(jié)全文，給出結(jié)論。

2 TPC編譯碼方式

2.1 TPC編碼原理

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

圖1 TPC編碼結(jié)構(gòu)圖

圖2 TPC譯碼流程圖

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

傳統(tǒng)TPC譯碼一般采用Chase-II 迭代譯碼算法，它既可以用于行譯碼又可以用于列譯碼?；驹硎牵簩邮盏降男盘?，利用硬判決譯碼器，根據(jù)不同的試探序列產(chǎn)生候選碼字，然后把它們與接收序列對比，選擇一個與接收序列有最小軟距離的候選碼字作為譯碼器的輸出碼字。

C的歐氏距離定義為

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

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

3 自適應(yīng)TPC迭代譯碼算法

本文的自適應(yīng)TPC譯碼算法是在Chase-II 迭代譯碼算法基礎(chǔ)上，通過觀察分析每次譯碼過程內(nèi)部的規(guī)律，研究總結(jié)后提出的。

3.1 基于Chase II譯碼算法的結(jié)論

為了方便討論，文中采用擴(kuò)展?jié)h明碼作為TPC的子碼，擴(kuò)展?jié)h明碼可以糾正一個隨機(jī)錯誤，同時發(fā)現(xiàn)兩個隨機(jī)錯誤。雖然本文的結(jié)論和推導(dǎo)證明是在此前提下得到的，但是只需要以此類推，便可以拓展到其它更為一般的子碼。

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

經(jīng)過對 TPC碼塊接收序列錯誤發(fā)生在可靠位和非可靠位的深入分析推導(dǎo)，我們可以得到如下 3個重要的結(jié)論：

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

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

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

3.2 自適應(yīng)TPC譯碼步驟

基于上述重要結(jié)論和證明，本文提出了一種全新的自適應(yīng)TPC迭代譯碼算法，通過調(diào)整不可靠位數(shù)的值p來進(jìn)行自適應(yīng)Chase譯碼。

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

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

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

步驟4 按照上述步驟1、步驟2、步驟3的規(guī)則進(jìn)行第2次，第3次，第4次基于Chase-II塊譯碼，并統(tǒng)計(jì)相同最小歐氏距離的個數(shù)sN ，不可靠位數(shù)p驅(qū)動下的自適應(yīng)TPC迭代譯碼，輸出最終譯碼結(jié)果。

圖3給出了TPC一個碼塊在一次迭代過程中，自適應(yīng)譯碼與傳統(tǒng)Chase-II譯碼的對比流程圖，圖中虛線框?yàn)樽赃m應(yīng)TPC譯碼流程圖，可以清楚看到本文自適應(yīng)譯碼算法的步驟及其與傳統(tǒng)譯碼算法的區(qū)別。上述3個重要的結(jié)論和步驟是自適應(yīng)TPC譯碼的核心，后文將通過仿真實(shí)驗(yàn)驗(yàn)證其誤碼率和復(fù)雜度性能。

4 仿真分析

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

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

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

圖3 自適應(yīng)TPC譯碼流程圖

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

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

5 結(jié)論

圖5 自適應(yīng)TPC復(fù)雜度性能曲線

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

[1] 詹明, 周亮. 一種基于對稱性的雙向雙二進(jìn)制卷積Turbo碼譯碼結(jié)構(gòu)研究[J]. 電子與信息學(xué)報(bào), 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] 戴利云, 楊鴻文, 堯文元. 改進(jìn)的Turbo類編碼的近似碼字錯誤率公式[J]. 電子與信息學(xué)報(bào), 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乘積碼譯碼算法的優(yōu)化和改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用, 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.