極化碼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]，核心思想是通過ln cosh x ≈|x|-ln2來簡化BP譯碼算法中的迭代更新公式。然而，對比BP譯碼算法，最小和譯碼算法在性能方面有較大退化，難以滿足高速數據傳輸編碼性能要求。

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

1 Polar碼及其譯碼算法

Polar碼可表示為(N,K,A,uAc)的GN陪集碼。其中N=2n（n是正整數）表示碼長；K代表維數，也是信息集合A（ A ? { 1 , 2,… ,N }）的大小，由信道極化選取信息集合A；uAc（uAc∈XN-K）代表固定比特。

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個處理單元。譯碼器中，1≤i≤n，1≤j≤N。在每個處理單元中，i和j的取值是1≤i≤n，1≤j≤N/2。圖1表示n=3時極化碼的因子圖，分為3個階段，每個階段有4個處理單元，圖2表示了每個處理單元的信息傳遞過程[10]。

圖1 n=3時極化碼的構造因子圖

圖2 BP算法中處理單元的信息傳遞

從圖2可以看出，每個處理單元共分為4個節點， 分 別 為 VN(i, j)、VN(i, j+N/2)、VN(i+1,2j-1)、VN(i+1,2j)。

節點之間存在以下邏輯關系：

開始解碼時，根據第j位是否為信息比特，初始化因子圖最左邊一層節點上的消息R1,j：

根據信道輸出的每個節點的對數似然比（LLR），初始化因子圖最右邊一層節點上的消息Ln+1,j為：

中間的其他節點初始化為0。迭代譯碼過程中，從左向右計算更新置信度消息Ri,j，并向右傳播至最右邊，再從右往左計算更新置信度消息Li,j，并向左傳播至最左邊，相鄰節點間的置信度傳播消息通過處理單元運算模塊計算。傳播一個往返為一次迭代過程。每一個處理單元運算模塊按照式（5）～式（8）計算L和R消息[11]：

或：

1.2 極化碼的最小和譯碼算法

其中，x1、x2表示信道的對數似然比信息。從式（10）、式（11）可知，最小和譯碼算法和BP譯碼算法的不同在于g(x1,x2)的定義有差別。

因此，組織必須根據自身管理特點和組織發展需要，對軟件供應商進行詳細的考察論證，選擇一套適合企業實際的軟件系統。

圖3 cosh x的近似函數

圖4 ln cosh x的近似函數

2 BP譯碼算法的量化方案

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

BP譯碼算法中，令ln cosh x≈|x|-ln 2得出了最小和譯碼算法，但在區間|x|≤2.5時，ln cosh x與|x|-ln 2的誤差較大。尤其當|x|=0時，ln cosh x與|x|-ln 2的差值達到了ln 2，具體如圖5所示。

圖5 ln cosh x的分段近似

由圖5可以看出，在|x|＞2.5時，ln cosh x與|x|≤2.5幾乎相同，誤差極小；而在|x|≤2.5時，ln cosh x與|x|-ln 2的誤差越來越大，進而極大地降低了譯碼算法的性能。為此，筆者提出在(-2.5,2.5)區間內按照8比特量化，即整體分為兩段：

具體如圖6所示。

圖6 ln cosh x 比特量化后的對比結果

將式（10）中的雙曲函數ln cosh x用式（13）代替，則式（10）轉化為：

通過分析，如果僅對函數ln cosh x進行量化，采用不同的量化方法對譯碼性能影響不大。相比于非均勻量化，采用均勻量化更利于硬件實現，所以文中對函數ln cosh x使用8比特量化，其中量化表如表1所示。

表1 y=ln cosh x在量化區間的量化表

在區間(-2.5,2.5)進行量化后的函數曲線，如圖7所示。

圖7 量化后的函數曲線

硬件實現中，當更新函數中變量落在(-2.5,2.5)區間時，可以通過查詢表1來實現。量化后的BP譯碼算法的迭代公式和節點之間的迭代更新信息規則均和BP譯碼算法相同，不同在于迭代更新公式的計算方法。具體得，更新公式由式（13）決定。

量化后的BP譯碼算法的詳細步驟如下。

（1）初始化：根據式（3）和式（4）計算左信息R1,j和右信息Ln+1,j，并設定迭代次數T；

（2）當迭代更新次數小于T時，在每輪迭代中，首先從因子圖中的第1階段到第n階段的每個處理單元中根據式（7）、式（8）更新每個階段中各個處理單元的節點的右信息Ri,j；然后，從第n階段到第1階段，利用式（5）、式（6）更新每個階段中各個處理單元的節點的左信息L[14]。

（3）當達到迭代次數T時進行比特判決，判決的依據是最后一次迭代更新的左信息Li,j值的大小。對于譯碼碼字u^j(1≤j≤N)的判定規則如下：

①當j∈Ac時，u^j=0；

② 當j∈A時， 若L1,j＞0， 則u^j=0； 若L1,j≤ 0，u^j=1。

3 算法性能分析

3.1 算法的計算復雜度分析

筆者提出的譯碼算法對ln cosh x進行量化，進而改變更新函數定義的算法公式。量化后的BP譯碼算法相比于BP譯碼算法，極大降低了更新公式的復雜度。而相比于最小和譯碼算法，它的算法復雜度有微弱增加，但性能有較大提升。從3種算法的更新式式（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）所示。

表2 三種譯碼算法調用g(x1,x2)各段占比

圖8比較了碼長為256時，量化后的BP譯碼算法、最小和譯碼算法和BP譯碼算法的誤碼率性能。可以看出，量化后的BP譯碼算法與BP譯碼算法的譯碼性能幾乎相同。與最小和譯碼算法對比，當Eb/N0小于2.5 dB時，在相同的誤碼率情況下，量化后的BP譯碼算法性能比最小和譯碼算法的性能要好，在0.25 dB左右。當信噪比大于2.5 dB時，二者性能差距逐漸減少，但量化后的BP譯碼算法性能仍優越于最小和譯碼算法。

圖8 N=256極化碼3種譯碼算法的性能

圖9 比較了碼長為512時，量化后的BP譯碼算法、最小和譯碼算法和BP譯碼算法的誤碼率性能。如圖9所示，量化后的BP譯碼算法與BP譯碼算法的譯碼性能幾乎相同。與最小和譯碼算法相較，當Eb/N0小于3 dB時，在相同誤碼率下，量化后的BP譯碼算法性能比最小和譯碼算法要好，在0.4 dB左右。而當信噪比大于3.5 dB時，二者的性能差距逐漸減少，但量化后的BP譯碼算法性能仍優越于最小和譯碼算法。

圖9 N=512極化碼的3種譯碼算法的性能

如表2所示，低信噪比下，量化后的BP譯碼算法調用情景1、情景2、情景3這3種情況所占的比例較高。而從圖8可知，低信噪比時量化后的BP譯碼算法的性能明顯優于最小和譯碼算法。隨著信噪比的提高，量化后的BP譯碼算法調用情景4的比例增加。從圖8可以看出，筆者提出的量化后的BP譯碼算法與最小和譯碼算法相比性能趨于變小，但仍具有顯著優勢。結合表2和圖8、圖9可以看出，量化后的BP譯碼算法相較于最小和譯碼算法，其性能提升明顯，幾乎達到與BP譯碼算法相同的性能。

4 結 語

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

[1] Zhou Y,Liu H,Pan Z,et al.Spectral and Energy Efficient Two-Stage Cooperative Multicast for LTE-A and Beyond[J].IEEE Wireless Magazine,2014(04):34-41.

[2] Liu L,Zhou Y, Tian L,et al.Load Aware Joint CoMP Clustering and Inter-cell Resource Scheduling in Heterogeneous Ultra Dense Cellular Networks[J].IEEE Trans. Vehicular Technology,Early Access,2017,99(11):1-14.

[3] Garcia V,Zhou Y,Shi J L.Coordinated Multipoint Transmission in Dense Cellular Networks with User-Centric Adaptive Clustering[J].IEEE Trans. Wireless Comm.,2014,13(08):4297-4308.

[4] 杜昊陽,王呈貴,欒亞婷.基于LDPC碼的多信道停等HARQ系統設計與分析[J].通信技術,2015,48(08):886-892.DU Hao-yang,WANG Chen-gui,LUAN Ya-ting.Design and Analysis of Multi-Channel Stop-And-Wait HARQ based on LDPC Codes[J].Communi-cations Technology,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.WU Dao-long.Polarization Code Construction and Decoding Algorithm[D].Xi’an:Xidian University,2016.

[11] 洪銀芳,李暉,王新梅.改進的Polar碼的最小和譯碼算法[J].北京郵電大學學報,2016,39(06):22-26.HONG Yin-fang,LI Hui,WANG Xin-mei.Min-sum Decoding Algorithm of Improved Polar Codes[J].Journal of Beijing University of Posts and Telecommunicatio ns,2016,39(06):22-26.

[12] 樊婷婷,楊維,許昌龍.Polar碼SC譯碼算法的量化問題[J].北京郵電大學學報,2015(04):95-100.FAN Ting-ting,YANG Wei,XU Chang-long.Quantization Problems of Polar Code SC Decoding Algorithm[J].Journal of Beijing University of Posts and Telecommunicatio ns,2015(04):95-100.

[13] 童勝,王鵬,王單等.LDPC碼量化和積譯碼的高效實現[J].西安電子科技大學學報:自然科學版,2004,31(05):709-713.TONG Sheng,WANG Peng,WANG Dan,et al.Efficient Implementation of Quantization and Product Decoding of LDPC Codes[J].Journal of Xidian University(Natural Science Edition),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.