極化碼BP解碼演算法中量化問題的研究

最新 03-13

摘要：第五代移動通信（5G）面向高可靠和低時延的海量數據交互場景，如何實現其高效編解碼方案是一個亟需解決的問題。現有編解碼方案難以有效平衡解碼過程中的計算複雜度和硬體實現難度，故無法應用於5G網路架構。針對該問題，提出了一種基於極化碼的置信度傳播（BP）解碼量化方案。該方案結合最小和解碼的近似演算法和量化思想，顯著降低了BP解碼演算法的計算複雜度和硬體實現難度。模擬成果表明，與最小和解碼演算法相比，量化後的BP解碼演算法極大地提高了解碼性能。相比於BP解碼演算法，在幾乎不降低解碼性能的基礎上，量化後的BP解碼演算法明顯降低了計算複雜度，更便於硬體實現。

正文內容：

0 引言

移動通信業務的變革使得數據通信流量呈指數增長，迫切需要新的移動通信技術滿足用戶的需求[1]。第五代移動通信（5G）作為下一代移動通信技術的重要發展方向[2][3]，面向mMTC（海量機器類通信）、eMBB（增強移動寬頻）、uRLLC（超可靠低時延通信）三種業務場景，不僅用於人與人通信，還實現人與物和物與物之間的互聯互通。與4G移動通信相比，5G為實現系統的低時延、高容量，對信道編碼方案提出了更高要求[4]。4G採用Turbo碼編碼方案，但其存在較高的編碼時延且演算法複雜度高。為此，E.Arikan提出了極化碼（Polar Codes）。這是唯一理論上證明可達到香農極限且編解碼過程簡單的高性能信道編碼方案[5]。在碼長無限長時，Polar碼可以達到二元對稱信道容量限，性能良好，但在碼長有限長時，與RS碼、LDPC碼等相比，性能相對較差。

目前，改善極化碼在有限長時性能的解碼方案主要是置信度傳播（Belief Propagation，BP）解碼演算法[6]。BP解碼演算法的核心思想是利用極化碼的構造因子圖，實現並行解碼的迭代演算法，具有良好的性能。它的主要缺點是演算法複雜度較高，且硬體實現比較複雜。為了降低解碼演算法的複雜度及利於硬體實現，Leroux等提出了最小和近似方法[7]，核心思想是通過來簡化BP解碼演算法中的迭代更新公式。然而，對比BP解碼演算法，最小和解碼演算法在性能方面有較大退化，難以滿足高速數據傳輸編碼性能要求。

在上述研究基礎上，結合5G對信道編碼的要求，提出了極化碼BP解碼的量化問題。該演算法簡化最小和解碼演算法中的迭代更新公式，選擇和誤差較大的的區間進行量化，從而便於提高解碼演算法的性能。同時，考慮查表法可以大大降低計算複雜度、硬體的實現難度以及提升演算法的解碼速率，通過引入大小為8比特的量化表來實現解碼過程。模擬結果表明，在8比特均勻量化時，其解碼性能幾乎與置信度傳播解碼演算法相同。

1　Polar碼及其解碼演算法

1.1　極化碼的BP解碼演算法

BP解碼演算法自身的並行性使得其更加易於硬體實現[8]。BP解碼演算法按照極化碼構造因子圖表示[9]。一個（N,K）極化碼通過一個n （其中n=log2N ）階段的因子圖進行迭代解碼，因子圖包含N(n+1) 個節點，用整數對(i,j) 表示每個節點，其中i 代表階層，j 表示行。第一階層的節點(1,j) 與信源矢量u 相關，n+1 階層的節點（n+1，j）與接收到的信息相關。每個階段有N/2 個處理單元。解碼器中，

,在每個處理單元中，i 和j 的取值是。圖1表示=3 時極化碼的因子圖，分為3個階段，每個階段有4個處理單元，圖2表示了每個處理單元的信息傳遞過程[10]。

1.2　極化碼的最小和解碼演算法

在BP解碼演算法的基礎上，最小和解碼演算法利用，如圖3所示，故有

，如圖4所示。

2　BP解碼演算法的量化方案

通過對BP解碼演算法進行量化，可以提高BP解碼演算法的解碼性能，降低解碼演算法的計算複雜度。文獻[12-13]提出的量化方案，其演算法由於涉及到加減法、比較、查表運算，從而在一定程度上降低了演算法的計算複雜度，提高了演算法性能。筆者主要基於這種思想對最小和解碼演算法中誤差較大的區間範圍進行合理量化，從而減少誤差，提高解碼性能。下面將詳細介紹BP解碼演算法的量化方案。

3　演算法性能分析

3.1　演算法的計算複雜度分析

筆者提出的解碼演算法對ln cosh(x) 進行量化，進而改變更新函數定義的演算法公式。量化後的BP解碼演算法相比於BP解碼演算法，極大降低了更新公式的複雜度。而相比於最小和解碼演算法，它的演算法複雜度有微弱增加，但性能有較大提升。從三種演算法的更新式式（10）、式（11）、式（13）的定義中可以看出，在BP解碼演算法中，g(x1,x2) 的計算需要2次對數運算、2次雙餘弦函數的計演算法、2次乘法運算和3次加法運算。由於運算公式是指數形式，造成運算時延較大，硬體實現相對艱難。最小和解碼演算法由於g(x1,x2) 的計算公式較為簡單，僅需要2次符號運算、2次取絕對值和1次比較得出最小值。而量化後的BP解碼演算法最多需要2次比較運算、2次加法運算、2次絕對值運算、2次符號運算和2次查表運算，雖然相比於最小和解碼演算法多了查表運算，但整體的計算複雜度較低，運算時延較小，硬體實現上更加簡單。

3.2　演算法的模擬分析

為了驗證演算法的解碼性能，分別對量化後的BP解碼演算法、最小和解碼演算法和BP解碼演算法進行模擬實驗。實驗中均採取二進位輸入的高斯白雜訊信道，採取BPSK調製方式，碼長N 分別設為256和512，碼率為0.5，總迭代次數設為60次，幀數為50 000幀。

在不同信噪比（Eb/N0 ）下，量化後的BP解碼演算法、最小和解碼演算法及BP解碼演算法在節點更新函數中（如式（13）所示），調用分段函數g(x1,x2) 在各段所佔的比例，結果如表2所示，不同情景如式（14）所示。

4　結　語

提出了一種量化後的BP解碼演算法，在最小和解碼演算法的基礎上，在[-2.5,2.5]區間內，利用8比特的區間量化代替迭代更新公式中的，以均衡最小和解碼演算法的性能損失。模擬結果表明，量化後的BP解碼演算法相比於最小和解碼演算法略增加了計算複雜度，但演算法性能提高顯著，同BP解碼演算法的性能幾乎相同，同時演算法的計算複雜度又明顯低於BP解碼演算法，更利於硬體實現。

參考文獻：

[1] Y. Zhou, H. Liu, Z. Pan, L. Tian and J.L. Shi, 「Spectral and Energy Efficient Two-Stage Cooperative Multicast for LTE-A and Beyond」, IEEE Wireless Magazine, pp. 34-41, Apr. 2014.

[2] L. Liu, Y. Zhou, L. Tian and J.L. Shi, 「Load Aware Joint CoMP Clustering and Inter-cell Resource Scheduling in Heterogeneous Ultra Dense Cellular Networks」, IEEE Trans. Vehicular Technology, Early Access, vol. 99, pp. 1-14, Nov. 2017.

[3] V. Garcia, Y. Zhou and J.L. Shi, 「Coordinated Multipoint Transmission in Dense Cellular Networks with User-Centric Adaptive Clustering」, IEEE Trans. Wireless Comm., Vol. 13, No. 8, pp. 4297-4308, Aug. 2014.

[4]杜昊陽,王呈貴,欒亞婷.基於LDPC碼的多信道停等HARQ系統設計與分析[J].通信技術,2015,48(08):886-892.

[5] Arikan E.Channel Polarization:A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memory less Channels[J].IEEE Transactions on Information Theory,2009,55(07):3051-3073.

[6] Zhang Y,Liu A,Pan X,et al.A Modified Belief Propagation Polar Decoder[J].IEEE Communications Letters,2014,18(07):1091-1094.

[7] Leroux C,Raymond A J,Sarkis G,et al.Hardware Implementation of Successive-Cancellation Decoders for Polar Codes[J].Journal of Signal Processing Systems,2012,69(03):305-315.

[8] Niu K,Chen K.Stack Decoding of Polar Codes[J].Electronics Letters,2012,48(12):695-697.

[9] Hussami N,Korada S B,Urbanke R.Performance of Polar Codes for Channel and Source Coding[C].IEEE International Symposium on Information Theory,2009:1488-1492.

[10] 吳道龍.極化碼構造與解碼演算法研究[D].西安:西安電子科技大學,2016.

[11] 洪銀芳,李暉,王新梅.改進的Polar碼的最小和解碼演算法[J].北京郵電大學學報,2016,39(06):22-26.

[12] 樊婷婷,楊維,許昌龍.Polar碼SC解碼演算法的量化問題[J].北京郵電大學學報,2015(04):95-100.

[13] 童勝,王鵬,王單等.LDPC碼量化和積解碼的高效實現[J].西安電子科技大學學報:自然科學版,2004,31(05):709-713.

[14] Fayyaz U U,Barry J R.A Low-complexity Soft-output Decoder for Polar Codes[C].Global Communications Conference IEEE,2014:2692-2697.

作者：任　潔1,2，韓　娟2，3，4，馮雪林2，劉　林2

單位：1.重慶郵電大學，重慶 400065；

2.中國科學院計算技術研究所無線通信技術研究中心，北京 100190；

3.移動計算與新型終端北京市重點實驗室，北京 100190；4.中國科學院大學，北京 100190

作者簡介：任　潔，女，碩士，主要研究方向為物理層基帶演算法；

韓　娟，女，博士，副研究員，主要研究方向為寬頻移動通信信號處理、移動通信測試測量技術等；

馮雪林，女，碩士，高級工程師，主要研究方向為無線通信；