呂全通，張旻，李歆昊，朱宇軒

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

基于碼重分布距離的自同步擾碼識別方法

呂全通1，2，張旻1，2，李歆昊1，2，朱宇軒3

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

針對線性分組碼的自同步擾碼識別問題，提出了一種基于碼重分布距離的自同步擾碼識別方法。該方法首先證明了線性分組碼的自同步擾碼序列構(gòu)造不同維數(shù)的矩陣時，矩陣周期性的存在線性相關(guān)列，且該周期為線性分組碼的碼長；然后分析了線性分組碼的碼重分布的獨特特性；在獲取線性分組碼碼長的基礎(chǔ)上，通過遍歷計算抽取序列與隨機序列的碼重分布距離并尋找最大值的方式實現(xiàn)了對自同步擾碼多項式的識別。仿真實驗表明，該方法在序列不均衡度ε=0時也能有效識別，且不需要已知線性分組碼的編碼參數(shù)。

自同步擾碼；盲識別；線性分組碼；碼重分布距離

0 引言

在數(shù)字通信中，擾碼技術(shù)的應(yīng)用不僅保證了數(shù)據(jù)同步傳輸?shù)臏蚀_性，而且也擴展了信號頻譜，提高了其抗干擾能力。擾碼盲識別是信道編碼盲識別的重要內(nèi)容，在信息截獲、信息對抗和智能通信等領(lǐng)域都具有十分重要的作用。因此，擾碼的盲識別研究越來越引起國內(nèi)外相關(guān)領(lǐng)域?qū)W者和專家的重視［1-7］。

自同步擾碼的保密性較同步擾碼更強，是擾碼的一種主要形式。目前公開發(fā)表的自同步擾碼的盲識別算法都是基于加擾前信息序列是0、1分布不均衡的，如文獻［8—9］的擾碼多項式的判決準則都是基于0、1比特不平衡性提出的；文獻［10］重點研究了信源不平衡條件下的自同步擾碼序列的重碼統(tǒng)計特性，實現(xiàn)了對自同步擾碼多項式的識別；文獻［11］討論了信源不平衡條件下的自同步擾碼序列的游程數(shù)與擾碼多項式階數(shù)的關(guān)系，實現(xiàn)了對自同步擾碼階數(shù)的判斷。但在實際通信系統(tǒng)中還存在著信道編碼后加擾的情況，由于信道編碼后序列的不均衡度非常小甚至趨近于0［4］，使得現(xiàn)有的基于加擾前序列0、1分布不均衡的算法大都失效。目前國內(nèi)外鮮有文獻涉及此類問題，文獻［4］針對線性分組碼的同步擾碼識別展開研究，將擾碼生成多項式的識別轉(zhuǎn)化為二元假設(shè)檢驗問題，利用擾碼序列構(gòu)造一個服從正態(tài)分布的隨機變量，根據(jù)給出的判決閾值實現(xiàn)擾碼多項式的識別，但該方法需要已知加擾前線性分組碼的校驗矩陣的先驗知識，離全盲識別的要求還有一定差距。本文針對此問題，提出了一種基于碼重分布距離的自同步擾碼識別方法。

1 自同步擾碼原理

通信系統(tǒng)中，加擾器一般位于信源編碼之后，但是實際中也存在加擾器在分組編碼之后的情況，其結(jié)構(gòu)如圖1所示，其中，輸入xk為加擾前的線性分組編碼序列，輸出zk為加擾后的自同步擾碼序列。

圖1 線性分組碼的自同步擾碼結(jié)構(gòu)Fig.1 The structure of self-synchronous scrambler placed after the linear block code

自同步擾碼器主要是由LFSR（線性反饋移位寄存器）構(gòu)成，其結(jié)構(gòu)如圖2所示。

自同步擾碼的加擾過程可表示為：

其中，ci?｛0，1｝，0＜i≤L且cL=1是LFSR的反饋系數(shù)，式中⊕表示模二加，∑表示模二累加。

自同步解擾器由線性前饋移位寄存器組成，其結(jié)構(gòu)如圖3所示?？蓮妮斎氲臄_碼序列zk中得到原始序列xk，解擾輸出序列：

圖2 自同步擾碼器結(jié)構(gòu)圖Fig.2 The structure of self-synchronized scrambler

圖3 自同步解擾器結(jié)構(gòu)Fig.3 The structure of self-synchronized descrambler

2 線性分組碼的自同步擾碼盲識別

2.1 線性分組碼自同步擾碼的線性相關(guān)性分析

性質(zhì)1［13］：任何一個（n，k）線性分組碼都可以由其生成矩陣G的基線性表示，如果將收到的一組碼字排成p行n列（p＞n）的矩陣形式，即每行是一個完整的碼字，對該矩陣進行初等行變換，則矩陣的前k行可以化成［IkH ］的形式，其余p～k行化簡為0。

引理1［14］：對于m×n的矩陣A和m×q的矩陣B，rank［ A，B］≤rank（A）+rank（B）。

引理2［14］：如果矩陣A經(jīng)有限次初等變換變成矩陣B，就稱矩陣A與B等價，記作A～B。

定理1［14］：若矩陣A～B，則rank（A）=rank（B）。

推論1：由（n，k）線性分組碼序列構(gòu)造的p×p矩陣M有如下性質(zhì)：

1）當(dāng)p=mn（m≥2）時，即矩陣列值p為線性分組碼碼長n的整數(shù)倍數(shù)時，矩陣M各行至少包含m—1個完整對齊的碼字，如式（3）所示，根據(jù)性質(zhì)1可知，此時矩陣M存在線性相關(guān)列。

2）當(dāng)p≠mn（m≥2）時，即矩陣列值p不等于線性分組碼碼長n的整數(shù)倍數(shù)時，矩陣M各行沒有完整對齊的碼字，此時矩陣M不存在線性相關(guān)列。性質(zhì)2：（n，k）線性分組碼序列C=c1，c2，…，cN，…，經(jīng)過一個s位長的延遲器形成序列C1（結(jié)構(gòu)如圖4所示），序列C2由序列C和序列C1的邏輯異或得到，由序列C2構(gòu)造的p×p矩陣（p=mn），僅在矩陣列值p為線性分組碼碼長n的整數(shù)倍數(shù)時，矩陣存在線性相關(guān)列。證明：根據(jù)題設(shè)條件，序列C2=C⊕C1，其中，序列C可表示為C=（c1，c2，…，cN，… ），序列C1可表示為C1=（c1，…，cs，c1，c2，…，cN，…），（c1，…，cs）為延遲器的初始狀態(tài)。

由序列C構(gòu)造的p×p矩陣C，當(dāng)p=mn，m= 1，2，…時，矩陣各行碼字起點對齊，矩陣排列如式（4）所示。

圖4 序列的延遲異或結(jié)構(gòu)Fig.4 The XOR structure of delayed sequence

由序列C1構(gòu)造的p×p矩陣C1，矩陣排列如式（5）所示。

矩陣C進行有限次的初等變換得到如式（6）的結(jié)果。

由于矩陣C1與矩陣C的實線框中的數(shù)據(jù)是完全一致的，因此，矩陣C1與矩陣C進行相同的步驟的初等變換可得到如（7）式的結(jié)果。

由序列C2=C⊕C1可知，矩陣C2=C⊕C1，而矩陣C～B，C1～B1。由此可得，C⊕C1=C2～B⊕B1，即：

由式（8）可知，初等變換后的矩陣B和矩陣B1實線框中的全0行的位置是對齊的，此時矩陣Umn，（m—1）n存在線性相關(guān)列且rank（Umn，（m—1）n）=（m—1）k。而由推論1可知，矩陣D'mn，s和矩陣F'mn，n—s的各行不存在完整對齊的碼字，矩陣為列滿秩矩陣，因此，rank（D'mn，s）=s，rank（F'mn，n—s）=n—s。

由引理1和定理1可得：

因此，由序列C2構(gòu)造的p×p矩陣C2，當(dāng)矩陣列值p=mn，m=1，2，…時，矩陣存在線性相關(guān)列。

當(dāng)矩陣列值p不為線性分組碼碼長n的整數(shù)倍數(shù)時，即p≠mn，m=1，2，…，矩陣C1、矩陣C都為滿秩矩陣，此時矩陣C2也為滿秩矩陣，不存在線性相關(guān)列。

綜上所述，由序列C2構(gòu)造的p×p矩陣C2，僅在矩陣列值p取得線性分組碼碼長n的整數(shù)倍數(shù)時，矩陣存在線性相關(guān)列。

性質(zhì)2得證。

自同步擾碼由于誤碼擴散率與生成多項式的項數(shù)成正比，一般都使用2項式或3項式［8］，現(xiàn)以3項式自同步擾碼器為例（其結(jié)構(gòu)如圖5所示），其擾碼器輸出可由線性分組碼及其延遲序列異或而得到，即zk=xk⊕yk—1⊕yk—L=xk⊕yk，其中yk—1、yk—L是線性分組碼序列xk的延遲序列。因為序列yk= yk—1⊕yk—L，由推論1及性質(zhì)2可知，由序列yk構(gòu)造的p×p矩陣，在矩陣列值P取得線性分組碼碼長n的整數(shù)倍數(shù)時，矩陣存在線性相關(guān)列。同理，對于自同步擾碼輸出序列zk=xk⊕yk，擾碼序列也有如性質(zhì)2的特性。

圖5 自同步擾碼器結(jié)構(gòu)Fig.5 The structure of self-synchronized scrambler

綜合上述分析可得，對于線性分組碼的自同步擾碼序列，由該序列構(gòu)造的p×p的矩陣，在矩陣列值P取得線性分組碼碼長n的整數(shù)倍數(shù)時，矩陣存在線性相關(guān)列。

2.2 線性分組碼碼重特性分析

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

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

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

其中，n為估計碼長。

2.3 序列抽取

自同步擾碼器的生成多項式可以表示為：

其中，L是LFSR的反饋邏輯輸出級數(shù)，rv是生成多項式f（x）的項數(shù)。

自同步擾碼的輸入序列為xk，擾碼器的輸出序列為zk。定義GF（2）上的多項式

按照多項式g（x）對擾碼序列抽取并進行模二求和得

當(dāng)g（x）=f（x）時，該抽取并模二求和的過程實際上等價于自同步擾碼的解擾的過程。

因此，抽取并模二求和后的序列mk1即為加擾前的線性分組編碼序列。

當(dāng)g（x）≠f（x）時，式（14）所示的處理過程不再是解擾過程，由于擾碼序列zk中的0、1等概率出現(xiàn)，因此，在錯誤抽取時抽頭位0、1比特出現(xiàn)的概率是相等的，即

其中，rw是多項式g（x）的項數(shù)。

在錯誤抽取時抽頭位0、1比特出現(xiàn)的概率是相等的，因此模二求和的輸出序列mk2中的0、1也是等概率出現(xiàn)的，近似為隨機序列。

2.4 識別步驟

綜合上述分析提出以下識別步驟：

步驟1：對于待識別的擾碼序列，遍歷碼長構(gòu)造P×P矩陣，其中P=1，2，…，160，統(tǒng)計矩陣的秩差，矩陣的秩差R-Dj=j—Rj（其中j=1，2，…，P為矩陣列值，Rj為矩陣的秩），矩陣的秩差在矩陣列數(shù)取碼長整數(shù)倍時周期性取得峰值，其峰值對應(yīng)的列值的最大公約數(shù)即為加擾前線性分組碼的碼長n。

步驟2：遍歷N個多項式對擾碼序列抽取并模二求和，其輸出序列為：mtk，其中，t=1，2，…，N，t為多項式集合G中的多項式序號。

步驟3：根據(jù)判斷得出的碼長n，遍歷抽取的輸出序列mtk的碼字起點f=1，2，…n，計算與隨機序列的碼重分布距離，統(tǒng)計遍歷碼字起點時的最大碼重分布距離：

步驟4：最大碼重分布距離對應(yīng)的多項式即為所待識別擾碼多項式：g（x）= G｛ s｝，s= argmaxd（ t）。

3 仿真實驗及性能對比

為了驗證識別方法的效性，使用軟件matlab 7.10進行仿真實驗。

3.1 仿真實驗

實驗1：自同步擾碼與線性分組碼的秩差統(tǒng)計

隨機產(chǎn)生長度為N=30 000 bit的（15，5）線性分組碼作擾碼器的輸入信息數(shù)據(jù)，仿真長度為30 000 bit、生成多項式為f（x）=1+x18+x23的自同步擾碼序列，統(tǒng)計（15，5）線性分組碼、自同步擾碼序列的秩差，其統(tǒng)計結(jié)果如圖6、圖7所示。

由圖6、圖7所示的統(tǒng)計結(jié)果可以看出，（15，5）線性分組碼及其自同步擾碼的秩差統(tǒng)計都在矩陣列值取碼長整數(shù)倍時周期性取得峰值，其峰值統(tǒng)計結(jié)果如表1所示，（15，5）線性分組碼及其自同步擾碼的秩差統(tǒng)計的峰值對應(yīng)的矩陣列值的最大公約數(shù)都為15。因此，通過對線性分組碼的自同步擾碼的秩差統(tǒng)計，可以預(yù)先識別出加擾前線性分組碼的碼長。

圖6 （15，5）線性分組碼Fig.6 （15，5）linear block code

圖7 自同步擾碼Fig.7 Self-synchronized scrambler

表1 峰值統(tǒng)計結(jié)果Tab.1 The result of peak value statistics_

實驗2：自同步擾碼多項式的識別

實際通信中LFSR的級數(shù)絕大多數(shù)分布在3～60之間，自同步擾碼由于誤碼擴散率與生成多項式的項數(shù)成正比，一般都使用2項式或3項式，比如ITU V.34中使用的就是3項式1+x18+x23［8］。因此，有限的多項式項數(shù)和LFSR的階數(shù)是擾碼盲識別方法可行的重要前提條件。

為給出較為實際有效的正確識別率，在仿真遍歷多項式時，采用三組多項式作為自同步擾碼的生成多項式：第一組，由3～60階的全部58個2項式f（x）=1+xL（L=3，4，…，60）組成；第二組，由3～60階的全部1 769個3項式f（x）=1+xk+xL，L= 3，…，60，k=1，…，L—1組成；第三組，由3～60階的5項式組成，由于3～60階的5項式的總數(shù)過于龐大，因此在各個階數(shù)對應(yīng)的5項式中分別隨機抽取10個或11個多項式，若相應(yīng)階數(shù)的5項式不足10個（比如3～6階）則該階數(shù)對應(yīng)的5項式全部抽取，共555個5項式。多項式集合中多項式共2 382個。

實驗中采用ITUV.34中常用的生成多項式為f（x）=1+x18+x23的自同步加擾方式，隨機產(chǎn)生長度為N=45 000 bit的（15，5）線性分組碼作擾碼器的輸入信息數(shù)據(jù)，線性分組碼序列的不均衡為0，仿真長度為45 000 bit的自同步擾碼序列進行盲識別實驗，統(tǒng)計結(jié)果如圖8和表2所示（表2是碼重分布距離按從大到小排序的前5個值，以及其碼重分布距離對應(yīng)的多項式）。

表2 碼重分布距離統(tǒng)計Tab.2 Weight distribution distance statistics

由圖8及表2的實驗結(jié)果可以知，在多項式序號為306（多項式取g（x）=1+x18+x23）時，碼重分布距離取得最大值0.0273，且與其他多項式對應(yīng)的碼重分布距離有明顯差異，可以判斷自同步擾碼的生成多項式為g（x）=1+x18+x23，與待識別自同步擾碼的多項式一致。因此，通過計算并尋找擾碼抽取序列與隨機序列的碼重分布距離最大值的方法可以有效地實現(xiàn)此類自同步擾碼多項式的識別。

3.2 性能比較

為了更好地說明本文所提方法的識別性能，將本文所提的方法與文獻［10］的方法進行比較。仿真對比實驗中使用ITU V.34（其自同步擾碼多項式為1+x18+x23）和ITU G.709（其自同步擾碼多項式為1+x43）這2個實際系統(tǒng)所使用的生成多項式，分別仿真長度從0～9 000 bit以900 bit步長變化的線性分組碼序列作為擾碼器的輸入信息序列且線性分組碼序列的不均衡為0，分別使用本文方法和文獻［10］的方法對相應(yīng)的自同步擾碼序列進行蒙特卡洛仿真實驗，蒙特卡洛仿真次數(shù)為500次，仿真結(jié)果如圖9、圖10所示。

由圖9、圖10的仿真結(jié)果可知，本文方法的識別率與不均衡度ε無關(guān)，在ε=0時也可以實現(xiàn)正確識別，但本文方法識別率與擾碼序列長度有關(guān)，在數(shù)據(jù)量為8 000 bit時，正確識別率能達到90%以上，在數(shù)據(jù)量大于9 000 bit時，正確識別率能達到100%。文獻［10］所提方法的識別率均為0，對加擾前序列為線性分組碼的自同步擾碼無法識別。綜上所述，本文方法針對加擾前序列為線性分組碼的自同步擾碼序列具有很好的識別性能，且本文方法不需要已知線性分組碼的具體參數(shù)也能有效地識別。

圖8 碼重分布距離Fig.8 Weight distribution distance

圖9 ITU V.34的擾碼識別率對比曲線Fig.9 Comparison of recognition ratio of the ITU V.34 scrambler performance

圖10 ITU G.709的擾碼識別率對比曲線Fig.10 Comparison of recognition ratio of the ITU G.709 scrambler performance

4 結(jié)論

本文提出了基于碼重分布距離的自同步擾碼識別方法。該方法證明了線性分組碼的自同步擾碼序列碼組間的線性相關(guān)性，利用線性分組碼序列與隨機序列的碼重分布特性的差異，實現(xiàn)了對線性分組碼的自同步擾碼多項式的識別。仿真實驗表明，本文方法在序列不均衡度ε=0時也能有效識別，且不需要已知線性分組碼的編碼參數(shù)。但是，本文方法仍然需要遍歷大量的多項式，計算復(fù)雜度較大，在下一步的研究中還需要對算法進一步的優(yōu)化。

［1］袁葉.線性擾碼的盲識別研究［D］.成都：電子科技大學(xué)，2013.

［2］Cluzeau M.Reconstruction of a Linear Scrambler［J］. IEEE Transaction on Computers，2007，56（9）：1283-1291.

［3］Liu X B，Soo N K，Wu X W，et al.Reconstructing a linear scrambler with improved detection capability and in the presence of noise［J］.IEEE Transaction on Information Forensics and Security，2012，7（1）：208-218.

［4］Liu X B，Soo N K，Wu X W.A study on reconstruction of linear scrambler using dual words of channel encoder［J］.IEEE Transactions on Information Forensics and Security，2013，8（3）：542-552.

［5］郝士琦，戚林，王勇.一種新的偽隨機擾碼盲識別方法［J］.電路與系統(tǒng)學(xué)報，2011，16（4）：6-12.

［6］廖斌，張玉，楊曉靜.含錯擾碼序列生成多項式的快速恢復(fù)方法［J］.電子信息對抗技術(shù)，2014，29（1）：13-16.

［7］伍文君，黃芝平，唐貴林，等.含錯擾碼序列的快速恢復(fù)［J］.兵工學(xué)報，2009，30（8）：1134-1138.

［8］廖紅舒，袁葉，甘露.自同步擾碼的盲識別方法［J］.通信學(xué)報，2013，34（1）：136-143.

［9］張永光，王挺，樓才義.一種自同步擾碼生成多項式的盲識別方法［P］.中國：CN102201912A，2011.

［10］呂喜在，蘇紹璟，黃芝平.一種新的自同步擾碼多項式盲恢復(fù)方法［J］.兵工學(xué)報，2011，32（6）：680-685.

［11］黃芝平，周靖，蘇紹璟，等.基于游程統(tǒng)計的自同步擾碼多項式階數(shù)估計［J］.電子科技大學(xué)學(xué)報，2013，42（4）：541-545.

［12］姜丹.信息論與編碼［M］.合肥：中國科學(xué)技術(shù)大學(xué)出版社，2011.

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

［14］張賢達.矩陣分析與應(yīng)用［M］.北京：清華大學(xué)出版社，2014.

Self-synchronized Scrambler Recognition Based on Code Weight Distributing Distance

LU Quantong1，2，ZHANG Min1，2，LI Xinhao1，2，ZHU Yuxuan3
（1.Electronic Engineering Institute of PLA，Hefei 230037，China；2.Key Laboratory Electronic Restricting Technique，Hefei 230037，China；3.Department of Electronic Engineer，Tsinghua University，Beiiing 100084，China）

A recognition method based on code weight distributing distance was proposed to solve the problem of the identifying of the self-synchronized scrambler placed after the linear block code.Firstly，the conclusion was proved that the sequence of self-synchronized scrambler after a linear block encoder in the different dimension matrix structure was periodic exist linear correlation matrix，and the period was the length of linear block code；Then，the weight distribution characteristic of the linear block code was analyzed.Finally，the length of linear block code are being identified，and the polynomial of the scrambler was determined with maximum value searching for all possible distance of code weight distributing of the extracted sequence and the random sequence. Simulation results showed that this method could effectively identify the self-synchronized scrambler when the sequence bias is equal to zero without knowing the parameters of the linear block code.

self-synchronized scrambler；blind recognition；linear block code；distance of code weight distributing

TP391

A

1008-1194（2015）05-0007-07

2015-04-07

國家自然科學(xué)基金項目資助（60972161）；安徽省自然科學(xué)基金項目資助（1408085QF115）

呂全通（1990—），男，山東人，碩士研究生，研究方向：通信與信息系統(tǒng)。E-mail：lvquantong90@126.com