低復雜度的TPC自適應譯碼算法

韓明，張佳巖，趙洪林

?

低復雜度的TPC自適應譯碼算法

韓明，張佳巖，趙洪林

(哈爾濱工業大學通信技術研究所，黑龍江哈爾濱，150001)

為降低TPC譯碼算法復雜度，提出一種新的低復雜度自適應譯碼算法。新算法適用于子碼為擴展漢明碼的TPC碼，以不估計SNR的自適應譯碼算法為基本框架結構，利用碼字可靠性特征，引入1個可用于外信息計算的簡單公式，在自適應減小不可靠比特數的同時，降低外信息的計算量。研究結果表明：對于擴展漢明碼(64,57,4)為子碼的TPC碼，新算法相比于原自適應譯碼算法在誤碼率為10?5時b/0僅降低了0.05 dB，復雜度卻降低約1/3，可見新算法在性能和復雜度方面實現了很好的平衡和折中。

TPC；Chase?Pyndiah譯碼；自適應譯碼；低復雜度

Turbo乘積碼(Turbo product code，TPC)由Turbo碼延伸而來，是一種高效的信道編碼方式[1]，具有很強的糾錯能力，因性能接近香農極限而受到關注。目前4G LTE(long term evolution)網絡已開始應用，更快的數據傳輸需要通信新技術的支持，TPC碼也可應用于LTE中以提高系統可靠性[2?3]。TPC自提出以來，各國學者一直致力于其譯碼算法的研究[4?6]。PYNDIAH等[7]以Chase算法[8]為基礎，提出了TPC的軟輸入軟輸出(soft input soft output, SISO)迭代譯碼算法，稱為經典的Chase?Pyndiah算法。該算法性能優越，但復雜度較高，如何在性能和復雜度間找到最佳平衡點是必須要解決的實際問題。隨著譯碼過程的進行，自適應改變與運算量相關的參數是一種有效的解決方法。MAHRAN等[9]首先提出了TPC自適應譯碼算法，通過設定與信噪比SNR有關的門限，降低了譯碼復雜度。LIU等[10]對自適應譯碼算法進行改進，使其更適合實際使用，但是該算法要對SNR進行估計，這不僅帶來了相當數量的乘法運算，而且要有大量的數據才能確保估計結果相對準確。黨小宇等[11]提出了不估計SNR的自適應譯碼算法，根據接收碼字的統計特性來調整參數，使得譯碼復雜度降低。盡管近些年有部分學者研究了TPC譯碼新算法[12?13]，但自適應譯碼依舊是一個值得探討的方向。本文作者以不估計SNR的自適應譯碼算法為基礎，融入1個計算外信息的簡單公式，提出自適應譯碼新方法。

1 TPC編碼與譯碼

1.1 TPC編碼結構

TPC碼具有二維塊狀結構[14]，如圖1所示，子碼為線性系統分組碼，和分別表示碼字長度和信息位長度，其碼型可以靈活選取，通常為漢明碼、BCH碼或RS碼，相應編碼的擴展碼字形式也常被采用以增加糾錯能力。

TPC編碼簡單，先對信息比特矩陣逐行編碼，再將得到的矩陣逐列編碼即可[15]。行列編碼的先后順序不同，不影響編碼效果。理論上講，對行和列的編碼可以采用不同的編碼結構和編碼方式，但考慮到實際實現中的編譯碼復雜度，一般采用相同的編碼規則來構造TPC碼。

圖1 TPC編碼結構

1.2 傳統的Chase?Pyndiah譯碼算法

針對TPC譯碼，PYNDIAH等[7]提出了SISO的概念，其基本思想是：根據接收到信號的軟信息，確定個不可靠位，從而形成()個測試序列，然后對測試序列進行代數譯碼得到候選碼字集合，最后通過歐氏距離信息，在中找到似然碼字和競爭碼字，從而計算軟輸出和外信息。第個碼元的軟輸出和外信息w可以由式(1)和式(2)來表示。

(2)

Chase?Pyndiah算法的1次迭代過程如圖2所示，由2個半迭代構成。圖2中：為外信息；為半迭代次數；為重量因子，用于調整外信息在軟輸入信息里所占的比重；row和col分別表示行和列。迭代結構中的軟輸入信息的表達式如下：

圖2 Chase?Pyndiah迭代譯碼結構

Fig. 2 Structure of Chase?Pyndiah iterative decoder

Chase?Pyndiah算法的復雜度主要來自2方面：一方面是構造候選碼字集合時大量的代數譯碼，另一方面是計算外信息時繁雜的算數運算[4]。對于行列編碼方式相同的TPC碼，以每一行(列)接收信號的譯碼運算量來說明復雜度：每一行(列)數據都確定個最不可靠位，對應測試序列個，需要進行次代數譯碼，若迭代次數為T，則構造每一行(列)的候選碼字集就要次代數譯碼；對于外信息的計算，先要找到行(列)中每個碼元所對應的競爭碼字，若子碼的碼長為，則要進行次算術運算(主要比較和存儲等相關操作)。

對TPC譯碼性能有明顯影響，而以上分析知算法復雜度也隨呈指數增加，故的選擇要從性能和復雜度2方面折中考慮。隨譯碼過程進行，碼字可靠性提高，合理地減小將是簡化譯碼算法的有效手段，而算法的復雜度則可以用代數譯碼(hard-decision decoding，HDD)數目和算術運算(arithmetic operation，AO)數目來衡量和評價。

1.3 不估計SNR的自適應譯碼算法

不估計SNR的自適應譯碼算法見文獻[11]。子碼為擴展漢明碼時，首先統計與接收信號相同最小歐氏距離的候選碼字數目，依據統計數據，自適應地減小不可靠比特數，從而降低算法復雜度。其實現過程簡單介紹如下。

1) 對于接收信號序列中的1個TPC碼塊，使用Chase?Pyndiah算法進行1次行譯碼。設定不可靠位數為，每行信息譯碼后都會得到代數譯碼后的數據與軟輸入信息的歐氏距離個。

3) 進行行列交織，按照步驟1)和2)的規則，使用已經更新過的對碼塊列譯碼，根據譯碼后統計結果與門限值的關系再次對調整。

4) 按以上3步繼續進行，TPC迭代譯碼，隨著迭代次數的進行不停調整，輸出最終譯碼結果。需要注意的是：為了保證譯碼性能，當為1以后，不管是否滿足減1的條件，都保持不變。

此算法采用了自適應譯碼的新思想，不需要進行SNR估計，不但減小了譯碼復雜度，而且更有利于算法的實現，但是降低復雜度方面仍然有很大的提升空間。接下來以該算法為基礎，融入1個用于計算外信息的簡單公式，給出新的自適應譯碼算法。

2 新的自適應譯碼算法

2.1 計算外信息的簡單公式

Chase?Pyndiah算法中，不存在競爭碼字，表示代數譯碼后可靠性較高。若可靠，則外信息可通過和1個可靠性參數來進行估計。這樣就可以引入1個計算外信息的簡單公式，見文獻[16]中。因新算法中此公式至關重要，現將其推導過程介紹如下。

對于高斯白噪聲信道下的BPSK調制，比特可靠性信息(log likelihood radio,LR)可以用下式表示：

(6)

因此，式(6)可以近似表達為

(9)

(10)

而

(12)

故

這樣式(4)變為

(14)

以上的推導過程都是建立在代數譯碼可靠這一理論基礎上的，而可靠性是()的函數，故可以設定1個門限，若＜，則認為代數譯碼可靠，式(14)即可使用。門限的選擇與子碼碼型有關，應在其最大糾錯能力以內，可通過軟件仿真來確定，見文獻[16]。

2.2 新算法譯碼流程

新算法以1.3中介紹的不估計SNR的自適應譯碼算法為基礎，融入新的外信息公式，在自適應減小的同時，簡化可靠碼字的外信息計算。

盡管由2.1節中推導過程可知式(14)也適用于糾多位錯的BCH碼或RS碼，但不估計SNR的自適應譯碼算法是以TPC子碼是擴展漢明碼為前提提出的，算法中的理論和譯碼步驟都與擴展漢明碼對應，新算法以此為基本框架，所以為方便討論，也采用擴展漢明碼作為子碼，其他碼型需要進一步類比分析。由于擴展漢明碼只能糾正全部一位錯誤和部分2位錯 誤[18]，若門限過低，則必然影響譯碼性能，綜合考慮糾錯能力，可將門限設定為1，也就是說，對于每一行(列)的外信息計算，若原碼字正確，則利用新公式，否則使用傳統算法。需要注意的是，譯碼正確意味著，此時式(14)簡化為

以碼塊的1次行譯碼為例來介紹新算法，其基本流程如圖3所示，具體步驟如下。

1) 硬判決操作。接收到的TPC碼塊信號，每行均進行硬判決，第行的硬判決碼字可記為。

2) 代數譯碼。對硬判決后的序列逐行進行代數譯碼，第行代數譯碼得到。

4) 自適應調整。根據N與門限的關系來調整不可靠比特數。

圖3 新的自適應譯碼算法流程圖

3 算法仿真分析

為證明新算法在性能和復雜度方面的優良特性，使用Matlab軟件對傳統算法、1.3節的自適應譯碼算法和2.2節的新算法分別進行仿真和對比分析。TPC子碼設定為(64,57,4)的擴展漢明碼，采用BPSK調制方式，信息在加性高斯白噪聲信道中傳輸，不可靠比特初始值設為=4，迭代4次。另外，如1.2節中分析，算法復雜度可用代數譯碼數目和算術運算數目來衡量和評價。

對于不估計SNR的自適應譯碼算法，設定的門限越小，復雜度越低，但是性能也隨之變差，若性能損失太大，則得不償失。不同門限的算法譯碼性能如圖4所示。以誤碼率為10?5為例，=56時和=48時，分別損失了約0.1 dB和約0.5 dB的性能；而=40時，性能損失過大，不宜選取。

1—未編碼BPSK；2—傳統算法；3—自適應A=56；4—自適應A=48；5—自適應A=40。

為保證譯碼性能，設定=56，對新算法進行仿真，性能和復雜度如圖5~7所示，其中歸一化代數譯碼和算術運算的運算量分別用HDD和AO表示。在誤碼率為10?5處，相比于傳統算法，新算法b/0僅降低了約0.15 dB，但是代數譯碼運算量降低了約60%，算數運算量降低了約70%，總體復雜度在傳統算法的40%以下；相比于原自適應譯碼算法，新算法b/0僅降低了0.05 dB，算法復雜度卻降低了約1/3，可以在很大程度上減少譯碼延時。

1—未編碼BPSK；2—傳統算法；3—原自適應A=56；4—新算法A=56。

1—傳統算法；2—原自適應算法；3—新算法。

1—傳統算法；2—原自適應算法；3—新算法。

從譯碼流程和仿真結果來看：由于新算法對可靠碼字都使用式(15)進行了相同處理，而忽略了各碼元差異性，使得外信息矩陣較傳統方法有所變化，雖變化不大，但當不可靠比特數減小時，這種變化的影響已逐漸表現出來，導致性能稍有下降。但是，新算法根據譯碼程度來減少不可靠比特數，并對可靠碼字只進行1次代數譯碼，而未進行復雜的候選碼字集構造和外信息計算等操作，簡化了運算。綜合分析，新算法盡管性能略有降低，但極大地降低了譯碼復雜度，優勢明顯。

4 結論

1) 在分析傳統TPC譯碼復雜度來源的基礎上，介紹了不估計SNR的自適應譯碼算法，并以此算法為基礎，引入1個用于外信息計算的簡單公式，提出了新的自適應譯碼算法，實現不可靠比特數和外信息計算的同步簡化。通過與原自適應算法對比，新算法以性能的略微降低為代價，卻使復雜度大幅下降，更利于硬件實現。

2) 由于新算法以不估計SNR的自適應譯碼算法為基本框架，而原算法是在子碼為擴展漢明碼的前提下提出的，這限制了新算法的適用范圍，針對BCH碼、RS碼等碼型的特點，將新算法擴展到更為一般的TPC碼將是下一步研究的方向。

[1] MUKHTAR H, AL-DWEIK A, AL-MUALLA M, et al. Adaptive hybrid ARQ system using Turbo product codes with hard/soft decoding[J]. IEEE Communications Letters, 2013, 17(11): 2132?2135.

[2] CAO Jin, MA Maode, LI Hui, et al. A survey on security aspects for LTE and LTE-A networks[J]. IEEE Communications Surveys & Tutorials, 2014, 16(1): 283?302.

[3] ZHANG Xia, ZHANG Peijian, JIANG Wei, et al. The analysis of coded overlapped time division multiplexing system[C]// IEEE 3rd International Conference on Broadband Network and Multimedia Technology (IC-BNMT). Beijing, China, 2010: 488?494.

[4] PYNDIAH R, COMBELLES P, ADDE P. A very low complexity block Turbo decoder for product codes[C]// IEEE Global Telecommunications Conference, Communications: The Key to Global Prosperity. London, UK, 1996: 101?105.

[5] ARGON C, MCLAUGHLIN S W. A parallel decoder for low latency decoding of Turbo product codes[J]. IEEE Communications Letters, 2002, 6(2): 70?72.

[6] 董政, 鞏克現, 葛臨東. 低復雜度和低譯碼時延 TPC 迭代譯碼算法[J]. 四川大學學報(工程科學版), 2012, 44(2): 122?129. DONG Zheng, GONG Kexian, GE Lindong. A low complexity and low latency TPC Iterative Decoding Algorithm[J]. Journal of Sichuan University (Engineering Science Edition), 2012, 44(2): 122?129.

[7] PYNDIAH R, GLAVIEUX A, PICART A, et al. Near optimum decoding of product codes[C]// IEEE Global Telecommunications Conference. San Francisco, CA, 1994: 339?343.

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

[9] MAHRAN A, BENAISSA M. Adaptive Chase algorithm for block Turbo codes[J]. Electronics Letters, 2003, 39(7): 617?619.

[10] LIU Xingcheng, WANG Kang. Adaptive SNR estimation based decoding algorithm for block Turbo codes[C]// IEEE Fourth International Conference on Communications and Networking in China (CHINACOM). Xi’an, China, 2009: 1?6.

[11] 黨小宇, 陶靜, 虞湘賓, 等. 一種低復雜度 Turbo 乘積碼自適應Chase譯碼算法[J]. 電子與信息學報, 2014, 36(3): 739?743. DANG Xiaoyu, TAO Jing, YU Xiangbin, et al. A low- complexity adaptive Chase decoding algorithm for Turbo product code[J]. Journal of Electronics & Information Technology, 2014, 36(3): 739?743.

[12] AL-DWEIK A, GOFF S L, SHARIF B. A hybrid decoder for block Turbo codes[J]. IEEE Transactions on Communications, 2009, 57(5): 1229?1232.

[13] SUN W C, CHEN Y M, WENG C Y, et al. An efficient implementation of the distance-based decoding for block Turbo codes[C]// IEEE 8th International ICST Conference on Communications and Networking in China (CHINACOM). Guilin, China, 2013: 675?679.

[14] AL-DWEIK A J, SHARIF B S. Non-sequential decoding algorithm for hard iterative Turbo product codes[J]. IEEE Transactions on Communications, 2009, 57(6): 1545?1549.

[15] CHO J, SUNG W. Reduced complexity Chase?Pyndiah decoding algorithm for Turbo product codes[C]// IEEE Workshop on Signal Processing Systems (SiPS). Beirut, Lebanon, 2011: 210?215.

[16] LU P Y, LU E H, CHEN T C. An efficient hybrid decoder for block turbo codes[J]. IEEE Communications Letters, 2014, 18(12): 2077?2080.

[17] LIN S, COSTELLO D J. 差錯控制編碼[M]. 2版. 晏堅, 何元智, 潘亞漢, 等譯. 北京: 機械工業出版社, 2007: 4?6. LIN S, COSTELLO D J. Error control coding[M]. 2nd ed. YAN Jian, HE Yuanzhi, PAN Yahan, et al, trans. Beijing: China Machine Press, 2007: 4?6.

[18] AL-DWEIK A J, SHARIF B S. Closed-chains error correction technique for Turbo product codes[J]. IEEE Transactions on Communications, 2011, 59(3): 632?638.

(編輯 楊幼平)

A low-complexity adaptive decoding algorithm for Turbo product code

HAN Ming, ZHANG Jiayan, ZHAO Honglin

(Communication Research Center, Harbin Institute of Technology, Harbin 150001, China)

A new efficient adaptive decoding algorithm was proposed to reduce the complexity of Turbo product code (TPC) decoding algorithm. The new algorithm was suitable for the TPCs formed by extended Hamming codes. The adaptive decoding algorithm without estimating SNR was the basic framework of the proposed algorithm and a simple formula for calculating the extrinsic information was introduced after analyzing codeword reliability. In the proposed algorithm, the least reliable bits could be reduced adaptively; meanwhile, computation of the extrinsic information should be simplified. The results show that when the extended Hamming code (64,57,4) is the subcode of TPC and the bit error rate is 10?5, the performance loss of the proposed algorithm is only 0.05 dB compared with the adaptive decoding algorithm without estimating SNR. But the complexity is decreased by about 1/3. So the proposed algorithm is an excellent balance and compromise between complexity and performance.

Turbo product code; Chase?Pyndiah decoding; adaptive decoding; low complexity

10.11817/j.issn.1672-7207.2017.01.020

TN911.22

A

1672?7207(2017)01?0141?07

2016?01?25；

2016?03?20

國家科技重大專項(2012ZX03003011-004) (Project(2012ZX03003011-044) supported by the Major Program of the National Science and Technology)

趙洪林，教授，博士生導師，從事寬帶抗干擾通信技術研究；E-mail: hlzhao@hit.edu.cn