誤碼條件下的LDPC碼盲識別算法

包昕,周磊砢,何可,王桂良,游凌

(盲信號處理重點實驗室, 610041, 成都)

?

誤碼條件下的LDPC碼盲識別算法

包昕,周磊砢,何可,王桂良,游凌

(盲信號處理重點實驗室, 610041, 成都)

為解決誤碼條件下信道編碼校驗矩陣難以逆向重建的問題,提出了一種新穎的LDPC碼盲識別算法,簡稱迭代篩選(IS)算法。首先,由被截獲數據構造含錯矩陣,通過實施列消元運算獲取其對偶向量;接著,利用校驗向量判定準則從對偶向量中篩選出LDPC碼的有效校驗向量;進而再對被截獲數據中的含錯碼組進行辨識和剔除;迭代進行以上操作,不斷提高被截獲數據內無誤碼碼組的比例,直至將原問題退化為無誤碼時的簡單場景;最終使用漸進行變換算法,實現LDPC碼校驗矩陣的稀疏化。仿真和實測均顯示,IS算法對于802.16e、802.11n、DVB-S2、GJB7296、GB20600等公開標準均有效,能夠在誤碼率不高于10-4條件下的非合作場合實現LDPC碼的盲識別,LDPC碼校驗矩陣獲得了完整重建。

變換信道編碼;LDPC碼;盲識別;誤碼率

信道編碼是一種保證通信可靠性的技術手段,是現代通信系統的重要組成部分。在非合作條件下,展開對信道編碼的有效識別,具有重要的軍事意義和情報價值。信道編碼盲識別問題力求解決,如何通過含噪序列R重建編碼C,而LDPC碼盲識別問題是其子問題。

對于傳統信道編碼,Valembois證明了其盲識別問題是一種NP完全問題[1],基于此結論,相關研究成果均將快速搜索次優解作為解決問題的途徑。較有代表性的有:Cluzeau提出了一種有效的對偶碼組搜索策略[2],該策略借鑒了Canteaut提出的最小碼重搜索算法[3]和Gallager提出的置信度傳播概率譯碼思想[4];游凌利用Walsh-Hadamard變換,提高了誤碼條件下短碼校驗關系的窮舉速度[5];陸佩忠基于Gr?nber基理論,將卷積碼識別問題等價為線性移位寄存器的綜合[6]。然而,以上方法均不適用于LDPC碼識別問題。

LDPC碼是一種由校驗矩陣定義的分組碼,具有碼長長、校驗矩陣稀疏、性能逼近香農限的特點。自1995年LDPC碼被重新發現以來,人們圍繞其構造、編碼、譯碼方法展開了深入的研究,當前已應用于衛星、深空、移動、無線、光纖在內的各種通信系統,成為最具潛力的信道編碼解決方案。

然而,針對LDPC碼盲識別問題的研究成果極為有限。Cluzeau證明,足夠多的LDPC碼碼組是確保多項式時間內重建LDPC碼的充要條件[7]。文獻[8-9]通過計算后驗概率對數似然比(LLR),將實數域上的軟解調序列與LDPC碼的校驗關系聯系在一起。文獻[10]在此基礎上,形成閉集識別算法。遺憾的是,這些研究成果遠不能滿足非合作背景下LDPC碼盲識別的現實需求。

本文著重解決誤碼條件下的LDPC碼開集識別問題,嘗試綜合利用列消元運算、校驗向量判定準則及漸進行變換等方法,以發現正確校驗向量和剔除含誤碼碼組作為手段,最終將原問題成功退化為無誤碼條件下的稀疏校驗矩陣重建問題,實現了誤碼條件下的LDPC碼盲識別。

1 問題描述與分析

LDPC碼盲識別的最終目標,是實現稀疏校驗矩陣的正確重建。碼長n和碼組起點的正確識別,是該目標得以實現的基礎,文獻[11-12]以矩陣二元域上的秩作為統計判決量,重點研究了此問題?？紤]到該問題的復雜性和獨立性,本文為簡化討論和分析,假設碼長和碼組的起點已知。

在無誤碼情況下,對LDPC碼接收序列進行高斯消元,總能夠獲取碼字空間的一組基,即生成矩陣G,進而方便地獲取至少一個非稀疏校驗矩陣Hd。在此基礎上,利用足夠多次數的線性行變換運算,可最終實現稀疏校驗矩陣的正確重建。圖1給出了無誤碼條件下的盲識別流程。

圖1 無誤碼條件下的校驗矩陣重建

在誤碼條件下,由于高斯消元法對誤碼極為敏感,此時已不可能通過使用高斯消元運算獲取LDPC碼碼字空間的基。因此,需尋找新的解決思路。本文將稀疏校驗矩陣的重建問題分解為3個相對獨立的子問題:①獲得含錯碼組的正交向量;②對碼字空間C的有效校驗向量進行辨識;③稀疏化有效校驗向量。其中,問題2將在第3節中詳細討論,問題3的解決方案將在其余文章中專門討論。問題1是本文重建問題的核心。一種樸素的正交向量發現思想是,通過窮舉n維空間內的所有2n組向量,搜索滿足正交性的校驗向量。但是,無論是使用Canteaut方法、Walsh-Hadamard變換或者是借助巨型機,該思想都不現實。本文引入的k階列消元運算,將方便地解決問題1。

圖2給出了本文所提出的解決方案:首先,使用k階列消元運算,獲取含誤碼碼組的大量正交向量,稱作疑似校驗向量;接著,利用統計判定準則,從正交向量中遴選出碼字空間的有效校驗向量;然后,利用以上有效校驗向量,辨識和剔除接收序列中被發現的含誤碼碼組;迭代進行以上一系列操作,不斷提高接收序列內無誤碼碼組的比例,只要待識別碼組數量足夠多,經過有限次迭代,總能找到足夠多的有效校驗向量,同時剔除所有含誤碼碼組。此時,誤碼條件下的盲識別問題,已退化為前述無誤碼時的情況。

圖2 誤碼條件下的校驗矩陣重建方案框圖

至此,本文給出了一種誤碼條件下的LDPC碼有效盲識別方法,后續章節將對具體實現技術展開討論。

2 k階列消元運算

k階列消元運算的目標,是將任意給定的二元矩陣M,通過k步操作,變換為形如下式的下階梯型矩陣

(1)

并得到M的對偶矩陣Θ。

設M經i-1步運算后記為M(i-1),可構造形如下式的矩陣

(2)

(1)無誤碼的情況。設MN×n=mG,其中m為N×k維信息矩陣,G為C的生成矩陣,易得

(3)

若對M進行k階列消元運算,必然存在矩陣Θn×(n-k),使得0=M1Θ,即

(4)

因此,存在矩陣Θ,使得MΘ為全0陣。

(2)存在誤碼的情況。設MN×n=mG+EN×n,E為錯誤圖樣。易得

(5)

對M進行k階列消元運算,必然存在矩陣Θn×(n-k),使得0=M1Θ,即

(6)

因此

(7)

圖3給出了對M進行k階列消元后的變化結果,其中M由100組(40,25)分組碼組成?？梢?經k階列消元運算后,當M無誤碼時,MΘ為全0陣;當M存在誤碼時,MΘ前k行為全0陣,余下N-k行存在非零元素。由此,k階列消元運算一方面可用于快速獲取編碼矩陣M的正交矩陣,另一方面可方便地判定矩陣M是否存在誤碼。

(a)無誤碼 (b)誤碼率為10-4圖3 對某(40,25)分組碼的列消元處理結果

3 疑似校驗向量的判定

Gallager指出,若n維二元向量中元素為1的概率記做p,則該向量中存在偶數個1的概率為[1+(1-2p)n]/2[4]。Chabot給出了如下結論[12]。

定理1 令向量p,q∈R,且w表示q中非零元素個數,則p、q正交概率pr(〈p,q〉=0)為

(8)

式中:R⊥表示空間R的對偶空間;pb為p中非零元素的出現概率。當p表示校驗向量h、q表示含噪接收向量r時,該定理可用于判定r是否屬于碼字空間C;同理,當p表示編碼向量c、q表示任意向量h時,該定理可用于判定h是否屬于校驗空間C⊥。

(9)

式中:τ=[1-(1-2pe)w(h)]/2。

4 矩陣的稀疏化

(n,k)分組碼碼字空間C由2k個碼字c組成,可看作由2k個信息向量m通過生成矩陣G的線性表出。若G由k個n維線性無關向量組成,則G稱作碼字空間C的一組基;相似地,若校驗矩陣H由n-k個n維線性無關向量組成,由于H與(n,k)分組碼的所有2k個碼字c正交,則由H張成的空間必定與碼字空間C正交,該空間稱為C的校驗空間C⊥,H稱為C⊥的一組基。因此,恢復(n,k)分組碼的生成矩陣G,就是尋找碼字空間C的某組基;而恢復校驗矩陣H,就是尋找碼字校驗空間C⊥的某組基。

漸近行變換(gradual row transform,GRT),是一種以非稀疏檢驗矩陣行作為優化對象的矩陣稀疏化算法,能夠有效實現無誤碼條件下LDPC碼的矩陣重建。

5 誤碼條件下的盲識別算法

5.1 算法描述

前述章節依次解決了對偶向量的獲取、有效校驗向量的辨識、矩陣的稀疏化3個問題。這些問題的綜合,即為誤碼條件下的LDPC碼盲識別問題。將N個接收碼組ri,i=1,2,…,N逐行排列形成矩陣M,則盲識別算法步驟如下。

(2)采用GRT算法,獲得如下稀疏矩陣: 對M進行高斯消元獲得G; 對G使用GTT算法獲得M。

表1給出了算法復雜度分析?？梢娝惴ǖ挠嬎銖碗s度最多為O≈2Nn3+OGRT。

表1 算法復雜度分析

注:N′表示一次迭代中M的碼組個數;l表示一次迭代獲取的有效校驗向量個數;OGRT表示GRT運算級計算量。

5.2 算法測試

當前,LDPC碼已應用于衛星、深空、移動、無線、光纖在內的各種通信系統。本節僅以無線城域網IEEE 802.16e標準[13]為例展開算法測試。

例1 給定(576,288)LDPC碼,誤碼率pe=10-4時,設定碼組個數N=3k=864。測試顯示,經4次迭代運算,可獲得807組無誤碼碼組c和528組有效校驗向量h。對以上無誤碼碼組采用GRT算法,所獲得的非稀疏矩陣及重建后的稀疏矩陣分別如圖4a、圖4b所示,經與真實校驗矩陣(圖4c)比對,可確認稀疏校檢矩陣H獲得了正確重建。

(a)非稀疏校驗矩陣

(b)重建后的稀疏校驗矩陣

(c)真實校驗矩陣圖4 例1中(576,288)LDPC碼仿真情況

例2 保持碼組數N=864不變,將誤碼率提高到pe=3×10-4。此時,經6次迭代后,共獲得750組無誤碼碼組c和354組有效校驗向量h。經GRT算法處理后,所重建的矩陣如圖5所示。

經統計,該矩陣包含非零元素1 852個、4環1個、6環46個,而在圖4c所示的真實矩陣中,以上參數分別為1 824、0和24?？梢?測試中所獲取的354組有效校驗向量h還未能完整張成(576,288)編碼的對偶空間,校驗矩陣重建失敗。

圖5 例2中(576,288)LDPC碼仿真情況

例3 保持誤碼率pe=3×10-4,將碼組數提高到N=5k=1 440。經7次迭代后,共獲得1 188組無誤碼碼組c和1 152組有效校驗向量h,稀疏校驗矩陣H再次獲得重建。

表2給出了此次測試時,迭代過程的中間變量?？梢?首次迭代所獲取的有效校驗向量可以極少,隨著迭代的進行,越來越多的有效校驗向量h將被發現,越來越多的誤碼碼組將被剔除,最終,含誤碼碼組比例由最初的16.53%收斂至0%,同時有效校驗向量個數正好等于288組。

表2 例2中(576,288)LDPC碼的仿真中間變量

例4 擴大碼長,選取(1 152,864)LDPC碼,測試參數為pe=10-4,N=10k=8 640。經3次迭代運算,共獲得7 590組無誤碼碼組c和4 608組有效校驗向量h。校驗矩陣重建結果如圖6所示。

圖6 例4中(1 152,864)LDPC仿真情況

本文還對DVB-S2[14]、IEEE 802.11n[15]、GJB 7296及GB 20600[16]等標準/協議進行了測試。測試結果顯示,本文算法具備較好的通用性。

5.3 討論

由仿真可以發現,通過增加碼組數量N,在一定層度上可提高算法的容錯性能。本算法成功的關鍵是能否通過若干次k階列消元運算,湊齊足夠多的無誤碼碼組。一方面,參與算法的N個碼組中應當確實存在至少k個無誤碼碼組,即

(10)

此為N的一個松弛下限。另一方面,即使N個碼組中存在k個無誤碼碼組,能否將其發現也存在不確定性。由于一次k階列消元運算僅能獲取子矩陣Mi的n-k個正交向量,而其中并不保證存在編碼C的有效校驗向量h。將一次k階列消元運算中有效校驗向量h的產生概率稱為發現概率ph。

(11)

特別地,當ph→0時,N→∞,算法等價于失效。

(a)發現概率 (b)被發現校驗向量數圖7 不同編碼時誤碼率與發現概率和被發現校驗向量數關系的仿真曲線

至此,分別得出了算法有效時所需碼組數量N與誤碼率pe的兩種表述方法,為算法復雜度與容錯性能的折中問題提供了一定依據。

6 結 論

針對誤碼條件下的LDPC碼開集盲識別問題,本文提出了一種有效的解決方案。測試結果顯示,算法適用于包括802.16e、802.11n、DVB-S2、GJB7296、GB20600在內的多種LDPC標準/協議,實用性強。本文算法通過將原本棘手的研究對象分解為3個相對獨立的子問題,綜合利用k階列消元運算、基于統計學原理的校驗向量判定準則和漸進行變換算法,成功地將問題退化為無誤碼條件下的LDPC碼盲識別問題,最終實現了LDPC碼稀疏校驗矩陣的完整重建。特別是本文得出了利用增加碼組數量換取算法容錯性能的結論,具有一定的現實指導意義。

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

[2] CLUZEAU M. Block code reconstruction using iterative decoding techniques [C]∥Proceedings of 2006 IEEE International Symposium on Information Theory. Piscataway NJ, USA: IEEE, 2006: 2269-2273.

[3] CANTEAUT A, CHABAUD F. A new algorithm for finding minimum-weight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511 [J]. IEEE Transactions on Information Theory, 1998, 44(1): 367-378.

[4] GALLAGER R G. Low-density parity-check codes [J]. IEEE Transactions on Information Theory, 1962, 8(1): 21-28.

[5] 游凌, 朱中梁. Walsh函數在解二元域方程組上的應用 [J]. 信號處理, 2000, 16(S1): 27-30. YOU Ling, ZHU Zhongliang. The application of Walsh function in resolving of GF(2) equations [J]. Signal Processing, 2000, 16(S1): 27-30.

[6] 陸佩忠. 刪除卷積碼的盲識別 [J]. 中國科學學: E輯, 2005, 35(2): 173-185. LU Peizhong. Blind recognition of punctured convolutional codes [J]. Science in China: Series E, 2005, 35(2): 173-185.

[7] CLUZEAU M, TILLICH J. On the code reverse engineering problem [C]∥Proceedings of IEEE International Symposium on Information Theory. Piscataway, NJ, USA: IEEE, 2008: 634-638.

[8] 于沛東. 一種利用軟判決的信道編碼識別新算法 [J]. 電子學報, 2013(2): 301-306. YU Peidong. A novel algorithm for channel coding recognition using soft decision [J]. Acta Electronica Sinica, 2013(2): 301-306.

[9] XIA T. Novel blind identification of LDPC codes using average LLR of syndrome: a posteriori probability

[J]. IEEE Transactions on Signal Processing, 2014, 62: 632-640.

[10]包昕. 基于軟解調序列的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.

[11]BARBIER J. SICOT G, HOUCKE S. Algebraic approach for the reconstruction of linear and convolutional error correcting codes [J]. Proceedings of World Academy of Science Engineering & Technology, 2006, 2(3): 113-118.

[12]CHABOT C. Recognition of a code in a noisy environment [C]∥Proceedings of IEEE International Symposium on Information Theory. Piscataway, NJ, USA: IEEE, 2007: 2211-2215.

[13]LAN/MAN Standards Committee of IEEE Computer 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]. New York, USA: IEEE Standards Activities Department, 2005.

[14]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]. Geneva, Switzerland: European Telecommunications Standards Institute, 2006.

[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: Part 11 Wireless LAN medium access control (MAC) and physical layer (PHY) specifications [S]. New York, USA: IEEE Standards Activities Department, 2009.

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

(編輯 劉楊)

A Recognition Algorithm for LDPC Codes of Blind in a Noisy Environment

BAO Xin,ZHOU Leike,HE Ke,WANG Guiliang,YOU Ling

(Science and Technology on Blind Signals Processing Laboratory, Chengdu 610041, China)

A novel recognition algorithm (called iterative screening, IS) for LDPC codes of blind is proposed to solve the problem that the parity-check matrix of Channel Coding is hard to reconstruct in a noisy environment. A matrix with the intercepted data is constructed, and then dual vectors of the matrix are obtained by using column elimination operation. Effective parity-check vectors of the dual-space of the LDPC code are selected and error code blocks are recognized and deleted from the intercepted data. These steps are iteratively carried out until the original problem is reduced to a simple problem, i.e., blind recognition of some error-free codes. The sparse parity check matrix is finally obtained by using Gradual Row Transformation. Simulation and experimental results show that the IS algorithm can apply to most LDPC standards, such as 802.16e, 802.11n, DVB-S2, GJB7296 and GB20600. It is able to be used in the non-cooperative context with the bit error rate less than 10-4, and reconstructs the sparse parity check matrix of LDPC codes.

channel coding; LDPC codes; blind recognition; error bit rate

2015-04-23。

包昕(1986—),男,博士生;游凌(通信作者),男,高級工程師,博士生導師。

國家自然科學基金資助項目(61172140)。

時間:2015-10-03

10.7652/xjtuxb201512009

TN911.22

A

0253-987X(2015)12-0053-06

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20151003.1918.004.html