基于線性約束關(guān)系的LDPC碼校驗矩陣盲識別算法

羅路為，雷迎科

(國防科技大學(xué)電子對抗學(xué)院，安徽 合肥 230017)

0 引言

近年來，在非合作信號處理領(lǐng)域，信道編碼識別分析成為一個新的研究熱點，其在智能通信、信息截獲和信息對抗等領(lǐng)域，有越來越廣泛的應(yīng)用[1]。在智能通信中已經(jīng)廣泛采用了自適應(yīng)調(diào)制編碼技術(shù)(AMC)。自適應(yīng)調(diào)制編碼能夠根據(jù)信道質(zhì)量的改變情況，隨時改變信道編碼的方式，使其獲得最佳的通信效率和服務(wù)質(zhì)量。然而在實際情況中，由于在傳輸過程中會受時延、干擾、中斷等因素的影響，有時候發(fā)送方不能正確或地準時將相關(guān)控制信息傳送到接收端，從而無法建立通信[2]。這時就需要接收方僅僅由接收的未知數(shù)據(jù)快速識別出信道編碼的體制、參數(shù)，以達到智能通信的目的。在各類信道編碼方式中，LDPC碼因其具有接近香農(nóng)極限的糾錯性能，以及譯碼簡單譯碼錯誤可檢測等優(yōu)異性能，十分有利于高速信息傳輸，從而成為了信道編碼理論新的研究熱[3]。在下一代5G通信系統(tǒng)中，由于LDPC碼較強的糾錯性能，可以較好地實現(xiàn)協(xié)作中繼傳輸和多小區(qū)協(xié)作傳輸，這對LDPC碼盲識別算法的研究提出了迫切的需求[4]。

然而，對于LDPC碼校驗矩陣的盲識別的研究成果相對較少。Cluzeau通過的理論和實驗證明，重建LDPC碼必須有充分的LDPC碼組[5]。包昕等人充分利用后驗概率對數(shù)似然比，建立軟解調(diào)序列與LDPC碼的校驗矩陣之間的映射關(guān)系，實現(xiàn)對LDPC碼的盲識別[6]。而文獻[7]結(jié)合信道輸出的軟判決接收序列，依次搜索信道編碼集合里的全部碼長和碼率，把伴隨式Hamming重量最小的參數(shù)組合作為識別結(jié)果，但是這種方法需要接收序列中有足夠長的無誤碼序列。這些研究成果大都需要較高的信噪比條件，對于誤碼條件下的LDPC碼盲識別，還不能達到較為理想的識別效果。本文針對誤碼條件下LDPC碼校驗矩陣難以逆向構(gòu)造的問題，提出了基于線性約束關(guān)系的LDPC碼盲識別算法。

1 問題描述

LDPC的盲識別包括其碼長、碼率、校驗矩陣等相關(guān)參數(shù)的識別。每一種LDPC碼都有唯一對應(yīng)的校驗矩陣。對LDPC碼進行盲識別的終極目標就是要實現(xiàn)其校驗矩陣的正確重建。文獻[6]在無誤碼的情況下，采用高斯消元法對LDPC碼的校驗矩陣進行了盲識別。整個盲識別過程如圖1所示。首先對LDPC碼接收序列進行高斯消元，得到生成矩陣G，然后利用LDPC碼校驗矩陣的特性，獲取得非稀疏校驗矩陣Hd。最后，利用足夠的數(shù)據(jù)，進行線性行變換，實現(xiàn)了無誤碼條件下LDPC碼校驗矩陣的識別。然而，在誤碼條件下，進行高斯消元運算，會把錯誤進行傳播和放大[8]。想通過高斯消元獲取碼字空間的基已經(jīng)變成不可能。只能尋求新的解決辦法。本文針對在誤碼條件下，將LDPC碼校驗矩陣的盲識別問題分解為相對獨立的三個步驟：第一步：利用含錯碼組，求解其正交向量；第二步：通過校驗關(guān)系準則，提取碼字空間C的校驗向量；第三步：對有效校驗向量進行稀疏化處理。對于第一步的處理，傳統(tǒng)的線性分組碼是利用n維空間的向量進行Walsh-Hadamard變換，或者利用高速計算機進行校驗方程的求解，尋找滿足正交性的校驗向量[9]。但是，LDPC碼碼長通常較長，而且校驗矩陣十分稀疏，傳統(tǒng)的方法都不能很好的用于LDPC碼。本文通過線性約束關(guān)系，采用k階列消元，實現(xiàn)對含錯碼正交向量的求解。

圖2是針對在誤碼條件下所提出LDPC校驗矩陣的盲識別方案：首先對含錯碼編碼矩陣進行列消元運算，求解其正交向量，求解結(jié)果可當(dāng)作疑似校驗向量。其次，通過校驗關(guān)系的判定準則，提取碼字空間C的有效校驗向量，同時剔除掉大量的含錯碼組。然后對有效校驗向量進行稀疏化處理。對上述步驟進行迭代，不斷剔除被截獲數(shù)據(jù)中的誤碼碼組，提高無誤碼碼組的比例。若干次迭代后，我們能夠獲取足夠的有效校驗向量。此時，就能夠?qū)⒄`碼條件變相地轉(zhuǎn)化為無誤碼條件，就能實現(xiàn)了LDPC碼校驗矩陣的盲識別。

圖1 在無誤碼時的校驗矩陣重建過程Fig.1 Reconstruction of check matrix without error

圖2 本文LDPC校驗矩陣的盲識別方案Fig.2 Blind recognition method of LDPC check matrix in this paper

綜上所述，本文提出了一種基于線性約束關(guān)系的誤碼條件下LDPC碼盲識別方案，下面對針對此問題進行分析討論。

2 基于線性約束關(guān)系的LDPC碼校驗矩陣盲識別算法

基于線性約束關(guān)系的LDPC碼校驗矩陣的盲識別算法分為三步。第一步：利用LDPC碼校驗矩陣的線性約束關(guān)系，對接收矩陣進行k階列消元，獲取校驗向量空間。第二步：利用校驗關(guān)系約束準則，對校驗向量空間中的疑似校驗向量進行判定，獲取有效的校驗向量。第三步：利用漸近行變換對有效的校驗向量進行稀疏化，獲取LDPC碼的稀疏校驗向量。

2.1 接收矩陣的k階列消元

通過k階列消元，我們可以將二元矩陣M，變換成如式(1)的下階梯型矩陣[10]，這個過程只需要k步操作。

(1)

而且，還可以得到M的對偶矩陣Θ。假設(shè)M經(jīng)過i-1步運算后，記為M(i-1)，可以構(gòu)造形如式(2)的矩陣

(2)

并計算M(i)=M(i-1)Ψ(i)。經(jīng)過k步運算后，最終，M(k)能變換為如式(1)的下階梯形矩陣。設(shè)Ψ(1)Ψ(2)…Ψ(k)=Γn×kΘn×(n-k)，這時矩陣M的對偶矩陣就是矩陣Θ。

1) 若無誤碼。設(shè)MN×n=mG，其中m為信息矩陣，維度是N-k維，C的生成矩陣是G，易得：

(3)

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

(4)

因此，存在這樣的矩陣Θ，可使得MΘ為全0陣[11]。

2) 若有誤碼。設(shè)MN×n=mG+EN×n，其中E是錯誤圖樣。可得：

(5)

如果對M采取k階列消元運算，則存在這樣的矩陣Θn×(n-k)，使得0=M1Θ，即：

(6)

因此：

(7)

由上述分析可知，經(jīng)k階列消元運算后，如果M無誤碼，MΘ為全0陣；如果M有誤碼，MΘ前k行為全0陣，而在剩下的N-k行中會有非零元素。由此可以說明，通過對含錯碼組進行k階列消元運算，我們不僅僅可以獲得編碼矩陣M的校驗矩陣，而且能夠判斷矩陣M中有沒有誤碼存在。

2.2 判定疑似校驗向量

Gallager定理表明[12]，設(shè)p是n維二元向量中元素1的概率，則該向量中存在偶數(shù)個1的概率為(1+(1-2p)n)/2。同時，Chabot又提出了如下定理[12]：

定理1：令向量p，q∈R，且w表示q中非零元素個數(shù)，則p，q正交概率pr為：

(8)

式(8)中，p中出現(xiàn)非零元素的概率記為pb，R⊥則表示R的對偶空間。利用定理1，我們可以用q來表示任意向量h，用p表示編碼向量c時，則通過式(8)能夠判定h是否屬于校驗空間C⊥，而當(dāng)我們用q來表示誤碼碼組r，用p來表示校驗向量h，則可用于判斷r是否屬于碼字空間C。

(9)

2.3 進行矩陣稀疏化

在獲取足夠的有效校驗向量后，需要對組成的非稀疏校驗矩陣進行稀疏化處理，來獲得所需的LDPC碼稀疏校驗矩陣。參考文獻[6]是通過漸近行變換算法對非稀疏檢驗矩陣進行稀疏化處理。漸近行變換(Gradual Row Transform，GRT)是對非稀疏檢驗矩陣進行優(yōu)化的矩陣稀疏化算法。該算法是使用線性行變換的手段，用非稀疏矩陣的行重W作為稀疏化度量，將原本非稀疏校驗矩陣Hd在有限次運算后轉(zhuǎn)變?yōu)橄∈栊ｒ灳仃嘓s。該稀疏校驗矩陣將以某種準則近似等價于真實的LDPC校驗矩陣H。

2.4 算法的步驟

通過前面幾節(jié)，我們能夠獲取對偶向量，進行有效校驗向量的識別以及對非稀疏校驗矩陣進行稀疏化，綜合這三個步驟我們將誤碼條件退化為無誤碼條件，從而將盲識別問題轉(zhuǎn)化為校驗矩陣的重新構(gòu)造問題。進而實現(xiàn)了誤碼條件下LDPC碼校驗矩陣的盲識別。下面對整個算法的步驟進行歸納。

1)由接收誤碼碼組ri,i=1,2,…,N構(gòu)造矩陣M；

3)采用漸近行變換算法，獲取稀疏陣：首先對M進行高斯消元處理，得到G，然后對G進行漸近行變換又獲得M；

4)迭代，獲取足夠多的正確碼組：fori∈{1,|M|}，如果〈ri,h〉≠0,h∈Θ，則M=M/ri。

2.5 算法計算量分析

結(jié)合以上步驟，對算法的運算量進行分析。k階列消元運算時的計算量為：k2n2≈n4。在判定疑似校驗向量，需要獲取有效地校驗向量，此時的計算量為(n-k)N'n2

3 仿真與分析

通過上文的分析討論，本節(jié)利用Matlab軟件進行仿真實驗，以無線城域網(wǎng)IEEE802.11n標準為例對算法進行測試分析。

實驗1：對于誤碼率為pe=10-4的(648,324)LDPC碼，我們設(shè)定碼組的個數(shù)為N=3k=972。實驗結(jié)果顯示，4次迭代運算后，本文算法能夠得到916組無誤碼碼組c和603組有效校驗向量h。圖3是采用文獻[6]的方法獲取的校驗矩陣。圖4是本文算法獲取的。圖5是發(fā)送方所使用的真實校驗矩陣。

從實驗1的結(jié)果可以看出，在誤碼條件下，文獻[6]的算法重建的校驗矩陣與發(fā)送方所使用的校驗矩陣相差甚遠，重建失敗。而本文的算法可以較好地實現(xiàn)誤碼條件下LDPC碼校驗矩陣的重建工作，本文算法重建的校驗矩陣與真實校驗矩陣的相似度高達98%以上。

圖3 文獻[6]算法的獲取的校驗矩陣Fig.3 Check matrix of algorithms in[6]

圖4 本文算法重建的稀疏矩陣Fig.4 The sparse matrix reconstructed by the algorithm in this paper

圖5 真實的校驗矩陣Fig.5 True check matrix

實驗2：碼組數(shù)仍是N=972，我們將誤碼率提高到pe=3×10-4。實驗結(jié)果顯示，在經(jīng)6次迭代后，本算法能夠獲得860組無誤碼碼組c和554組有效校驗向量h。經(jīng)漸近行變換算法處理后，得到如圖6所示的稀疏校驗矩陣。

在對圖6的矩陣進行統(tǒng)計后發(fā)現(xiàn)，所獲矩陣中有非零元素1 942個、4環(huán)0個、6環(huán)32個，與真實矩陣的相似度為98%，稀疏校驗矩陣重建成功。實驗2進一步說明了本文算法較好的抗誤碼性能。

圖6 提高誤碼率后重建的矩陣Fig.6 Matrix reconstructed after increasing bit error rate

實驗3：保持誤碼率pe=3×10-4，將碼組數(shù)提高到N=3k=972。實驗結(jié)果顯示，經(jīng)7次迭代后，能夠獲得1 239組無誤碼碼組c和1 186組有效校驗向量h。說明通過算法該LDPC碼的校驗矩陣H獲得重建。在此時實驗過程中，我們對迭代過程中的中間變量進行了記錄，結(jié)果如表1所示。從表1中可以看出，開始含誤碼碼組的比例較高，第一次迭代得到的有效校驗向量也非常少，然而，隨著迭代次數(shù)的增加，所獲得的有效校驗向量也越來越多，誤碼碼組也逐漸被剔除。迭代完成后，可以得到編碼所需的324組有效校驗向量，誤碼碼組比例由開始的17.12%慢慢收斂至0%。

表1 實驗3中(648,324)LDPC碼的仿真中間變量Tab.1 Intermediate variables for simulation of (648, 324) LDPC codes in Experiment 3

實驗4：擴大碼長，選取誤碼率為pe=3×10-4的(1 924,481)LDPC碼。經(jīng)4次迭代后，實驗結(jié)果顯示，能夠獲得共獲得8 376組無誤碼碼組c和3 021組有效校驗向量h。圖7給出了本次實驗所重建的稀疏校驗矩陣。

圖7 校驗矩陣的重建結(jié)果Fig.7 Reconstruction of check matrix

通過實驗3和實驗4可知，通過不斷的迭代處理，可以不斷提高無誤碼碼組的比例，而且，通過增加碼組數(shù)量N，在一定程度上可提高算法的容錯性能。利用本文算法，可以較好地實現(xiàn)誤碼條件下的LDPC碼校驗矩陣的正確重建。

實驗5：為進一步驗證本文算法的性能，利用識別出的校驗矩陣對LDPC碼進行譯碼分析。都采用常規(guī)的最小和BP譯碼算法。圖8給出了本文算法與文獻[6]算法的譯碼增益性能比較。

圖8 本文算法與文獻[6]算法譯碼增益對比Fig.8 Comparisons of decoding gains between the algorithm and the reference [6] algorithm

4 結(jié)論

本文提出了基于線性約束關(guān)系的LDPC碼校驗矩陣的盲識別算法。該算法利用LDPC碼校驗向量的線性約束準則，將原誤碼條件下盲識別問題，退化為無誤碼條件下的線性約束關(guān)系重建問題，而且通過對有效校驗向量的迭代，有效地提高了算法的抗誤碼性能。仿真實驗結(jié)果表明，本文所提算法在IEEE802.11n標準中有較好的識別效果。在誤碼率不高于10-4非合作條件下，利用本文算法，接收方可以重建發(fā)送方所使用的校驗矩陣。而且相對于已有算法，本文算法的抗誤碼性能獲取了較大提高。