極化碼BP譯碼算法中量化問題的研究*

任 潔，韓 娟，馮雪林，劉 林

0 引 言

移動(dòng)通信業(yè)務(wù)的變革使得數(shù)據(jù)通信流量呈指數(shù)增長，迫切需要新的移動(dòng)通信技術(shù)滿足用戶的需求[1]。第五代移動(dòng)通信（5G）作為下一代移動(dòng)通信技術(shù)的重要發(fā)展方向[2-3]，面向mMTC（海量機(jī)器類通信）、eMBB（增強(qiáng)移動(dòng)寬帶）、uRLLC（超可靠低時(shí)延通信）三種業(yè)務(wù)場(chǎng)景，不僅用于人與人通信，還實(shí)現(xiàn)人與物和物與物之間的互聯(lián)互通。與4G移動(dòng)通信相比，5G為實(shí)現(xiàn)系統(tǒng)的低時(shí)延、高容量，對(duì)信道編碼方案提出了更高要求[4]。4G采用Turbo碼編碼方案，但其存在較高的編碼時(shí)延且算法復(fù)雜度高。為此，E.Arikan提出了極化碼（Polar Codes）。這是唯一理論上證明可達(dá)到香農(nóng)極限且編譯碼過程簡單的高性能信道編碼方案[5]。在碼長無限長時(shí)，Polar碼可以達(dá)到二元對(duì)稱信道容量限，性能良好，但在碼長有限長時(shí)，與RS碼、LDPC碼等相比，性能相對(duì)較差。

目前，改善極化碼在有限長時(shí)性能的譯碼方案主要是置信度傳播（Belief Propagation，BP）譯碼算法[6]。BP譯碼算法的核心思想是利用極化碼的構(gòu)造因子圖，實(shí)現(xiàn)并行譯碼的迭代算法，具有良好的性能。它的主要缺點(diǎn)是算法復(fù)雜度較高，且硬件實(shí)現(xiàn)比較復(fù)雜。為了降低譯碼算法的復(fù)雜度及利于硬件實(shí)現(xiàn)，Leroux等提出了最小和近似方法[7]，核心思想是通過ln cosh x ≈|x|-ln2來簡化BP譯碼算法中的迭代更新公式。然而，對(duì)比BP譯碼算法，最小和譯碼算法在性能方面有較大退化，難以滿足高速數(shù)據(jù)傳輸編碼性能要求。

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

1 Polar碼及其譯碼算法

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

1.1 極化碼的BP譯碼算法

BP譯碼算法自身的并行性使得其更加易于硬件實(shí)現(xiàn)[8]。BP譯碼算法按照極化碼構(gòu)造因子圖表示[9]。一個(gè)(N,K )極化碼通過一個(gè)n（其中n=log2N）階段的因子圖進(jìn)行迭代譯碼，因子圖包含N(n+1)個(gè)節(jié)點(diǎn)，用整數(shù)對(duì)(i, j)表示每個(gè)節(jié)點(diǎn)，其中i代表階層，j表示行。第一階層的節(jié)點(diǎn)(1, j)與信源矢量u相關(guān)，n+1階層的節(jié)點(diǎn)(n+1, j)與接收到的信息相關(guān)。每個(gè)階段有N/2個(gè)處理單元。譯碼器中，1≤i≤n，1≤j≤N。在每個(gè)處理單元中，i和j的取值是1≤i≤n，1≤j≤N/2。圖1表示n=3時(shí)極化碼的因子圖，分為3個(gè)階段，每個(gè)階段有4個(gè)處理單元，圖2表示了每個(gè)處理單元的信息傳遞過程[10]。

圖1 n=3時(shí)極化碼的構(gòu)造因子圖

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

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

節(jié)點(diǎn)之間存在以下邏輯關(guān)系：

開始解碼時(shí)，根據(jù)第j位是否為信息比特，初始化因子圖最左邊一層節(jié)點(diǎn)上的消息R1,j：

根據(jù)信道輸出的每個(gè)節(jié)點(diǎn)的對(duì)數(shù)似然比（LLR），初始化因子圖最右邊一層節(jié)點(diǎn)上的消息Ln+1,j為：

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

或：

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

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

因此，組織必須根據(jù)自身管理特點(diǎn)和組織發(fā)展需要，對(duì)軟件供應(yīng)商進(jìn)行詳細(xì)的考察論證，選擇一套適合企業(yè)實(shí)際的軟件系統(tǒng)。

圖3 cosh x的近似函數(shù)

圖4 ln cosh x的近似函數(shù)

2 BP譯碼算法的量化方案

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

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

圖5 ln cosh x的分段近似

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

具體如圖6所示。

圖6 ln cosh x 比特量化后的對(duì)比結(jié)果

將式（10）中的雙曲函數(shù)ln cosh x用式（13）代替，則式（10）轉(zhuǎn)化為：

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

表1 y=ln cosh x在量化區(qū)間的量化表

在區(qū)間(-2.5,2.5)進(jìn)行量化后的函數(shù)曲線，如圖7所示。

圖7 量化后的函數(shù)曲線

硬件實(shí)現(xiàn)中，當(dāng)更新函數(shù)中變量落在(-2.5,2.5)區(qū)間時(shí)，可以通過查詢表1來實(shí)現(xiàn)。量化后的BP譯碼算法的迭代公式和節(jié)點(diǎn)之間的迭代更新信息規(guī)則均和BP譯碼算法相同，不同在于迭代更新公式的計(jì)算方法。具體得，更新公式由式（13）決定。

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

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

（2）當(dāng)?shù)麓螖?shù)小于T時(shí)，在每輪迭代中，首先從因子圖中的第1階段到第n階段的每個(gè)處理單元中根據(jù)式（7）、式（8）更新每個(gè)階段中各個(gè)處理單元的節(jié)點(diǎn)的右信息Ri,j；然后，從第n階段到第1階段，利用式（5）、式（6）更新每個(gè)階段中各個(gè)處理單元的節(jié)點(diǎn)的左信息L[14]。

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

①當(dāng)j∈Ac時(shí)，u^j=0；

② 當(dāng)j∈A時(shí)， 若L1,j＞0， 則u^j=0； 若L1,j≤ 0，u^j=1。

3 算法性能分析

3.1 算法的計(jì)算復(fù)雜度分析

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

3.2 算法的仿真分析

為了驗(yàn)證算法的譯碼性能，分別對(duì)量化后的BP譯碼算法、最小和譯碼算法和BP譯碼算法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中均采取二進(jìn)制輸入的高斯白噪聲信道，采取BPSK調(diào)制方式，碼長N分別設(shè)為256和512，碼率為0.5，總迭代次數(shù)設(shè)為60次，幀數(shù)為50 000幀。

在不同信噪比（Eb/N0）下，量化后的BP譯碼算法、最小和譯碼算法及BP譯碼算法在節(jié)點(diǎn)更新函數(shù)中（如式（13）所示），調(diào)用分段函數(shù)g(x1,x2)在各段所占的比例，結(jié)果如表2所示，不同情景如式（14）所示。

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

圖8比較了碼長為256時(shí)，量化后的BP譯碼算法、最小和譯碼算法和BP譯碼算法的誤碼率性能?？梢钥闯?，量化后的BP譯碼算法與BP譯碼算法的譯碼性能幾乎相同。與最小和譯碼算法對(duì)比，當(dāng)Eb/N0小于2.5 dB時(shí)，在相同的誤碼率情況下，量化后的BP譯碼算法性能比最小和譯碼算法的性能要好，在0.25 dB左右。當(dāng)信噪比大于2.5 dB時(shí)，二者性能差距逐漸減少，但量化后的BP譯碼算法性能仍優(yōu)越于最小和譯碼算法。

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

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

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

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

4 結(jié) 語

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

[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系統(tǒng)設(shè)計(jì)與分析[J].通信技術(shù),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] 吳道龍.極化碼構(gòu)造與譯碼算法研究[D].西安:西安電子科技大學(xué),2016.WU Dao-long.Polarization Code Construction and Decoding Algorithm[D].Xi’an:Xidian University,2016.

[11] 洪銀芳,李暉,王新梅.改進(jìn)的Polar碼的最小和譯碼算法[J].北京郵電大學(xué)學(xué)報(bào),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].北京郵電大學(xué)學(xué)報(bào),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碼量化和積譯碼的高效實(shí)現(xiàn)[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,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.