張 俊

(同濟(jì)大學(xué)電子與信息工程學(xué)院，上海 201804)

基于統(tǒng)計特性的LDPC碼分析識別研究

張 俊

(同濟(jì)大學(xué)電子與信息工程學(xué)院，上海 201804)

從統(tǒng)計角度出發(fā)，提出對LDPC碼分析思路和初步方法，在仿真的情況下進(jìn)行驗證。利用LDPC碼作為分組碼的特性，通過統(tǒng)計和對統(tǒng)計特性的分析，在一定程度上克服傳統(tǒng)方法——解高斯方程法的局限性，實現(xiàn)了對LDPC碼部分特性分析。同樣適用于其他分組碼的分析識別。

信道編碼分析識別;低密度奇偶校驗碼;統(tǒng)計特性

目前，有關(guān)智能通信(認(rèn)知通信)領(lǐng)域的研究蓬勃發(fā)展。智能通信就是通信的發(fā)送方可以根據(jù)所處的地理、電磁環(huán)境、頻譜約束等情況以及業(yè)務(wù)需求，選擇最佳的通信體制、通信方式和通信參數(shù)與接收方進(jìn)行可靠通信。也就是說智能通信系統(tǒng)的通信體制、通信方式和通信參數(shù)是隨時地不斷變化，這就要求智能通信系統(tǒng)的接收方必須能正確地對接收信號進(jìn)行識別分析，包括對信道載頻、信號參數(shù)、信道編碼方式、編碼參數(shù)等進(jìn)行識別分析。

目前對信道編碼的分析識別［1－4］主要停留在有限先驗知識情況下的識別分析上，真正的全盲識別分析還不多。從研究對象來看，主要集中在卷積碼的識別分析［5－7］上，對碼長較短的分組碼(包括 RS 碼［8－9］)也有涉及，但由于 LDPC 可能成為下一代移動通信標(biāo)準(zhǔn)，目前尚未像其他碼一樣廣泛應(yīng)用(DVB－S||信號中采用LDPC碼，)，同時受制于其較長的碼長，傳統(tǒng)的分析方法受到很大的局限，因此對LDPC碼的分析識別有待于進(jìn)一步的深入研究。

1 LDPC碼及解高斯方程分析法

1.1 LDPC 碼

LDPC(Low Density Parity Check) 碼［10］是Gallager于1962年提出的一種具有稀疏校驗矩陣的分組糾錯碼，亦稱Gallager碼。本文討論的GF(2)域上的LDPC碼C是一種(n，k)線性分組碼，碼長為n，信息序列長度為k，可以由其校驗矩陣H唯一定義

H的維數(shù)是m×n，其中m=n－k，每一行對應(yīng)一個校驗方程，每一列對應(yīng)碼字的一位。每一行中非元素的個數(shù)為行重，每一列中非零的個數(shù)稱為列重。LDPC碼和其他分組碼的最大區(qū)別在于其校矩陣中非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個數(shù)，或矩陣的行重和列重與碼長相比是很小的數(shù)，即在校驗矩陣H中，每一行只有很少的1，同時每一列也只有很少的1。如果校驗矩陣的各行中非零元素的個數(shù)是相同的，各列中非零元素的個數(shù)也相同，這樣的LDPC碼稱為規(guī)則碼。已經(jīng)證明，當(dāng)分組長度很大時，LDPC碼的性能大大超過了卷積碼。

1.2 解高斯方程法

信道編碼識別中，分組碼識別的重點在于生成多項式(或校驗多項式)的識別，傳統(tǒng)的識別方法為解高斯方程法［11－12］。線性分組碼的數(shù)學(xué)模型可以描述為:C=M·G，其中 M=［M0，M1，…Mi…］表示以k比特為分組單位的輸入信息序列，Mi=［mi，0，mi，1…mi，k－1］表示第 i時刻輸入的 k 個比特信息;C=［C0，C1，…Ci…］表示以 n比特為分組單位的編碼輸出序列，Ci=［ci，0，ci，1，…ci，n－1］表示第i時刻輸出的n個比特信息;G表示生成矩陣。對分組碼進(jìn)行識別分析重點在于僅知C而很少知道或完全未知其他信息的條件下如何估計生成矩陣G，進(jìn)而成功恢復(fù)信息序列M。對編碼輸出序列C，有校驗關(guān)系C·HT=0成立，若能通過識別分析求出HT，則由C·HT=0可求出生成矩陣G。當(dāng)接收碼字序列無誤碼時，有校驗關(guān)系C·HT=0，其中 H=(h0，h1，…h(huán)n－k－1)，則有如下線性方程組:

求解上述方程的常規(guī)方法是高斯消元法，通過數(shù)學(xué)變化，可得到如下形式的增廣矩陣:

其中d為解空間的維數(shù)。

方程組中 h0，h1，…h(huán)n－k－1解空間的標(biāo)準(zhǔn)基形式如下:

上述解中，只要d=n－k，則hi即可能為所求。

1.3 解高斯方程法局限性

對于碼長較短的分組碼(包括RS碼)及卷積碼，其約束關(guān)系都較短。分組碼的約束長度和其分組長度相關(guān)，而卷積碼的約束長度和其分組長度及存儲深度有關(guān)。如在DVB－S標(biāo)準(zhǔn)中，(204，188)RS碼約束長度為1632比特;對于廣泛使用的(2，1，6)卷積碼，其約束長度為14比特。一個典型信道噪聲信道的比特誤碼率約為10－2至 10－3，因此，對于碼長較短的分組碼和卷積碼，在典型信道噪聲信道中總可以找到一段碼字無誤碼，通過求解高斯方程的方法來確定其校驗矩陣H(或生成矩陣G)。對于碼長較長的LDPC碼而言，求解高斯方程的主要有兩個缺點，一是該方法不容錯，即使在誤碼率為10－3情況下，其碼長內(nèi)不可避免出現(xiàn)誤碼，即使出現(xiàn)一個比特誤碼，都會導(dǎo)致求解高斯方程失敗;其次是該方法運算量巨大，如 DVB－S||標(biāo)準(zhǔn)［13］中 LDPC碼長為64800比特，求解方程的矩陣為64800×64800，解方程的運算次數(shù)約為8.389×109次。因此，正是由于很難同時滿足這兩個條件，因此用傳統(tǒng)的解高斯方程法在對LDPC碼的分析識別中受到很大的局限性。

2 基于統(tǒng)計特性的LDPC碼分析研究

在信道編碼的參數(shù)分析識別中，對糾錯碼而言，包括碼型識別(分組碼還是卷積碼)、碼率判斷、碼分組起點判斷以及生成多項式(或校驗多項式)的識別。本文中的統(tǒng)計方法主要解決在已知分組長度n的情況下，如何通過統(tǒng)計特性的分析，進(jìn)行碼率以及分組起點判斷的問題。

2.1 按列0/1頻次統(tǒng)計法

2.1.1 按列0/1頻次統(tǒng)計方法

在通信過程中，信源編碼主要利用信息冗余度進(jìn)行壓縮，來解決信息傳輸?shù)男蕟栴};信道編碼主要利用添加校驗，來解決信息傳輸?shù)目煽啃詥栴}。在現(xiàn)實通信過程中，很多信息(包括語音、圖象、文本等)本身具有較大的冗余度。如果冗余度較大的信息不進(jìn)行壓縮，或者壓縮率較小的情況下，如果按照特定的方法，對該信息進(jìn)行統(tǒng)計，那么統(tǒng)計結(jié)果應(yīng)該呈現(xiàn)出一定的不平衡特性。下面分別以64M字節(jié)的u率話音編碼數(shù)據(jù)及512M字節(jié)符合G.733格式的一次群數(shù)據(jù)做按列0/1頻次統(tǒng)計(統(tǒng)計幀長為48比特)，其結(jié)果如圖1。從統(tǒng)計結(jié)果可以看出，這兩種統(tǒng)計結(jié)果都呈現(xiàn)出明顯的不平衡性。

圖1 u率話音編碼數(shù)據(jù)和G.733一次群數(shù)據(jù)按列0/1頻次統(tǒng)計直方圖

同樣，對于(n，k)LDPC碼，如果 k位信息是01非平衡的數(shù)據(jù)，那么信息位置經(jīng)按列0/1頻次統(tǒng)計后每一列的0/1比例是不平衡的，由LDPC碼的生成方法可知，其(n－k)位校驗是經(jīng)過多個不平衡的信息位運算而得到的(在域GF(2)上是信息位的模2加)，所以趨于平衡，這樣k位信息與(n－k)位校驗在按列0/1頻次統(tǒng)計下有不同的特性。

按列0/1頻次統(tǒng)計是指在一定的幀長n下，統(tǒng)計每一列數(shù)據(jù)的0/1頻次。統(tǒng)計方法如下:

如果數(shù)據(jù)隨機，每一列數(shù)據(jù)按列1的頻次的理論值為

程序及式(1)中，n為統(tǒng)計幀長，databegin為信息比特起點，dataover為信息比特終點，符號?.」表示下取整，下同。

2.1.2 分析特性

k位信息采用的是符合G.733格式的一次群信號，校驗矩陣采用(96，3，6)規(guī)則LDPC碼，按列0/1頻次統(tǒng)計可以分析LDPC碼的信息與校驗位位置，圖1是LDPC碼編碼之后的按列0/1頻次直方圖。

圖2 規(guī)則LDPC碼的按列0/1頻次直方圖

分析圖1，前48位的1頻次參差不齊，且大于平均頻次，是信源G.733語音編碼之間的相關(guān)性造成的;后48位的1頻次趨于一致，且接近平均頻次，是在約束關(guān)系之內(nèi)，多個不平衡的信息位根據(jù)校驗關(guān)系經(jīng)過運算而得到，所以體現(xiàn)出相對較為平衡的現(xiàn)象。因此，通過按列0/1頻次統(tǒng)計，可以直觀得到信息位k，從而確定該分組碼的碼率k/n。

2.2 字符頻次統(tǒng)計下的分析特性

2.2.1 字符頻次統(tǒng)計

對于(n，k)LDPC碼，由其生成方法可知，在大小為2n的符號空間中，只取2k個碼字，如果無誤碼，應(yīng)該出現(xiàn)(2n－2k)個零頻。如果統(tǒng)計起點和碼起點一致，以碼長n做字符頻次統(tǒng)計，那么將得到的2k個非零頻和(2n－2k)個零頻，與理論值一致;如果統(tǒng)計起點和真實碼起點不一致，由于分組關(guān)系的錯亂，即對不同分組的信息和校驗位進(jìn)行統(tǒng)計，顯然得不到正確的統(tǒng)計關(guān)系。因此，通過不同起點下字符頻次統(tǒng)計，可以對碼長、分組起點等參數(shù)進(jìn)行分析。

字符頻次統(tǒng)計是統(tǒng)計數(shù)據(jù)中字符的頻次，然后對頻次出現(xiàn)的概率進(jìn)行分析。

字符頻次統(tǒng)計有兩個統(tǒng)計參數(shù)，字符寬度n及字符統(tǒng)計移位起點codebegin，codebegin滿足

記連續(xù)n比特為一個字符，每次移位n比特，再將連續(xù)n比特記為一個字符。統(tǒng)計方法如下:

程序中，databegin為信息比特起點，dataover為信息比特終點。字符統(tǒng)計的平均頻次為:

式(2)中，符號?.」表示下取整。

2.2.2 分析特性

LDPC碼是分組碼，設(shè)生成矩陣為G，信息為M=(m0，m1，…，mk－1)。

如果數(shù)據(jù)是(n，k)LDPC碼，則在大小為2n的符號空間中，只有2k個碼字。用碼字的準(zhǔn)確起點對數(shù)據(jù)作字符長度為n的字符頻次統(tǒng)計，將有2n－2k個字符是零頻(出現(xiàn)頻次為0)，2k個符號不是零頻，且出現(xiàn)頻次為

NUMS0=2k/2n=1/2n－k。 (4)

從碼字的前一比特或后一比特開始作字符長度為n的字符頻次統(tǒng)計?？梢詫分為兩部分(n－1，1)，其中前 n－1比特中仍將取自2n的符號空間中的2k個碼字，而后面1比特則有21種情況，可以算出，在這種情況下將有2n個碼字中，將有2n－2k+1個字符是零頻(出現(xiàn)頻次為0)，有2k×21=2k+1個符號不是零頻，且出現(xiàn)頻次為

以此類推，可以得出如表1所示的頻次表。表1中的統(tǒng)計起點指距離LDPC碼碼字的起點多少比特，第一行是碼空間內(nèi)的碼字的出現(xiàn)頻次，其它起點出現(xiàn)的非零頻碼字也可能是碼空間內(nèi)的碼字。

表1 在不同起點下LDPC碼非零頻字符的出現(xiàn)頻次

為示意起見，對一個(10，2，4)LPDC碼進(jìn)行字符頻次統(tǒng)計結(jié)果見表2。

表2 不同起點下(10，2，4)LDPC編碼非零頻字符的出現(xiàn)頻次

續(xù)表

該碼碼長n為10比特，其中信息位為6比特，校驗為4比特，則在大小為210的符號空間中，只有26個碼字。從統(tǒng)計得出的表2情況看，如果統(tǒng)計起點為碼分組起點的話，其中出現(xiàn)的非零字符頻次為26，從碼字的前一比特或后一比特做字符頻次統(tǒng)計，其中出現(xiàn)的非零字符頻次為27，以次類推。因此，在已知分組碼長n的情況下，可以統(tǒng)計出在2n的符號空間中實際非零頻字符出現(xiàn)概率，從而算出其信息位的個數(shù)，從而推導(dǎo)出碼率;通過比較不同起點下非零頻字符出現(xiàn)概率，從而確定該碼的起點。

3 結(jié)論

由于傳統(tǒng)方法——解高斯方程法在對LDPC碼的分析識別上存在很大局限性，本文提出了基于統(tǒng)計特性的分析法，并對其中的按列0/1頻次統(tǒng)計及字符頻次統(tǒng)計法等方法進(jìn)行介紹?；诮y(tǒng)計特性的分析法利用了LDPC碼作為分組碼的特性，通過相關(guān)統(tǒng)計，并對其特性進(jìn)行分析和研究，可以得到碼率、起點位置以及分組長度等信息。相對解高斯方程法，這兩種統(tǒng)計方法不對數(shù)據(jù)質(zhì)量做很高的依賴，只需得到一個近似的結(jié)果就可以進(jìn)行分析，一定程度上克服了解高斯方程法的局限性，解決了LDPC碼部分特性的分析識別問題。

［1］柴先明，黃知濤.信道編碼識別問題研究［J］.通信對抗，2008(2):6 －11.

［2］宋鏡業(yè).信道編碼識別技術(shù)研究［D］.西安:西安電子科技大學(xué)，2009.

［3］張永元，樓才義，王挺.一種線性分組碼編碼參數(shù)的盲識別方法［P］.中國:CN101623224A.

［4］李艷斌.低碼率二進(jìn)制線性分組碼的盲識別［J］.無線電工程，2009，39(1):37 －41.

［5］韓國賓.刪除卷積碼的識別技術(shù)［D］.西安:西安電子科技大學(xué)，2009.

［6］ WANG Feng Hua，HUANG Zhi Tao，ZHOU Yi Yu.A method for blind recogn－ition of convolution code based on Enclidean algorithm.IEEE International Conference on Wireless Communications［J］.IEEE Press，2007，22(3):1414－1417.

［7］JJ Chang，DJ Hwang，MC Lin.Some Extend Results on the Search for Good Convolutional Codes［J］.IEEE Trans.Inform Theory，2008，43(5):1682 －1697.

［8］劉健，謝浩，周希元.RS碼的盲識別方法［J］.西安電子科技大學(xué)學(xué)報，2009，38(3):28－32

［9］陳衛(wèi)東，劉健.一種容誤碼的RS碼編碼參數(shù)盲識別方法［P］.中國:CN101534168A.

［10］R G Gallager.Low －Density Parity －Check Codes［J］.IRE Transactions on Information Theory，1962，38(3):358－367.

［11］趙樹杰，趙建勛.信號監(jiān)測與估計理論［M］.北京:清華大學(xué)出版社，2007.

［12］朱中梁.Walsh函數(shù)在解二元域方程組上的應(yīng)用［J］.信號處理，2008(B12):9 －13.

［13］BROWN，J SET AL.European Standard Digital Video Broadcasting(DVB)［S］.IEEE Press，2004，12(4):91－111.

Research on Identification of LDPC Code Based on Statistical Properties

ZHANG Jun
(School of Electronics and Information Engineering，Tongji University，Shanghai 201804，China)

In this Paper，the ideas and methods of the analysis of LDPC(Low Density Parity Check)code have been put forward from a statistical point，and they have been confirmed in the simulation conditions.The methods analyse some LDPC code’s properties in statistical view using the way taking LDPC code as a kind of block code.To a certain extent，the ideas and methods overcome the limitations of Gaussian equation method，a the traditional method，and solve some problems of achieving part characterization of the LDPC code.The ideas and methods are also applicable to the analysis and identification of other block codes.

identification of channel coding;LDPC;statistical properties

TN911.6

A

1009－315X(2012)01－0028－05

2011－09－29;最后

2011－11－09

張俊(1979－)，男，江西樟樹人，助理研究員，主要從事信道編碼、數(shù)字信號處理、網(wǎng)絡(luò)協(xié)議等研究。

(責(zé)任編輯 劉敏)