LDPC碼稀疏校驗矩陣的重建方法

包 昕，周磊砢，何 可，游 凌

?

LDPC碼稀疏校驗矩陣的重建方法

包 昕，周磊砢，何 可，游 凌

(西南電子電信技術研究所 成都 610041)

針對LDPC碼識別過程中的稀疏校驗矩陣重建問題，研究并提出了3種算法。在分析和比較LDPC碼與一般分組碼識別模型的基礎上，將LDPC碼的識別問題定義為尋找碼字對偶空間下某組稀疏基的數學問題。通過以校驗向量行重作為優化對象，先后設計和實現了了2-階行間線性變換、-階行間線性變換、線性關系有限窮舉的3種矩陣稀疏化算法，力求實現無誤碼條件下對適度碼長長度LDPC碼校驗矩陣的有效重建。測試結果表明，該算法適用于包括802.16e、802.11n、DVB-S2、GJB7296、GB20600在內的多種LDPC碼標準。

信道編碼識別; LDPC識別; 校驗矩陣; 稀疏化

信道編碼識別即是根據解調后的比特流序列，辨識所采用的糾錯編碼類型及其對應參數，廣義上還包括對交織和擾碼的識別。

LDPC碼雖屬于分組碼范疇，但由于其碼長往往極長，構造方法多樣且隨機，故傳統識別思路在可接受計算量內難以發揮作用。文獻[10-12]通過計算后驗概率對數似然比(LLR)，將軟解調序列與LDPC碼校驗關系聯系在一起。文獻[13]在前者基礎上，進一步完善了約束關系模型，推導并量化了相應統計學特征。

以上LDPC碼的研究成果均將編碼識別問題弱化為一種假設檢驗判決問題，是在已知集合內實現碼型的準確匹配，僅能適用于閉集識別應用背景。本文重點關注無誤碼LDPC碼的開集識別問題，力求在從無誤碼編碼序列流中，重建LDPC碼稀疏校驗矩陣，最終實現非合作條件下的有效譯碼。

1 問題描述與分析

1.1 一般線性分組碼識別問題

由于有限維線性空間中的每個線性無關向量組，都可以充當此空間一組基。因此，生成矩陣作為編碼空間的一組基，并不唯一。若設定分組碼采用系統結構，且信息前置，則生成矩陣必然滿足形式，其中，為單位矩陣。通過對無誤碼碼字做高斯消元線性變換，獲得該形式的為：

綜上，這種以恢復或測量碼字空間的基為目標、獲得編碼生成矩陣或校驗矩陣的編碼識別思路，是幾乎所有編碼識別方法的理論基礎。

1.2 LDPC碼的識別

信道編碼識別的本質目的不僅是獲取一系列編碼參數，而是在此基礎上實現非合作條件下的信息獲取。對于一般線性分組碼，和的恢復問題等價，按照前述計算流程，在獲取或的基礎上，結合各種代數譯碼方法即可展開譯碼，識別工作基本完成。

然而，LDPC碼的識別工作則相對不同。LDPC碼稀疏校驗矩陣的結構對該碼譯碼性能具有決定性的影響?；谥眯哦葌鞑サ腂P算法是LDPC碼的常用譯碼算法，它建立在節點間信息傳遞具備統計獨立性這一基本假設上。若所對應Tanner圖中存在短環，則某一節點發出的信息經過短環傳遞回自身，則將破壞該統計獨立性假設，進而影響譯碼性能。因此，LDPC碼在構造稀疏校驗矩陣時，總是力求減少甚至完全規避短環。

因此，直接按1.1節所述方法獲取的校驗矩往往不可能取得好的譯碼效果。以IEEE 802.16e的(576,288) LDPC碼為例，圖1a所示為標準中所定義的具備準循環結構的真實校驗矩陣，圖1b所示為根據式(2)所得的具備結構的等價校驗矩陣。

綜上，LDPC碼識別問題與一般線性分組碼識別問題不同，它不僅是尋找分組碼碼字零化空間的任意一組基，而且是在前者基礎上，恢復所有基中某組具備稀疏特性的基。本文不限定LDPC碼的具體構造方法，嘗試僅利用碼字空間的線性相關性，實現稀疏校驗矩陣的重建，即對原非稀疏校驗矩陣的稀疏化，用以實現無誤碼條件下的LDPC碼識別。

2 矩陣的稀疏化

2.1 2-階行間線性變換算法

5) 返回步驟1)。

6) 直至再也沒有行可替換，迭代終止。

圖2記錄了IEEE 802.16e (576，288)LDPC碼使用該算法所得的歷次迭代后的行重分布圖。原始待稀疏校驗矩陣，平均行重58.5，最大行重68，最小行重48，經過12次稀疏化迭代后，行重降為6或7。

最終的稀疏化結果如圖3所示。由圖可見，其與圖1a所示的真實校驗矩陣是等價的，算法成功。

圖2 (576,288)LDPC碼歷次迭代的行重分布

2.2 仿真測試

當前，LDPC碼已廣泛應用于衛星、深空、無線等通信領域，具有代表性的公開標準包括IEEE 802.16e[14]、IEEE 802.11n[15]及DVB-S2[16]、GJB 7296[17]，各種私有標準也層出不窮。本文使用2-階行間線性變換算法，對它們展開測試。

圖4針對IEEE 802.16e標準進行，參數(2 112, 1 056)。圖4a為待稀疏校驗矩陣，圖4b為稀疏化后的結果。由圖可見，稀疏化后校驗矩陣已具備明顯的準循環結構，經比對，與標準中描述的真實校驗矩陣完全相同。

同理，圖5是針對IEEE 802.11n的(1 944，1 620)LDPC碼進行仿真結果，算法證實有效。

圖6描述了針對GJB 7296-2011標準的試驗情況。編碼參數(992,744)，該系列LDPC碼由清華大學設計，已成功應用于嫦娥探月工程。圖6b為稀疏化結果，與真實矩陣完全一致。

以上3種LDPC標準，均屬于準循環LDPC結構(QC, Quasi-Cyclic)，前兩種的擴展矩陣由單位陣循環移位形成，后一種的擴展矩陣被定義為一個基于伽羅華域的偽隨機交織陣。

DVB-S2的校驗矩陣采用了另一種結構化設計思路。其左側為若干帶狀化矩陣，可在碼長極長的同時控制存儲量，編碼效率也獲得提高。圖7針對DVB-S2標準中(16 200,14 400)LDPC短碼進行仿真，圖7b的稀疏結果呈現明顯的帶狀形態，非零元素比由最初的降為，經與真實矩陣比對后證實完全相同。

對于采用隨機構造方式產生的LDPC碼，本文選擇了某商用衛星LDPC編碼進行算法試驗，結果如圖8所示。該矩陣右側保持雙對角形式，左側非零元素位置隨機分布。經算法處理后，非零元素個數僅占，四環個數為0，可見本文的算法依然有效。

3 矩陣重建問題的解決

3.1 p-階行間線性變換算法

更為全面的測試顯示，前述算法在某些應用場合可能失效。

圖9給出了GB20600[19]中編碼參數為(7 493, 6 096)的LDPC碼校驗矩陣。該標準采用信息后置設定，構造方法雖屬于QC結構(擴展因子127 bit)，但與以往明顯不同的是，左側規模為的校驗區，并非由每行2個的單位陣組成雙對角結構，而是由每行4個的循環移位陣組成不規則的4對角結構。

反觀圖9所示的GB20600校驗矩陣，其校驗區方陣為不規則4對角，若利用原有算法，的確難以實現矩陣恢復。將原2-階行間線性變換，拓展為-階行間線性變換，形成如下-階行間線性變換算法。

6) 回到步驟2)。

7) 回到步驟1)。

8) 直至再也沒有行可替換，迭代終止。

3.2 線性關系有限窮舉算法

前述兩種算法均可以從一定程度上，實現LDPC碼的校驗矩陣重建。前者基于2-階行間線性變換這一手段，適用于采用雙對角結構的LDPC碼；后者是對前者的加強，將運算規則拓展為-階行間線性變換，但仍未徹底解決稀疏校驗矩陣的重建問題。

經過更為豐富的測試，本文發現：無論是2-階行間線性變換算法還是-階行間線性變換算法，其基本思想均是希望通過遍歷原始待稀疏校驗矩陣中若干種行線性變換，窮舉出有限量級內可能的稀疏化校驗向量；但在實際算法進行時，第層的校驗節點將可能隨機地等價為大于等于個原始矩陣的校驗節點的線性組合；而所希望的個校驗節點間的線性組合并未得到窮舉，稀疏效果因此難以保證最優。這也解釋了-階行間線性變換算法仍未能徹底實現矩陣稀疏化的根本原因。

基于確保校驗關系得到窮舉這一目標，本文形成了矩陣稀疏化通用算法：

1) 足夠稀疏；

綜上所述，該算法為一種確定性算法，以確保重建結果存在并局部最優。算法復雜度約為，其中。

4 結 束 語

本文研究了無誤碼條件下LDPC碼稀疏校驗矩陣的重建問題。經過與一般分組碼識別問題的分析與比較，將LDPC碼識別問題等價為尋找LDPC碼碼字零化空間內某組稀疏基的數學問題，相繼設計并實現了2-階行間線性變換、-階行間線性變換、線性關系有限窮舉在內的3種矩陣稀疏化算法。以上算法均以線性變換作為工具，以非稀疏校驗矩陣的行重作為優化對象，力求實現無誤碼條件下，對適度碼長長度LDPC碼校驗矩陣的有效重建。針對包括802.16e、802.11n、DVB-S2、GJB7296在內的多種LDPC標準/協議的測試結果顯示，本文算法所重建的稀疏矩陣與真實校驗矩陣完全相同，實現了非合作條件下的等效譯碼，基本驗證了該算法的有效性。

對于難度更大的誤碼條件下LDPC碼重建問題，將在后續文章中提出相應的解決方案。

[1] VALEMBOIS A. Detection and recognition of a binary linear code[J]. Discrete Applied Mathematics, 2001, 111(1): 199-218.

Recognition of a code in a noisy environment [C]//Proceedings of IEEE International Symposium on Information Theory. Nice, USA: IEEE, 2007: 2211-2215.

[4] CLUZEAU M, TILLICH J. On the code reverse engineering problem[C]//Proceedings of IEEE International Symposium on Information Theory. Toronto, ON, USA: IEEE, 2008: 634-638.

[5] CLUZEAU M. Block code reconstruction using iterative decoding techniques[C]//Proceedings of 2006 IEEE International Symposium on Information Theory. Seattle, WA, USA: IEEE, 2006: 2269-2273.

[6] 昝俊軍．低碼率線性分組碼的盲識別[J]．無線電技術，2009, 39(1): 19-24.

ZAN Jun-jun. Blind recognition of low code-rate binary linear block codes[J]. Radio Engineering, 2009, 39(1): 19-24．

[7] 張永光．信道編碼及其識別分析[M]．北京：電子工業出版社, 2010.

ZHANG Yong-guang. Recognition and analyze the channel coding[M]. Beijing: Publishing House of Electronic Industry, 2010.

[8] 游凌, 朱中梁. Walsh函數在解二元域方程組上的應用[J]. 信號處理, 2000, 16: 27-30.

YOU Ling. The application of walsh function in resolving of GF(2) equations[J]. Signal Processing, 2000,16: 27-30.

[9] 陸佩忠.刪除卷積碼的盲識別[J].中國科學(E輯), 2005, 35(2): 173-185.

LU Pei-zhong. Blind recognition of punctured convolutional codes[J]. Science in China, Series E, 2005, 35(2): 173-185.

于沛東.一種利用軟判決的信道編碼識別新算法[J]. 電子學報, 2013 (2): 301-306.

YU Pei-dong. A norei algorithm for channei coding recognition using soft decision[J]. Acta Electronica Sinica, 2013(2): 301-306.

iori probability [C]//2012 12th International Conference on ITS Telecommunications (ITST). [S.l.]: IEEE, 2012: 12-16.

[13] 包昕. 基于軟解調序列的LDPC碼閉集識別方法[J]. 電訊技術, 2015, 55(1): 55-60.

BAO Xin. A finite set recognition algorithm of LDPC coding by using soft-demodulation sequence[J]. Telecommunication Engineering, 2015, 55(1): 55-60.

[14] LAN/MAN Standards Committee of IEEE Computer Society, IEEE Microwave Theory and Techniques Society. Draft IEEE standard for local and metropolitan area networks part 16: Air interface for fixed and mobile broadband wireless access systems amendment for physical and medium access control layers for combined fixed and mobile operation in licensed bands[S]. IEEE P802.16e. New York, USA: IEEE Standards Activities Department, 2005: 472-475.

[15] LAN/MAN Standards Committee of IEEE Computer Society. IEEE standard for information technology telecommunications and information exchange between systems-local and metropolitan area networks specific requirements part11: Wireless lan medium access control (MAC) and physical layer (PHY) specifications[S]. IEEE P802.11n. New York, USA: IEEE Standards Activities Department, 2009: 289-293.

[16] European Broadcasting Union. Digital video broadcasting (DVB): Second generation framing structure, channel coding and modulation systems for broadcasting, interactive services, news gathering and other broadband satellite applications[S]. DVB-S2. Europe: European Telecommunications Standards Institute, 2006: 21-23.

[17] 中國人民解放軍總參謀部. 軍用低密度奇偶校驗碼參數及編譯碼算法[S]. GJB-7296. 北京: 中國人民解放軍總參謀部, 2011.

The General Equipment Department of the Chinese People’s Liberation Army. Parameters and algorithm of low density parity check code for military application[S]. GJB-7296. Beijing: Chinese People’s Liberation Army Press, 2011.

[18] 中國國家標準化管理委員會. 數字電視地面廣播傳輸系統幀結構, 信道編碼和調制[S]. GB 20600-2006. 北京: 中國標準出版社, 2007.

Standardization Administration of the People's Republic of China. Digital TV terrestrial broadcasting transmission system: Frame structure, channel encoding and modulation [S]. GB 20600-2006. Beijing: China Standard Press, 2007.

[19] QIN H, DIAO Q, LIN S, et al. Cyclic and quasi-cyclic LDPC codes on constrained parity-check matrices and their trapping sets[J]. IEEE Transactions on Communications, 2012, 58(5): 2648-2671.

編 輯 黃 莘

A Method of Restructuring LDPC Parity-Check Matrix

BAO Xin, ZHOU Lei-ke, HE Ke, and YOU Ling

(Southwest Electronics and Telecommunication Technology Research Institute Chengdu 610041)

To solve the problem of restructuring sparse parity-check matrix in low-density parity-check (LDPC) recognition processing, three algorithms are proposed. Through analyzing and comparing the LDPC recognition model with the tradition coding recognition models, the former one is defined as a problem of finding a group sparse-base which spans the dual-space of the coding. Then, by making the weight of check-vector as the optimized object, the 2-order linear transformation algorithm,-order linear transformation algorithm, and linear relationship exhaustive searching algorithm are proposed to restructure sparse parity-check matrix of a LDPC code with suitable code length in an error free environment. The result of simulations show that these algorithms fit most of LDPC standards, including 802.16e, 802.11n, DVB-S2, GJB7296, GB20600 and so on.

channel coding recognition; LDPC recognition; parity-check matrix ; sparse

TN911.22

A

10.3969/j.issn.1001-0548.2016.03.006

2014 - 12 - 10；

2015 - 11 - 06

國家自然科學基金(61172140)

包昕(1986 - )，男，博士生，主要從事盲信號處理、信道編碼分析等方面的研究.