張旻，呂全通，朱宇軒

1.電子工程學院網(wǎng)絡系，合肥230037 2.安徽省電子制約技術重點實驗室，合肥230037 3.清華大學電子工程系，北京100084

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

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

1.電子工程學院網(wǎng)絡系，合肥230037 2.安徽省電子制約技術重點實驗室，合肥230037 3.清華大學電子工程系，北京100084

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

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

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

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

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

1　自同步擾碼原理

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

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

圖1　自同步擾碼器結構Figure 1 Structure of self-synchronized scrambler

圖2　自同步解擾器結構Figure 2 Structure of self-synchronized descrambler

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

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

2.1識別原理

2.1.1游程特性分析

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

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

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

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

圖3　碼字分布圖Figure 3 Codeword distribution

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

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

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

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

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

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

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

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

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

2.1.2擾碼序列的抽取

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

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

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

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

1）正確抽取

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

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

2）錯誤抽取

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

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

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

2.2識別準則

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

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

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

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

2.3識別步驟

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

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

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

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

步驟4最大歐幾里得距離對應的多項式即為待識別擾碼多項式

3　仿真實驗及性能比較

3.1仿真實驗

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

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

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

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

3.2性能比較

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

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

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

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

4　結語

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

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

［2］廖紅舒，袁葉，甘露.自同步擾碼的盲識別方法［J］.通信學報，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］.電路與系統(tǒng)學報，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］廖斌，張玉，楊曉靜.含錯擾碼序列生成多項式的快速恢復方法［J］.電子信息對抗技術，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］伍文君，黃芝平，唐貴林，劉純武.含錯擾碼序列的快速恢復［J］.兵工學報，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］.信息技術，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］張永光，王挺，樓才義.一種自同步擾碼生成多項式的盲識別方法［P］.中國：CN102201912A，2011.

［11］呂喜在，蘇紹璟，黃芝平.一種新的自同步擾碼多項式盲恢復方法［J］.兵工學報，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)計的自同步擾碼多項式階數(shù)估計［J］.電子科技大學學報，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

國家自然科學基金（No.60972161）資助

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