基于游程間隔特征的線性分組碼碼長識別方法

李歆昊，張 旻，陸 凱，呂全通

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

0 引言

為了實現(xiàn)通信的可靠性，并提高通信的效率，信道編碼在現(xiàn)代通信中得到了普遍的應(yīng)用。如在智能移動通信、多點廣播通信、認(rèn)知無線電和認(rèn)知通信領(lǐng)域，都需要接收方僅根據(jù)接收的未知數(shù)據(jù)快速識別出信道編碼參數(shù)；此外，在非合作的通信條件下，信道編碼識別可以準(zhǔn)確獲取編碼參數(shù)從而完成信息的還原，因此在通信偵察和網(wǎng)絡(luò)對抗領(lǐng)域也有著迫切的軍事需求。信道編碼識別已經(jīng)成為目前國內(nèi)外研究的熱點問題［1］。

信道編碼主要分為線性分組碼和卷積碼，其中線性分組碼被廣泛應(yīng)用在數(shù)字通信系統(tǒng)和衛(wèi)星通信系統(tǒng)中［2］。但目前對信道編碼識別的研究還主要集中在卷積碼上，對線性分組碼的識別偶有涉及，且深度遠(yuǎn)遠(yuǎn)不夠［1］。而且信道編碼的識別分析主要停留在有限先驗知識的情況下進(jìn)行［3-9］，真正的全盲識別分析還不多。如在已知碼字起點的基礎(chǔ)上，通過碼重分布距離的方法完成對線性分組碼的盲識別［3］；在碼長已知的前提下利用高斯解方程和綜合分析法，實現(xiàn)線性分組碼的盲識別［1］。文獻(xiàn)［8］雖然利用線性分組碼對偶碼字的統(tǒng)計特性和Walsh-Hadamard變換實現(xiàn)了全盲識別，但算法對誤碼率要求過高，距離實際應(yīng)用還有較大差距?？梢姡壳坝行У男诺谰幋a盲識別是在已知碼長或碼字起點的基礎(chǔ)上完成對生成矩陣或生成多項式的識別，而實際分組序列的碼字起始點往往難以獲得，因此獲取碼長后再對碼字進(jìn)行盲識別就具有十分重要的意義。

本文針對現(xiàn)有識別算法中存在的對接收序列誤碼率要求高和需要一定先驗知識的不足，提出了基于游程間隔特征的碼長識別方法。算法通過統(tǒng)計接收序列的游程間隔分布實現(xiàn)了對碼長的識別，與現(xiàn)有的單位化矩陣求秩相比，本文算法可以極大地降低計算量且提高了識別效率和算法的魯棒性，具有較好的抗誤碼性能。

1 線性分組碼的基本概念

1.1 線性分組碼的定義

定義1：將信息碼元分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼。若每個監(jiān)督碼元都是由碼組中某些信息碼元線性相加得到的，則稱這樣的分組碼為線性分組碼［9］。

定義2：GF（q）上的n維線性空間Vn中的k維子空間Vn，k構(gòu)成的碼字稱為（n，k）線性分組碼［10］。

顯然，在二進(jìn)制下，2n個n維組成了一個GF（2）上的n 維線性空間，2k個碼字集合構(gòu)成了一個k 維線性子空間。而這2k個碼字完全可由k 個相互獨立碼字構(gòu)成的一組基線性表示出來，如果把這個基寫成矩陣形式G，即稱為（n，k）碼的生成矩陣，它的秩是k，k／n就是編碼碼率。

1.2 線性分組碼碼長的定義

對于線性分組碼的碼長識別問題，首先要了解碼字的產(chǎn)生方式，然后通過對碼字序列的分析處理，從而估計出碼長。其數(shù)學(xué)模型描述為：

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

2 基于游程間隔的碼長識別

2.1 游程的基本概念

定義3：設(shè)a是GF（2）上周期為v的周期序列，將a的一個周期a= （a0，a1，a2，…，av-1）依次按循環(huán)排列，使av-1與a0相鄰，則把如100…001 和011…110的一連串兩兩相鄰的項分別稱為a的一個周期中的一個0游程和1游程。0游程中的0的個數(shù)或1游程中1的個數(shù)稱為這個游程的長［1］。

2.2 游程間隔的基本概念

定義4：相同游程長度下前后相鄰的兩兩0游程或1游程之間間隔的碼元數(shù)稱為游程間隔［1］。

對長度為L 的（n，k）線性分組碼編碼序列，定義碼字C 的游程間隔H（C）是x（x ＜L）個整數(shù)的集合H（C）=｛Ni，1≤i≤x｝，Ni表示C 中游程間隔為i的數(shù)目。

2.3 線性分組碼的游程間隔特性

定理1：（n，k）線性分組碼的k位信息生成的n位碼字集v是n 維空間V 的子集，且每組碼字的校驗位由該組的信息位唯一確定［1］。

對于（n，k）線性分組碼，生成的碼字集大小為2k?2n，k位信息生成的n位碼字的集合必定隸屬于n位碼字組成的碼字集合。其中k位信息碼元共有2k個不同組合，輸出的碼字矢量也應(yīng)當(dāng)有2k種，如圖1（a）所示；長度為n的二元隨機(jī)序列共有2n個可能的碼字矢量，如圖1（b）所示?？梢姡╪，k）編碼有2n-2k個禁用碼字，破壞了線性分組碼的隨機(jī)特性，導(dǎo)致線性分組碼的隨機(jī)性能變差。

圖1 碼字分布圖Fig.1 Code word distribution

由于游程長度t與信息位長度k 的關(guān)系直接影響到游程間隔的分布，而游程間隔的分布對于碼長的識別又起到了關(guān)鍵的作用。因此，分析游程長度t與信息位長度k 之間存在以下三種可能：

t＜k

當(dāng)游程長度小于信息位長度時，游程長度為t的0游程或1游程可能在一個碼字的信息位和監(jiān)督位中都出現(xiàn)，如圖2（a）所示（此時t=1）；還可能在多個碼字中同時出現(xiàn)，如圖2（b）所示（此時t=3）。此時的游程間隔分布沒有周期性且比較隨機(jī)；

n＞t≥k

由于游程長度大于等于信息位長度、小于碼長時的監(jiān)督位很難出現(xiàn)多個連續(xù)的0和1，所以僅在t≈k時，游程長度為t的0游程或1游程才會在某兩個碼字首尾相接處出現(xiàn)，如圖2（c）所示（此時t=6）。此時的游程間隔呈現(xiàn)周期分布特征，且在碼長整數(shù)倍的位置上，游程間隔分布取得峰值。

3）t＞n

當(dāng)游程長度大于碼長時，隨著游程長度的增加，此時游程長度為t的0游程或1游程出現(xiàn)的次數(shù)極少甚至不出現(xiàn)，即便是在兩個碼字首尾相接處，因為信息位和監(jiān)督位很難出現(xiàn)連續(xù)的0和1，所以滿足條件的0游程和1游程也很難出現(xiàn)。

圖2 游程間隔分布Fig.2 Run interval distribution

由以上分析可知，僅在游程長度大于等于信息位長度時，游程間隔才呈現(xiàn)周期分布的特征，而且周期長度等于碼長。

2.4 游程間隔的碼長識別

對于接收到的一串長度為L，碼長為n 的二進(jìn)制線性分組碼編碼序列，將其按照游程長度t劃分，統(tǒng)計1游程的游程間隔分布。從編碼序列的第一位開始，尋找游程長度為t的1游程，記錄下滿足條件的游程起點，并繼續(xù)搜尋下一起點，計算兩點之間的間隔碼元數(shù)。按照以上方法，依次遍歷每個碼元位置，計算所有可能的間隔碼元數(shù)，統(tǒng)計相同間隔碼元數(shù)出現(xiàn)的次數(shù)，得到1游程的游程間隔分布。按照同樣的方法統(tǒng)計0游程的間隔分布，最后繪制圖形識別碼長。具體識別步驟如下：步驟1）初始化游程長度t，提取編碼序列的0 游程和1 游程的游程間隔H（C）；步驟2）利用步驟1）得到的游程間隔H（C）繪制游程間隔分布圖，并進(jìn)行周期峰值檢測，如未檢測到周期峰值，游程長度加1，返回步驟1）；步驟3）繼續(xù)提取相應(yīng)游程長度下的游程間隔H（C），直到出現(xiàn)周期性峰值；步驟4）當(dāng)檢測到周期峰值時，此時對應(yīng)的周期即為碼長n，完成識別。

3 仿真實驗

為了驗證算法的有效性，使用matlab軟件進(jìn)行仿真實驗。按照上文的算法，本文針對線性分組碼分別產(chǎn)生了10萬組四種不同的碼字進(jìn)行游程間隔的仿真對比實驗，并選取其中三種碼字在不同誤碼率的情況下作了抗誤碼性能的分析，實驗結(jié)果驗證了本文算法的有效性和魯棒性。

3.1 線性分組碼的碼長識別

3.1.1 游程間隔的周期特性

選?。?，3）線性碼10萬組，統(tǒng)計游程長度為2、3、4且無誤碼情況下的游程間隔分布情況，結(jié)果如圖3所示。

當(dāng)游程長度為2小于信息位長度時，游程間隔分布集中在間隔長度為4處，且隨著間隔長度的增加，游程間隔數(shù)量的取值越來越少，沒有出現(xiàn)周期性特征，如圖3（a）所示；當(dāng)游程長度為4和3大于等于信息位長度時，游程間隔分布在碼長整數(shù)倍的位置上都取得峰值，游程間隔分布出現(xiàn)周期性特征，如圖3（b）、圖3（c）所示。當(dāng)游程長度繼續(xù)增加，游程間隔分布的周期性特征也逐漸消失，與上文分析結(jié)果一致。

圖3 （6，3）線性分組碼游程間隔特征Fig.3 Run interval feature of（6，3）linear block code

3.1.2 碼長的識別

選?。?，4）、（8，4）和（15，5）線性碼各10萬組，統(tǒng)計游程長度為4、4、5且無誤碼情況下的游程間隔分布情況，（7，4）碼和（8，4）碼的游程間隔取前50位值，（15，5）碼的游程間隔取前200位，結(jié)果如圖4所示。

游程長度分別為4、4和5，此時三組碼字的游程長度都等于信息位長度。圖4（a）中，在間隔長度為14、21、28等7的整數(shù)倍位置上游程間隔分布取得峰值；圖4（b）中，在間隔長度為16、24、32等8的整數(shù)倍位置上游程間隔分布取得峰值；圖4（c）中，在間隔長度為30、45、60等15的整數(shù)倍位置上游程間隔分布取得峰值。三組圖片中，游程間隔分布都周期性的出現(xiàn)了峰值，而此周期的長度即等于待識別序列的碼長。

圖4 三組線性分組碼游程間隔特征Fig.4 Run interval feature of 3different linear block code

圖5 誤碼影響Fig.5 BER impact

3.2 誤碼性能分析

3.2.1 誤碼影響

選?。?，3）、（7，4）和（8，4）線性碼各10萬組，在不同誤碼率情況下各進(jìn)行50的蒙特卡洛仿真實驗。圖5所示的是三種碼字在誤碼率不斷升高的情況下，能夠成功識別的概率圖?？梢钥闯?，在誤碼率小于3%的情況下，三種碼長成功識別的概率都在50%以上，其中（6，3）線性碼的最高。隨著誤碼率的不斷升高，成功識別的概率有所下降。

3.2.2 性能比較

選?。?，3）線性碼10萬組，分別利用單位化矩陣求秩算法和游程間隔分析法在不同誤碼率的情況下各進(jìn)行50次的蒙特卡洛仿真實驗。由圖6可知，在誤碼率等于1%時，游程間隔分析法成功識別的概率達(dá)到了100%，而單位化矩陣求秩算法成功識別的概率在65%左右。隨著誤碼率的升高，當(dāng)誤碼率達(dá)到2%時，單位化矩陣求秩算法成功識別的概率接近0，已無法保證正確識別，而游程間隔分析法在誤碼率達(dá)到6%時仍然保持了90%的高識別率。可以看出，本文算法具有更好的容錯性能和更高的實際應(yīng)用價值。

圖6 性能比較Fig.6 Performance comparison

4 結(jié)論

本文提出了基于游程間隔的線性分組碼盲識別方法。該方法根據(jù)線性分組碼的結(jié)構(gòu)特征和理論分析，得到了隱藏在0-1序列內(nèi)的游程間隔在游程長度大于等于信息位長度時會呈現(xiàn)周期性的特征。利用上述特征，通過統(tǒng)計不同游程長度下游程間隔的數(shù)量得到游程間隔的周期分布并從中提取出周期長度，實現(xiàn)對線性分組碼碼長的識別。由于信息位長度較短，所以算法無需完全遍歷，計算復(fù)雜度低。仿真實驗表明，在誤碼率一定的情況下，以上的方法仍可以很好地識別出線性分組碼，具有一定的工程應(yīng)用價值。在后續(xù)的研究中，我們將對算法進(jìn)行改進(jìn)，并嘗試將其應(yīng)用在其他碼型的參數(shù)識別中。

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

［2］解輝，黃知濤，王豐華.信道編碼盲識別技術(shù)研究進(jìn)展［J］.電子學(xué)報，2013，（6）：1166-1176

［3］昝俊軍，李艷斌 .低碼率二進(jìn)制線性分組碼的盲識別［J］.無線電工程，2009，39（1）：19-22.

［4］王甲峰，岳旸，權(quán)友波.二進(jìn)制BCH 碼的一種盲識別方法［J］.信息與電子工程，2011，9（5）：591-595.

［5］王蘭勛，李丹芳，汪洋.二進(jìn)制本原BCH 碼的參數(shù)盲識別［J］.河北大學(xué)學(xué)報，2012，32（4）：416-428.

［6］楊曉靜，聞年成.基于碼根信息差熵和碼根統(tǒng)計的BCH碼識別方法［J］.探測與控制學(xué)報，2010，32（3）：69-73.

［7］Cluzeau M，F(xiàn)iniasz M.Recovering a code length and synchronization from a noisy international［C］／／Symposium on Information Theory.Seoul：ISIT，2009：1-5.

［8］楊曉煒，甘露.基于Walsh-Hadamard變換的線性分組碼參數(shù)盲估計算法［J］.電子與信息學(xué)報，2012，34（7）：1643-1646.

［9］WANG F H，HUANG Z T，ZHOU Y Y.A method for blind recognition of convolution code based on Euclidean algorithm［C］／／IEEE International Conference on Wireless Communications.Shanghai：IEEE Press，2007：1414-1417.

［10］王新梅，肖國鎮(zhèn).糾錯碼——原理與方法［M］.西安：西安電子科大出版社，2001.