基于實時檢測的擾碼重建算法

馬 鈺 張立民

?

基于實時檢測的擾碼重建算法

馬 鈺 張立民*

(海軍航空工程學(xué)院 煙臺 264001)

基于Walsh-Hadamard變換的擾碼重建算法在最大成立數(shù)準(zhǔn)則下尋找全局最優(yōu)解，是求解線性反饋關(guān)系的一種有效方法，但其計算復(fù)雜度隨著變換階數(shù)的增加而迅速增加。為降低算法的計算復(fù)雜度，論文提出一種基于實時檢測的擾碼重建算法，即在進(jìn)行Walsh-Hadamard變換的過程中，實時判斷檢測對象是否為反饋關(guān)系；當(dāng)檢測到反饋關(guān)系時，即可停止運算。引入實時檢測后可使計算復(fù)雜度平均減少50%。

線性反饋移位寄存器；擾碼；反饋多項式；Walsh-Hadamard變換

1 引言

在合作通信中，通信雙方預(yù)先知道調(diào)試樣式及參數(shù)、編碼方式及參數(shù)和通信協(xié)議等信息，接收方可以根據(jù)這些先驗信息獲得發(fā)送方的信源信息。在非合作通信偵察領(lǐng)域，被偵察方的通信參數(shù)是很難預(yù)先獲得的，通常需要采用非合作的信號處理技術(shù)進(jìn)行識別和估計。非合作通信信號處理按照處理對象的不同可分為3個層級：波形級、比特流級和更高等級。波形級，主要包括調(diào)制樣式識別、調(diào)制參數(shù)估計、擴(kuò)頻碼估計等；比特流級，主要包括BCH碼識別、卷積碼識別、交織識別、擾碼識別等；更高等級，主要包括協(xié)議分析、信息恢復(fù)等[8]。本文的主要研究方向是，擾碼識別算法。

擾碼器作為物理層中一項重要的組成模塊，被廣泛應(yīng)用在數(shù)字通信當(dāng)中。通?？蓪_碼器可分為兩種類型：同步擾碼器和自同步擾碼器，其對信息流的加擾方式稍有區(qū)別，但是它們構(gòu)造的核心均在于線性反饋移位寄存器(Linear Feedback Shift Register, LFSR)的反饋關(guān)系。本文以同步擾碼為例進(jìn)行擾碼重建算法研究，其主要包括反饋多項式檢測和初始狀態(tài)恢復(fù)兩個方面，使用快速相關(guān)攻擊算法可進(jìn)行初始狀態(tài)的恢復(fù)，所以主要討論反饋多項式檢測。

文獻(xiàn)[13]在研究“利用Walsh函數(shù)解二元域方程組”的問題時首先指出，作為求解m序列極小多項式的一種有效算法，可以利用Walsh-Hadamard變換進(jìn)行擾碼反饋關(guān)系的檢測，變換后譜系數(shù)可表示為方程組成立個數(shù)與不成立個數(shù)之差。文獻(xiàn)[14]在游凌Walsh-Hadamard變換應(yīng)用研究的基礎(chǔ)上，進(jìn)一步研究了含錯擾碼序列的重建問題，構(gòu)建了含錯情況下的擾碼序列生成多項式估計算法，但在建立數(shù)學(xué)模型模中同樣未考慮信息序列的影響；文獻(xiàn)[15]基于信源不平衡性；對符合抽頭位置的比特狀態(tài)不平衡性進(jìn)行了理論分析，提出了一種自同步擾碼生成多項式的盲識別算法；文獻(xiàn)[16]基于游程統(tǒng)計估計了自同步擾碼的多項式階數(shù)。另外，采用低重量倍式搜索，文獻(xiàn)[17]中提出了檢測信息序列有偏性的擾碼重建算法(Cluzeau算法)，文獻(xiàn)[15]中的算法可以歸為此類統(tǒng)計檢測算法，文獻(xiàn)[18]通過更精確的方差估計改進(jìn)了Cluzeau算法的性能，并提出了有含噪情況下的重建算法。

基于Walsh-Hadamard變換的擾碼重建算法，是在全局尋找最優(yōu)解，可描述為在最大成立數(shù)準(zhǔn)則下的最優(yōu)判決。以加法運算為單位進(jìn)行統(tǒng)計，基于Walsh-Hadamard變換的擾碼重建算法的計算復(fù)雜度可以表示為(22(L+1))，使用快速變換算法時可降為[19]

如果難以在可以接收的時間內(nèi)檢測到反饋多項式，那么將導(dǎo)致基于Walsh-Hadamard變換的擾碼重建算法不可用。本文將Cluzeau算法中的判決過程引入到Walsh-Hadamard變換，即對每次運算進(jìn)行實時檢測，以判斷是否為反饋關(guān)系，并計算誤判概率。當(dāng)檢測到反饋關(guān)系時，即完成反饋關(guān)系重建，從而避免全局搜索，降低Walsh-Hadamard變換方法的復(fù)雜度。

本文首先建立擾碼重建的數(shù)學(xué)模型；其次，簡要介紹基于Hadamard變換的擾碼重建算法；再次，給出基于實時檢測的線性擾碼重建算法；最后，討論算法的計算復(fù)雜度。

2 數(shù)學(xué)模型

擾碼器將偽隨機(jī)序列和輸入信息序列組合，輸出加擾序列。通常采用LFSR產(chǎn)生偽隨機(jī)的擾碼序列，而一個LFSR序列由反饋多項式和初始狀態(tài)決定。將擾碼序列{s}與信息序列{x}進(jìn)行模-2加，輸出加擾序列{y}(圖1，圖2)，可表示為

圖1 信源加擾后傳輸框圖

其中，?表示模-2加運算。令表示LFSR中寄存器的數(shù)量，LFSR的反饋多項式表示為()。令

那么，由LFSR生成的偽隨機(jī)序列滿足如式(4)關(guān)系：

假設(shè)二進(jìn)制信息序列{x}由一有偏信源產(chǎn)生，

其中，x?{0,1},表征有偏性。信道采用二進(jìn)制對稱信道模型，信道噪聲n滿足

本文研究擾碼重建算法時，首先考慮無噪聲情況，然后將算法擴(kuò)展到有噪環(huán)境。

3 基于Walsh-Hadamard變換的反饋多項式估計算法

根據(jù)Walsh-Hadamard變換解含錯方程組的原理，可通過變換求解m序列極小多項式，變換后譜系數(shù)的物理意義可表示為使反饋關(guān)系成立的數(shù)據(jù)量與不成立數(shù)據(jù)量之差[13]。最終，將使反饋關(guān)系成立數(shù)據(jù)量最多的多項式，作為LFSR反饋關(guān)系的估計值。下面簡要回顧基于Walsh-Hadamard變換的反饋關(guān)系估計方法。

定義Walsh-Hadamard矩陣,為

其中，初始矩陣

2維列矢量，經(jīng)Walsh-Hadamard變換后，生成2列矢量，可描述為

基于Walsh-Hadamard變換的反饋關(guān)系估計算法步驟如下：

(1)接收二進(jìn)制序列{r}，以+1個數(shù)據(jù)為一組，進(jìn)行連續(xù)分組并轉(zhuǎn)換為十進(jìn)制數(shù)，即把轉(zhuǎn)換成十進(jìn)制數(shù)，個接收數(shù)據(jù)產(chǎn)生個十進(jìn)制數(shù)；

(3)由式(9)，進(jìn)行Walsh-Hadamard變換生成2+1維矢量；

(4)將矢量中最大元素所在位置進(jìn)行二進(jìn)制表示，并轉(zhuǎn)換為反饋關(guān)系，矢量中的第個元素所在位置的十進(jìn)制表示為。

由Walsh-Hadamard變換的物理意義，將查找最大元素的估計準(zhǔn)則稱為最大成立數(shù)準(zhǔn)則。本文中，假設(shè)線性反饋多項式的階數(shù)已知。

4 基于實時檢測的線性擾碼重建算法

從上節(jié)分析可知，基于Walsh-Hadamard變換的反饋關(guān)系估計算法，是在測試集合中以最大成立數(shù)為準(zhǔn)則尋找最優(yōu)解，需要遍歷每一個測試對象，在未完成Walsh-Hadamard變換之前不能得出反饋關(guān)系的估計。根據(jù)式(1)，在低階數(shù)Walsh-Hadamard變換情況下，計算復(fù)雜度問題并不明顯，但隨著階數(shù)的不斷增加，Walsh-Hadamard變換的計算復(fù)雜度將呈指數(shù)增加。因此，為降低算法計算復(fù)雜度，考慮引入實時檢測，即在進(jìn)行Walsh-Hadamard變換的過程中不斷進(jìn)行反饋關(guān)系判定，當(dāng)判決通過時，即完成反饋關(guān)系的估計?；趯崟r檢測的重建算法，不需要等到變換完成后在全局尋找最優(yōu)解，因此可降低算法計算復(fù)雜度。

我們國家在國際分工當(dāng)中的地位要取決于出口產(chǎn)品的質(zhì)量以及數(shù)量，我們長期占有的是數(shù)量的優(yōu)勢，其質(zhì)量要依靠的是企業(yè)生產(chǎn)環(huán)節(jié)帶來的附加價值，所以國際分工的檔次位置是根據(jù)所創(chuàng)造出的附加值來區(qū)分和比較。紡織品、服裝等傳統(tǒng)生產(chǎn)方式仍然處于簡單加工的環(huán)節(jié)，因此帶來的附加值比較少。我們現(xiàn)階段實現(xiàn)的是從中低端產(chǎn)品向高端工業(yè)制品的轉(zhuǎn)換，附加值要在高精尖技術(shù)行業(yè)當(dāng)中去實現(xiàn)，很多創(chuàng)新要不斷升級改造，適應(yīng)社會經(jīng)濟(jì)的變化，不斷升級的國際分工當(dāng)中，各環(huán)節(jié)的附加值仍然需要一定的時間去體現(xiàn)。

本節(jié)首先給出判決多項式是否為反饋多項式的方法，然后給出基于實時檢測的擾碼重建算法。

因為y=x?s,，所以

{x}是有偏信息序列，所以

其中，“奇數(shù)”表示累加中的取值為奇數(shù)。根據(jù)文獻(xiàn)[17]中定理1和文獻(xiàn)[18]中第IV節(jié)中的方差分析可知，如果()是擾碼的反饋多項式，那么當(dāng)時，

漸進(jìn)服從標(biāo)準(zhǔn)正態(tài)分布律。

當(dāng)()不是反饋多項式時，由偽隨機(jī)序列的隨機(jī)性可得Pr{z=0}=0.5，那么漸進(jìn)服從方差為的正態(tài)分布，其均值隨()變化。在非反饋多項式情況下，均值的浮動會降低反饋多項式檢測的性能，因此，令均值為，這將使得大部分(99.7%)測試值在此范圍內(nèi)[20]。在判決反饋多項式時，基于以下兩個假設(shè)：

H0:~(,)。(()不是反饋多項式)；

Pr(=|H0)=Pr(=|H1) (16)

即

因此，可得門限

其中

虛警概率P和漏檢概率P分別為

實際中，需要首先確定虛警概率指標(biāo)P，然后計算達(dá)到性能條件時的門限。由式(21)得，

令

那么，判決門限滿足

如果<，接受H0假設(shè)；否則，接受H1假設(shè)。

基于實時檢測的擾碼重建算法步驟如下：

(1)確定虛警概率P；

(2)接收二進(jìn)制序列{r}，以+1個數(shù)據(jù)為一組，進(jìn)行連續(xù)分組并轉(zhuǎn)換為十進(jìn)制數(shù)，即把rr+1r+L轉(zhuǎn)換成十進(jìn)制數(shù)，個接收數(shù)據(jù)產(chǎn)生個十進(jìn)制數(shù)；

(4)根據(jù)式(25)，計算判決門限；

(5)由式(9)，設(shè)

(6)依次從1變換到2+1；

(7)計算b=aT；

(8)如果b>，那么將進(jìn)行二進(jìn)制表示，并轉(zhuǎn)換為反饋關(guān)系；否則重復(fù)步驟(6)至步驟(8)。

值得注意的是，步驟(7)中并未考慮快速算法，同樣可以使用快速算法計算b。

5 有噪條件下的擾碼重建

在上節(jié)的算法分析中，并沒有考慮噪聲干擾的情況，本節(jié)將擴(kuò)展所提算法到有噪情況。在經(jīng)過二進(jìn)制對稱信道后，接收序列{r}可表示為r=y?n(圖1)。由y=x?s得

r=x?s?n=x?n?s=?s(27)

不論實時檢測，還是全局查找最大成立數(shù)，算法的檢測性能均與待檢測數(shù)據(jù)源的有偏性息息相關(guān)。將修正后的有偏性代入式(11)和式(12)，可得到修正的H1假設(shè)：

H1:~(|μ|,σ2)

其中，

對于觀測者而言，需要在一定的性能指標(biāo)下，確定所需的接收數(shù)據(jù)量N。設(shè)待檢測的多項式重量為，需要達(dá)到的虛警概率和漏報概率分別為P和P，令

根據(jù)式(24)，式(29)，式(30)和式(31)可得，數(shù)據(jù)量需求N滿足

在重量增加的情況下，為達(dá)到既定的檢測性能指標(biāo)，需要更多觀測數(shù)據(jù)(圖3)。對于Walsh- Hadamard變換而言，待測試多項式的重量是波動變化的，在觀測數(shù)據(jù)量一定的情況下檢測性能會隨

重量產(chǎn)生波動。但是，對于不滿足反饋關(guān)系的高重量待檢測多項式，根據(jù)式(21)可知，虛警概率指標(biāo)與待檢測多項式的重量無關(guān)，只決定于數(shù)據(jù)量N。因此，在考慮數(shù)據(jù)量需求時，只需關(guān)注反饋關(guān)系式的重量。從上述分析亦可知，實時檢測算法的性能與數(shù)據(jù)量、數(shù)據(jù)有偏性和反饋多項式重量密切相關(guān)；同時，擾碼的初始狀態(tài)和反饋多項式重量分布，這些隨機(jī)因素在大樣本的情況下，對于統(tǒng)計結(jié)果的影響可以忽略。

圖3 不同反饋多項式重量情況下數(shù)據(jù)量需求隨數(shù)據(jù)有偏性的變化曲線，Pn=Pf =105

6 計算復(fù)雜度和仿真分析

以加法運算為單位進(jìn)行統(tǒng)計，2+1階Walsh- Hadamard變換的計算復(fù)雜度為(22(L+1))，使用快速算法的情況下復(fù)雜度可降為[19]

在分析Walsh-Hadamard變換復(fù)雜度中，未考慮構(gòu)造2(L+1)維矢量的計算復(fù)雜度，通常應(yīng)用中，數(shù)據(jù)量應(yīng)當(dāng)在可承受的范圍內(nèi)，所以忽略此處的復(fù)雜度。在數(shù)據(jù)量一定的情況下，根據(jù)虛警概率指標(biāo)，就可計算得到判決門限。假設(shè)擾碼的反饋關(guān)系落在2(L+1)維矢量中任意位置的概率相同，那么平均進(jìn)行

次判決就可得到反饋關(guān)系。根據(jù)式(34)可知，基于實時檢測可以平均減少50%的運算量。

表1 基于實時檢測的擾碼重建算法仿真結(jié)果

圖4 擾碼反饋多項式為1+x2+x3+x4+x8情況下的Walsh-Hadamard變換譜系數(shù)

圖5 擾碼反饋多項式為1+x+x6+x7+x9情況下的Walsh-Hadamard變換譜系數(shù)

圖6 擾碼反饋多項式為1+x+x5+x10情況下的Walsh-Hadamard變換譜系數(shù)

7 結(jié)束語

為降低基于Walsh-Hadamard變換的擾碼重建算法的計算復(fù)雜度，本文提出了一種基于實時檢測的擾碼重建算法，即在Walsh-Hadamard變換過程中實時對反饋關(guān)系作出判斷，而不是在全局尋找最優(yōu)解，進(jìn)而降低了算法計算復(fù)雜度。其檢測性能受穩(wěn)定性因素和隨機(jī)性因素兩個方面影響，其中穩(wěn)定性影響因素主要包括：信源有偏性、接收數(shù)據(jù)序列長度和反饋多項式重量；隨機(jī)性影響因素主要包括：LFSR初始狀態(tài)和反饋多項式的重量分布。這些因素同樣會影響基于Walsh-Hadamard變換的擾碼重建算法的檢測性能，雖然在最大成立數(shù)準(zhǔn)則下尋找全局最優(yōu)解，可以平衡一些不確定因素的影響，但文中檢測性能的分析亦可用來指導(dǎo)基于Walsh- Hadamard變換的擾碼重建算法的應(yīng)用。

[1] 錢國兵, 李立萍, 郭亨藝. 多入單出正交空時分組碼系統(tǒng)的調(diào)制識別[J]. 電子與信息學(xué)報, 2015, 37(4): 863-867. doi: 10.11999/JEIT140644.

QIAN Guobing, LI Liping, and GUO Hengyi. Modulation identification for orthogonal space-time block code in multiple input single output systems[J].&, 2015, 37(4): 863-867. doi: 10.11999/JEIT140644.

[2] 沈斌, 王建新. 基于奇異值分解的直擴(kuò)信號偽碼序列及信息序列盲估計方法[J]. 電子與信息學(xué)報, 2014, 36(9): 2098-2103. doi: 10.3724/SP.J.1146.2013.01692.

SHEN Bin and WANG Jianxin. Blind estimation of the PN sequence and information sequence of a DSSS signal based on SVD[J].&, 2014, 36(9): 2098-2103. doi: 10.3724/SP.J.1146.2013.01692.

[3] 沈斌, 王建新. 窄帶干擾條件下含有未知載頻的直擴(kuò)信號的偽碼序列估計[J]. 電子與信息學(xué)報, 2015, 37(7): 1556-1561. doi: 10.11999/JEIT141322.

SHEN Bin and WANG Jianxin. Estimation of PN sequence in DSSS signals with unknown carrier frequency under narrow band interference[J].&, 2015, 37(7): 1556-1561. doi: 10.11999/JEIT141322.

[4] 闊永紅, 曾偉濤, 陳健. 基于概率逼近的本原BCH碼編碼參數(shù)的盲識別方法[J]. 電子與信息學(xué)報, 2014, 36(2): 332-339. doi: 10.3724/SP.J.1146.2013.00584.

KUO Yonghong, ZENG Weitao, and CHEN Jian. Blind identi6cation of primitive BCH codes parameters based on probability approximation[J].&, 2014, 36(2): 332-339. doi: 10.3724/ SP.J.1146.2013.00584.

[5] 解輝, 王豐華, 黃知濤. 基于最大似然檢測的(,1,)卷積碼盲識別方法[J]. 電子與信息學(xué)報, 2013, 35(7): 1671-1676. doi: 10.3724/SP.J.1146.2012.01578.

XIE Hui, WANG Fenghua, and HUANG Zhitao. Blind recognition of (,1,) convolutional code based on maximum likelihood detection[J].&, 2013, 35(7): 1671-1676. doi: 10.3724/SP.J.1146. 2012.01578.

[6] 解輝, 王豐華, 黃知濤. 卷積交織器盲識別方法[J]. 電子與信息學(xué)報, 2013, 35(8): 1952-1957. doi: 10.3724/SP.J.1146.2013. 00287.

XIE Hui, WANG Fenghua, and HUANG Zhitao. A method for blind recognition of convolutional interleave[J].&, 2013, 35(8): 1952-1957. doi: 10.3724/SP.J.1146.2013.00287.

[7] 趙知勁, 顧驍煒, 沈雷. 非周期長碼直擴(kuò)信號的長擾碼識別[J]. 電子與信息學(xué)報, 2014, 36(8): 1792-1797. doi: 10.3724/ SP.J.1146.2013.01454.

ZHUAO Zhijin, GU Xiaowei, and SHEN Lei. An identification method of long pseudo-random code sequence in non-periodic direct sequence spread spectral signals[J].&, 2014, 36(8): 1792-1797. doi: 10.3724/SP.J.1146.2013.01454.

[8] 高逸龍. 基于網(wǎng)絡(luò)層的鏈路層協(xié)議盲分析[D]. [碩士論文], 電子科技大學(xué), 2013.

GAO Yilong. Blind analysis of the link layer protocol based on the network layer[D]. [Master dissertation], University of Electronic Science and Technology of China, 2013.

[9] MEIER W and STAFFELBACH O. Fast correlation attack on stream ciphers[C]. Advances in Cryptology, Davos, Switzerland, 1988: 301-314. doi: 10.1007/3-540-45961-8_28.

[10] MEIER W and STAFFELBACH O. Fast correlation attack on stream ciphers[J]., 1989, 1(3): 159-176. doi: 10.1007/BF02252874.

[11] JOHANSSON T and J?NSSON F. Improved fast correlation attacks on stream ciphers via convolutional codes[C]. Advances in cryptology, Prague, Czech Republic, 1999: 347-362. doi: 10.1007/3-540-48910-X_24.

[12] JOHANSSON T and J?NSSON F. Fast correlation attacks through reconstruction of linear polynomials[C]. 20th Annual International Cryptology Conference Santa Barbara, California, USA, 2000: 300-315. doi: 10.1007/3-540-44598- 6_19.

[13] 游凌, 朱中梁. Walsh函數(shù)在解二元域方程組上的應(yīng)用[J]. 信號處理, 2000, 16(增刊): 27-30.

YOU Ling and ZHU Zhongliang. The application of Walsh function in resolving of F(2) equations[J]., 2000, 16(Supplement): 27-30.

[14] 伍文君, 黃芝平, 唐貴林, 等. 含錯擾碼序列的快速恢復(fù)[J]. 兵工學(xué)報, 2009, 30(8): 1134-1138.

WU Wenjun, HUANG Zhiping, TANG Guilin,. Fast recovery of interfered scrambling code sequence[J]., 2009, 30(8): 1134-1138.

[15] 廖紅舒, 袁葉, 甘露. 自同步擾碼的盲識別方法[J]. 通信學(xué)報, 2013, 34(1): 136-143. doi: 10.3969/j.issn.1000-436x.2013.01. 016.

LIAO Hongshu, YUAN Ye, and GAN Lu. Novel blind recognition method for self-synchronized scrambler[J]., 2013, 34(1): 136-143. doi: 10. 3969/j.issn.1000-436x.2013.01.016.

[16] 黃芝平, 周靖, 蘇紹璟, 等. 基于游程統(tǒng)計的自同步擾碼多項式階數(shù)估計[J]. 電子科技大學(xué)學(xué)報, 2013, 42(4): 541-545. doi: 10.3969/j.issn.1001-0548.2013.04.002.

HUANG Zhiping, ZHOU Jing, SU Shaojing,. Order estimation of self-synchronizing scrambling polynomial based on run statistic[J].2013, 42(4): 541-545. doi: 10.3969/j.issn.1001-0548.2013.04.002.

[17] CLUZEAU M. Reconstruction of a linear scrambler[J]., 2007, 56(9): 1283-1291. doi: 10.1109/TC.2007.1055.

[18] LIU X B, KOH S N, WU X W,. Reconstruction of a linear scrambler with improved detection capability and in the presence of noise[J]., 2012, 7(1): 208-218. doi: 10.1109/ TIFS.2011.2169790.

[19] AHMED N and RAO K R. Orthogonal Transforms for Digital Signal Processing[M]. Berlin Heidelberg, Springer, 1975.

[20] MA Yu, ZHANG Limin, and WANG Haotong. Reconstructing synchronous scrambler with robust detection capability in the presence of noise[J]., 2015, 10(2): 397-408. doi: 10.1109/TIFS.2014.2378143.

Reconstruction of Scrambler with Real-time Test

MA Yu ZHANG Limin

(,264001,)

Scrambler reconstruction algorithm based on Walsh-Hadamard transformation is a promising method to recover the feedback relationships, which picks out the optimal solution under the rule of maximum number. However, its computation complexity increases markedly with the transformation degree. In order to reduce the complexity, a method to reconstruct the scrambler with real-time test is proposed. In the process of Walsh- Hadamard transformation, the objects can be tested in real time. If the feedback polynomial is detected, the transformation can be terminated. With real-time test, the computation complexity can be reduced about 50% on average.

Linear Feedback Shift Register (LFSR); Scrambler; Feedback polynomial; Walsh-Hadamard transformation

TN919

A

1009-5896(2016)07-1794-06

10.11999/JEIT151068

2015-09-21；改回日期：2016-04-08；網(wǎng)絡(luò)出版：2016-05-24

張立民 iamzlm@163.com

泰山學(xué)者工程專項經(jīng)費

Taishan Scholar Special Foundation

馬 鈺： 男，1986年生，助理工程師，博士生，研究方向為非合作通信信號處理.

張立民： 男，1966年生，教授，研究方向為衛(wèi)星信號處理及應(yīng)用.