基于碼重分布與漢明距離的線性碼盲識別方法

李歆昊，張 旻

（1.解放軍電子工程學(xué)院，安徽 合肥 230037；2.安徽省電子制約技術(shù)重點實驗室，安徽 合肥 230037）

0 引言

為了實現(xiàn)通信的可靠性，并提高通信的效率，信道編碼在數(shù)字通信中得到了普遍的應(yīng)用。信道編碼識別分析不僅在智能通信領(lǐng)域有應(yīng)用前景，尤其是在通信偵察或網(wǎng)絡(luò)對抗領(lǐng)域有迫切的軍事需求［1］。因此，信道編碼的盲識別就成了現(xiàn)在面臨的主要問題。

目前，信道編碼盲識別分析技術(shù)方面的研究大部分都集中在卷積碼的盲識別，對于線性分組碼以及屬于線性分組碼的循環(huán)碼和BCH碼識別一般需要有一定的先驗知識或在一定條件下進(jìn)行。如文獻(xiàn)［2］提出了二進(jìn)制BCH碼的一種識別方法，其基本思路是根據(jù)循環(huán)特性等得到備選多項式；再根據(jù)校正子權(quán)重和最小原則得到最優(yōu)多項式；最后通過因式分解得到生成多項式的最終估計表達(dá)式。但此算法需要在幀長度已知的前提下進(jìn)行，對于碼字的全盲識別還不可行。文獻(xiàn)［3］對低碼率的二進(jìn)制線性分組碼采用碼重分布距離對接收碼字進(jìn)行盲識別。但此算法需要知道碼字起點。文獻(xiàn)［4］針對BCH碼的盲識別問題，提出了基于歐幾里德算法的最大公因式的識別方法，主要是通過求取最大公因式確定碼長，再由系數(shù)矩陣求出生成多項式。但在容錯性方面，此算法具有抗末端誤碼能力，對前段和中段誤碼卻無能為力。文獻(xiàn)［5］利用碼根信息差熵函數(shù)識別BCH碼的碼長，進(jìn)而利用碼根統(tǒng)計獲取生成多項式的整數(shù)根，通過遍歷該域中的本原多項式以尋求滿足BCH碼生成多項式根性質(zhì)的碼根和本原多項式，從而實現(xiàn)BCH碼的盲識別。文獻(xiàn)［6］則提出了BCH碼的一種生成多項式快速識別方法，在采用已有的碼根信息差熵的思想獲得二進(jìn)制本原BCH碼分組長度之后，利用有限域同構(gòu)的原理來求取生成多項式。但文獻(xiàn)［5］和文獻(xiàn)［6］都只對低碼率的碼字有較好的識別效果。文獻(xiàn)［7］主要是利用線性分組碼對偶碼字的統(tǒng)計特性和 Walsh－Hadamard變換解線性方程組，并采用“3倍標(biāo)準(zhǔn)差”準(zhǔn)則給出判決門限，通過判斷對偶空間歸一化維數(shù)的最大值來實現(xiàn)碼長和碼字起點的估計。該算法雖然可以完成對碼長和碼字起點的判別，但運算時間較長，需要多次迭代，導(dǎo)致計算量較大?？梢钥闯?，現(xiàn)有的識別技術(shù)離工程應(yīng)用還有一定的距離，如何在全盲的情況下對線性碼進(jìn)行識別的問題還有待解決。

目前，針對線性分組碼的識別方法，大多要在一定的先驗知識下才能進(jìn)行。如已知碼字起點來識別碼長，無法實現(xiàn)碼字的全盲識別。因此，本文提出了一種利用碼重分布和漢明距離相結(jié)合的方法，在無先驗知識的情況下，識別碼長和碼字起點，進(jìn)而得到生成矩陣或生成多項式，實現(xiàn)線性分組碼的全盲識別。

1 線性分組碼識別基礎(chǔ)

1.1 線性分組碼基礎(chǔ)

定義1 將每k個信息位分為一組進(jìn)行獨立處理，變成長度為n（n＞k）位的編碼稱為（n，k）分組碼，其碼率r＝k／n，校驗位長（n－k）。若校驗位是信息位的線性組合，則稱該編碼為（n，k）線性分組碼［7］。

1.2 盲識別的數(shù)學(xué)模型

對于線性分組碼的盲識別問題，就是在不知道編碼先驗信息的情況下，通過對碼字序列的分析處理，從而估計出其生成矩陣。其數(shù)學(xué)模型描述為：

式中，M＝｛M1，M2，…，Mi，…｝表示以k比特為分組單位的輸入，Mi＝｛M1，M2，…，Mk｝表示第i時刻輸入的k 個比特信息；C＝｛C1，C2，…，Ci，…｝表示以n比特為分組單位的編碼輸出序列，Ci＝｛C1，C2，…，Cn｝表示第i時刻輸出的n個比特信息；G表示生成矩陣。實際中，C是通過對接收或偵察信號解調(diào)處理得到。因此，線性分組碼的盲識別問題就是在僅知道C的前提下如何獲得生成矩陣G，進(jìn)而完成對信息的還原。

線性分組碼識別分析包括的未知參數(shù)有：碼字起點、碼長和生成矩陣。對于截獲到或偵察到的一串經(jīng)過線性分組碼編碼的碼字，我們要從中提取出有用的信息，必須對碼字的編碼形式和編碼參數(shù)進(jìn)行識別。由于截獲數(shù)據(jù)的任意性，我們首先要對接收到的第一個碼字的碼字起點i（0≤i≤n）進(jìn)行判斷，本文稱i為碼組的碼字起點，簡稱碼字起點。

對于一串長度為L的數(shù)據(jù)流，假設(shè)它是（n，k）線性分組碼，在確定了碼字起點i之后，我們就從第i個碼符號開始，對余下的L－i＋1個碼符號進(jìn)行分組，每組長度為n，一共可以得到N＝（L－i＋1）／n」個碼字（·」表示向下取整）。每一個碼字為一行，組成一個N×n的矩陣，通過求解出的i和n可以得到生成矩陣G，從而解出信息序列。因此，求解碼字序列的碼長n和碼字起點i成為了線性分組碼盲識別的關(guān)鍵。

1.3 碼重的理論分析

一個碼字（或任何向量）的Hamming重量等于該碼字中的非零元素的個數(shù)。對（n，k）線性分組碼，定義碼字C的碼重分布W（C）為n＋1個整數(shù)的集合W（C）＝｛Ni＝d，0≤d≤n｝，W （C）表示C 中Hamming重量為d的所有碼組的數(shù)目。重量為d的碼組在C中出現(xiàn)的概率pi就是該重量碼組的碼重分布概率。

定理1 對于一個數(shù)字通信系統(tǒng)，在一個碼組中同時發(fā)生t個錯誤的概率為P（t），則

定理2 （n，k）線性分組碼的k位信息生成的n位碼字集v是n維空間V的子集，且v在V中的分布是非等概率的。

由定理1可知，誤碼對碼組的碼重分布影響很小，所以可根據(jù)碼重分布來對碼長進(jìn)行估計。

對于（n，k）線性分組碼，生成的碼字集大小為2k?2n，k位信息生成的n位碼字的集合必定隸屬于n位碼字組成的碼字集合，前者在后者中的分布是非等概率的。

如若估計碼長不為真實碼長，則分組內(nèi)碼字之間不存在約束關(guān)系，可認(rèn)為0或1是等概率出現(xiàn)的，可假設(shè)此時數(shù)據(jù)的碼重分布是等概率分布模型，不同碼重的碼組出現(xiàn)概率為：

如設(shè)Pi為實際上重量為i的碼組所出現(xiàn)的概率，定義碼重分布距離公式為：

其中，n為估計碼長，D為實際分布與均勻分布的方差距離。由上述定理可知，當(dāng)碼重分布距離D最大時的n 即為真實碼長的估計＾n［1］。

文獻(xiàn)［3］在已知二進(jìn)制線性分組碼碼字起點時，采用碼重分布距離對接收碼字進(jìn)行識別。然而，在未知碼字起點的全盲情況下，難以準(zhǔn)確獲得碼長。

2 基于碼重分布與漢明距離的盲識別方法

根據(jù)上述的理論基礎(chǔ)，本文識別算法的步驟是：首先，根據(jù)碼重分布，判斷出碼長，并粗判斷出碼字起點；然后，在粗判斷出的碼字起點上，利用漢明距離的方法，實現(xiàn)對碼字起點的準(zhǔn)確判斷；最后，由識別出的碼長和碼字起點得到碼字的生成矩陣。具體過程如下。

2.1 碼重的碼長判斷

在全盲情況下，可以對二進(jìn)制線性碼進(jìn)行遍歷識別。當(dāng)遍歷到的碼長準(zhǔn)確時，會出現(xiàn)周期性的峰值，下面對此進(jìn)行分析。

對于接收到的一串長度為L，碼長為n的二進(jìn)制線性分組碼編碼序列，當(dāng)碼字起點與真實碼字起點相差太多或者碼長與真實碼長不一致時，碼重分布類似隨機(jī)，因而很難出現(xiàn)周期性的峰值。當(dāng)碼字起點與真實碼字起點相差不多并且在碼長判斷準(zhǔn)確的情況下，此時，碼字起點判斷錯誤對每組碼字碼重的影響要么沒有，要么很小，所以對整體碼重分布的影響可以忽略不計，碼重分布還會出現(xiàn)周期性的峰值。峰值處對應(yīng)的碼長即為真實碼長，而碼字起點判斷的正確與否則不能斷定，不過必定小于真實值，所以可先進(jìn)行碼字起點的粗判斷。假設(shè)通過遍歷判斷碼長為n的情況，可以得到如式（5）所示的編碼序列。

式（5）中，i為判斷的碼字起點，n是碼長。當(dāng)碼字起點i與碼字序列一致時，碼重便取得固定的幾個值，此時碼重分布距離在碼長n處所對應(yīng)的D取得極大值。當(dāng)碼字起點i與碼字序列存在偏差時，會導(dǎo)致碼重取值的增多，造成碼重分布分散，特別是在i值與碼字序列起點相差越多時，造成碼重分布越分散且極值越不明顯。我們以（15，5）碼字為例，做了碼重分布取得極值與碼字起點關(guān)系圖1。

圖1 碼重分布距離與碼字起點關(guān)系圖Fig.1 Weight distribution distance codeword starting point diagram

從圖1可以看出，當(dāng)Ci與碼字起點一致，即橫坐標(biāo)取值在1點時，碼重分布取最大值；當(dāng)相差7位，取在第8位時，即圖1中橫坐標(biāo)取在8處，此時碼重分布取得最小值。圖2所示的就是i與碼字起點相差3位到1位時的極值取值情況。

因此，可以利用碼重遍歷的方法，在碼重分布出現(xiàn)周期性峰值時準(zhǔn)確判斷出碼長。然而，遍歷的方法還無法精確判斷出碼字起點，因為在實際情況中，存在誤差且受編碼序列隨機(jī)分布的影響，加上相差位數(shù)較多時，造成了極值相差很小。所以，利用碼重只能實現(xiàn)碼字起點的粗判斷。

圖2 碼字起點取不同值時的碼重分布情況Fig.2 Codeword starting point for different values of code weight distribution

2.2 漢明距離的碼字起點精確識別

設(shè)xi和yi是由碼符號集｛0，1｝中的碼符號“0”和“1”組成的長度為n的兩個符號序列

其中xi1，xi2，…，xin∈ ｛0，1｝；yi1，yi2，…，yin∈ ｛0，1｝。xi和yi之間相同時刻的不同碼符號的位置數(shù)dH（xi，yi）稱為xi和yi之間的漢明距離。

最小漢明距離d0是（n，k）分組碼的一個重要參數(shù)，它表明了分組碼抗干擾能力的大小，糾錯碼的基本任務(wù)之一就是構(gòu)造出碼率R一定，d0盡可能大的碼。線性分組碼碼字之間的漢明距離一定大于等于該分組碼的最小距離和非零碼字的最小重量。

在糾錯編碼領(lǐng)域里，設(shè)計最差的分組碼的性能是只檢測和糾正1個隨機(jī)錯誤，即e＝1。對于任意（n，k）分組碼，若要在碼字內(nèi)：1）檢測e個隨機(jī)錯誤，則要求碼的最小距離d0≥e＋1；2）糾正t個隨機(jī)錯誤，則要求d0≥2t＋1［8］。因此分組碼的最小距離d0≥3。分組碼要有檢測和糾正的作用，最小距離d0一定不等于1。

對于上述已經(jīng)精確判斷出碼長n和粗判斷出碼字起點i的碼字序列，從碼字起點i開始，按照碼長n對序列進(jìn)行劃分，并畫出劃分后碼字之間的漢明距離分布圖。判斷在漢明距離為1和2的位置處是否有分布，若有分布，則碼字起點向后移一位，繼續(xù)判斷，直到漢明距離為1和2處沒有分布為止。此時的碼字起點i即為正確的碼字起點。

2.3 識別生成矩陣

對于一個二元域GF（2）上的（n，k）線性分組碼，可以由k個線性獨立的碼字組成的基底張成。把這k個線性獨立的碼字按行排列，即可得到（n，k）線性分組碼的生成矩陣G。因此，對于一組編碼后的碼字，要想得到它的生成矩陣G，只要從中找出k個線性獨立的碼字即可。

在碼字起點和碼長已知的情況下，就可以用碼長對接收序列進(jìn)行劃分，選取一定數(shù)目的碼字建立待化簡矩陣G′，通過對G′進(jìn)行二進(jìn)制運算的化簡，求出矩陣的k個最大線性無關(guān)向量，即得到生成矩陣G［8］。

為了避免誤碼情況對結(jié)果的影響，可以進(jìn)行多次化簡計算，選取出現(xiàn)概率最高的一組最大線性無關(guān)向量組作為生成矩陣，從而完成對生成矩陣的識別［8］。

3 仿真實驗

3.1 實驗一 編碼參數(shù)的識別

為了說明本文算法的有效性，使用matlab軟件，隨機(jī)產(chǎn)生碼長為n的碼字序列進(jìn)行編碼識別。各選取1 160組碼字，對（7，4）、（15，5）和（31，16）三組典型的二進(jìn)制線性分組碼進(jìn)行識別：

1）基于碼重分布的碼長判斷

如圖3所示的是（7，4）、（15，5）和（31，16）三種典型的二進(jìn)制線性分組碼的碼重分布情況。可以發(fā)現(xiàn)，在三組圖片中，當(dāng)碼長n識別正確時，碼長n及碼長整數(shù)倍an（a∈N）處所對應(yīng)的碼重分布取到峰值。因為，此時的碼長為真實碼長，分組內(nèi)碼字之間存在約束關(guān)系，所以各碼重的出現(xiàn)不存在隨機(jī)性，此時的方差距離D取到極大值，因此可以將其判斷為真實碼長。

圖3 三種不同的二進(jìn)制線性分組碼的碼重分布情況Fig.3 Three different binary linear block code's code weight distribution

2）基于漢明距離的碼字起點判斷

如圖4所示的是（7，4）、（15，5）和（31，16）三種典型的二進(jìn)制線性分組碼的漢明距離分布情況。在無誤碼的情況下，當(dāng)碼字起點判斷正確時，各個碼組內(nèi)存在線性約束關(guān)系，且這三種碼字都有檢錯糾錯能力，因此，最小漢明距離d0≥3。所以，在d0＝1和d0＝2的位置處，漢明距離的分布應(yīng)該等于零。由圖4也可以看出，雖然三種碼字的糾錯能力不同，導(dǎo)致漢明距離的分布情況不同，但總體趨勢還是一致的，即漢明距離分布的取值主要集中在某幾點處，且在低值處的分布都為零。若碼字起點判斷錯誤，此時的編碼不具有檢錯與糾錯的能力，漢明距離的分布在各個取值處也就相對平均。因此，運用漢明距離的分布可以正確地判斷出碼字起點。

圖4 三種不同的二進(jìn)制線性分組碼的漢明距離分布情況Fig.4 Three different binary linear block code's Hamming distance distribution

3）生成矩陣的獲取

對于線性分組碼，在知道了碼長和碼字起點以后，就能很容易地求得生成矩陣。在起點處，以碼長劃分線性分組碼序列，選取一定數(shù)量互不相同的碼字組成待化簡矩陣G′，對矩陣進(jìn)行基于二進(jìn)制運算的化簡，最終得到以上三組序列的生成矩陣為：

3.2 實驗二 誤碼的影響

在上述的實驗條件下，本文加入了誤碼，并仿真了在誤碼率不斷升高的情況下對識別效果的影響。

圖5所示的是（7，4）線性分組碼、（15，5）線性分組碼和（31，16）線性分組碼在誤碼率不斷升高的情況下，能夠成功識別的概率圖?？梢钥闯?，在誤碼率小于1%的情況下，（7，4）線性分組碼和（31，16）線性分組碼成功識別的比例在90%左右，而（15，5）線性分組碼成功識別的概率可以達(dá)到100%。隨著誤碼率的升高，（15，5）線性分組碼的抗噪性能要好得多，而（7，4）線性分組碼和（31，16）線性分組碼在誤碼率接近2%的時候，識別的成功率也在50%左右，所以該方法具有較好的容錯性能和較高的實際應(yīng)用價值。

圖5 存在誤碼下的識別概率Fig.5 Presence of the bit error probability of identification

4 結(jié)論

本文提出了基于碼重分布與漢明距離的線性分組碼盲識別方法。該方法利用碼組內(nèi)碼重分布不等概的性質(zhì)，通過觀察碼重分布的極值取值情況，來判斷出正確的碼長并初步判斷出碼字起點；接著，從已判斷出的碼字起點開始，利用糾錯碼的糾錯能力與漢明距離之間關(guān)系的性質(zhì)，利用漢明距離的分布，準(zhǔn)確判斷出碼字起點，進(jìn)而完成對線性分組碼的盲識別。仿真實驗表明，在誤碼率一定的情況下，以上的方法仍可以很好地識別出低碼率的二進(jìn)制線性分組碼。但隨著識別碼字碼長的增加，計算量會不斷增大，導(dǎo)致運算時間變長，所以算法還有待改進(jìn)優(yōu)化。

［1］張永光，樓才義.信道編碼及其識別分析［M］.北京：電子工業(yè)出版社，2010.

［2］王甲峰，岳旸，權(quán)友波.二進(jìn)制BCH碼的一種盲識別方法［J］.信息與電子工程，2011，9（5）：591－595.WANG Jiafeng，YUE Yang，QUAN Youbo.Blind recognition method of binary BCH code［J］.Information and Electronic Engineering，2011，9（5）：591－595.

［3］昝俊軍，李艷斌.低碼率二進(jìn)制線性分組碼的盲識別［J］.無線電工程，2009，39（1）：19－22.ZAN Junjun，LI Yanbin.Blind recognition of low coderate binary linear block code ［J］.Radio Engineering.2009，39（1）：19－22

［4］王蘭勛，李丹芳，汪洋.二進(jìn)制本原BCH碼的參數(shù)盲識別［J］.河北大學(xué)學(xué)報，2012，32（4）：416－428.WANG Lanxun，LI Danfang，WANG Yang.Blind recognition of binary primitive BCH codes parameters［J］.Journal of Hebei University，2012，32（4）：416－428

［5］楊曉靜，聞年成.基于碼根信息差熵和碼根統(tǒng)計的BCH碼識別方法［J］.探測與控制學(xué)報，2010，32（3）：69－73.YANG Xiaojing，WEN Niancheng.Recognition method of BCH codes based on roots information dispersion entropy and roots statistic［J］.Journal of Detection ＆ Control，2010，32（3）：69－73.

［6］呂喜在，黃芝平，蘇紹璟.BCH碼生成多項式快速識別方法［J］.西安電子科技大學(xué)學(xué)報，2011，38（6）：159－172.LV Xizai，HUANG Zhiping，SU Shaojing.Fast recognition method for generator polynomial of BCH codes［J］.Journal of Xidian University.2011，38（6）：159－172.

［7］楊曉煒，甘露.基于 Walsh－Hadamard變換的線性分組碼參數(shù)盲估計算法［J］.電子與信息學(xué)報，2012，34（7）：1643－1646.YANG Xiaowei，GAN Lu.Blind estimation algorithm of the linear block codes parameters based on WHT［J］.Journal of Electronics ＆Information Technology.2012，34（7）：1643－1646.

［8］閆郁翰，湯建龍.基于漢明距離的二進(jìn)制線性分組碼盲識別方法［J］.通信對抗，2011（4）：20－23.YAN Yuhan，TANG Jianlong.Blind recognition method of binary linear block codes based on hamming distance［J］.Communication Countermeasures，2011（4）：20－23.