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

鄭昊

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

關鍵詞：極化碼;置信度傳播譯碼;計算復雜度;時間復雜度;香農極限;無線通信

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

0 引 言

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

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

1 BP譯碼算法

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

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

2 改進的BP譯碼算法

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

3 譯碼算法仿真

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

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

4 結 語

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

參 考 文 獻

[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譯碼算法的研究與實現[D].成都：電子科技大學，2017.

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

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

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

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

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