一種極化碼的譯碼算法研究

鄭昊

摘 要：極化碼是近年來提出的一種新型編譯碼技術(shù)，是目前唯一能被證明達到香農(nóng)極限的糾錯編碼，是無線通信領(lǐng)域的重大突破，因此受到了國內(nèi)外學(xué)者的廣泛關(guān)注和研究。各國學(xué)者相繼提出了一些譯碼算法，但這些算法在譯碼性能、延時、吞吐率、計算復(fù)雜度等方面表現(xiàn)的并不理想。通過對標準BP譯碼算法迭代過程方程式的改進，文章提出了一種改進的BP譯碼算法，經(jīng)仿真分析，對比標準的BP譯碼算法，改進算法在保持譯碼性能不降低的前提下，有效降低了計算復(fù)雜度和時間復(fù)雜度。

關(guān)鍵詞：極化碼;置信度傳播譯碼;計算復(fù)雜度;時間復(fù)雜度;香農(nóng)極限;無線通信

中圖分類號：TP39 文獻標識碼：A 文章編號：2095-1302（2019）05-00-03

0 引 言

極化碼[1]由土耳其學(xué)者Arikan于2008年提出，在碼長趨于無窮大時，極化碼可達到信道容量。極化碼具有結(jié)構(gòu)化、編譯碼復(fù)雜度低等特點，引起了各國學(xué)者的廣泛關(guān)注和研究。極化碼的核心在于信道極化現(xiàn)象，包括信道組合、信道分裂。通過對已知信道的極化處理，部分子信道容量趨近于1，部分子信道容量趨近于0，我們選擇在趨近于1的信道上傳輸有用的信息，在趨近于0的信道上傳輸冗余信息?；诖颂匦?，文獻[2]提出了串行抵消譯碼算法（Successive Cancellation，SC），文獻[3]提出了列表串行抵消譯碼算法（Successive Cancellation List，SCL），文獻[4]提出了置信度傳播譯碼算法（Belief Propagation，BP），但SC，SCL都是串行譯碼算法，存在延時較高、吞吐率較低的缺陷，而BP譯碼算法又涉及大量乘除運算，計算復(fù)雜度較高。

針對上述譯碼算法的不足，文章提出了一種改進的BP譯碼算法，對標準BP算法的迭代公式進行改進，并對數(shù)域簡化。經(jīng)仿真分析，在保持譯碼性能不降低的前提下，可有效降低譯碼計算復(fù)雜度和時間復(fù)雜度。

1 BP譯碼算法

（N，K）的極化碼迭代譯碼因子圖網(wǎng)絡(luò)由（M+1）N個節(jié)點組成，其中N=2M，每一個節(jié)點（i，j）與相鄰節(jié)點進行信息傳遞更新，當(dāng)達到預(yù)置的最大迭代次數(shù)之后，將迭代后的信息輸出再進行硬判決譯碼。圖1所示為N=8的極化碼因子圖。

因子圖包括3層，每層包含4個基本運算單元，用來更新和迭代計算譯碼信息，通過相鄰層之間的信息迭代更新，達到最佳譯碼性能。在相鄰層之間節(jié)點進行迭代信息交換的過程中，包含左向迭代信息和右向迭代信息。在一次迭代過程中先計算從右至左的傳播信息，直至最左邊一層，再計算從左至右的傳播信息，直至最右邊一層，此時完成一次迭代運算。圖2所示為BP譯碼算法的基本計算單元。

2 改進的BP譯碼算法

上節(jié)詳細描述了標準BP譯碼算法，可以看出，標準算法在迭代計算的過程中，第i次迭代計算需要第i-1次迭代計算的數(shù)據(jù)作為輸入，增加了運算成本。同時，標準算法是基于概率域的運算，涉及大量乘除運算，計算復(fù)雜度高且可能造成數(shù)據(jù)溢出。為了改善以上問題，本文提出了一種改進的BP譯碼算法，所有信息傳遞過程都在本次迭代內(nèi)完成，不涉及之前的迭代輪次，迭代過程如圖4、圖5所示，同時將概率域內(nèi)的運算變換至對數(shù)域，以有效降低計算復(fù)雜度，并防止數(shù)據(jù)溢出。改進的BP譯碼算法在對數(shù)域內(nèi)經(jīng)過min-sum[5]簡化后，得到迭代過程方程式，見式（7）～式（10）。譯碼流程與標準BP譯碼算法相同。

3 譯碼算法仿真

對碼長N=1 024，碼率R=0.5的極化碼，在BPSK（二進制相移鍵控）和AWGN（加性高斯白噪聲）信道下對標準BP譯碼算法和改進的BP譯碼算法進行譯碼性能仿真，如圖6所示。從圖中可以看出，在迭代次數(shù)為40次，信噪比較小時兩種算法性能幾乎一致，隨著信噪比增大，改進算法性能略優(yōu)于標準算法。

迭代譯碼算法通常根據(jù)最差噪聲情況來設(shè)置固定的迭代次數(shù)，但是在實際信噪比情況下，較少的迭代次數(shù)就可以達到收斂條件。我們使用基于CRC的迭代終止準則[6]對兩種譯碼算法進行對比，如圖7所示。從圖中可以看出，相同條件下，改進的BP譯碼算法所需要的迭代次數(shù)隨著信噪比的增加遠小于標準BP譯碼算法，因此在時間復(fù)雜度上優(yōu)于標準BP譯碼算法。

4 結(jié) 語

本文對極化碼標準BP譯碼算法進行了簡要概述，通過分析不足對其進行了改進，提出一種改進的BP譯碼算法，并對兩種算法進行仿真比較。仿真結(jié)果表明，在譯碼性能略優(yōu)于原算法的情況下，改進的BP譯碼算法可以有效降低計算復(fù)雜度和時間復(fù)雜度。

參 考 文 獻

[1] ARIKAN E. Channel polarization：a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE trans. Inf. theory，2009，55（7）：：3051-3073.

[2] ARIKAN E. Channel polarization：a method for constructing capacity-achieving codes[C]// IEEE International Symposium on Information Theory（ISIT）， 2008：1173-1177.

[3] TAL I，VARDY A. List decoding of polar codes[C]// in Proceedings of the IEEE International Symposium on Information Theory Proceedings （ISIT11），2011：1-5.

[4] ARIKAN E. A performance comparison of polar codes and Reed-Muller codes[J]. IEEE communications letters，2008，12（6）：447-449.

[5]黃勝武.Polar Code譯碼算法的研究與實現(xiàn)[D].成都：電子科技大學(xué)，2017.

[6]刑超，趙生妹，鄭寶玉.極化碼置信傳播算法早期終止準則的研究[J].信號處理，2016，32（3）：253-259.

[7]田佳佳.極化碼的譯碼算法研究[D].成都：電子科技大學(xué)，2016.

[8]吳道龍.極化碼構(gòu)造與譯碼算法研究[D].西安：西安電子科技大學(xué)，2016.

[9]刑超，徐順頻，趙生妹.一種基于整數(shù)操作的極化碼最小和譯碼算法[J].南京郵電大學(xué)學(xué)報（自然科學(xué)版），2015，35（1）：52-55.

[10]王繼偉.極化碼編碼與譯碼算法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013.