基于深度強化學習的置信傳播譯碼算法

高源浩 劉乃金 魯淵明

摘 ?要：文章通過深度強化學習的方法來尋求二進制線性編碼的有效解碼策略。在加性高斯白噪聲的條件下，將置信傳播（BP）解碼算法中軟信息的迭代看作是對軟信息的連續決策，并將其映射到馬爾可夫決策過程，用深度強化學習網絡代替傳統譯碼器，擴大探索空間以提高譯碼性能，從而實現對數據驅動的最佳決策策略的學習。結果表明，相較于傳統BP解碼器，在誤碼率=10-5時，學習型BP解碼器在BCH碼上取得大約0.75 dB的優勢，這在一定程度上解決了以往研究中過于依賴數據的問題。

關鍵詞：深度強化學習;置信傳播譯碼;馬爾可夫決策;最佳決策

中圖分類號：TP18 ? ?文獻標識碼：A文章編號：2096-4706（2021）21-0098-05

Abstracts： This paper uses a deep reinforcement learning approach to find an efficient decoding strategy for binary linear codes. Under the condition of additive Gaussian white noise， the iteration of soft information in the belief propagation （BP） decoding algorithm is regarded as a continuous decision-making of soft information， which is mapped to the Markov decision-making process. The deep reinforcement learning network is used to replace the traditional decoder， expand the exploration space to improve the decoding performance， so as to realize the learning of the best data-driven decision-making strategy. The results show that compared with the traditional BP decoder， when the bit error rate is 10-5， the learning BP decoder has an advantage of about 0.75 dB in BCH code， which solves the problem of relying too much on data in previous research to a certain extent.

Keywords： deep reinforcement learning; belief propagation decoding; Markov decision-making; best decision-making

0 ?引 ?言

數字信號在傳輸過程中，由于受到各種干擾的影響，碼元波形將變壞，接收端收到后可能發生錯誤判決。由乘性干擾引起的碼間串擾，可以采用均衡的方法進行糾正。而加性干擾的影響則需要通過其他方法解決。在設計數字通信系統的時候，應該首先從合理選擇調制制度、解調方法以及發送功率等方面考慮，使得加性干擾不足以影響到誤碼率要求。在仍不能滿足要求時，就要考慮采用信道編碼方法了。

為了改善通信的質量，研究者們嘗試了很多辦法。信道編碼是人們在改善通信質量方面最早采用的方法之一，通過給原數據添加相關的冗余信息來對抗傳輸過程中的干擾。信道編碼中以線性分組碼應用最廣，廣泛應用于衛星通信、移動通信、存儲設備、數字視頻廣播等領域，此外，線性分組碼可以在傳輸效率與糾錯能力之間進行權衡，允許其在更低的發射功率下保持同質量的服務。因此，提高線性分組碼性能具有極其重要的意義。

糾錯碼的解碼可以看作是一個分類問題，能夠通過監督機器學習的方式得以解決。一般的想法是將解碼器視為一個參數化的函數（比如，一個神經網絡），通過數據驅動的優化來學習良好的參數配置。如果沒有對編碼方法的進一步限制，深度學習方法通常只對短碼字有較好的效果，不適用于超過幾百個碼字長度的非結構化代碼。對線性分組碼來說，這個問題就大大簡化了。人們只需學習一個決策區域即可，而無需學習每個碼字所在的各個區域，然而，這仍然是一個極具挑戰性的問題，因為一個好的編碼方案通常具有復雜的決策區域，每一個碼字都有大量相鄰的碼字。Tobias Gruber認為可以通過深度神經網絡對隨機碼和結構化碼（如polar碼）進行一次性解碼[1]。通過學習，發現結構化編碼更容易學習。對于結構化編碼，神經網絡能夠泛化到它在訓練期間從未見過的碼字。Tim OShea提出并討論了深度學習（DL）在物理層面的幾個新應用[2]。通過將通信系統解釋為一個自動編碼器，將通信系統設計視為一個端到端的重建任務，尋求在單一過程中同時優化發射器和接收器組件。EliyaNachmani提出一種基于改進信念傳播算法的新型深度學習方法[3]。該方法通過給Tanner圖的邊分配權重的方式來概括標準的信念傳播算法，然后使用深度學習技術對這些邊進行訓練。信念傳播算法的一個眾所周知的特性是對所傳輸碼字性能的獨立性。Amir Bennatan提出一個新的框架，將深度神經網絡（DNN）應用于任意塊長度的線性編碼的軟解碼[4]。他們所提出的框架允許無約束的DNN設計，能夠自由靈活地應用在其他背景下開發的強大設計，對抑制許多競爭性方法的過擬合具有魯棒性，這源于其訓練所需呈指數級增長的大量編碼。結果表明，其性能有時接近有序統計解碼（OSD）算法的性能。EliyaNachmani介紹了一個基于逐次松弛方法的循環神經解碼器架構，在較稀疏的Tanner圖表示的編碼上也觀察到了比標準信念傳播得更好的性能改進。此外，他們還證明了神經信念傳播解碼器可以用來提高短BCH碼的性能，或者是降低接近最佳解碼器的計算復雜性。

本文中，我們從機器學習的角度研究了二進制線性碼的解碼。置信傳播算法利用節點與節點之間相互傳遞信息來更新當前所有節點的狀態。通過消息傳播，將該節點的概率分布狀態傳遞給相鄰的節點，從而影響相鄰節點的概率分布狀態，經過一定次數的迭代，每個節點的概率分布將收斂于一個穩態。在實際的置信傳播譯碼過程中，校驗節點和變量節點之間的消息傳遞雖然存在重復信息，但是重復信息比較少，因此可以近似地認為每一次的迭代譯碼都只用上一次迭代后的對數似然比值進行計算，這滿足于馬爾可夫決策中狀態的改變只與上一個狀態有關，而與上一個狀態之前的狀態無關的特點。因此，可以將置信傳播譯碼中軟信息的迭代看作是對軟信息的連續決策，并將其映射到馬爾可夫決策過程。利用深度強化學習網絡解決譯碼問題，通過自主探索逼近最佳性能。當前，BP解碼已經得到了廣泛的研究，例如文獻[5-7]等。據調研，本文提出的BP解碼方法仍然是較為新穎的。事實上，研究和探討RL解碼的參考文獻很少[8，9]，只是涉及一些比較典型的工作。簡單回顧一下迭代譯碼算法，它們都是基于連續的決策步驟，因此RL適用于這些算法。

1 ?信道解碼原理

假設C是一個由M×N的奇偶校驗矩陣H定義的一個（N，K）二進制線性分組碼，其中N為碼長，K為碼的維度。該碼字用于將信息編碼成碼字c=（c1，...，cN）T，然后在加性高斯白噪聲（AWGN）信道上傳輸，傳輸碼字經過信道得到接收碼字y，y的每一個分量yn=（-1）Cn+ωn，ωn～N（0，（2REb/N0）-1），R=K/N稱作碼率，將Eb/N0稱為信噪比，用SNR表示。接收到的碼字y經過硬判決得到結果z=（z1，...，zN）T， zN是通過對yN的符號進行映射得到的，映射規則為+1→0，-1→1。

當前，常用的高效迭代解碼算法有兩種，這兩種算法的每一步都涉及決策過程：

（1）比特翻轉解碼算法。BF解碼的一般思路是構建一個合適的度量，允許解碼器根據編碼約束條件下的可靠性對比特進行排序[10]。在其最簡單的形式中，BF使用硬判決輸出z，并在迭代地尋找翻轉之后，找出能最大限度減少當前違反PC方程數量的位置。當前，BF解碼在學術界得到了廣泛的研究，在許多現代編碼理論的文獻中都有涉及，比如[11-14]。

（2）置信傳播譯碼算法。BP算法是一種迭代算法，消息沿著由編碼的tanner圖表示的邊進行傳播。BP算法的大概流程為：

首先是初始化，可由式（1）（2）實現：

其中，Ki為校正因子，保證成立。如果大于0.5則為當前碼字判決為0，反之判決為1，從而得到判決結果r。

4）校正子計算方法為s′=Hr=[s0，s1，s2，...，sn]，然后將smod 2得到校正子s。如果s不為0向量，則轉至1）繼續迭代過程直到譯碼成功或者達到譯碼最大次數上限。

2 ?馬爾可夫決策過程

馬爾可夫決策過程，為確定或隨機環境下的決策建模提供了一個數學框架。馬爾可夫決策過程可以用來獲得最優的決策策略，用數據驅動的最優度量的學習來替代啟發式學習。

一個時不變的馬爾可夫隨機過程S0，S1，…，其狀態轉移概率僅受代理根據對過去狀態的了解而采取的行動At影響。其中，s、s′∈S，a∈A，S和A是包含所有可能狀態與動作的有限集合。代理同樣會接收到一個獎勵Rt=R（St，At，St+1），并且獎勵只取決于狀態St，St+1和動作At。這個代理的決策過程被描述為一個策略π：S→A，表示將觀察到的狀態映射到動作。我們的目標是找到一個最佳決策π*，使使得在每個可能的狀態下以預期獎勵返回一個最佳動作，其中，0<γ<1是未來獎勵的衰減因子。

過渡和獎勵概率已知的情況下，可以采用動態編程來計算最優策略;概率未知的情況下，如果假設狀態和獎勵是可觀察的，則仍可以通過與環境的反復交互發現最優策略，這就是所謂的強化學習（RL）。下面介紹兩種文獻中最常用的RL方法：

（1）Q-learning。最直接的RL實例被稱為Q-learning。其最優策略根據Q函數Q：S×A→R，通過式子：得到。Q函數用于衡量行動的質量，正式定義為當智能體處于狀態s，采取行動a，然后采取最佳行動時的預期折現的未來獎勵。Q函數的主要優點是，它可以從任何“足夠隨機”的代理的觀察中反復估計。下文給出了Q-learning的偽代碼，其中第5行中生成行動的一個探索策略為：

Input： learning rate α， discount factor γ

Output： estimated Q-function

Initialize Q（s， a） ← 0 for all s ∈ S， a ∈ A

Fori = 1， 2， … do

initialize starting state s ? ? ? ? ?// restart the MDP

while s is not terminal do

choose action a ? ? ? ? ? ? // ε-greedy

execute a， observe reward r and next state s

Q（s， a） ← （1-α）Q（s，a）+α（r+ γmaxa∈AQ（s， a））

s ←s

由此，我們發現Q函數能用式（9）遞歸的表示為：

這個表達式構成了Q-learning的理論基礎，它在一定條件下收斂于真正的Q-函數。

（2）帶有函數近似值的擬合Q-學習。對于標準的Q-learning，人們必須存儲一個|S|×|A|的實值表。如果其中一個集合非常大，那么標準的Q-learning將難以實現。擬合Q-learning的想法是學習Q（s，a）的低復雜度近似值。將Qθ（s，a）作為Q函數的近似值，以θ為參數。擬合Q-learning在模擬MDP和更新當前參數之間交替進行，以獲得對Q-函數的更好估計。假設我們已經模擬并存儲了一個集合D中B個過往經驗（s，a，r，s′）。更新參數θ是為了減少經驗損失，可由式（10）表示：

下面給出擬合Q-learning的偽代碼：

Input： learning rate α， batch size B

Output： parameterized estimate of the Q-function

Initialize parameters θ and D←?

Fori = 1， 2， … do

initialize starting state s ? ? ? ? ?// restart the MDP

while s is not terminal do

choose action a ? ? ? ? ? ? // ε-greedy

execute a， observe reward r and next state s

store transition（s， a， r， ） in D

s←

if |D| = B then

θ←θ-α▽θLD（θ）

empty D

其中，梯度下降是用來根據損失（1）更新參數θ的。通常選擇Qθ（s，a）作為一個（深度）神經網絡（NN），在這種情況下，θ是網絡的權重，擬合Q-learning被稱為深度Q-learning。深度Q-learning所采用的主要技巧是經驗回放（experience replay），即將每次和環境交互得到的獎勵與狀態更新情況都保存起來，用于后面目標Q值的更新。通過經驗回放得到的目標Q值與通過Q網絡計算得到的Q值，二者之間肯定是存在一定誤差的，我們可以通過梯度的反向傳播來更新神經網絡的參數w。我們使用了兩個Q網絡，一個當前Q網絡Q用于選擇動作，更新模型參數。另一個目標Q網絡Q′用于計算目標Q值。目標Q網絡的網絡參數不需要迭代更新，而是每隔一段時間從當前Q網絡Q復制過來（即延時更新），這樣可以減少目標Q值與當前Q值的相關性。

3 ?基于深度強化學習的置信傳播算法

我們提出了一種利用深度強化學習來改善置信傳播算法的方案。利用軟信息進行譯碼簡單來說就是通過每一次的迭代去更新各個信息節點的對數似然比值，然后進行判決，判斷譯碼是否正確。當前對數似然比值僅與上次迭代過程中的對數似然比值有關，而與之前的狀態無關（即在tanner圖上進行數據傳遞），tanner圖如圖1所示。因此，可以將利用軟信息進行譯碼的過程與馬爾科夫決策過程相類比，將軟判決譯碼映射到馬爾科夫決策過程中去（有些文獻里也用c表示校驗節點，即圖1中的s節點）。

?本方案的基本流程為：

（1）利用接收碼字初始化各個信息節點的對數似然比值，作為初始狀態S0。

（2）根據既定的探索策略選擇一個動作At，更新變量節點的對數似然比值。

（3）根據動作選擇，變量節點轉變為新的狀態s′和反饋獎勵r。

（4）利用神經網絡生成擬合的Q值并更新神經網絡參數。

（5）根據新的狀態s′生成判決結果x，判決HTx是否為0（或者是否到最大迭代步數），是則結束，否則轉步驟（2）。

本方案的基本參數設定為：

（1）狀態空間S。取所有變量節點的對數似然比值作為狀態，由于對數似然比值是一個連續值，因此狀態空間是一個連續的狀態空間，我們需要引入神經網絡來擬合Q-學習中的Q值。

（2）動作空間A。任選其中一個變量節點，取一個改變值Δ（V ），選擇在原來對數似然比的基礎上+Δ（V ）/-Δ（V ）兩種動作，則At一共有2N種動作。本方案中取Δ（V ）= 0.01。

（3）信道選擇。AWGN信道，信噪比SNR滿足SNR=10lg（10Eb/N0），白噪聲服從高斯分布，且均值為0，方差為噪聲平均功率。因為假定的AWGN信道只有高斯白噪聲，所以在信噪比SNR設定完成后就能直接在傳輸碼字上添加確定的噪聲，之后獲得接收碼字。

4 ?仿真結果

本方案所采用的開發工具是PyCharm和MATLABR2020a。傳統的置信傳播方法采用MATLAB語言實現，而基于深度強化學習的置信傳播算法則采用Python語言開發，開發環境為Python3.8，主要使用了torch庫（用于引入神經網絡）和matplotlib庫（用于繪圖）。編碼方案為BCH（63，45），其中，輸入為63維，輸出為126維，所以該神經網絡是非常復雜的，其探索空間也是比較大的。該網絡一共有三層：輸入層（63，64）、中間層（64，64）、輸出層（64，126），激活函數為relu，探索率下限設置為0.1。

圖2展示了采取三種不同探索率下限來對比誤碼率的結果，其中x軸為SNR（即信噪比Eb/N0取對數后的結果），單位為dB，y軸為誤碼率BER（之后的圖表x，y軸也相同）。如果神經網絡訓練穩定之后，誤碼率會隨著神經網絡探索率下限的降低而升高，在SNR小于10 dB的范圍內，SNR-BER曲線符合我們的預期。同時，我們采取不同的網絡結構來對比誤碼率的結果，例如去掉中間層（64，64），如圖3所示。可以看到，神經網絡層數越多，誤碼率越低，在SNR<10 dB的區間內，SNR-BER基本符合預期。

?同時，我們也完成了基于深度強化學習的BCH（63，45）譯碼，并用訓練結果（BF_RL）與用BP方法實現的BCH（63，45）碼字解碼（BP）相對比，如圖4所示，從圖中可以看出基于深度強化學習的BCH（63，45）譯碼明顯優于傳統的BP算法，在BER為10-5時有大約0.75 dB的優勢。

?最后，我們針對比特翻轉譯碼使用強化學習方法對文獻[14]進行了簡單復現（BF_RL），并將本文使用的基于深度強化學習的置信傳播譯碼方法進行了對比，如圖5所示，結果顯示在（7，3）線性分組碼中優勢比較明顯，在BER為10-5時大約有2 dB增益。

?5 ?結 ?論

在本文中，我們提出了一個新穎的二進制線性碼BP解碼的RL框架。研究表明，如果適當選擇狀態和行動空間，BP解碼可以映射到馬爾科夫決策過程。原則上，這可以實現數據驅動的最佳BP決策策略的學習。標準的（基于表格的）和裝有NN函數近似器的Q-learning都被用來從數據中學習好的決策策略。結果表明，我們所提出的學習型BP解碼器具有一定的優勢，然而，優勢僅僅局限在中短碼字上，長碼字始終面臨狀態空間和動作空間過大的問題。因此，利用強化學習進行長碼字的解碼仍然是一個極具挑戰性的問題，這將是我們之后的研究方向。

參考文獻：

[1] GRUBER T，CAMMERER S，HOYDIS J，et al. On deep learning-based channel decoding [C]//2017 51st Annual Conference on Information Sciences and Systems （CISS）.Baltimore：IEEE，2017：1-6.

[2] OSHEA T，HOYDIS J. An introduction to deep learning for the physical layer [J].IEEE Transactions on Cognitive Communications and Networking，2017，3（4）：563-575.

[3] 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 （Allerton）.Monticello：IEEE，2016：341-346.

[4] BENNATAN A，CHOUKROUN Y，KISILEV P. Deep learning for decoding of linear codes-a syndrome-based approach [C]//2018 IEEE International Symposium on Information Theory （ISIT）.Vail：IEEE，2018：1595-1599.

[5] NACHMANI E，MARCIANO E，LUGOSCH L，et al. Deep learning methods for improved decoding of linear codes [J].IEEE Journal of Selected Topics in Signal Processing 2018，12（1）：119-131.

[6] 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 （Allerton）. Monticello：IEEE，2016：341-346.

[7] LIANG F，SHEN C，WU F. An iterative BP-CNN architecture for channel decoding [J]. IEEE Journal of Selected Topics in Signal Processing，2018，12（1）：144-159.

[8] Wang X B，Zhang H Z，Li R，et al. Learning to flip successive cancellation decoding of polar codes with LSTM networks [C]//2019 IEEE 30th Annual International Symposium on Personal， Indoor and Mobile Radio Communications （PIMRC）. Istanbul：IEEE，2019：1-5.

[9] CARPI F，H?GER C，MARTAL? M，et al. Reinforcement learning for channel coding： Learned bit-flipping decoding [C]//2019 57th Annual Allerton Conference on Communication， Control， and Computing （Allerton）. Monticello：IEEE，2019：922-929.

[10] Ryan W，Lin S. Channel codes： classical and modern [M]. Cambridge university press，2009.

[11] BOSSERT M，HERGERT F. Hard-and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes （Corresp.） [J]. IEEE transactions on information theory，1986，32（5）：709-714.

[12] KOU Y，LIN S，FOSSORIER M P C. Low-density parity-check codes based on finite geometries： a rediscovery and new results [J].IEEE Transactions on Information theory，2001，47（7）：2711-2736.

[13] Zhang J T，FOSSORIER M P C. A modified weighted bit-flipping decoding of low-density parity-check codes [J].IEEE Communications Letters，2004，8（3）：165-167.

[14] JIANG M，ZHAO C M，SHI Z H，et al. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes [J].IEEE Communications Letters，2005，9（9）：814-816.

作者簡介：高源浩（1997—），男，漢族，重慶銅梁人，碩士研究生在讀，研究方向：基于強化學習的線性分組碼譯碼方法。