LDPC碼置信傳播譯碼時序研究

南京信息工程大學電子與信息工程學院 周 華 李誠謙 余嘉昊

LDPC碼置信傳播譯碼時序研究

南京信息工程大學電子與信息工程學院 周 華 李誠謙 余嘉昊

本文對低密度奇偶校驗（LDPC）碼置信傳播譯碼的三種基本時序安排進行詳細介紹，包括洪泛譯碼、串行譯碼、動態譯碼。對各譯碼時序的原理、收斂速度、誤碼率等進行闡述和比較，并提出一些可行性改進措施來提高LDPC碼的譯碼性能。

LDPC碼；置信傳播；譯碼時序

1. 低密度奇偶校驗碼介紹

低密度奇偶校驗碼（LDPC碼） 由二進制稀疏矩陣定義，矩陣中大部分元素是 0，剩余部分元素為 1。LDPC碼的一個重要研究成果是1981年著名學者Tanner提出了用圖模型來表述LDPC碼的理念。該模型根據LDPC碼的校驗矩陣中1的位置提出雙向二分圖。通過二分圖可構造性能良好的 LDPC 碼，支持并行譯碼，大大降低譯碼復雜度。Mackay 和 Neal 利用二分圖對 LDPC 碼性能進行了深入研究，發現采用置信傳播（belief propagation）譯碼算法的 LDPC碼譯碼性能逼近香濃極限。

2. LDPC碼置信傳播譯碼算法

假設一個（N,K）的LDPC碼，校驗位數量為M=N-K，則校驗矩陣H是一個M*N的矩陣。矩陣H的二分圖如圖1所示。圖1下方的N個圓圈節點表示N個碼字符號，稱作變量節點；上邊的M個方形節點表示M個校驗方程，稱作校驗節點。當變量節點和校驗節點存在于同一個校驗方程時，就用邊將兩者連接。和每個節點相連的邊的個數稱作該節點的度。從某個節點出發再次回到該節點所經歷邊的個數即為環的長度，其中最短環所經過的邊的數量構成二分圖的圍長。如圖1，黑色加粗的邊構成了一個圍長等于4的短環。我們構造矩陣的時候尤其關注最小圍長，因為它直接關系到LDPC碼的譯碼性能。

圖1 LDPC碼的校驗矩陣和二分圖

3. 置信傳播的調度安排

LDPC碼最常用的譯碼算法是置信傳播。理論分析表明，如果與其校驗矩陣對應的二分圖無環路存在，則BP算法會收斂于全部比特的后驗概率，也是LDPC碼具有良好性能的原因之一。

通常評估一種譯碼算法有三個指標：譯碼速率、譯碼復雜度和譯碼性能。譯碼器通過迭代算法更新消息，直到滿足停止條件。迭代算法的本質是對二分圖中的信息進行調度。調度是指置信傳播過程中變量節點和校驗節點之間的消息更新次序。下面介紹幾種常見的時序調度譯碼算法：

第一，洪泛機制是標準置信傳播算法釆取的調度策略，屬于并行消息傳遞機制，也是最普遍最基本的調度策略。它的做法是：在每一輪迭代過程中，所有校驗節點同時收集從相鄰變量節點傳來的消息，更新完畢后，再利用已更新過的所有校驗節點的消息同時去更新所有變量節點的消息，最后每個變量節點根據判決條件進行判決，如此反復，直到滿足停止條件。這種消息傳遞機制最為簡單，譯碼速率也很高，但性能并不是最優的。研究標明，洪泛往往需要較大的迭代次數才能收斂，從而引起高運算量以及很長的譯碼時延。泛洪的置信傳播調度方式如圖2所示。

圖2 泛洪算法節點間消息傳播的過程

第二，串行調度按照一定的次序，依次對各節點進行更新。直到所有的校驗節點（或變量節點）更新完畢，一次迭代過程才算結束。串行的消息傳遞機制，與洪泛機制相比，具有收斂速度快，復雜度低，且實際占用硬件資源少的特點。分層置信傳播是一種典型的串行調度策略。研究表明，LBP譯碼的收斂速度大概是洪泛的兩倍，且復雜度與洪泛保持一致。這是一種相對理想的，幾乎不增加復雜度代價的更新策略。但是無論是洪泛還是LBP，其更新節點的順序是不變的，稱其為非動態消息更新策略。LBP的置信傳播調度方式如圖3所示。

圖3. 泛洪算法節點間消息傳播的過程

第三，動態調度動態選擇節點進行更新，使得譯碼達到最優的性能和最大的收斂速率。其中殘差置信傳播策略能較大提高譯碼收斂速率。RBP為一種動態消息調度策略，每次需要對所有的消息計算更新前后的差值，然后進行排序。篩選出最大殘差值所在的邊，對其優先更新。其原理是，當譯碼收斂的時候，節點前后兩次消息的殘差值會趨向于0，也就是說，如果節點間消息殘差值越大，則可以認為該消息在迭代譯碼中還未收斂，更新該消息對整個算法收斂具有較大貢獻。因此優先對該節點進行處理，能有效的加快譯碼的整體收斂速率。RBP在高性噪比區可能存在誤碼平層現象，因而大大限制了譯碼性能。繼而一種面向節點的RBP的動態策略(NWRBP)被提出，在一定程度上有效克服誤碼平層現象。NW-RBP在原有的算法上做了改進，與RBP不同，NW-RBP在選中最大殘差值之后，讓更多的變量節點參與更新。仿真結果表明, NW-RBP不僅提高了譯碼收斂速率，而且改善了RBP的譯碼性能，但是相對復雜度比較高。RBP和NW-RBP的置信傳播調度方式如圖4所示。

圖4 RBP（左）和NW-RBP（右）算法節點間消息傳播的過程

為比較以上三種調度方式的效果，采用（1944,972）碼在AWGN信道下進行以上幾種置信調度機制仿真，仿真結果如圖5所示。當迭代次數較小的時候，RBP性能要顯著優于其他三種算法。但隨著迭代次數繼續增大，RBP的FER曲線開始變得平緩，不再隨著迭代次數的增加而降低，曲線出現了誤碼平層現象。尤其，在RBP迭代4次時候的FER與LBP在迭代次13的時候的FER相同，而且兩種算法的FER曲線在迭代次數19次的時候相交，這說明了在RBP譯碼過程中，雖然迭代次數增大，仍然有些錯誤無法正確譯出。當迭代次數較小，NW-RBP的性能并不如RBP，然后在迭代次數為10次的時候，RBP的性能曲線出現了瓶頸，而NW-RBP的FER繼續得到改善而降低，這說明NW-RBP能較好得克服錯誤平臺現象而使得譯碼的性能更好。此外，NW-RBP在迭代15次的時候的FER與LBP在迭代50次的時候的FER相同，且在迭代10次之后，NW-RBP相比RBP和LBP分別有1dB和0.8dB的FER增益，這說明NW-RBP能有效克服誤碼平層現象。

圖5 信噪比Eb/N0=1.75dB時，（1944,972）碼的FER隨迭代次數變化的情況

4. 改進措施展望

以上介紹的串行、動態調度置信傳播，雖然取得了快速收斂的效果。然而，在迭代次數較多的情況下，現有的一些改進方案并不能較大提高NW-RBP的誤碼率。由香濃極限所得，當LDPC碼碼長足夠長時，迭代置信譯碼算法可以無限接近香濃極限。由此可見，LDPC碼中的短環結構的存在，是導致譯碼算法無法收斂的重要原因。基于這一點，本文提出兩點可行性改進措施：第一，統計LDPC碼Tanner圖中的短環分布情況。短環分布不僅要計算出短環的數量，還要統計出具體哪些變量節點參與組成短環，即短環結構。第二，在完成短環分布統計的基礎上，分析短環對置信迭代算法的影響，研究殘差值隨迭代次數增加的變化趨勢，從以下幾個方面嘗試設計新的快速收斂調度方法：（1）賦予參與組成較多短環的變量節點優先調度權；（2）與比特反轉算法相結合，當置信算法無法收斂時，反轉短環中的某些變量節點的符號，從而達到提高收斂速度和譯碼正確率的目的；（3）參考RBP算法，首先依據參與短環數對變量節點進行歸類，對參與短環較多者并且殘差最大者優先調度。以上幾種方法的有效性，將在今后的研究中予以驗證。

5. 總結

本文對低密度奇偶校驗碼的三種置信傳播譯碼時序進行詳細介紹。這三種譯碼時序分別是洪泛譯碼、串行譯碼、動態譯碼。通過展示LDPC碼二分圖中信息的傳遞順序和各譯碼時序的仿真案例，對各譯碼時序的譯碼原理、收斂速度、譯碼誤碼率等進行闡述和比較，并提出一些可行性改進措施，以期望提高LDPC碼的譯碼性能。

[1]R.Gallager.Low density parity check codes.IET Transactions on Informaiton Theory.1962.

[2]F.Kschischang,B.J.R.Frey,and H.A.Loeliger.Factor graphs and the sum-product algorithm. IET Transactions on Informaiton Theory. 2001.

[3]A.I.V.Casado,M.Griot,and R.D.Wesel.LDPC decoders with informed dynamic scheduling.IEEE Transactions on Communications. 2010.

結束語

通過對微控制器的嵌入式低功耗應用方面相關內容的探討，可知嵌入式系統低功耗設計目標的實現，需要加強微控制器的合理運用。在具體的設計過程中，應提高對微控制器結構特點的全面認識，確保其在嵌入式低功耗應用中能夠達到預期的效果，并在可靠的低功耗模式支持下，提高相關資源利用效率的同時完善系統的服務功能，實現對系統功耗的有效控制。

參考文獻

[1]邵貝貝.單片機嵌入式應用的在線開發方法 .清華大學出版社,2004.

[2]林東寧,張強.墨盒芯片,實用新型專利,專利號ZL 200620060165.9.

[3]劉長龍,嚴新文.嵌入式低功耗8位微控制器的設計[J].天津大學學報,2010,(12).

[4]李多,葉樺.一種基于STM32的嵌入式低功耗無線手持控制器設計[J].電子設計工程,2014,(18).

[5]劉偉偉.嵌入式系統低功耗技術的研究和應用[D].鄭州大學,2012,(05).

項目資助：江蘇省級大學生實踐創新訓練計劃項目（201610300049），江蘇高校品牌專業建設工程資助項目，江蘇高校優勢學科Ⅱ期建設工程資助項目。