高誤碼率下LDPC 稀疏校驗矩陣重建

吳昭軍，張立民，鐘兆根，劉仁鑫

（1.海軍航空大學(xué)航空作戰(zhàn)勤務(wù)學(xué)院，山東 煙臺 264001；2.海軍航空大學(xué)航空基礎(chǔ)學(xué)院，山東 煙臺 264001）

1 引言

為了對抗信道中噪聲的干擾，數(shù)字通信系統(tǒng)中廣泛采用信道編碼技術(shù)。受Turbo 碼迭代譯碼思想的啟發(fā)，LDPC（low density parity check code）被再次發(fā)現(xiàn)，目前，已經(jīng)被廣泛應(yīng)用于如IEEE 802.11、DVB-S2 等數(shù)據(jù)傳輸協(xié)議中。從非合作通信方的角度，研究高誤碼率條件下LDPC 稀疏校驗矩陣的重建，對于目前大量采用LDPC 編碼的通信協(xié)議逆向分析具有非常重要的意義。

目前，針對信道編碼參數(shù)識別的研究主要集中于分組碼[1-2]、卷積碼[3]以及Turbo 碼[4-7]等，而對LDPC 參數(shù)識別的文獻(xiàn)較少。同時，在有誤碼條件下LDPC 稀疏校驗矩陣的重建問題一直是一個難點，主要原因在于LDPC 的碼長較長，在有誤碼條件下，目前針對信道編碼識別的算法，如矩陣分析[8]、Walsh-Hadarmd 變換[9]等往往失效。從已發(fā)表的論文來看，LDPC 的重建分為閉集識別和開集識別。針對LDPC 的閉集識別，文獻(xiàn)[10-11]引入了對數(shù)似然比（LLR,log-likelihood ratio）的概念，將LDPC閉集識別問題等價于LLR 的優(yōu)勢統(tǒng)計問題，即遍歷閉集中可能的LDPC 稀疏校驗矩陣，求解出對應(yīng)于LLR 值最大的稀疏校驗矩陣，從而完成識別。為了提高算法的實時性，文獻(xiàn)[12]詳細(xì)分析了LLR 的統(tǒng)計特性，基于最小錯誤判決準(zhǔn)則設(shè)定最優(yōu)門限，快速完成閉集中LDPC 識別，但文獻(xiàn)[12]為了簡化計算，在計算LLR 時進(jìn)行了近似處理，使在低信噪比下基于LLR 的識別算法性能變差。針對該問題，文獻(xiàn)[13]提出了基于余弦符合度的識別方法，該方法計算比較簡便，同時未采用近似處理，在低信噪比下性能明顯優(yōu)于基于LLR 的算法。雖然文獻(xiàn)[10-13]能夠在低信噪比下完成LDPC 識別，但是這種識別的前提條件是已知幾類稀疏校驗矩陣，嚴(yán)格來說這不是真正的盲識別，在某些微波通信或是短波通信系統(tǒng)中，通信協(xié)議往往是人為設(shè)定的，對于非合作方而言，幾乎沒有先驗信息，故LDPC 的開集識別更具實用性，同時也更具挑戰(zhàn)性。文獻(xiàn)[14]最先研究LDPC 開集識別問題，首先利用截獲的數(shù)據(jù)構(gòu)造碼字矩陣，然后采用高斯消元方法得到校驗向量，同時利用校驗向量對誤碼碼字進(jìn)行篩選和剔除，該方法雖然具有一定的容錯性，但是在有誤碼條件下所需數(shù)據(jù)量較大，同時獲得的校驗矩陣是非稀疏的，無法用來譯碼。為了獲得稀疏校驗向量，文獻(xiàn)[15]提出了基于2 階行消元和P階行消元變換的校驗矩陣稀疏化算法，該算法針對雙對角線形式的稀疏矩陣具有較好的實用性，但是對于非雙對角線形式的稀疏矩陣，其消元的階次較高，計算復(fù)雜度會急劇增大。為了克服文獻(xiàn)[15]的缺點，文獻(xiàn)[16]提出基于Canteaut-Chabaud 算法[17]的隨機(jī)稀疏化方法，該方法的通用性較好，對于非雙對角線形式的稀疏校驗矩陣也能較好地重建，但是該方法需要多次的迭代消元，在稀疏化過程中具有一定的盲目性，這使方法的計算復(fù)雜度較高。文獻(xiàn)[18]從提高LDPC 校驗矩陣重建性能出發(fā)，引入了LDPC 反饋迭代譯碼方法，利用重建的部分稀疏校驗向量對LDPC 譯碼糾錯，從而改善獲取的碼字質(zhì)量，較好地提升了算法的性能，但是該算法需要反復(fù)進(jìn)行高斯消元、稀疏化以及迭代譯碼，導(dǎo)致其計算復(fù)雜度很高。從目前LDPC 研究現(xiàn)狀來看，開集識別仍然是一個棘手的問題，還需要進(jìn)一步從計算復(fù)雜和容錯性能2 個方面改進(jìn)。

基于此，本文提出了一種新的LDPC 稀疏矩陣重建方法，該方法首先多次隨機(jī)抽取碼字中部分比特進(jìn)行高斯消元，當(dāng)隨機(jī)抽取的比特位包含稀疏校驗向量的校驗位時，消元后的結(jié)果張成的空間中一定包含稀疏校驗向量，從而完成稀疏校驗向量的獲取；其次，為了使隨機(jī)抽取過程中可靠出現(xiàn)抽取的位包含稀疏校驗向量校驗位，分析了一次隨機(jī)抽取包含校驗位的概率，得到了最小抽取次數(shù)；最后，詳細(xì)分析了有誤碼條件下疑似稀疏校驗向量的統(tǒng)計規(guī)律，基于最小錯誤判決準(zhǔn)則，實現(xiàn)了LDPC稀疏校驗向量的判定，最終完成稀疏校驗矩陣的重建。

2 LDPC 原理以及重建問題描述

LDPC 是由稀疏校驗矩陣來定義的。1962 年，Gallager 通過稀疏校驗矩陣的特性定義了LDPC；Tanner 在稀疏校驗矩陣的基礎(chǔ)上結(jié)合圖論提出了LDPC 因子圖描述方法。下面，給出稀疏校驗矩陣以及LDPC 的定義。

定義1[19]一個線性分組碼的監(jiān)督矩陣中元素“1”的個數(shù)占總元素個數(shù)的比例非常小，則這個監(jiān)督矩陣被稱為稀疏校驗矩陣，這個線性分組碼被稱為LDPC。

對于一個維度為(n-k)×n的LDPC 稀疏校驗矩陣H，通過初等行變換方式，可將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，即

其中，I(n-k)×(n-k)為(n-k) × (n-k)維的單位矩陣。由標(biāo)準(zhǔn)形式的校驗矩陣，可得到LDPC 的生成矩陣為

其中，Ik×k為k×k維的單位矩陣，矩陣PT為P的轉(zhuǎn)置。

將待編碼的信息序列按照kbit 分成一組，然后與G相乘，即可得到LDPC 的碼字。在目前的通信系統(tǒng)中，每一幀數(shù)據(jù)都有固定的同步碼，利用同步碼可以快速完成LDPC 的碼長以及碼字起點的識別，所以LDPC 識別的重點是在有誤碼的條件下利用截獲的碼字序列重建出LDPC 的稀疏校驗矩陣H。

3 傳統(tǒng)重建算法的缺陷

傳統(tǒng)的LDPC 稀疏校驗矩陣重建主要分為兩步，即非稀疏校驗矩陣的獲取[14]和校驗矩陣稀疏化處理[15]，其中非稀疏校驗矩陣的獲取是校驗矩陣稀疏化處理的前提。傳統(tǒng)方法將整個LDPC 的碼字進(jìn)行高斯消元，然后得到非稀疏的校驗向量，不妨設(shè)LDPC 的碼長為n，截獲到的序列長度為l，構(gòu)造的碼字矩陣為A，即

設(shè)在高斯消元過程中，A的初等行變換矩陣為RN×N，初等列變換矩陣為Sn×n，則經(jīng)過初等行變換以及初等列變換后，矩陣A變?yōu)?/p>

其中，0k′×(n-k′)為k′× (n-k′)維的全零矩陣。

設(shè)列變換矩陣Sn×n=[s1,s2,…,sn]，其中si(1≤i≤n)為Sn×n的列向量，在無誤碼條件下，式(4)中k′=k，此時列向量s k+1,sk+2,…,sn正好構(gòu)成LDPC 非稀疏校驗矩陣，同時D(N-k′)×(n-k′)為全零矩陣；當(dāng)存在誤碼時，部分線性關(guān)系受到破壞，此時k′＞k，列向量sk′+1,sk′+2,…,sn構(gòu)成LDPC 部分非稀疏校驗矩陣，同時D(N-k′)×(n-k′)為一稀疏矩陣。在極端情況下，k′=n，矩陣A為列滿秩矩陣，未能重建出非稀疏校驗向量。由上述分析可知，對A進(jìn)行高斯消元時，真正對結(jié)果產(chǎn)生影響的是前n個碼字，只有當(dāng)前n個碼字同時滿足同一校驗關(guān)系時，才能得到校驗向量。

不妨設(shè)LDPC 中某一校驗向量為v，其碼重為w，當(dāng)誤碼率為pe時，通過對矩陣A進(jìn)行高斯消元，仍能得到校驗向量v，則必須滿足以下條件：向量v中元素為1 的位置對應(yīng)于A中前n個碼字中比特沒有出現(xiàn)誤碼或出現(xiàn)誤碼的個數(shù)為偶數(shù)，此時通過模2 運算，誤碼沒有產(chǎn)生影響，即單個碼字滿足v的校驗關(guān)系概率為

其中，C 表示求組合數(shù)運算。

對A進(jìn)行高斯消元，得到非稀疏校驗向量v，則至少需要n個滿足校驗關(guān)系的碼字，即能夠通過高斯消元求解得到v的概率為P1=Pn。

由此可知，對于傳統(tǒng)算法而言，在信道誤碼率一定時，能夠獲取到校驗向量的概率隨碼長n和校驗向量碼重w的增大而呈指數(shù)級下降。在實際工程中，LDPC 的碼長通常很大，對應(yīng)于非稀疏校驗向量的碼重也非常大，故誤碼率一旦增大，能夠通過高斯消元求解校驗向量的概率將非常小，同時高斯消元算法的計算復(fù)雜度近似為O(n3)，由此可知，對于碼長較長的LDPC 而言，計算復(fù)雜度較大。

對于非稀疏校驗向量的稀疏化，傳統(tǒng)方法采用2 階和P階行變換方式，對于非雙對角線形式的稀疏校驗矩陣，P的選取具有一定的盲目性，故計算量比較大，這導(dǎo)致其算法的實時性較差。

從上述分析來看，在有誤碼條件下，傳統(tǒng)的重建算法與工程實用化還有一定的差距。基于此，本文提出了一種新的思路，利用LDPC 校驗矩陣非常稀疏這一特點，通過多次隨機(jī)抽取碼字中部分比特進(jìn)行高斯消元，當(dāng)抽取的比特包含稀疏校驗向量中校驗位時，經(jīng)過消元后可直接得到涵蓋稀疏校驗向量的對偶空間，由于抽取的是碼字中部分比特，故該對偶空間維度會很小，通過遍歷對偶空間中向量，可以很快提取到稀疏校驗向量。由于參與消元的僅為碼字的部分比特，故與傳統(tǒng)方法相比，計算復(fù)雜度以及容錯性能均會有明顯改善，同時在一定程度上避免了稀疏化步驟。

4 LDPC 稀疏矩陣重建模型建立

4.1 隨機(jī)抽取次數(shù)的確定

從傳統(tǒng)識別算法來看，為了獲取校驗向量，算法將整個LDPC 的碼字進(jìn)行列消元，但是從LDPC稀疏校驗矩陣特點來看，構(gòu)成LDPC 碼字校驗關(guān)系的比特長度實際上很短，在求解稀疏校驗向量過程中，沒有必要將整個LDPC 碼字進(jìn)行消元，如果抽取碼字中部分比特進(jìn)行列消元，當(dāng)抽取到的比特中涵蓋了稀疏校驗向量的校驗位時，消元的結(jié)果構(gòu)成的對偶空間一定含有稀疏校驗向量，同時對偶空間的維度較小，很容易找到稀疏校驗向量。由于一次隨機(jī)抽取并不能保證涵蓋一個稀疏校驗向量中完整的校驗位，故需要多次抽取，為了確定抽取次數(shù)，實現(xiàn)可靠涵蓋到整個完整的校驗位，需要分析一次隨機(jī)抽取的比特位置能夠包含完整校驗位的概率。不妨設(shè)LDPC 稀疏校驗矩陣中，某一稀疏校驗向量為v′，對應(yīng)于校驗節(jié)點數(shù)目為w′，碼字中隨機(jī)抽取的比特數(shù)目為s，則對于碼長為n的LDPC，抽取出s個位置的樣本空間數(shù)目為，而這s個位置中正好包含w′的校驗節(jié)點的個數(shù)為，故得到一次隨機(jī)抽取可包含v′中稀疏校驗節(jié)點的概率為

由式(6)可知，當(dāng)LDPC 碼長固定后，概率P2與s和稀疏校驗向量的碼重有關(guān)，s越大，校驗向量越稀疏，則P2的值就越大。通常情況下，LDPC 重稀疏校驗向量碼重很小，一般不超過10；對于s而言，雖然取值越大，得到校驗向量的可能性就越大，但是獲取到的對偶空間的維度也會增大，這不利于稀疏向量的求取，極端情況下，s=n，算法退化為傳統(tǒng)算法，故s的取值不宜過大。為兼顧P2與對偶空間維度，一般參考LDPC 碼率來選擇，設(shè)LDPC 碼率為R，則每次隨機(jī)抽取的比特數(shù)目可為Rn。

確定概率P2后，下面進(jìn)一步探討如何確定隨機(jī)抽取的次數(shù)，從而可靠實現(xiàn)在抽取的比特中包含校驗節(jié)點。不妨設(shè)隨機(jī)抽取的次數(shù)為iter，則在iter 次的隨機(jī)抽取中，能夠出現(xiàn)包含稀疏校驗節(jié)點的次數(shù)T服從二項式分布，即

當(dāng)抽取的次數(shù)iter 較大時，由棣莫弗-拉普拉斯定理可得

其中，N(0,1)表示標(biāo)準(zhǔn)正態(tài)分布。

在數(shù)理統(tǒng)計過程中，當(dāng)事件發(fā)生的概率大于0.997 5 時，可將該事件定義為大概率事件，即在隨機(jī)抽取iter 次過程中，至少發(fā)生一次，則iter 必須滿足式(9)。

通過查詢正態(tài)分布表可知

求解式(10)，得到iter 的取值范圍為

從而得到可靠包含稀疏校驗節(jié)點的最小隨機(jī)抽取次數(shù)為

4.2 疑似校驗向量判定

隨機(jī)抽取碼字中部分比特序列構(gòu)成新的碼字矩陣，通過高斯消元法得到的解向量僅能滿足前s個碼字，這類解向量被定義為疑似校驗向量，此時需要綜合考慮在疑似校驗向量下整個碼字成立的情況，所以需要利用真實校驗向量與非校驗向量下，碼字校驗關(guān)系成立的統(tǒng)計特性進(jìn)行判定。不妨設(shè)得到的疑似校驗向量為h，對應(yīng)的碼重為wh。首先，考慮以下2 類假設(shè)條件：H0表示h不是校驗向量，H1表示h是校驗向量。

在信道誤碼率為pe、假設(shè)條件為1H下，由式(5)可知，校驗關(guān)系仍然成立的概率為

對于假設(shè)條件H0，由于h不是校驗向量，因此碼字校驗關(guān)系成立概率隨機(jī)，即Ph0=0.5。將碼字成立個數(shù)與不成立個數(shù)之差t作為統(tǒng)計量，當(dāng)碼字個數(shù)N充分大時，在假設(shè)條件H1下，t服從均值為N(2Ph1-1)、方差為4N Ph1(1-Ph1)的正態(tài)分布，即

在假設(shè)條件0H下，t服從均值為0、方差為N的正態(tài)分布，即

為方便描述，不妨記μ0=0,=N，μ1=N(2Ph1-1)，=4N Ph1(1-Ph1)。設(shè)2 類假設(shè)的判決門限為Λ，則虛警概率Pf為

漏警概率Pa為

綜合2 類錯誤判決概率，得到平均錯誤判決概率為

利用Per對Λ求導(dǎo)數(shù)，并令其等于0，得到

對式(19)兩邊取對數(shù)，將其化為一元二次方程，求解得到最小錯誤判決門限Λopt為

當(dāng)N足夠大時，Λopt可近似為

通過高斯消元得到疑似校驗向量后，求取對應(yīng)的統(tǒng)計量t，然后計算最小錯誤判決門限Λopt，當(dāng)t≥Λopt時，即可判定為校驗向量。需要注意的是，由于每次高斯消元僅利用了前s個碼字，為了增大疑似校驗向量獲取的概率，充分利用截獲的碼字，可以采用多次迭代隨機(jī)選擇s個碼字進(jìn)行消元，直到出現(xiàn)疑似校驗向量。

4.3 LDPC 稀疏校驗矩陣重建算法步驟

所提算法充分利用了LDPC 校驗矩陣非常稀疏這一特點，即對于任一稀疏校驗向量而言，碼字中實際參與校驗的比特位是非常小的，當(dāng)隨機(jī)抽取的比特位置中正好涵蓋了校驗節(jié)點時，通過高斯消元可得到包含稀疏校驗向量的對偶空間，且對偶空間的維度較小，通過遍歷的方式，可以快速獲取稀疏向量，具體的算法步驟如下。

步驟1初始化參數(shù)s，迭代消元次數(shù)iter1，i1=1，i2=1，用截獲的數(shù)據(jù)構(gòu)造LDPC 碼字矩陣AN×n，其中N為碼字?jǐn)?shù)目，n為LDPC 碼長。

步驟2計算隨機(jī)抽取次數(shù)itermin，從而保證可靠出現(xiàn)涵蓋稀疏校驗向量節(jié)點位置。

步驟3隨機(jī)抽取AN×n中s列數(shù)據(jù)，構(gòu)造新的碼字矩陣CN×s，同時i1=i1+1。

步驟4隨機(jī)選取CN×s中s行數(shù)據(jù)構(gòu)成方陣Bs×s，同時采用高斯消元法得到Bs×s的對偶空間基向量。

步驟5若對偶空間為非零空間，則利用對偶空間基遍歷整個解空間，尋找稀疏校驗向量；否則i2=i2+1，重復(fù)步驟4，直到i2＞iter1。

步驟6計算稀疏向量對應(yīng)的統(tǒng)計量t以及最小錯誤判決門限Λopt，若t≥Λopt，則保存該稀疏校驗向量于集合H中，同時重復(fù)步驟3，i2置1；否則i2=i2+1，重復(fù)步驟4，直到i2＞iter1。

步驟7判斷i1＞itermin是否成立，若成立，則輸出稀疏校驗矩陣H；否則轉(zhuǎn)至步驟3，直到i1＞itermin。

在步驟5 中，由于隨機(jī)抽取了實際碼字中部分比特進(jìn)行高斯消元，故其對偶空間維度遠(yuǎn)小于實際LDPC 對偶空間維度，通過遍歷解空間中向量，能很容易地求解對偶空間中稀疏向量。

在實際仿真中，算法對每次得到的校驗向量都要進(jìn)行篩選和判定，當(dāng)向量的碼重與碼長之比小于0.03 時，將其判定為稀疏校驗向量，保存的校驗向量不僅要滿足稀疏條件，同時還必須滿足與已保存的稀疏向量相互線性不相關(guān)的條件，故稀疏校驗向量的個數(shù)等于重建矩陣的秩。在后續(xù)算法性能驗證過程中，本文將重建的稀疏向量個數(shù)與定義的稀疏矩陣秩之比定義為重建率，在不同誤碼條件下，利用重建率這一指標(biāo)來表征算法的性能。由于LDPC 譯碼依賴于稀疏校驗矩陣，故在信道較惡劣的條件下，利用本文重建的部分稀疏校驗矩陣可以對LDPC 進(jìn)行迭代譯碼，從而改善截獲的碼字質(zhì)量，進(jìn)一步提升算法的性能。

4.4 計算復(fù)雜度分析

設(shè)隨機(jī)抽取的列數(shù)為s，隨機(jī)抽取的次數(shù)為itermin，構(gòu)造方陣Bs×s并進(jìn)行高斯消元的最大次數(shù)為iter1；由于進(jìn)行一次高斯消元的計算復(fù)雜度為O(s3)，則在最不利條件下，本文算法的最大計算量為O(iterminiter1s3)。由于本文算法僅抽取碼字中部分比特進(jìn)行消元，故得到的對偶空間維度較小，可以很容易地找到稀疏校驗向量，而且在絕大多數(shù)情況下，能直接得到稀疏校驗向量。對于傳統(tǒng)算法而言，針對碼率為k/n的LDPC，需要將整個碼字進(jìn)行高斯消元，其最大計算量為O(iter1n3)，由于得到的是非稀疏校驗向量，故還需要進(jìn)行稀疏化處理，在稀疏化處理過程中，采用P階行變化處理，其計算復(fù)雜度為，故傳統(tǒng)算法[14-15]總的計算復(fù)雜度為，對于非雙對角線形式的LDPC，P的取值一般會比較大，此時傳統(tǒng)算法的復(fù)雜度會急劇增加，由此可知，本文算法的通用性要優(yōu)于傳統(tǒng)方法。

5 仿真驗證

本節(jié)首先驗證本文算法的有效性，即能夠在有誤碼條件下，完成雙對角以及非雙對角線形式的稀疏校驗矩陣重建；其次考察在不同迭代消元次數(shù)、不同截獲碼字個數(shù)、不同碼長以及碼率條件下，算法的重建性能；最后將本文算法與傳統(tǒng)的LDPC 重建方法[14-15]進(jìn)行對比。

5.1 算法有效性驗證

5.1.1 雙對角線稀疏校驗矩陣重建

本節(jié)設(shè)定LDPC 的稀疏校驗矩陣為協(xié)議IEEE 802.11n 中定義的LDPC(648,324)，其稀疏校驗矩陣具有明顯的雙對角線，如圖1(a)所示。設(shè)截獲的碼字個數(shù)為5 000 個，誤碼率為0.001 5，高斯消元迭代次數(shù)為20 次，本文算法重建結(jié)果如圖1(b)所示。由于重建稀疏矩陣行順序是隨機(jī)的，為了方便與圖1(a)對比，將圖1(b)的行順序參照圖1(a)的行順序重新排列，得到結(jié)果圖1(c)。為了與本文算法進(jìn)行對比，在同等條件下，傳統(tǒng)算法也對該稀疏校驗矩陣進(jìn)行了重建，圖1(d)為傳統(tǒng)算法重建的非稀疏校驗矩陣，而圖1(e)為稀疏化后的結(jié)果。

圖1 2 種算法針對雙對角線稀疏校驗矩陣的重建過程

從圖1 可以看出，當(dāng)誤碼率為0.001 5 時，本文算法直接重建出306 個稀疏校驗向量，即重建率達(dá)到94.44%。與原始稀疏校驗矩陣對比發(fā)現(xiàn)，重建的稀疏校驗向量與原始稀疏校驗矩陣中向量完全一致（重新排列得到的圖1(c)與圖1(a)是一致的），這說明本文算法能夠很好地重建稀疏矩陣；相反，傳統(tǒng)重建算法在誤碼率為0.001 5 時，僅得到8 個非稀疏的校驗向量，經(jīng)過稀疏化處理后，得到6 個稀疏校驗向量，重建率僅為1.85%，這說明傳統(tǒng)算法對誤碼的穩(wěn)健性較差。

5.1.2 非雙對角線稀疏校驗矩陣重建

本節(jié)設(shè)LDPC 為QC-LDPC(600,300)，該稀疏校驗矩陣不再具有雙對角線形式，如圖2(a)所示，生成的LDPC 碼字個數(shù)為5 000，信道誤碼率為0.001，高斯迭代消元次數(shù)為20。本文算法重建結(jié)果如圖2(b)所示，為了方便與原始稀疏校驗矩陣對比，同樣將圖2(b)的行順序參照圖2(a)的行順序進(jìn)行重排列，得到圖2(c)結(jié)果。在同等條件下，利用傳統(tǒng)重建方法首先得到如圖2(d)所示的非稀疏校驗矩陣，然后稀疏化處理得到如圖2(e)的結(jié)果。

從圖2 可以看出，本文算法有效恢復(fù)出了295 個稀疏校驗向量，雖然實際的稀疏校驗向量個數(shù)為300 個，但由于該稀疏校驗矩陣是非滿秩矩陣，其秩為295，故本文算法重建的LDPC 稀疏校驗矩陣和原始矩陣等效；同時由圖2(c)可知，本文重建的稀疏校驗向量和原始的稀疏校驗向量是完全一致的，這進(jìn)一步說明本文算法能夠較好地重建出稀疏矩陣。雖然傳統(tǒng)的重建方法能夠得到295 個非稀疏的校驗向量，但是通過多次行消元稀疏，得到的結(jié)果仍然不夠稀疏，同時存在大量4 環(huán)（稀疏矩陣的設(shè)計應(yīng)避免出現(xiàn)4 環(huán)），這說明傳統(tǒng)算法針對非雙對角形式的稀疏校驗矩陣重建效果不佳。

5.2 算法容錯性驗證

圖2 2 種算法針對非雙對角線形式的LDPC 重建過程

本節(jié)主要考察消元迭代次數(shù)、截獲碼字個數(shù)、碼長以及碼率幾個因素對算法性能的影響，記錄在某一因素、不同誤碼率下的重建率。

5.2.1 迭代次數(shù)的影響

仿真設(shè)定LDPC 稀疏校驗矩陣為協(xié)議IEEE 802.11e 中定義的LDPC(576,288)，設(shè)截獲的碼字個數(shù)為1 500 個，在高斯消元過程中，迭代次數(shù)分別設(shè)定1 次、5 次、10 次、15 次、20 次；設(shè)定誤碼率范圍為0～0.005，取值間隔為0.000 25，統(tǒng)計在不同迭代次數(shù)以及不同誤碼率下，LDPC 稀疏校驗矩陣重建率，結(jié)果如圖3 所示。

圖3 不同迭代次數(shù)對算法的影響

從圖3 可以看出，增加迭代次數(shù)可以有效提高LDPC 稀疏校驗矩陣的重建率。主要原因在于，在高斯消元過程中，迭代次數(shù)一旦增加，滿足同一校驗關(guān)系的碼字被抽到的概率就會增加，此時重建出的稀疏校驗向量也會相應(yīng)增多。此外，本文提出的重建算法具有較好的容錯性，在誤碼率為0.001 的條件下，稀疏校驗矩陣重建率能達(dá)到95%以上。

5.2.2 截獲碼字?jǐn)?shù)目影響

同樣設(shè)定LDPC 稀疏校驗矩陣為協(xié)議IEEE 802.11e 中的LDPC(576,288)，設(shè)信道誤碼率為0.000 5、0.001、0.001 5、0.002、0.002 5，高斯消元迭代次數(shù)為20 次，截獲的LDPC 碼字個數(shù)范圍為500～2 000，取值為間隔100，統(tǒng)計5 種信道誤碼率情況下，不同截獲碼字個數(shù)對應(yīng)的稀疏矩陣重建率，結(jié)果如圖4 所示。

從圖4 可以看出，增加碼字個數(shù)能夠有效增大稀疏校驗矩陣的重建率，原因在于，當(dāng)碼字個數(shù)增多時，滿足同一校驗關(guān)系的碼字會隨之增加，所以在迭代消元過程中，隨機(jī)抽取到這一類碼字的可能性就會增大；當(dāng)碼字增加后，計算的判決門限會更加準(zhǔn)確，對疑似校驗向量的誤判就會減少。

圖4 不同碼字個數(shù)對算法的影響

5.2.3 碼長和碼率的影響

仿真設(shè)定LDPC 碼率為1/2 和2/3，每種碼率對應(yīng)的碼長為576、648 以及768，選取的稀疏校驗矩陣都為IEEE 802.11 協(xié)議中定義的校驗矩陣，設(shè)截獲的碼字個數(shù)為2 000，誤碼率范圍為0～0.004，取值間隔為0.000 25，高斯消元迭代次數(shù)為20 次，統(tǒng)計在不同LDPC 編碼類型下，不同誤碼率對應(yīng)的稀疏校驗矩陣重建率，結(jié)果如圖5 所示。

圖5 不同碼長和碼率對算法影響

從圖5 結(jié)果來看，在同一碼長條件下，算法重建率隨碼率的增加而降低；在同一碼率條件下，重建率隨碼長的增加而下降。主要原因在于，首先，當(dāng)碼長增加時，抽取參與消元的比特相應(yīng)增加，此時誤碼會隨比特消元過程而擴(kuò)散，參與消元的比特越多，擴(kuò)散情況越嚴(yán)重；其次，當(dāng)碼率增加時，稀疏校驗矩陣中向量碼重增加，此時能夠抽取到包含校驗節(jié)點的數(shù)據(jù)比特的概率會降低，同時碼重增加后，疑似校驗向量的誤判概率也會增加，這2 個因素綜合起來會導(dǎo)致算法性能降低。

5.3 與傳統(tǒng)算法比較

本文算法與傳統(tǒng)算法比較時，選取IEEE 802.11協(xié)議中LDPC(576,288)（碼率為1/2）、LDPC(648,324)（碼率為1/2）以及LDPC(648,432)（碼率為2/3）。設(shè)截獲的碼字個數(shù)為2 000，信道誤碼率范圍為0～0.005，取值間隔為0.000 25，統(tǒng)計不同誤碼率下2 種算法的重建率，結(jié)果如圖6 所示。

圖6 本文算法與傳統(tǒng)算法重建率對比

從圖6 可以看出，本文算法重建率明顯優(yōu)于傳統(tǒng)算法。主要原因在于，首先，本文算法通過隨機(jī)抽取碼字中部分比特進(jìn)行消元，實際參與消元的比特數(shù)目遠(yuǎn)小于碼字長度，所以本文算法對于信道噪聲具有更強(qiáng)的穩(wěn)健性；其次，傳統(tǒng)算法的重建性能較差，信道誤碼率稍有增加，算法重建率就急劇下降。由此可見，本文算法在高誤碼率下具有更好的工程實用性。

6 結(jié)束語

本文基于LDPC 稀疏校驗矩陣的特征，提出了可直接重建稀疏校驗矩陣的算法。算法首先通過多次隨機(jī)抽取碼字中部分比特序列進(jìn)行高斯消元，當(dāng)抽取的比特序列包含稀疏校驗節(jié)點時，從消元的結(jié)果中可直接獲取LDPC 稀疏校驗向量；其次分析了在有誤碼條件下，碼字校驗關(guān)系成立的統(tǒng)計特性，基于最小錯誤判決準(zhǔn)則，完成疑似校驗向量的判定，最終完成LDPC 稀疏校驗矩陣的重建。與傳統(tǒng)重建算法相比，本文算法不再需要單獨進(jìn)行稀疏化步驟，不僅具有較好的容錯性能，而且對于雙對角線與非雙對角線形式的稀疏校驗矩陣都具有很好的通用性。