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

?

LDPC碼稀疏校驗(yàn)矩陣的重建方法

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

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

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

信道編碼識(shí)別; LDPC識(shí)別; 校驗(yàn)矩陣; 稀疏化

信道編碼識(shí)別即是根據(jù)解調(diào)后的比特流序列，辨識(shí)所采用的糾錯(cuò)編碼類型及其對(duì)應(yīng)參數(shù)，廣義上還包括對(duì)交織和擾碼的識(shí)別。

LDPC碼雖屬于分組碼范疇，但由于其碼長(zhǎng)往往極長(zhǎng)，構(gòu)造方法多樣且隨機(jī)，故傳統(tǒng)識(shí)別思路在可接受計(jì)算量?jī)?nèi)難以發(fā)揮作用。文獻(xiàn)[10-12]通過計(jì)算后驗(yàn)概率對(duì)數(shù)似然比(LLR)，將軟解調(diào)序列與LDPC碼校驗(yàn)關(guān)系聯(lián)系在一起。文獻(xiàn)[13]在前者基礎(chǔ)上，進(jìn)一步完善了約束關(guān)系模型，推導(dǎo)并量化了相應(yīng)統(tǒng)計(jì)學(xué)特征。

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

1 問題描述與分析

1.1 一般線性分組碼識(shí)別問題

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

綜上，這種以恢復(fù)或測(cè)量碼字空間的基為目標(biāo)、獲得編碼生成矩陣或校驗(yàn)矩陣的編碼識(shí)別思路，是幾乎所有編碼識(shí)別方法的理論基礎(chǔ)。

1.2 LDPC碼的識(shí)別

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

然而，LDPC碼的識(shí)別工作則相對(duì)不同。LDPC碼稀疏校驗(yàn)矩陣的結(jié)構(gòu)對(duì)該碼譯碼性能具有決定性的影響?；谥眯哦葌鞑サ腂P算法是LDPC碼的常用譯碼算法，它建立在節(jié)點(diǎn)間信息傳遞具備統(tǒng)計(jì)獨(dú)立性這一基本假設(shè)上。若所對(duì)應(yīng)Tanner圖中存在短環(huán)，則某一節(jié)點(diǎn)發(fā)出的信息經(jīng)過短環(huán)傳遞回自身，則將破壞該統(tǒng)計(jì)獨(dú)立性假設(shè)，進(jìn)而影響譯碼性能。因此，LDPC碼在構(gòu)造稀疏校驗(yàn)矩陣時(shí)，總是力求減少甚至完全規(guī)避短環(huán)。

因此，直接按1.1節(jié)所述方法獲取的校驗(yàn)矩往往不可能取得好的譯碼效果。以IEEE 802.16e的(576,288) LDPC碼為例，圖1a所示為標(biāo)準(zhǔn)中所定義的具備準(zhǔn)循環(huán)結(jié)構(gòu)的真實(shí)校驗(yàn)矩陣，圖1b所示為根據(jù)式(2)所得的具備結(jié)構(gòu)的等價(jià)校驗(yàn)矩陣。

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

2 矩陣的稀疏化

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

5) 返回步驟1)。

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

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

最終的稀疏化結(jié)果如圖3所示。由圖可見，其與圖1a所示的真實(shí)校驗(yàn)矩陣是等價(jià)的，算法成功。

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

2.2 仿真測(cè)試

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

圖4針對(duì)IEEE 802.16e標(biāo)準(zhǔn)進(jìn)行，參數(shù)(2 112, 1 056)。圖4a為待稀疏校驗(yàn)矩陣，圖4b為稀疏化后的結(jié)果。由圖可見，稀疏化后校驗(yàn)矩陣已具備明顯的準(zhǔn)循環(huán)結(jié)構(gòu)，經(jīng)比對(duì)，與標(biāo)準(zhǔn)中描述的真實(shí)校驗(yàn)矩陣完全相同。

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

圖6描述了針對(duì)GJB 7296-2011標(biāo)準(zhǔn)的試驗(yàn)情況。編碼參數(shù)(992,744)，該系列LDPC碼由清華大學(xué)設(shè)計(jì)，已成功應(yīng)用于嫦娥探月工程。圖6b為稀疏化結(jié)果，與真實(shí)矩陣完全一致。

以上3種LDPC標(biāo)準(zhǔn)，均屬于準(zhǔn)循環(huán)LDPC結(jié)構(gòu)(QC, Quasi-Cyclic)，前兩種的擴(kuò)展矩陣由單位陣循環(huán)移位形成，后一種的擴(kuò)展矩陣被定義為一個(gè)基于伽羅華域的偽隨機(jī)交織陣。

DVB-S2的校驗(yàn)矩陣采用了另一種結(jié)構(gòu)化設(shè)計(jì)思路。其左側(cè)為若干帶狀化矩陣，可在碼長(zhǎng)極長(zhǎng)的同時(shí)控制存儲(chǔ)量，編碼效率也獲得提高。圖7針對(duì)DVB-S2標(biāo)準(zhǔn)中(16 200,14 400)LDPC短碼進(jìn)行仿真，圖7b的稀疏結(jié)果呈現(xiàn)明顯的帶狀形態(tài)，非零元素比由最初的降為，經(jīng)與真實(shí)矩陣比對(duì)后證實(shí)完全相同。

對(duì)于采用隨機(jī)構(gòu)造方式產(chǎn)生的LDPC碼，本文選擇了某商用衛(wèi)星LDPC編碼進(jìn)行算法試驗(yàn)，結(jié)果如圖8所示。該矩陣右側(cè)保持雙對(duì)角形式，左側(cè)非零元素位置隨機(jī)分布。經(jīng)算法處理后，非零元素個(gè)數(shù)僅占，四環(huán)個(gè)數(shù)為0，可見本文的算法依然有效。

3 矩陣重建問題的解決

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

更為全面的測(cè)試顯示，前述算法在某些應(yīng)用場(chǎng)合可能失效。

圖9給出了GB20600[19]中編碼參數(shù)為(7 493, 6 096)的LDPC碼校驗(yàn)矩陣。該標(biāo)準(zhǔn)采用信息后置設(shè)定，構(gòu)造方法雖屬于QC結(jié)構(gòu)(擴(kuò)展因子127 bit)，但與以往明顯不同的是，左側(cè)規(guī)模為的校驗(yàn)區(qū)，并非由每行2個(gè)的單位陣組成雙對(duì)角結(jié)構(gòu)，而是由每行4個(gè)的循環(huán)移位陣組成不規(guī)則的4對(duì)角結(jié)構(gòu)。

反觀圖9所示的GB20600校驗(yàn)矩陣，其校驗(yàn)區(qū)方陣為不規(guī)則4對(duì)角，若利用原有算法，的確難以實(shí)現(xiàn)矩陣恢復(fù)。將原2-階行間線性變換，拓展為-階行間線性變換，形成如下-階行間線性變換算法。

6) 回到步驟2)。

7) 回到步驟1)。

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

3.2 線性關(guān)系有限窮舉算法

前述兩種算法均可以從一定程度上，實(shí)現(xiàn)LDPC碼的校驗(yàn)矩陣重建。前者基于2-階行間線性變換這一手段，適用于采用雙對(duì)角結(jié)構(gòu)的LDPC碼；后者是對(duì)前者的加強(qiáng)，將運(yùn)算規(guī)則拓展為-階行間線性變換，但仍未徹底解決稀疏校驗(yàn)矩陣的重建問題。

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

基于確保校驗(yàn)關(guān)系得到窮舉這一目標(biāo)，本文形成了矩陣稀疏化通用算法：

1) 足夠稀疏；

綜上所述，該算法為一種確定性算法，以確保重建結(jié)果存在并局部最優(yōu)。算法復(fù)雜度約為，其中。

4 結(jié) 束 語

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

對(duì)于難度更大的誤碼條件下LDPC碼重建問題，將在后續(xù)文章中提出相應(yīng)的解決方案。

[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] 昝俊軍．低碼率線性分組碼的盲識(shí)別[J]．無線電技術(shù)，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] 張永光．信道編碼及其識(shí)別分析[M]．北京：電子工業(yè)出版社, 2010.

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

[8] 游凌, 朱中梁. Walsh函數(shù)在解二元域方程組上的應(yīng)用[J]. 信號(hào)處理, 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] 陸佩忠.刪除卷積碼的盲識(shí)別[J].中國(guó)科學(xué)(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.

于沛東.一種利用軟判決的信道編碼識(shí)別新算法[J]. 電子學(xué)報(bào), 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] 包昕. 基于軟解調(diào)序列的LDPC碼閉集識(shí)別方法[J]. 電訊技術(shù), 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] 中國(guó)人民解放軍總參謀部. 軍用低密度奇偶校驗(yàn)碼參數(shù)及編譯碼算法[S]. GJB-7296. 北京: 中國(guó)人民解放軍總參謀部, 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] 中國(guó)國(guó)家標(biāo)準(zhǔn)化管理委員會(huì). 數(shù)字電視地面廣播傳輸系統(tǒng)幀結(jié)構(gòu), 信道編碼和調(diào)制[S]. GB 20600-2006. 北京: 中國(guó)標(biāo)準(zhǔn)出版社, 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

國(guó)家自然科學(xué)基金(61172140)

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