一種改進的基于深度前饋神經網絡的極化碼BP譯碼算法

劉斌 李立欣 李靜

【摘? 要】近年來高性能和低復雜度的信道譯碼算法一直是5G移動通信的核心技術之一，深度學習方法因在譯碼性能方面表現突出已成為研究熱點。基于深度神經網絡的極化碼譯碼器使用多尺度置信傳播算法可以得到較低復雜度和延遲性能，但其譯碼性能依舊有待提高。在多尺度置信傳播譯碼算法的基礎上提出了一種具有多偏移因子的最小和極化碼譯碼算法，通過使用交叉熵損失函數與提出的交叉熵多損失函數對深度神經網絡譯碼器進行訓練，生成的深度神經網絡譯碼器可以降低復雜度和時延，顯著提高譯碼性能。

【關鍵詞】深度學習;極化碼;置信傳播;深度神經網絡譯碼器

中圖分類號：TN929.5

文獻標志碼：A? ? ? 文章編號：1006-1010（2019）04-0008-07

[Abstract]?In recent years， channel decoding algorithm with high performance and low complexity has been one of the core technologies of 5G mobile communications. Deep learning methods have become a research hotspot because of the outstanding performance in decoding performance. The polar code decoder based on deep neural network can obtain better decoding performance by using multi-scale Belief Propagation （BP） algorithm， and have lower complexity and delay， but the decoding performance still needs to be improved. Based on the multi-scale BP decoding algorithm， a minimum sum decoding algorithm with multiple offset factors is proposed in this paper. The deep neural network decoder is trained by cross-entropy loss function and the proposed cross-entropy multi-loss function， respectively. The generated deep neural network decoder can not only reduce the complexity and delay， but also significantly improve the decoding performance.

[Key words]?deep learning; polar code; belief propagation; deep neural network decoder

1? ?引言

根據工信部最新統計數據，截至2018年10月末，中國移動、中國聯通以及中國電信三家運營商的移動電話用戶總數已經高達15.5億戶，和2017年同時段相比，數據增長了10.7%。這些統計數據清晰地表明：未來移動通信系統將面臨巨大的流量需求方面的挑戰。移動數據需求的激增給現有的蜂窩網絡帶來了巨大的負擔，這已經引發了對第五代移動通信系統的深入研究。高數據速率需要低譯碼延遲，然而傳統的譯碼算法由于迭代計算導致其具有很高的復雜度。因此，迫切需要設計一種全新的高速低延遲譯碼器。最近，深度學習方面的研究[1]因為能夠解決此類問題而受到了學者的廣泛關注。

極化碼作為第一種經過嚴格證明可以達到香農容量的信道編碼方法是信道編碼領域的新突破。極化碼已經被選為5G控制信道的編碼方案[2]。其譯碼算法主要包括連續消除（Successive Cancelation， SC）算法和置信傳播（Belief Propagation， BP）算法。SC算法一直是極化碼譯碼中的研究熱點，雖然復雜度低，但長碼字下存在吞吐量有限和高延遲的問題。與SC譯碼算法相比，BP譯碼算法由于并行處理的特性能實現更高的數據吞吐量和更低的延遲，但也引入了更高的計算復雜度，所以最近提出了最小和近似譯碼算法和早期終止方案[3]以降低復雜度，然而在有限迭代次數下仍不能實現最大似然譯碼性能。

學者們開始采用深度學習方法來解決低復雜度和低延遲的信道譯碼問題。在文獻[4]中，通過在Tanner圖的邊上分配適當的權重來改善譯碼性能，并使用深度學習技術來獲得權重，但是該方法需要大量的乘法運算。文獻[5]中作者提出了一種神經偏移最小和算法，其中沒有乘法運算、參數數量少且硬件實現也比較容易。文獻[6]提出了一種深度神經網絡譯碼器，通過學習大量碼字可以實現最大后驗譯碼性能，但是長碼字增加了訓練的復雜度，所以該方法只局限于短碼字的使用。文獻[7]中將極性碼的編碼圖分成較小的子塊并分別進行訓練來獲得更好的譯碼性能，但是這種方法復雜度很高，高吞吐量的硬件實現也很困難。文獻[8]中提出了一種多尺度BP譯碼算法以及適用于任意碼長的基于深度學習的極化碼譯碼器。

針對多尺度BP譯碼算法譯碼性能有待提高的問題，本文首先提出了具有多偏移因子的最小和譯碼算法，并將該算法用于深度前饋神經網絡架構中。其次，通過對比具有多偏移因子的最小和譯碼算法和多尺度BP譯碼算法來證明所提出的算法在性能方面的優勢。最后，在提出的神經網絡譯碼結構中，將每次譯碼迭代得到的輸出疊加形成的多損失函數用于訓練深度神經網絡譯碼器。

2? ?研究背景

2.1? 深度神經網絡

深度神經網絡也稱作深度前饋神經網絡，這種網絡模型在各層之間具有全連接的神經元結構，其中信息沒有反饋的從左向右傳輸，圖1所示的是深度神經網絡的模型。連接輸入和輸出的每層神經元結構具有以下映射關系：

神經網絡中輸入和輸出映射中的參數通常指的是權重和偏差。前饋神經網絡通過多個權重系數矩陣和輸入數據在隱藏層中進行一系列線性運算。從輸入層開始層層向后傳播，最后通過非線性激活函數得到輸出結果。為了獲得神經網絡的最優參數解，輸入輸出映射的訓練集和特定的損失函數必須是已知的。交叉熵損失函數是衡量實際輸出值和期望輸出值間誤差的常用方法之一，通常通過使用隨機梯度優化和反向傳播算法優化參數以最小化損失函數的值。

2.2? 極化碼

極化碼是Arikan在信道極化研究的基礎上提出的一種新的編碼思想，當碼長趨于無窮時，極化碼能夠逼近香農極限且具有很低的編碼復雜度。極化碼的結構基于核矩陣，使用Kronecker乘法線性轉換N比特數據，然后通過二進制對稱離散無記憶信道傳輸。極化碼生成矩陣的構造方式為：

2.3? BP譯碼算法

BP譯碼算法是廣泛使用的一種消息傳遞算法，而極化碼BP譯碼算法是基于Forney提出的碼字因子圖表示并在因子圖上進行的譯碼。（N， K）極化碼的因子圖由N（n+1）個節點和n=log2N個階段組成，每個節點由整數對（i， j）表示，其中i表示階段，j表示輸入比特，并且有1≤i≤n+1，1≤j≤N。圖2給出了碼長為8的極化碼的因子圖：

最小和近似譯碼算法是一種可以降低BP譯碼算法復雜度的改進算法，硬件上易于實現。其基本思想是將BP譯碼算法信息更新公式（3）中的g（x， y）簡化為g（x，y）=sign（x）sign（y）min（|x|，|y|）。由于使用近似，與原始BP譯碼算法相比，誤比特率（Bit Error Ratio， BER）性能會有一定的降低。為了減少最小和譯碼算法與BP譯碼算法之間的性能差距，已經提出了一些解決策略，如偏移最小和譯碼算法（Offset Min-sum Algorithm， OMSA）、歸一化最小和譯碼算法（Normalized Min-sum Algorithm， NMSA）等[9]。

3? ?深度神經網絡譯碼器

3.1? 具有多偏移因子的最小和譯碼算法

目前OMSA和NMSA已廣泛用于低密度校驗（Low Density Parity-Check， LDPC）碼的譯碼中，也可以把這種譯碼思想應用到極化碼中。與最小和近似譯碼相比，OMSA譯碼算法性能有很大提升，在中高信噪比區域甚至超過了BP譯碼算法的性能。與NMSA算法相比，OMSA算法有相對較好的譯碼性能。對NMSA譯碼算法中的單一因子α取不同的變量時可以得到具有多個歸一化因子的最小和（Multiple Normalized Min-sum， MNMS）譯碼算法，此時的算法等效為多尺度BP譯碼算法。

本節中提出了一種具有可學習偏移參數的多偏移最小和（Multiple Offset Min-sum， MOMS）譯碼算法。與OMSA算法使用單個全局偏移參數不同，MOMS算法中使用多個偏移參數，其中可學習的偏移因子減少了由最小和近似帶來的性能損失。MOMS譯碼算法中消息傳遞的更新迭代公式為：

與NMSA算法相比，OMSA算法雖然計算復雜度以及譯碼時延高，但其譯碼性能突出。所以如果這兩種算法在每次譯碼迭代過程中每個節點處使用不同的參數因子，得到的改進MNMS譯碼算法和MOMS譯碼算法性能上都會有所提升，并且MNMS譯碼算法的譯碼性能可能會不如MOMS譯碼算法。也可以說多尺度BP譯碼算法的譯碼性能可能不如MOMS譯碼算法，不過譯碼性能的比較還是應該通過最后的仿真結果來確定。但可以明顯看出MOMS譯碼算法的復雜度相對較高，所以譯碼時延也會較高。同多尺度BP譯碼算法一樣，MOMS譯碼算法中的多個偏移因子通過傳統的方法也很難求解，所以后面會根據深度神經網絡來幫助求解算法中的多個偏移因子，進而完成極化碼的譯碼過程。

3.2? 深度神經網絡譯碼器

傳統的信道譯碼算法中使用的單個參數因子通常是通過仿真實驗或者經驗獲得的，但這并不是最好的求解方法，因為通過實驗或者經驗并不能得到最優的參數。同時，當使用MNMS譯碼算法、MOMS譯碼算法或者多尺度BP譯碼算法對極化碼進行譯碼時，需要求解的參數數量會大大增加，因此通過傳統的仿真實驗求解最優參數顯然不現實。而深度學習具有處理復雜任務的能力，可以使用該工具去求解上述算法中復雜的參數問題。同時，由于深度前饋神經網絡和極化碼的BP因子圖在結構上相似，所以可以使用深度神經網絡來解決信道譯碼的問題。上一小節提到的MNMS譯碼算法、MOMS譯碼算法以及多尺度BP譯碼算法中的多個參數可以看作是深度前饋神經網絡的權重，這些權重可以通過使用小批量隨機梯度下降來訓練。

更確切地說，本文使用的深度前饋神經網絡譯碼器可以看作極化碼BP因子圖的展開形式。圖3給出了（8， 4）極化碼在神經網絡中的一次完整的迭代譯碼過程，它是根據圖2所示的（8， 4）極化碼的BP因子圖展開的。輸入層由8個神經元組成，隱藏層對應著從左到右的信息傳輸和從右到左的信息傳輸，它們分別占據2層神經網絡和3層神經網絡，所以中間總共有5層隱藏層。從右到左信息傳輸的最后一個隱藏層計算原始因子圖的最左邊節點的輸出。為了讓神經網絡譯碼器得到的碼字估值范圍為[0， 1]，最后一層網絡的輸出層需要使用sigmoid激活函數來處理上一層網絡的信息。對于（N， K）極化碼，展開極化碼的因子圖可以得到每層都包括N個神經元的深度神經網絡譯碼器，它是由輸入層、輸出層以及中間（2n-1）個隱藏層組成的，其中n=log2N，并且中間的隱藏層分別對應著（n-1）層從左到右的信息傳輸和n層從右到左的信息傳輸。

為了增加神經網絡譯碼器的網絡深度以及譯碼迭代次數，可以直接增加分別對應著從左到右的信息傳輸和從右到左的信息傳輸的隱藏層的數量，每一次譯碼迭代后的輸出作為下一次迭代的輸入。對于（N， K）極化碼，通過T次迭代譯碼后，可以得到總共包含（2（N-1）T+3）層的深度神經網絡譯碼器。圖4是經過T次迭代的神經網絡譯碼器結構。

為了評估所使用的神經網絡譯碼器的譯碼性能，這里采用交叉熵損失函數來衡量深度神經網絡實際輸出值和期望輸出值之間的差距：

其中，N表示碼字長度，yi和oi分別表示深度神經網絡期望的輸出值和實際的輸出值。事實上，每次迭代后可以在深度神經網絡譯碼器的結構中添加一個額外的輸出層，并將每次迭代后的輸出加到原來的損失函數中生成新的多損失函數。多損失函數通過梯度下降優化方法可以加快梯度更新的過程并向譯碼器的更深層學習。形成的新的交叉熵多損失函數可表示為：

4? ?訓練及仿真結果

4.1? 訓練細節

本文使用的深度神經網絡譯碼器模型是在深度學習框架Tensorflow[10]上通過學習率為0.001的Adam[11]梯度下降優化算法進行訓練的。為了評估深度神經網絡譯碼器的譯碼性能，通過蒙特卡羅方法進行仿真實驗。選取全零碼字作為訓練數據，該數據是經過高斯信道傳輸得到的，信噪比的范圍為1 dB～5 dB，選取150個碼字作為mini-batch的大小（每個SNR分配30個碼字）。測試數據是經過極化編碼，二進制相移鍵控調制并在高斯信道上傳輸后得到的隨機二進制信息。使用標準正態分布中的隨機值初始化神經網絡的權重。

訓練深度神經網絡譯碼器時，網絡深度是影響譯碼性能的一個重要因素，通常網絡層數越多得到的譯碼性能越好，但是會產生很高的訓練復雜度，所以應該選擇合適的網絡深度來獲得BER性能和計算復雜度之間的一個折中。這里使用貪婪搜索算法來衡量神經網絡的深度大小：

（1）首先對于（N， K）極化碼，通過一次迭代譯碼后，得到的深度神經網絡譯碼器的層數為（2（N-1）+3）。

（2）上面的神經網絡經過訓練并達到收斂后，再將測試數據輸入到已經訓練好的神經網絡中來獲得BER性能。

（3）增加步驟（1）中的譯碼迭代次數，每增加一次迭代，神經網絡的層數增加（2n-1）層，并重復步驟（2）直到BER性能曲線趨于平穩。

4.2? 仿真結果

這一部分給出了深度前饋神經網絡譯碼器對（64， 32）和（512， 256）極化碼進行譯碼的結果，并對比了MOMS譯碼算法和多尺度BP譯碼算法的BER性能差異。

對于（64， 32）極化碼，通過上面的貪婪搜索算法測試了網絡深度（或者迭代次數）對BER性能的影響，結果如圖6所示。從圖6可以看出，一次迭代的效果非常差，并且隨著迭代次數增加譯碼性能變得越來越好，最后在迭代次數為5的情況下BER性能曲線相對穩定。所以選擇T=5作為理想的迭代次數，此時深度神經網絡譯碼器總共包括53層。基于這個結果，圖7展示了（64， 32）極化碼的深度神經譯碼器在5次迭代下進行訓練的收斂情況，圖7中的1個epoch指的是將訓練集中的全部樣本訓練一次，仿真結果中BER性能在6個epoch左右保持穩定，這表明了訓練的收斂性。

實驗也對比了多尺度BP譯碼算法（MSBP）和具有多偏移因子的最小和譯碼算法（MOMS）對（64， 32）和（512， 256）極化碼進行譯碼的BER性能，考慮到訓練的復雜度以及算法的可對比性，神經網絡譯碼器都選擇T=5作為迭代次數，并分別在圖8中給出了仿真結果。兩種算法在低信噪比情況下雖然性能相當，但是與多尺度BP譯碼算法相比，可以看出所提出的具有多偏移因子的最小和譯碼算法具有一定的性能提升，并且在相同碼長下的高信噪比區域具有更好的譯碼性能。當然該算法對（512， 256）極化碼進行譯碼能得到更好的BER性能，顯然可以得出網絡越深譯碼性能越好的結論。這些結果驗證了具有多偏移因子的最小和譯碼算法優于多尺度BP譯碼算法。同時圖9給出了（512， 256）極化碼用多損失函數訓練得到的BER譯碼結果，從圖9可以看出用多損失函數訓練的譯碼算法有更低的比特誤碼率，在高信噪比區域內能實現高達0.7 dB的性能改善。

5? ?結束語

本文提出了一種多偏移最小和譯碼算法，該算法通過使用多個可學習的偏移參數來推廣偏移最小和譯碼算法，可以應用于極化碼的深度神經網絡譯碼結構中。通過仿真結果可以看出，與多尺度BP譯碼算法相比，本文提出的多偏移最小和譯碼算法可以獲得更好的糾錯性能，同時通過訓練具有多損失函數的深度神經網絡可以獲得較低的BER性能，為今后進一步設計極化碼譯碼器提出了新的解決方案。

參考文獻：

[1] Goodfellow I， Bengio Y， Courville A， et al. Deep learning[M]. Cambridge： MIT press， 2016.

[2] Polar碼成為5G新的控制信道編碼[J]. 上海信息化， 2016（12）： 87-88.

[3] Pamuk A. An FPGA implementation architecture for decoding of polar codes[C]//2011 8th International Symposium on Wireless Communication Systems.Aachen， Germany， 2011： 437-441.

[4] Nachmani E， Beery Y， Burshtein D. Learning to decode linear codes using deep learning[C]//2016 54th Annual Allerton Conference on Communication， Control and Computing. Monticello， IL， 2016： 341-346.

[5] Lugosch L， Gross W J. Neural offset min-sum decoding[C]//2017 IEEE International Symposium on Information Theory （ISIT）. Aachen， Germany， 2017： 1361-1365.

[6] Gruber T， Cammerer S， Hoydis J， et al. On deep learning based channel decoding[C]//2017 51st Annual Conference on Information Sciences and Systems. Baltimore， MD， 2017： 1-6.

[7] Cammerer S， Gruber T， Hoydis J， et al. Scaling deep learning-based decoding of polar codes via partitioning[C]//2017 IEEE Global Communications Conference. Singapore， 2017： 1-6.

[8] Xu W， Wu Z， Ueng Y L， et al. Improved polar decoder based on deep learning[C]//2017 IEEE International Workshop on Signal Processing Systems. Lorient， France， 2017： 1-6.

[9] Angarita F， Valls J， Almenar V， et al. Reduced-complexity min-sum algorithm for decoding LDPC codes with low error-floor[J]. IEEE Transactions on Circuits and Systems I： Regular Papers， 2014，61（7）： 2150-2158.

[10] Abadi M， Agarwal A， Barham P， et al. Tensorflow： Large-scale machine learning on heterogeneous distributed systems[Z]. 2016.

[11] Kingma D P， Ba J. Adam： A method for stochastic optimization[Z]. 2014.