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

(盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室, 610041, 成都)

?

誤碼條件下的LDPC碼盲識(shí)別算法

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

(盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室, 610041, 成都)

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

變換信道編碼;LDPC碼;盲識(shí)別;誤碼率

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

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

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

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

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

1 問題描述與分析

LDPC碼盲識(shí)別的最終目標(biāo),是實(shí)現(xiàn)稀疏校驗(yàn)矩陣的正確重建。碼長n和碼組起點(diǎn)的正確識(shí)別,是該目標(biāo)得以實(shí)現(xiàn)的基礎(chǔ),文獻(xiàn)[11-12]以矩陣二元域上的秩作為統(tǒng)計(jì)判決量,重點(diǎn)研究了此問題?？紤]到該問題的復(fù)雜性和獨(dú)立性,本文為簡化討論和分析,假設(shè)碼長和碼組的起點(diǎn)已知。

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

圖1 無誤碼條件下的校驗(yàn)矩陣重建

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

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

圖2 誤碼條件下的校驗(yàn)矩陣重建方案框圖

至此,本文給出了一種誤碼條件下的LDPC碼有效盲識(shí)別方法,后續(xù)章節(jié)將對具體實(shí)現(xiàn)技術(shù)展開討論。

2 k階列消元運(yùn)算

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

(1)

并得到M的對偶矩陣Θ。

設(shè)M經(jīng)i-1步運(yùn)算后記為M(i-1),可構(gòu)造形如下式的矩陣

(2)

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

(3)

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

(4)

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

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

(5)

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

(6)

因此

(7)

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

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

3 疑似校驗(yàn)向量的判定

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

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

(8)

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

(9)

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

4 矩陣的稀疏化

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

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

5 誤碼條件下的盲識(shí)別算法

5.1 算法描述

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

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

表1給出了算法復(fù)雜度分析?？梢娝惴ǖ挠?jì)算復(fù)雜度最多為O≈2Nn3+OGRT。

表1 算法復(fù)雜度分析

注:N′表示一次迭代中M的碼組個(gè)數(shù);l表示一次迭代獲取的有效校驗(yàn)向量個(gè)數(shù);OGRT表示GRT運(yùn)算級(jí)計(jì)算量。

5.2 算法測試

當(dāng)前,LDPC碼已應(yīng)用于衛(wèi)星、深空、移動(dòng)、無線、光纖在內(nèi)的各種通信系統(tǒng)。本節(jié)僅以無線城域網(wǎng)IEEE 802.16e標(biāo)準(zhǔn)[13]為例展開算法測試。

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

(a)非稀疏校驗(yàn)矩陣

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

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

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

經(jīng)統(tǒng)計(jì),該矩陣包含非零元素1 852個(gè)、4環(huán)1個(gè)、6環(huán)46個(gè),而在圖4c所示的真實(shí)矩陣中,以上參數(shù)分別為1 824、0和24。可見,測試中所獲取的354組有效校驗(yàn)向量h還未能完整張成(576,288)編碼的對偶空間,校驗(yàn)矩陣重建失敗。

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

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

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

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

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

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

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

5.3 討論

由仿真可以發(fā)現(xiàn),通過增加碼組數(shù)量N,在一定層度上可提高算法的容錯(cuò)性能。本算法成功的關(guān)鍵是能否通過若干次k階列消元運(yùn)算,湊齊足夠多的無誤碼碼組。一方面,參與算法的N個(gè)碼組中應(yīng)當(dāng)確實(shí)存在至少k個(gè)無誤碼碼組,即

(10)

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

(11)

特別地,當(dāng)ph→0時(shí),N→∞,算法等價(jià)于失效。

(a)發(fā)現(xiàn)概率 (b)被發(fā)現(xiàn)校驗(yàn)向量數(shù)圖7 不同編碼時(shí)誤碼率與發(fā)現(xiàn)概率和被發(fā)現(xiàn)校驗(yàn)向量數(shù)關(guān)系的仿真曲線

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

6 結(jié) 論

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

[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函數(shù)在解二元域方程組上的應(yīng)用 [J]. 信號(hào)處理, 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] 陸佩忠. 刪除卷積碼的盲識(shí)別 [J]. 中國科學(xué)學(xué): 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] 于沛東. 一種利用軟判決的信道編碼識(shí)別新算法 [J]. 電子學(xué)報(bào), 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]包昕. 基于軟解調(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.

[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]中國國家標(biāo)準(zhǔn)化管理委員會(huì). 數(shù)字電視地面廣播傳輸系統(tǒng)幀結(jié)構(gòu), 信道編碼和調(diào)制 [S]. 北京: 中國標(biāo)準(zhǔn)出版社, 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—),男,博士生;游凌(通信作者),男,高級(jí)工程師,博士生導(dǎo)師。

國家自然科學(xué)基金資助項(xiàng)目(61172140)。

時(shí)間:2015-10-03

10.7652/xjtuxb201512009

TN911.22

A

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

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20151003.1918.004.html