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

張旻，呂全通，朱宇軒

1.電子工程學(xué)院網(wǎng)絡(luò)系，合肥230037 2.安徽省電子制約技術(shù)重點(diǎn)實(shí)驗(yàn)室，合肥230037 3.清華大學(xué)電子工程系，北京100084

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

張旻1,2，呂全通1,2，朱宇軒3

1.電子工程學(xué)院網(wǎng)絡(luò)系，合肥230037 2.安徽省電子制約技術(shù)重點(diǎn)實(shí)驗(yàn)室，合肥230037 3.清華大學(xué)電子工程系，北京100084

針對加擾前信息序列為線性分組碼情況下的自同步擾碼盲識別問題，提出了一種有效的解決方法.首先，從理論上分析了線性分組碼與隨機(jī)序列游程特性的差異，得出了擾碼序列正確抽取與錯誤抽取時輸出序列的游程特性的區(qū)別；然后，通過遍歷尋找抽取后序列的游程比值與隨機(jī)序列游程比值的歐幾里得距離的最大值方式實(shí)現(xiàn)了自同步擾碼多項(xiàng)式的盲識別.仿真實(shí)驗(yàn)驗(yàn)證了理論分析的正確性，解決了0、1均衡情況下的線性分組碼自同步擾碼盲識別問題，具有一定的工程應(yīng)用價值.

自同步擾碼；盲識別；線性分組碼；游程特性；歐幾里得距離

擾碼作為通信系統(tǒng)的關(guān)鍵技術(shù)之一，不僅能提高數(shù)據(jù)傳輸同步的準(zhǔn)確性，還能使信號頻譜彌散從而提高其抗干擾能力［1］.在數(shù)字通信系統(tǒng)中，只有對接收的通信信號正確地解擾，才能對后續(xù)的信源編碼或信道編碼數(shù)據(jù)進(jìn)行譯碼分析，進(jìn)而得到原始信息.在非合作通信領(lǐng)域中，正確有效地識別出擾碼的編碼參數(shù)并完成解擾，是未知信息繼續(xù)分析處理的前提條件，直接影響到原始信息的正確獲?。?］.因此，擾碼的盲識別研究引起相關(guān)領(lǐng)域?qū)W者的高度重視［3-8］.

自同步擾碼的收發(fā)雙方不需要嚴(yán)格同步，而且其保密性較同步擾碼更強(qiáng)，故廣泛應(yīng)用于通信系統(tǒng).在實(shí)際通信中，信源編碼序列普遍具有0、1不均衡性，目前已有的自同步擾碼的盲識別算法通常采用加擾前信源編碼序列0、1分布的不均衡特性，如文獻(xiàn)［2］以比特狀態(tài)統(tǒng)計(jì)概率分布與均勻分布之間的修正平方歐幾里得距離作為比特狀態(tài)不平衡性的衡量準(zhǔn)則來實(shí)現(xiàn)自同步擾碼的盲識別.文獻(xiàn)［9］根據(jù)自同步擾亂序列反映在方程組上的特征和擾亂前后數(shù)據(jù)序列的統(tǒng)計(jì)不均衡特性，利用Walsh-Hadamard變換解含錯方程組來恢復(fù)生成多項(xiàng)式.文獻(xiàn)［10］基于信源編碼序列不均衡，根據(jù)產(chǎn)生的擾碼序列與原始擾碼序列的相關(guān)度判斷自同步擾碼的生成多項(xiàng)式.文獻(xiàn)［11］在對信源不平衡條件下的自同步擾碼序列的重碼統(tǒng)計(jì)特性深入分析的基礎(chǔ)上，提出了一種優(yōu)于Walsh變換法的自同步擾碼多項(xiàng)式識別算法.文獻(xiàn)［12］分析了信源0、1分布不均衡下的自同步擾碼序列的游程統(tǒng)計(jì)結(jié)果與擾碼多項(xiàng)式階數(shù)的關(guān)系，實(shí)現(xiàn)了對同步擾碼多項(xiàng)式階數(shù)的估計(jì).在實(shí)際通信系統(tǒng)中，還存在著信道編碼后進(jìn)行加擾的情況，由于信道編碼后序列的不均衡度非常小甚至趨近于0，現(xiàn)有的基于序列0、1分布不均衡的算法難以識別此類擾碼［5］.文獻(xiàn)［5］利用信道編碼的校驗(yàn)矩陣對擾碼序列進(jìn)行預(yù)處理，通過二元假設(shè)檢驗(yàn)的方法識別擾碼參數(shù)，但需要加擾前線性分組碼的校驗(yàn)矩陣的先驗(yàn)知識，離全盲識別的要求還有一定差距.

本文針對自同步擾碼的輸入為線性分組碼的情況，提出了一種基于游程比值歐幾里得距離的自同步擾碼盲識別方法，通過遍歷多項(xiàng)式抽取擾碼序列，則抽取后的序列游程比值與隨機(jī)序列游程比值的歐幾里得距離最大的一組對應(yīng)的多項(xiàng)式即為待識別擾碼多項(xiàng)式.

1　自同步擾碼原理

自同步擾碼的加擾以線性反饋移位寄存器（linear feedback shift register，LFSR）為基礎(chǔ)［13］，其加擾器的結(jié)構(gòu)如圖1所示.擾碼序列zk的產(chǎn)生是由信息序列xk和LFSR的輸出序列yk共同決定的，其加擾過程可以表示為

式中，ci為LFSR的反饋系數(shù)，ci∈｛0，1｝，0＜i＜L且c0=cL=1；⊕表示模二加；Σ表示模二累加.

圖1　自同步擾碼器結(jié)構(gòu)Figure 1 Structure of self-synchronized scrambler

圖2　自同步解擾器結(jié)構(gòu)Figure 2 Structure of self-synchronized descrambler

從自同步擾碼的結(jié)構(gòu)來看，該結(jié)構(gòu)下的解擾器不需要建立同步；從解擾過程來看，解擾輸出的信息序列只與輸入的擾碼序列zk有關(guān).自同步擾碼的加、解擾器只需要相同的LFSR反饋多項(xiàng)式而不需要相同的LFSR初態(tài)，即可實(shí)現(xiàn)對數(shù)據(jù)的加擾和解擾.因此，自同步擾碼的盲識別問題就是根據(jù)截獲的擾碼序列zk識別出LFSR的多項(xiàng)式.

2　基于線性分組碼的自同步擾碼參數(shù)識別

2.1識別原理

2.1.1游程特性分析

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

對于周期為2n-1的m序列，在m序列的一個周期內(nèi)，共有2n-1個游程，其中0游程和1游程的數(shù)目各占一半，長度為m（0＜m 6 n-2）的游程有2n-m-1個［13］.

隨著游程長度的遞增，m序列的游程數(shù)按照1/2規(guī)律遞減，而且相同游程長度下的0、1游程數(shù)基本相等.m序列是偽隨機(jī)序列，因此隨機(jī)序列也具有m序列相似的0、1游程分布的特征.

對于（n，k）二元線性分組碼而言，k位信息經(jīng)編碼后生成n位碼字，構(gòu)成的集合v（2k）是n維向量空間V（2n）的一個子空間.由k位信息生成的n位線性分組碼的碼字集合v必定隸屬于由n位碼字所組成的碼字集合V，如圖3所示.（n，k）編碼有2n-2k個禁用碼字，破壞了線性分組碼游程的隨機(jī)特性，導(dǎo)致線性分組碼游程的隨機(jī)性變差.由于線性碼的k位信息元可隨機(jī)產(chǎn)生，長度小于k的游程可以在一個碼字中得到，大于等于k的游程只有在兩個碼字的拼接處才能得到.與隨機(jī)序列的游程特性相比，線性分組碼的游程數(shù)在信息位長k的附近發(fā)生較大畸變，其游程數(shù)不再呈現(xiàn)1/2的遞減規(guī)律.

圖3　碼字分布圖Figure 3 Codeword distribution

圖4　（6，3）線性分組碼碼字Figure 4（6，3）linear block codeword

對于圖4中的（6，3）線性分組碼的編碼序列，只有碼字011011和碼字110110前后拼接時才會出現(xiàn)長度為4的1游程，此種碼字組合出現(xiàn)的概率為，因此長度為4的1游程在該編碼序列中出現(xiàn)概率為.隨機(jī)序列不同長度下的0、1游程數(shù)是依1/2規(guī)律遞減的，且相同游程長度下的0、1游程數(shù)是相等的［13］，故長度為4的1游程出現(xiàn)概率為.由此可見，兩種序列的游程分布有較大差異.

仿真產(chǎn)生序列長度為30 000 bit的（6，3）線性碼和隨機(jī)序列，統(tǒng)計(jì)兩組序列的游程長度從1～10的游程數(shù)，其游程數(shù)的分布和相應(yīng)隨機(jī)序列游程數(shù)的分布如圖5和表1所示.

圖5　（6，3）線性碼游程統(tǒng)計(jì)Figure 5（6，3）linear block code's run statistics

（6，3）線性碼的游程分布與隨機(jī)序列游程分布相比有明顯的跳躍折點(diǎn)，如圖5虛線框中的部分所示.

表1　游程統(tǒng)計(jì)結(jié)果Table 1 Result of run statistics

根據(jù)表1的游程數(shù)統(tǒng)計(jì)結(jié)果，計(jì)算（6，3）線性碼的游程比值ui和隨機(jī)序列的游程比值ui（其中ui=vi+1/vi，i=1，2，···，l，i表示游程長度，vi表示長度為i的游程數(shù)），統(tǒng)計(jì)結(jié)果如表2所示.

由表2統(tǒng)計(jì)結(jié)果可知，（6，3）線性碼的游程比值分布與隨機(jī)序列游程比值分布有較大差異，線性碼的0、1游程數(shù)不再呈現(xiàn)1/2的遞減規(guī)律.

表2　游程比值統(tǒng)計(jì)結(jié)果Table 2 Result of the run ratio statistics

2.1.2擾碼序列的抽取

對于圖1所示的自同步擾碼器，其生成多項(xiàng)式可以表示為

式中，L為LFSR的反饋邏輯輸出階數(shù)，rv為生成多項(xiàng)式f（x）的項(xiàng)數(shù)

自同步擾碼的輸入序列為xk，擾碼器的輸出序列為zk.定義GF（2）上的多項(xiàng)式

按照多項(xiàng)式g（x）對擾碼序列抽取并進(jìn)行模二求和得

1）正確抽取

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

式中，mk1為擾碼器的輸入序列，即mk1為線性分組編碼序列.

2）錯誤抽取

當(dāng)g（x）6=f（x）時，式（5）所示的處理過程不是正確的解擾過程.由于擾碼序列zk中的0、1等概率出現(xiàn)，錯誤抽取時抽頭位置的0、1比特出現(xiàn)的概率是相等的，其概率為

式中，rw為比特抽取時非生成多項(xiàng)式的項(xiàng)數(shù).

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

2.2識別準(zhǔn)則

由2.1.2節(jié)分析可知，正確抽取時的輸出序列mk1為線性分組碼，而錯誤抽取時的輸出序列mk2為隨機(jī)序列，因此抽取的輸出序列為線性分組碼時對應(yīng)的多項(xiàng)式即為待識別擾碼多項(xiàng)式，此時游程數(shù)的比值與隨機(jī)序列游程數(shù)的比值相比較分布最不均衡.游程比值分布的不均衡性可用幾何距離來衡量，如用歐幾里得距離衡量抽取序列與隨機(jī)序列的游程比值的距離為

式中，Pi為抽取序列的游程比值，Qi=1/2（i=1，2，···，l）為隨機(jī)序列游程比值，d為0、1游程比值的歐幾里得距離之和.

d越大表征抽取序列的游程比值分布與隨機(jī)序列游程比值分布的距離越遠(yuǎn)，即游程比值分布越不均衡.當(dāng)抽取選取的多項(xiàng)式恰好為擾碼的生成多項(xiàng)式時，游程比值分布的距離取得最大值.因此，待識別擾碼多項(xiàng)式為

式中，G為需要遍歷的多項(xiàng)式集合，t為集合G中多項(xiàng)式序號，s為最大歐幾里得距離對應(yīng)的多項(xiàng)式序號.

2.3識別步驟

根據(jù)2.1和2.2節(jié)的分析，提出了以下的識別步驟：

步驟1對于截獲的擾碼序列，按照式（5）遍歷多項(xiàng)式對擾碼序列抽取并模二求和，其輸出序列為mk；

步驟2統(tǒng)計(jì)輸出序列mk的游程數(shù)（i表示游程長度，j表示0、1游程），并計(jì)算其0、1游程數(shù)的前后比值，其中j=0，1，i=1，2，···，l；

步驟3統(tǒng)計(jì)每個多項(xiàng)式對應(yīng)的抽取序列與隨機(jī)序列的游程比值的歐幾里得距離

步驟4最大歐幾里得距離對應(yīng)的多項(xiàng)式即為待識別擾碼多項(xiàng)式

3　仿真實(shí)驗(yàn)及性能比較

3.1仿真實(shí)驗(yàn)

實(shí)際通信中擾碼使用的LFSR階數(shù)絕大多數(shù)分布在3～60之間，通常采用二項(xiàng)式或三項(xiàng)式，比如ITU V.34中使用的就是三項(xiàng)式1+x18+x23.為給出較為實(shí)際有效的正確識別率，遍歷多項(xiàng)式時采用三組多項(xiàng)式作為自同步擾碼的生成多項(xiàng)式：第1組，由3～60階的全部58個二項(xiàng)式f（x）=1+xL，L=3，4，···，60組成；第2組，由3～60階的全部1 769個三項(xiàng)式f（x）=1+xk+xL，L=3，···，60，k=1，···L-1組成；第3組，由3～60階的五項(xiàng)式組成.由于3～60階的五項(xiàng)式的總數(shù)過于龐大，在各個階數(shù)對應(yīng)的五項(xiàng)式中分別隨機(jī)抽取10個或11個多項(xiàng)式，若相應(yīng)階數(shù)的五項(xiàng)式不足10個（比如3～6階），則該階數(shù)對應(yīng)的五項(xiàng)式全部抽取，共555個五項(xiàng)式.多項(xiàng)式集合中共2 382項(xiàng)多項(xiàng)式.

實(shí)驗(yàn)中采用ITUV.34中常用的生成多項(xiàng)式為f（x）=1+x18+x23的自同步加擾方式，隨機(jī)產(chǎn)生長度為45 000 bit的（15，5）線性分組碼作信息序列，其序列不均衡度為0，仿真長度為45 000 bit的自同步擾碼序列進(jìn)行盲識別實(shí)驗(yàn)，得到的仿真結(jié)果如圖6所示.

圖6　游程歐幾里得距離統(tǒng)計(jì)Figure 6 Run square Euclidean distance statistics

由圖6中的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)多項(xiàng)式序號為306（多項(xiàng)式取g（x）=1+x18+x23）時，游程比值的歐幾里得距離統(tǒng)計(jì)取得最大值，而且與其他多項(xiàng)式對應(yīng)的游程比值的歐幾里得距離有明顯差異，由此可判斷自同步擾碼的生成多項(xiàng)式為g（x）=1+x18+x23，與待識別自同步擾碼的多項(xiàng)式一致.因此，通過統(tǒng)計(jì)并尋找抽取序列與隨機(jī)序列游程比值的歐幾里得距離最大值的方法，可以有效地實(shí)現(xiàn)對自同步擾碼多項(xiàng)式的識別.

3.2性能比較

為了更好地說明本文方法的識別性能，將其與文獻(xiàn)［2］的方法進(jìn)行對比實(shí)驗(yàn).仿真對比實(shí)驗(yàn)中使用ITU V.34（自同步擾碼多項(xiàng)式1+x18+x23）系統(tǒng)中所使用的生成多項(xiàng)式，按照ε=0.01和ε=0.05分別隨機(jī)生成長度從0～8 000 bit以200 bit步長變化的線性分組碼序列作為擾碼器的輸入信息序列，分別用本文和文獻(xiàn)［2］的方法對相應(yīng)的自同步擾碼序列進(jìn)行蒙特卡羅仿真實(shí)驗(yàn)，仿真次數(shù)為500次，仿真結(jié)果如圖7和8所示.

圖7　ε=0.01時的識別率Figure 7 Recognition rate of ε=0.01

圖8　ε=0.05時的識別率Figure 8 Rcognition rate of ε=0.05

由圖7和8的仿真結(jié)果可知，本文方法的識別率與不均衡度ε無關(guān)，在ε=0.01時也可以實(shí)現(xiàn)正確識別.本文方法的識別率與擾碼序列長度有關(guān)，當(dāng)數(shù)據(jù)量為5 800 bit時，正確識別率達(dá)到90%以上；當(dāng)數(shù)據(jù)量大于6 000 bit時，正確識別率達(dá)到100%.文獻(xiàn)［2］的方法與不均衡度ε大小關(guān)系密切，當(dāng)ε=0.01時算法失效；但該方法對數(shù)據(jù)量要求較低，當(dāng)ε=0.05，且數(shù)據(jù)量大于2 000 bit時就能準(zhǔn)確識別，優(yōu)于本文方法.

4　結(jié)語

本文針對線性分組碼不均衡度趨近于0的情況，利用擾碼抽取序列游程特性的差異，以抽取序列與隨機(jī)序列的游程比值歐幾里得距離作為判決準(zhǔn)則，提出了一種與均衡度無關(guān)的自同步擾碼識別方法.仿真實(shí)驗(yàn)結(jié)果表明，本文方法能有效識別不均衡度為0的線性分組碼的自同步擾碼，且不必已知線性分組碼的具體參數(shù)，但要遍歷多項(xiàng)式，計(jì)算量較大，因此下一步的研究還應(yīng)優(yōu)化算法以減少計(jì)算量.

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

［2］廖紅舒，袁葉，甘露.自同步擾碼的盲識別方法［J］.通信學(xué)報，2013，34（1）：136-143. LIAO H S，YUAN Y，GAN L.Novel blind recognition method for self-synchronized scrambler［J］.Journal on Communications，2013，34（1）：136-143.（in Chinese）

［3］CLUZEAU M.Reconstruction of a linear scrambler［J］.IEEE Transaction on Computers，2007，56（9）：1283-1291.

［4］LIU X B，SOO N K，WU X W，CHUI C C.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.

［5］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.

［6］郝士琦，戚林，王勇.一種新的偽隨機(jī)擾碼盲識別方法［J］.電路與系統(tǒng)學(xué)報，2011，16（4）：6-12. HAO S Q，QI L，WANG Y.A new blind recognition method of pseudo—randomizer code sequence［J］.Journal of Circuits and Systems，2011，16（4）：6-12.（in Chinese）

［7］廖斌，張玉，楊曉靜.含錯擾碼序列生成多項(xiàng)式的快速恢復(fù)方法［J］.電子信息對抗技術(shù)，2014，29（1）：13-16. LIAO B，ZHANG Y，YANG X J.The method of fast recovery the generate polynomial of interfered scrambling code sequence［J］.Electronic Information Warfare Technology，2014，29（1）：13-16.（in Chinese）

［8］伍文君，黃芝平，唐貴林，劉純武.含錯擾碼序列的快速恢復(fù)［J］.兵工學(xué)報，2009，30（8）：1134-1138. WU W J，HUANG Z P，TANG G L，LIU C W.Fast recovery of interfered scrambling code sequence［J］.Acta Armamentarii，2009，30（8）：1134-1138.（in Chinese）

［9］楊忠立，劉玉君.自同步擾亂序列的綜合算法研究［J］.信息技術(shù)，2005（2）：30-32. YANG Z L，LIU Y J.Algorithm research of self-synchronizing scrambler sequence［J］.Information Technology，2005（2）：30-32.（in Chinese）

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

［11］呂喜在，蘇紹璟，黃芝平.一種新的自同步擾碼多項(xiàng)式盲恢復(fù)方法［J］.兵工學(xué)報，2011，32（6）：680-685. Lü X Z，SU S J，HUANG Z P.A novel blind recovery method of self-synchronizing scrambling polynomial［J］.Acta Armamentarii，2011，32（6）：680-685.（in Chinese）

［12］黃芝平，周靖，蘇紹璟，劉純武，呂喜在.基于游程統(tǒng)計(jì)的自同步擾碼多項(xiàng)式階數(shù)估計(jì)［J］.電子科技大學(xué)學(xué)報，2013，42（4）：541-545. HUANG Z P，ZHOU J，SU S J，LIU C W，Lü X Z.Order estimation of self-synchronizing scrambling polynomial based on run statistic［J］.Journal of University of Electronic Science and Technology of China，42（4）：541-545.（in Chinese）

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

（編輯：王雪）

Blind Recognition of Self-Synchronized Scrambler Based on Linear Block Code

ZHANG Min1,2，Lü Quan-tong1,2，ZHU Yu-xuan3
1.Network Department，Institute of Electronic Engineering，Hefei 230037，China 2.Key Laboratory of Electronic Control technology，Hefei 230037，China 3.Department of Electronic Engineer，Tsinghua University，Beijing 100084，China

A blind recognition method of self-synchronous scrambler based on the linear block code with unbiased information source is proposed.Diferent run characteristics of the linear block code and random sequence are analyzed，leading to the conclusion that the run feature of correctly extracted scrambler sequence difers from that of the wrong one. A polynomial of the scrambler is determined with maximum value search in all possible Euclidean distances between the run ratios of extracted and random sequences.Experiments and simulation results show correctness of the theoretical analysis.Blind recognition of self-synchronous scrambler after the linear block code with unbiased information source can be realized，useful in engineering application.

self-synchronized scrambler，blind recognition，linear block code，run characteristic，Euclidean distance

TP391

0255-8297（2015）02-0178-09

10.3969/j.issn.0255-8297.2015.02.007

2014-09-19；

2014-12-15

國家自然科學(xué)基金（No.60972161）資助

張旻，教授，博導(dǎo)，研究方向：智能信息處理、通信信號處理，E-mail：dyzhangmin@163.com