一種高誤碼率下QC-LDPC碼的快速識(shí)別算法

宋秉璽，李廣峰，楊 松，郭曉東

(1.河北省電磁頻譜認(rèn)知與管控重點(diǎn)實(shí)驗(yàn)室，河北 石家莊050081;2.中國(guó)人民解放軍91746部隊(duì)，北京100094)

0 引言

在非合作情況下，信道編碼參數(shù)是不能直接獲取的，需要分析識(shí)別信道編碼參數(shù)。QC-LDPC碼是一種具有準(zhǔn)循環(huán)特性的LDPC碼，其校驗(yàn)矩陣都是由單位陣的循環(huán)移位構(gòu)成的[1-3]。QC-LDPC碼譯碼算法可采用并行結(jié)構(gòu)，方便硬件實(shí)現(xiàn)，可以達(dá)到很高的吞吐率[4-5]，因此在實(shí)際系統(tǒng)中被廣泛應(yīng)用，所以針對(duì)QC-LDPC碼進(jìn)行盲識(shí)別研究具有重大的科研意義，而LDPC碼的稀疏校驗(yàn)矩陣重構(gòu)是其識(shí)別的關(guān)鍵技術(shù)。文獻(xiàn)[6]介紹了LDPC碼在無(wú)誤碼下條件的校驗(yàn)矩陣重構(gòu)的基本方法。文獻(xiàn)[7]介紹了一種通過(guò)列相關(guān)關(guān)系剔除有誤碼碼字的方法，但二者都要求數(shù)據(jù)量很大，且誤碼率不能太高。文獻(xiàn)[8]相比文獻(xiàn)[7]實(shí)驗(yàn)結(jié)果上略有提升，但需求數(shù)據(jù)量依然很大。本文提出了一種位置矩陣與循環(huán)位移值分步識(shí)別的方法，降低了高斯消元法的方程維度，該方法可以在低信噪比、高誤碼率的情況下仍保持良好的識(shí)別準(zhǔn)確率[9-10]。

1 校驗(yàn)矩陣稀疏化基本方法

在信道信噪比高的情況下，如圖1所示，針對(duì)無(wú)誤碼LDPC碼數(shù)據(jù)，可以通過(guò)高斯消元法，獲取LDPC碼的一組生成基，此生成基即為生成矩陣。生成矩陣和校驗(yàn)矩陣之間為轉(zhuǎn)置關(guān)系，由此可以得到校驗(yàn)矩陣。但此種方法得到的校驗(yàn)矩陣并不是一個(gè)稀疏矩陣，不能用來(lái)譯碼，需要通過(guò)行變換，使其成為可用來(lái)譯碼的稀疏校驗(yàn)矩陣[11-12]。

圖1 無(wú)誤碼校驗(yàn)矩陣獲取流程圖Fig.1 Flowchart of obtaining check matrix

以IEEE802.16標(biāo)準(zhǔn)使用的QC-LDPC碼為例，給定LDPC(576,288)，使用無(wú)誤碼數(shù)據(jù)高斯消元可得生成矩陣，如圖2(a)所示，由對(duì)應(yīng)關(guān)系可得校驗(yàn)矩陣如圖2(b)所示，之后通過(guò)行變換，稀疏化矩陣為圖2(c)所示。

(a) 生成矩陣

2 誤碼碼字識(shí)別

在信噪比低的情況下，解調(diào)碼流存在誤碼，無(wú)法通過(guò)碼字行之間的高斯消元法，直接獲得生成矩陣與校驗(yàn)矩陣，需要剔除含誤碼碼元?？赏ㄟ^(guò)列之間的高斯消元法來(lái)判斷碼字中是否有誤碼。由于碼字M=[m,mG]，校驗(yàn)列是由信息列線(xiàn)性運(yùn)算獲得的，做列高斯消元可以化簡(jiǎn)為全0列，當(dāng)數(shù)據(jù)存在少量誤碼時(shí)，由于誤碼影響，誤碼行信息位將化簡(jiǎn)為全0，或者與誤碼行數(shù)值相等的列，化簡(jiǎn)為基本為0列。此規(guī)律當(dāng)誤碼較多時(shí)，由于誤碼之間的相互影響將不存在。以L(fǎng)DPC(576,288)碼加誤碼舉例，做列消元可以等價(jià)為數(shù)據(jù)轉(zhuǎn)置后做行消元，圖3中全0概率很高的行與列位置，即為誤碼行所在位置[13-14]。

圖3 列高斯消元結(jié)果圖Fig.3 Gauss elimination result use of column

當(dāng)誤碼率高時(shí)，單次列高斯消元法無(wú)法剔除所有誤碼行，需通過(guò)多次使用列高斯消元剔除誤碼數(shù)據(jù)，直至矩陣的秩等于信息位碼長(zhǎng)(一般可以通過(guò)估計(jì)的碼速率計(jì)算)為止，進(jìn)而通過(guò)校驗(yàn)矩陣稀疏化基本原理，求取校驗(yàn)矩陣。但此處理方式需要很大的數(shù)據(jù)量，并且誤碼率不可太高。通過(guò)實(shí)驗(yàn)仿真發(fā)現(xiàn)當(dāng)原碼矩陣的列中存在多個(gè)誤碼時(shí)，無(wú)法剔除誤碼行。

3 QC-LDPC校驗(yàn)矩陣快速獲取方法

上文提到的校驗(yàn)矩陣獲取方法是同時(shí)獲取二者，這需要巨大的數(shù)據(jù)量和復(fù)雜的高維向量運(yùn)算，對(duì)于碼長(zhǎng)較長(zhǎng)LDPC碼校驗(yàn)矩陣獲取不利。求解校驗(yàn)矩陣所需的數(shù)據(jù)量與碼長(zhǎng)N成N2比例關(guān)系，高斯消元所需的數(shù)據(jù)量與碼長(zhǎng)N成N3比例關(guān)系。當(dāng)碼字?jǐn)?shù)據(jù)量不足，或者誤碼率過(guò)高的情況下，如何求解QC-LDPC校驗(yàn)矩陣是本文研究重點(diǎn)。QC-LDPC是由位置基本矩陣和循環(huán)位移值來(lái)確定的[15]。本文通過(guò)先構(gòu)造位置基本矩陣求得循環(huán)塊位置，再抽取碼元數(shù)據(jù)計(jì)算循環(huán)位移值，這樣通過(guò)分布方法獲得稀疏矩陣，其可以簡(jiǎn)化數(shù)據(jù)運(yùn)算，降低數(shù)據(jù)量的需求。

3.1 位置矩陣獲取方法

QC-LDPC碼是按循環(huán)位移單元進(jìn)行編碼生成的，所以一個(gè)循環(huán)位移塊可以看為一個(gè)整體，可以通過(guò)碼元先構(gòu)造位置獲取向量組，其保留了循環(huán)單元位置信息，丟掉循環(huán)位移值的細(xì)節(jié)信息，這樣做的好處是極大地縮小了碼長(zhǎng)，使高斯消元方程維數(shù)降低，所需整體碼數(shù)量減少。假設(shè)循環(huán)塊大小為z，則數(shù)據(jù)維數(shù)為原數(shù)據(jù)碼長(zhǎng)的1/z，所以所需數(shù)據(jù)量減少為原來(lái)的1/z2，計(jì)算量為1/z3，并且對(duì)誤碼容忍度更高。以L(fǎng)DPC(576,288)為例，其位置獲取向量組做高斯消元之后的結(jié)果如圖4所示，之后行之間做變化求得位置矩陣，如圖5所示。

圖4 位置生成矩陣Fig.4 Position generation matrix

圖5 位置矩陣Fig.5 Position matrix

通過(guò)對(duì)比圖5與圖2(c)可知，位置矩陣的點(diǎn)出現(xiàn)的位置與實(shí)際校驗(yàn)矩陣的循環(huán)校驗(yàn)單元所在的分塊位置完全一致，證明此提取方法的正確性。求解過(guò)程中如若有誤碼行，用列高斯消元法剔除。

實(shí)際應(yīng)用中z可能是未知的，需要通過(guò)把碼長(zhǎng)N進(jìn)行因子分解，窮舉所有因子，以是否可以得到位置矩陣為判斷依據(jù)，求得循環(huán)單元z。

3.2 循環(huán)位移值求解方法

在得到校驗(yàn)位置矩陣后，需對(duì)每個(gè)位置的循環(huán)位移值求解。由于校驗(yàn)關(guān)系只與每一行參與校驗(yàn)的比特有關(guān)而與其他比特?zé)o關(guān)，所以按位置矩陣提供的信息，把相互校驗(yàn)的循環(huán)位移塊提取出來(lái)，然后做高斯消元，進(jìn)而得到循環(huán)位移值。依然以L(fǎng)DPC(576,288)碼為例，其位置矩陣第一行值為1的位置有[2,3,9,10,13,14]，由z=24計(jì)算循環(huán)塊在原碼字所處列為[25～48，49～72，193～216，217～240，289～312，313～336]，在原碼字中提取這144列，除去誤碼行，做高斯消元，解得矩陣如圖6所示。

圖6 相關(guān)循環(huán)塊-行高斯消元結(jié)果圖Fig.6 Correlation loop block-row Gaussian elimination result

提取矩陣最后24列，做轉(zhuǎn)置即為各個(gè)位置塊的循環(huán)校驗(yàn)矩陣，如圖7所示。再把循環(huán)校驗(yàn)矩陣放到[25～48，49～72，193～216，217～240，289～312，313～336]位置列上，其他位置為全0陣，即可得到QC-LDPC碼的稀疏校驗(yàn)矩陣的前24行取值，如圖8所示。之后依次按位置矩陣的后續(xù)行，取實(shí)際數(shù)據(jù)列，做高斯消元，可以每次解得24行校驗(yàn)矩陣，逐步獲得全部稀疏校驗(yàn)矩陣。

圖7 相關(guān)循環(huán)塊-循環(huán)位移值Fig.7 Correlation cyclic block-cyclic displacement value

圖8 校驗(yàn)矩陣前24行取值圖Fig.8 Value of the first 24 rows of the check matrix

在獲得多行校驗(yàn)行后，可預(yù)先憑借得到的部分校驗(yàn)矩陣，對(duì)碼元進(jìn)行譯碼，從而降低原數(shù)據(jù)誤碼率，有利于后續(xù)校驗(yàn)行的獲取。

3.3 算法整體過(guò)程

通過(guò)上文的研究分析，對(duì)于誤碼下QC-LDPC校驗(yàn)矩陣快速獲取方法，可以歸結(jié)為以下的整體算法步驟。

① 選幀長(zhǎng)大于1的最小整數(shù)因子為循環(huán)位移塊長(zhǎng)度；

② 通過(guò)原碼元數(shù)據(jù)獲取位置向量組，得到只含有位置信息的位置獲取數(shù)據(jù)；

③ 數(shù)據(jù)做列高斯消元，去除誤碼碼字；

④ 把只含位置信息的碼流，按做行高斯消元，得到位置生成矩陣；

⑤ 判斷矩陣的秩是否合理，或者得到的生成矩陣是否簡(jiǎn)潔，如果是則轉(zhuǎn)入步驟⑥，否則選取下一個(gè)因子轉(zhuǎn)入步驟②；

⑥ 把位置信息生成矩陣轉(zhuǎn)化為位置矩陣；

⑦ 按位置信息，在原碼元數(shù)據(jù)中提取具有相關(guān)關(guān)系的循環(huán)塊數(shù)據(jù)所在列位置，生成新的只含有循環(huán)位置信息的碼流數(shù)據(jù)；

⑧ 數(shù)據(jù)做列高斯消元，去除誤碼碼字；

⑨ 用只含有循環(huán)位置信息的碼流數(shù)據(jù)，做行高斯消元，得到生成矩陣；

⑩ 由生成矩陣得到循環(huán)塊位移值，并按位置矩陣填入校驗(yàn)矩陣所對(duì)應(yīng)位置；

具體流程圖如圖9所示。

圖9 誤碼下QC-LDPC校驗(yàn)矩陣快速獲取算法流程圖Fig.9 Flowchart of QC-LDPC check matrix fast acquisition algorithm under bit error

4 結(jié)論

本文研究了對(duì)未知協(xié)議下QC-LDPC碼稀疏矩陣分析方法，提出了位置矩陣與循環(huán)位移值分步識(shí)別的方法，降低了高斯消元法的方程維度，可以有效降低識(shí)別所需數(shù)據(jù)量與運(yùn)算時(shí)間，并且支持在誤碼下進(jìn)行分析識(shí)別。該方法尤其適用于碼長(zhǎng)大的QC-LDPC碼識(shí)別，可極大地降低算法所需運(yùn)算的時(shí)間。