(重慶郵電大學(xué) 信號與信息處理重慶市重點實驗室，重慶 400065)

基于分塊矩陣變換的線性分組碼盲識別*

趙 亮**，張?zhí)祢U，楊 強

(重慶郵電大學(xué) 信號與信息處理重慶市重點實驗室，重慶 400065)

為了解決傳統(tǒng)矩陣分析方法存在的誤碼擴散問題，提出了一種基于分塊矩陣變換的線性分組碼盲識別方法。首先，將截獲序列按照估計碼長構(gòu)造出分析矩陣，將分析矩陣分塊后分別進行矩陣下三角變換；然后，以各列列重為度量，根據(jù)相關(guān)列重量的統(tǒng)計分布特性設(shè)置相關(guān)列閾值，并統(tǒng)計出符合閾值的相關(guān)列的個數(shù)，當(dāng)相關(guān)列的個數(shù)最大時即為真實碼長的情況。該方法還可以識別碼字同步點，識別方法簡單。理論分析及仿真結(jié)果表明，該識別方法的容錯性能較好，在誤碼為5%的條件下，對(15,7)線性分組碼的正確識別率依然能達到80%。

線性分組碼；盲識別；分塊矩陣變換；相關(guān)列

1 引 言

分組碼包括線性分組碼和非線性分組碼，線性分組碼是重要的一種，它具有良好的檢錯和糾錯能力。在實際工程領(lǐng)域，信息傳輸過程中不可避免地要受到信道中噪聲的影響，使傳輸?shù)男畔l(fā)生誤碼。為了提高通信系統(tǒng)的可靠性，可引入糾錯編碼的方法，對需要傳輸?shù)男畔⑦M行編碼，為其加入一些冗余校驗比特，使其具有一定的抗誤碼能力。在信息對抗和電子偵察領(lǐng)域，如何通過截獲的數(shù)據(jù)，快速準確地識別出傳輸數(shù)據(jù)的編碼參數(shù)，進而獲取信息，是一個具有重要現(xiàn)實意義的問題[1-3]。

文獻[4]對分析矩陣求秩獲取碼長和碼率，但只考慮理想信道而沒有考慮誤碼的影響。文獻[5]利用漢明距離出現(xiàn)的概率分布和隨機序列的漢明距離出現(xiàn)的概率分布相比較，偏移量越大，說明線性約束的關(guān)系越強，可以識別碼長和碼字起點，進而識別生成矩陣；且與碼重分析法相比，識別結(jié)果清晰，在真實碼長位置才出現(xiàn)峰值，其他位置不會出現(xiàn)峰值。但上述兩種方法都未考慮誤碼的影響。文獻[6]提出基于歐幾里得算法的最大公因式識別算法，該方法在有誤碼時需要大量的分析數(shù)據(jù)。文獻[7]首次提出碼根信息熵的概念，利用碼根統(tǒng)計的方法解決了誤碼條件下的二進制本原BCH碼盲識別問題，但識別的計算量較大。文獻[8]利用碼根信息熵的思想獲得碼長以后，根據(jù)有限域同構(gòu)的原理，利用統(tǒng)計得到的碼根經(jīng)過有限域乘法并化簡直接求出BCH碼的生成多項式，但計算復(fù)雜度較高。文獻[6-8]中的識別方法只限于對線性分組碼的子類BCH碼的識別，適用范圍比較局限。文獻[13]首次引入數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘算法，但容錯性能較差，不能很好地適用于在高誤碼率下對線性分組碼的盲識別。

針對上述問題，本文提出了一種基于分塊矩陣變換的識別方法。首先根據(jù)估計碼長，對截獲序列構(gòu)造分析矩陣，再將分析矩陣進行分塊，在每個矩陣塊中做矩陣變換，以達到抑制誤碼擴散的目的。在無誤碼的情況下，校驗位所在的列可以被化為全零列，稱其為相關(guān)列，信息位所在列為獨立列。然后以各列的重量為度量，根據(jù)相關(guān)列和獨立列的列重的統(tǒng)計分布特性，設(shè)置閾值判斷各列是否為相關(guān)列，統(tǒng)計相關(guān)列的個數(shù)，當(dāng)相關(guān)列個數(shù)最大時，即為真實碼長的情況。碼長識別出來以后，通過循環(huán)移位，按照碼長識別的方法，當(dāng)相關(guān)列個數(shù)最大時即為正確碼字起點。本方法適用于多種碼率的線性分組碼參數(shù)識別，運算復(fù)雜度相對較低，且容錯性能較好。

2 線性分組碼盲識別原理

定義1[2]在GF(2)上的2k個k維信息向量可以生成2k個二進制的n維向量，它們的集合構(gòu)成(n,k)線性分組碼。k維信息向量也叫做信息位，生成的n維向量叫做其對應(yīng)的碼字。線性分組碼構(gòu)成了GF(2)上n維線性空間的k維子空間。

由于常用的線性分組碼碼字都是系統(tǒng)碼，所以c=(c1,c2,…,ck,…,cn)的前k位就是信息位u=(u1,u2,…,uk),碼字的后k位(c1+k,c2+k,…,cn)就是校驗位。對線性分組碼有

c=uG。

(1)

式中：G表示(n,k)線性分組碼的生成矩陣。

生成矩陣確定了信息位和校驗位的線性映射關(guān)系，不同的編碼方式使用的生成矩陣不同，也就有不同的映射關(guān)系,但是(n,k)線性分組碼的2k個碼字必定由對應(yīng)的k個信息比特位構(gòu)成的獨立向量線性表示。由此可知，碼字c中的(n-k)位校驗位是k位信息位的線性組合。因此,將碼字按真實碼長排列成矩陣形式，進行矩陣變換以后，校驗位對應(yīng)的列將被化為全零列，稱校驗位所在的列為相關(guān)列，信息位所在列為獨立列。在真實碼長和碼字正確起點時，碼字之間的信息位和校驗位對齊，可以被化為全零列的列數(shù)最多，即此時相關(guān)列最多。而在非真實碼長時信息位和校驗位未對齊，不存在相關(guān)列，在無誤碼時就沒有能夠化為全零的列存在；有誤碼時，不存在0的比例比1的比例大的列。本文就是基于這個思想提出了碼長和同步點的識別算法。本文中考慮的信息傳輸信道是二進制對稱信道(Binary Symmetric Channel,BSC)，這是一種無記憶信道，即二進制符號數(shù)據(jù)序列在傳輸過程中前后出現(xiàn)的錯誤是相互無關(guān)的。對于線性分組碼，其碼字之間的約束關(guān)系僅限于碼長范圍以內(nèi)，不受信道中的誤碼影響。

傳統(tǒng)的矩陣分析方法，將矩陣變?yōu)橄氯蔷仃嚨牟僮?，對矩陣整體進行行變換和列變換，雖然互換行、列只是交換碼字或者碼元的位置，均不會改變信息位和校驗位的線性約束關(guān)系，也不會造成誤碼擴散，但是行之間的模2加會造成誤碼在碼字之間傳播，列之間的模2加會造成誤碼在碼字內(nèi)的擴散。基于傳統(tǒng)方法改進后提出的高斯列消元方法，在矩陣變換時只使用列操作，避免了錯誤碼元在碼字之間的傳播，但依然存在較為嚴重的誤碼擴散現(xiàn)象。為了抑制這種現(xiàn)象，可以利用分塊處理的思想，為分析矩陣按行分塊，分別在每個矩陣塊內(nèi)進行矩陣變換，誤碼影響只在窗內(nèi)傳播并不影響其他窗內(nèi)的碼字，而且矩陣塊的規(guī)模越小，誤碼傳播范圍就越小。

算法步驟如下：

Step3 記X1為對A1處理后的下三角矩陣。依次對At(t=2,3,…,c)，進行上述處理，直到處理完Ac。

Step4 記錄經(jīng)過矩陣變換后的矩陣X=(X1,X2,…,Xc)T，并統(tǒng)計其各列的重量W=(w1,w2,…wc)。

3 統(tǒng)計特性分析及閾值的設(shè)置

當(dāng)xj是相關(guān)列時，

(2)

(3)

則xj的重量wj服從伯努利分布B(m,(1-(1-2pe)wb)/2),wb是其對偶向量的重量;

當(dāng)xj是獨立列時,

(4)

(5)

則xj的重量wj服從伯努利分布B(m,1/2),其中，

(6)

取碼字個數(shù)m=400，pe=0.12，wb=4，相關(guān)列和獨立列的列重wj的概率分布圖如圖1所示。

圖1 相關(guān)列和獨立列的重量wj對應(yīng)的概率分布圖Fig.1 The corresponding wj′s probability distribution of dependent column and independent column

在每個估計碼長下，對矩陣X進行循環(huán)移位，記每次移位的矩陣A(n0,d)，d為移位數(shù)，且0≤d≤n-1。

定義識別的數(shù)學(xué)模型：

φ(j)=wj/(m/2)=2wj/m。

(7)

經(jīng)過分析可以知道，φ(j)越小，xj的重量越小，1的比例越低，也越符合相關(guān)列的情況;反之，則符合獨立列。因此,設(shè)置閾值T，當(dāng)φ(j)≤T時，判定為相關(guān)列;反之則判定為獨立列。對每個移位矩陣A(n0,d)都有相關(guān)列的集合：

{j1,j2,…,jΘn0,d|φ(j)≤T} 。

(8)

式中：ji表示滿足閾值T的列所在位置。當(dāng)真實碼長和正確同步點時，集合的基數(shù)Θn,d達到最大，即相關(guān)列的數(shù)目最多。

對每一個估計碼長下相關(guān)列個數(shù)集合的Θn,d歸一化處理，有

(9)

可知，當(dāng)n0=αn(α∈+)時，n0為極大值。取α=1時的n0為碼長，即第一個極大值出現(xiàn)的位置就是真實碼長的位置。

對最優(yōu)閾值的求解如下：

令虛警概率為Pfa,漏警概率為Pnd，則

(10)

(11)

令

P=Pfa+Pnd,

(12)

定義閾值T使得概率P達到極小值,得

(13)

其中:

(14)

(15)

c=m[1-(1-2pe)wb](1-2pe)wb-

(16)

(17)

對于服從標準正態(tài)分布的變量x～N(0,1)，數(shù)學(xué)上認為|x|≥0.39是不可能事件，所以需要有

(18)

則取閾值為

T=min(T1,T2) 。

(19)

綜合以上分析，本文算法的流程圖如圖2所示。

圖2 算法流程圖Fig.2 Flow chart of the proposed algorithm

4 仿真分析

對(7,4)循環(huán)碼進行碼長和同步點的識別，仿真參數(shù)為：數(shù)據(jù)截獲長度300 bit,同步點5，誤碼率0.02。識別結(jié)果分別如圖3和圖4所示。

圖3 (7,4)循環(huán)碼的碼長識別結(jié)果Fig.3 Recognition result of (7,4) cyclic code

圖4 (7,4)循環(huán)碼碼字起點識別結(jié)果Fig.4 Recognition result of the code start bit for (7,4) cyclic code

識別出正確碼長后，按正確碼長構(gòu)造分析矩陣，經(jīng)過矩陣變換后，統(tǒng)計各種移位情況下的Θ值。從圖4可以看出，Θ的值在移位值為5時取得最大值，識別碼字起點為5，識別結(jié)果正確。

對(15,7)循環(huán)碼進行識別，仿真參數(shù)為：截獲數(shù)據(jù)長度300 bit，同步點13，誤碼率0.02。碼長和同步點的識別結(jié)果分別如圖5和圖6所示。

圖5 (15,7)循環(huán)碼的碼長識別結(jié)果Fig.5 Recognition result of(15,7) cyclic code

圖6 (15,7)循環(huán)碼碼字起點識別結(jié)果Fig.6 Recognition result of the code start bit for (15,7) cyclic code

識別出碼字長度為15以后，繼續(xù)估計碼字起始點，如圖6所示，在移位數(shù)為13時，Θ取得最大值，識別碼字起點為13，識別結(jié)果正確。

從以上(7,4)循環(huán)碼和(15,7)循環(huán)碼的識別情況可以看出，當(dāng)識別碼字起點時，Θ取得最大值所在的移位數(shù)即為正確碼字起點。但是,有時識別碼字起始點時，Θ的最大值不唯一，此時就需對其進行多次識別然后取均值，找到最大值唯一的情況。

在pe=0.02下對序列進行(15,11)循環(huán)碼編碼，識別出碼長后，識別碼字起點的結(jié)果如圖7所示。

圖7 (15,11)循環(huán)碼碼字起點識別結(jié)果Fig.7 Recognition result of the code start bit for (15,11) cyclic code

此時，最大值不止一個，在11、12、13處均有最大值。選取這三處的移位情況做多次求解Θ的值后做均值，次數(shù)為15次時識別結(jié)果如圖8所示。

圖8 (15,11)循環(huán)碼碼字起點最后的識別結(jié)果Fig.8 Final recognition result of the code start bit for (15,11) cyclic code

下面針對不同碼長的碼字進行仿真分析，分別選取(7,3)循環(huán)碼、(7,4)循環(huán)碼、(15,7)循環(huán)碼、(15,11)循環(huán)碼進行分析，在不同誤碼率下做100次蒙特卡洛仿真，仿真參數(shù)設(shè)置如表1所示，識別概率見圖9。

表1 對不同碼型識別性能實驗的仿真參數(shù)Tab.1 Simulation parameter

圖9 算法在不同誤碼率下的正確識別率Fig.9 The correct recognition rate of the algorithm under different bit error rate

從圖9可以看出，(7,4)循環(huán)碼、(7,3)循環(huán)碼比(15,7)循環(huán)碼、(15,11)循環(huán)碼的識別效果好,說明對于本算法來說，碼長越長，識別效果越差。(7,3)循環(huán)碼、(15,7)循環(huán)碼分別比(7,4)循環(huán)碼、(15,11)循環(huán)碼的識別效果好，說明碼率越高識別效果越差。對于(7,3)循環(huán)碼，在誤碼率為0.09時識別概率依然可以達到80%以上。

圖10給出了3種算法對(15,7)循環(huán)碼在不同誤碼率情況下的識別概率對比結(jié)果。仿真參數(shù)設(shè)置同前。與文獻[11]的性能相比，在誤碼率低于0.06時，文獻[11]的識別效果略優(yōu)于本文算法，但隨著誤碼率的提高，識別效果明顯比本文算法要差，且考慮文獻[11]的計算量較本文算法要大得多，因此本文算法依然具有優(yōu)勢。與文獻[12]中所提的傳統(tǒng)矩陣分析算法相比，本文識別效果具有明顯的正確識別優(yōu)勢,而且與文獻[13]中所用的關(guān)聯(lián)規(guī)則算法識別性能優(yōu)勢更加明顯。在誤碼率為0.05時，本文算法的正確識別率可以達到80%，而文獻[12]僅能達到50%左右，文獻[13]則僅能達到20%。本文算法對p×q階矩陣進行處理時，因為只需要進行O(N3)模2加法運算，其中N為分析矩陣的最大列數(shù)。因此,本文算法在性能和復(fù)雜度上與已有算法相比具有較為明顯的優(yōu)勢。

圖10 不同算法性能對比Fig.10 Performance comparision among different algorithms

5 結(jié) 論

為抑制誤碼的擴散提出的基于分塊矩陣變換的線性分組碼盲識別方法，本文利用線性分組碼相關(guān)列可以被化為0的特性，使用各列的列重來判斷是否為相關(guān)列，再根據(jù)真實碼長時相關(guān)列個數(shù)最大，成功識別碼長和碼字起始點。仿真實驗證明，在和傳統(tǒng)方法計算復(fù)雜度相當(dāng)?shù)那闆r下，有效抑制了誤碼的擴散，在高誤碼條件下依然可以有效識別碼長和碼字起點，而且與傳統(tǒng)方法相比，本文方法提高了在高誤碼條件下的正確識別概率，顯然有效抑制了誤碼的擴散。然而,如何進一步提升算法的容錯性能是需要后續(xù)研究的難點。

[1] 王俊霞,張?zhí)祢U,強幸子. 基于迭代列消元法的線性分組碼參數(shù)盲識別[J].電訊技術(shù),2017,57(2):197-202.

WANG Junxia,ZHANG Tianqi,QIANG Xingxi. Blind recognition of linear block codes parameters based on iterative column elimination algorithm[J].Telecommunication Engineering,2017,57(2):197-202.(in Chinese)

[2] MARAZIN M,GAUTIER R,BUREL G. Dual code method for blind identification of convolutional encoder for cognitive radio receiver design[C]//Proceedings of 2009 Global Telecommunications Conference.Hawaii,USA:IEEE,2009:1-6.

[3] MARAZIN M,GAUTIER R,BUREL G. Algebraic method for blind recovery of punctured convolutional encoders from an erroneous bitstream[J].IET Signal Processing,2012,6(2):122-131.

[4] BUREL G,GAUTIER R. Blind estimation of encoder and interleaver characteristics in a non cooperative context[C]//Proceedings of the Second IASTED International Coference on Communications,Internet and Information Technology.Scottsdale,AZ,USA:IEEE,2003:75-280.

[5] 閆郁翰,湯建龍. 基于漢明距離的二進制線性分組碼盲識別方法[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.(in Chinese)

[6] 王蘭勛,李丹芳,汪洋. 二進制本原BCH碼的參數(shù)盲識別[J].河北大學(xué)學(xué)報(自然科學(xué)版),2012,32(4):416-420.

WANG Lanxun,LI Danfang,WANG Yang. Blind recognition of binary primitive BCH codes parameters[J].Journal of Hebei University(Natural Science Edition),2012,32(4):416-420.(in Chinese)

[7] 楊曉靜,聞年成. 基于碼根信息差熵和碼根統(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 and Control,2010,32(3):69-73.(in Chinese)

[8] 呂喜在,黃芝平,蘇紹璟. BCH碼生成多項式快速識別方法[J].西安電子科技大學(xué)學(xué)報(自然科學(xué)版),2011,38(6):159-162.

LYU Xizai,HUANG Zhiping,SU Shaojing. Fast recognition method for generator polynomial of BCH codes[J].Journal of Xidian University(Natural Science Edition),2011,38(6):159-162.(in Chinese)

[9] LIN S,COSTELLO D J.Error control coding[M].2nd ed. New Jersey,USA:Prentice Hall,2005:44-45.

[10] CHABOT C. Recognition of a code in a noisy environment[C]//Proceedings of 2007 International Symposium on Information Theory.Nice,France:IEEE,2007:2211-2215.

[11] 張?zhí)祢U,易琛,張剛. 基于高斯列消元法的線性分組碼參數(shù)盲識別[J].系統(tǒng)工程與電子技術(shù),2013,35(7):1514-1519.

ZHANG Tianqi,YI Chen,ZHANG Gang. Blind identification of parameters of linear block codes based on columns Gaussian elimation[J].Systems Engineering and Electronics,2013,35(7):1514-1519.(in Chinese)

[12] 張永光,樓才義,王挺.一種線性分組碼編碼參數(shù)的盲識別方法:201010131103.3[P].2010-10-13.

[13] 張旻,李歆昊. 基于關(guān)聯(lián)規(guī)則的二進制線性分組碼盲識別[J].系統(tǒng)工程與電子技術(shù),2014,36(5):979-984.

ZHANG Min,LI Xinhao. Binary linear block code blind recognition based on association rules[J].Systems Engineering and Electronics,2014,36(5):979-984.(in Chinese)

BlindRecognitionofLinearBlockCodesBasedonBlockMatrixTransformation

ZHAO Liang,ZHANG Tianqi,YANG Qiang
(Chongqing Key Laboratory of Signal and Information Processing,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

To solove the problem of error diffusion in traditional matrix analysis methods,a linear block code blind recognition method is proposed based on block matrix transformation. Firstly,the analysis matrix is constructed according to the estimated code length,and the matrix is transformed into the low triangular matrix after the analysis matrix is divided. Then,the thresholds of the relevant columns are set according to the statistical distribution characteristics of the relevant column weights,and the number of correlation columns corresponding to the thresholds is counted when the number of related columns is the largest. The method is simple and can also identify codeword synchronization points. Theoretical analysis and simulation results show that the fault recognition performance of the method is good,and the correct recognition rate of(15,7) linear block codes can reach 80% under the condition of bit error rate of 5%.

linear block codes;blind recognition;block matrix transformation;related columns

date:2017-01-04；Revised date：2017-04-10

國家自然科學(xué)基金資助項目(61671095，61371164)；信號與信息處理重慶市市重點實驗室建設(shè)項目(CSTC2009CA2003)；重慶市教育委員會科研項目(KJ130524，KJ1600427，KJ1600429)

**通信作者：535836848@qq.com Corresponding author：535836848@qq.com

TN911.22

A

1001-893X(2017)10-1107-07

趙亮(1991—)，男，河南洛陽人，碩士研究生，主要研究方向為信道編碼參數(shù)的盲識別；

Email:535836848@qq.com

張?zhí)祢U(1971—)，男，四川眉山人，博士(后)，教授，主要研究方向為語音信號處理、通信信號的調(diào)制解調(diào)、盲處理、神經(jīng)網(wǎng)絡(luò)實現(xiàn)以及FPGA、VLSI實現(xiàn)；

楊強(1991—)，男，四川岳池人，碩士研究生，主要研究方向為通信信號處理。

10.3969/j.issn.1001-893x.2017.10.002

趙亮，張?zhí)祢U，楊強.基于分塊矩陣變換的線性分組碼盲識別[J].電訊技術(shù)，2017,57(10):1107-1113.[ZHAO Liang,ZHANG Tianqi,YANG Qiang.Blind recognition of linear block codes based on block matrix transformation[J].Telecommunication Engineering,2017,57(10):1107-1113.]

2017-01-04；

2017-04-10