方俊初，呂 虹，張愛雪

(1.安徽工程大學(xué)電氣工程學(xué)院，安徽蕪湖241000 2.安徽建筑工業(yè)學(xué)院電子與信息學(xué)院，安徽 合肥230022)

若n級移位寄存器的特征多項(xiàng)式為n階本原多項(xiàng)式，則該移位寄存器從任意一個(gè)非“0”狀態(tài)出發(fā)所形成的狀態(tài)圖是一個(gè)包含2n－1個(gè)狀態(tài)的大“圈”，如圖1所示。由它產(chǎn)生的GF(2)序列的周期也是2n－1，稱為最大長度序列，即m序列，是一類常用的偽隨機(jī)序列。在這2n－1個(gè)狀態(tài)中，某狀態(tài)S的下一個(gè)狀態(tài)稱為S的“后繼”，而S的前一個(gè)狀態(tài)稱為 S的“前驅(qū)”。而形如 S=(α0，α1，α2，…αn－1)，S*=(α0，α1，α2，…)則稱為一對共軛狀態(tài)。

若兩對共軛狀態(tài)的連線在“圈”內(nèi)存在交點(diǎn)，則交換它們的后繼仍能形成一個(gè)長度為2n－1的大“圈”，與這個(gè)新的狀態(tài)轉(zhuǎn)換較圖對應(yīng)的序列稱為原序列的子序列［1－2]。子序列形成過程如圖2所示，圖中S1和Sp是一對共軛狀態(tài)，Sk和Sq是另一對共軛狀態(tài)。實(shí)線箭頭表示原有的狀態(tài)轉(zhuǎn)換方向，虛線箭頭表示新的狀態(tài)轉(zhuǎn)換方向。

在圖2所示過程中，兩對共軛狀態(tài)的連線(圖中實(shí)線所示)在圈內(nèi)相交是這一轉(zhuǎn)換過程成功的關(guān)鍵。但是單從狀態(tài)轉(zhuǎn)換的角度來判斷哪兩對共軛狀態(tài)在“圈”內(nèi)有交點(diǎn)存在很大的困難，因而文獻(xiàn)［1] 只在每一級中確定了一個(gè)子序列的生成方法。

實(shí)際上，在n階本原多項(xiàng)式f(x)決定的線性移位寄存器中共有2n－1個(gè)狀態(tài)，因?yàn)?0…01在圈內(nèi)沒有共軛狀態(tài)，其余狀態(tài)將兩兩互為共軛，因此共有對共軛狀態(tài)，這些共軛狀態(tài)中符合上述交換條件的可能有很多，如何能快速準(zhǔn)確的找到這些滿足條件的共軛狀態(tài)呢?又如何通過它們簡便而又快速地實(shí)現(xiàn)這些m子序列呢?本文利用數(shù)學(xué)變換思想，建立了一種“映射”，將GF(2)域中“狀態(tài)”映射到整數(shù)域中，共軛狀態(tài)可以用編碼表示，通過該編碼很容易判斷出兩對共軛狀態(tài)在圈內(nèi)有沒有交點(diǎn)。

1 建立一種映射關(guān)系

表1是以GF(2)上以本原多項(xiàng)式f(x)=1+x2+x5為反饋函數(shù)生成的移位寄存器的狀態(tài)表［3－4]。

定義1:在給定本原多項(xiàng)式的基礎(chǔ)上，從任意一個(gè)初始狀態(tài)S0出發(fā)，按照狀態(tài)出現(xiàn)的先后順序?qū)⑦@些狀態(tài)依次記為 S0、S1、S2… S2n－2下標(biāo) 0、1、2…(2n－2)是該狀態(tài)的序號。

某個(gè)狀態(tài)的前驅(qū)與后繼僅與反饋函數(shù)相關(guān)而與初始狀態(tài)無關(guān)。因而可以得出:兩對共軛狀態(tài)在圈內(nèi)的連線是否會相交，與初始狀態(tài)的選擇無關(guān)［5]。

這樣2n－1個(gè)“狀態(tài)”就和0、1、2…2n－2共(2n－1)個(gè)整數(shù)建立了“映射”關(guān)系。編程時(shí)，假設(shè)這些狀態(tài)以數(shù)組的形式存在，那么知道了這個(gè)“序號”就可以找到(“引用”)該“狀態(tài)”，已知“狀態(tài)”也可以判斷其在“圈”中的位置。這為下面研究共軛狀態(tài)的相互關(guān)系提供了方便。

2 共軛狀態(tài)的表示方法

定義2:某一狀態(tài)為 Sk=(α0，α1，α2，…αn－1)，設(shè)其共軛狀態(tài)為Sp=，將它們的連線畫在圈內(nèi)，若k＜p則將這一對共軛狀態(tài)記為［k，p] ，若 k＞p則將這一對共軛狀態(tài)記為［p，k] ，稱為這一對共軛狀態(tài)的“坐標(biāo)”。

共軛狀態(tài)的“坐標(biāo)”包含了這一對共軛狀態(tài)在圈中的位置信息。［k，p] 中k稱為起點(diǎn)，p為終點(diǎn)，按上述定義，起點(diǎn)值一定比終點(diǎn)值要小，即要求0≤k＜p≤2n－2，舉個(gè)例子說，表1中S3和S5是一對共軛狀態(tài)，將其坐標(biāo)記為［3，5] ，而不是［5，3] 。這樣規(guī)定有兩個(gè)目的，一是確定了每一對共軛狀態(tài)只有唯一的一個(gè)坐標(biāo)了;二是方便用“遍歷”法生成共軛狀態(tài)表。有了共軛狀態(tài)表，就可以通過這些坐標(biāo)來研究共軛狀態(tài)在圈中的相互關(guān)系了。表2是根據(jù)表1按上述定義2編程得到的共軛狀態(tài)表。由表2可見共軛狀態(tài)表的特點(diǎn)一是起點(diǎn)是按從小到的順序排列的，二是每一對共軛狀態(tài)在表中只出現(xiàn)一次。

圖3畫出了表2中共軛狀態(tài)在圈中的連線?？梢?，這些共軛狀態(tài)的連線在圈內(nèi)的有的存在交點(diǎn)，有的不存在交點(diǎn)。有交點(diǎn)就可以產(chǎn)生新的序列，問題是在沒有畫出這個(gè)“圈”的情況下，如何才能確定兩對共軛狀態(tài)在圈內(nèi)有無交點(diǎn)呢?

表1 狀態(tài)表實(shí)例Tab.1 An example of state table

表2 共軛狀態(tài)表Tab.2 Conjugated state table

3 子序列生成條件的簡便判斷

觀察圖3中這些連線的相互關(guān)系，并結(jié)合表2，可以得到下面的定理。

定理1:若［k，p] 是一對共軛狀態(tài)，［m，n] 是另一對共軛狀態(tài)，將起點(diǎn)坐標(biāo)較小的這一對共軛狀態(tài)稱第一對共軛狀態(tài)，另一對稱為第二對共軛狀態(tài)，這里假設(shè)［k，p] 是第一對共軛狀態(tài)，若k＜m＜p＜n，則這兩對共軛狀態(tài)的連線在圈內(nèi)一定有交點(diǎn)。

證明:第一對共軛狀態(tài)［k，p] 的連線將“圈”一分為二，從起點(diǎn)出發(fā)，順時(shí)針方向的一側(cè)稱為“右側(cè)”，逆時(shí)針方向的一側(cè)稱為“左側(cè)”。k＜m＜p即第二對共軛狀態(tài)的起點(diǎn)位于第一對共軛狀態(tài)的“右側(cè)”，而 n＞p，根據(jù)定義1，則容易知道 n＞ k，即第二對共軛狀態(tài)的終點(diǎn)一定位于第一對共軛狀態(tài)的“左側(cè)”，因而這兩對共軛狀態(tài)的連線在“圈”內(nèi)必有交點(diǎn)，證畢。

定理1用數(shù)學(xué)語言將原來只能用文字表述的交換條件“數(shù)學(xué)化”了，這種數(shù)字化的結(jié)果是很方便編程統(tǒng)計(jì)出交點(diǎn)的個(gè)數(shù)，也能方便地判斷兩對共軛狀態(tài)是否滿足交換條件。例如上圖中的共軛狀態(tài)［1，14] 和［2，28] 在圈內(nèi)有交點(diǎn)，而［1，14] 和［6，10] 在圈內(nèi)就沒有交點(diǎn)。

應(yīng)當(dāng)指出的是，在反饋函數(shù)確定的情況下，初始狀態(tài)不同，則各狀態(tài)在圈中的序號都將改變，共軛狀態(tài)的坐標(biāo)也就改變，如圖4所示。用上述定義1規(guī)定的共軛狀態(tài)的表示方法仍能反映各共軛狀態(tài)在圈中的相互關(guān)系，如圖3中［1，14] 和［2，28] 對應(yīng)在圖4 就是［11，29] 和［25，30] ，仍可判斷它們的連線在圈內(nèi)有交點(diǎn)。而圖3中的［1，14] 和［6，10] 在圖 4 對應(yīng)的坐標(biāo)是［11，29] 和［3，7] 仍能判斷它們在圈內(nèi)沒有交點(diǎn)。

總之，共軛狀態(tài)在圈內(nèi)是否有交點(diǎn)與初始狀態(tài)無關(guān)，從任一個(gè)初始狀態(tài)出發(fā)進(jìn)行編號，并按定義1生成的共軛狀態(tài)表都能準(zhǔn)確反映共軛狀態(tài)在“圈”內(nèi)的相互關(guān)系。

4 應(yīng)用

4.1 子序列個(gè)數(shù)的統(tǒng)計(jì)

從一個(gè)已知的m序列的狀態(tài)圖，可以得到多少個(gè)子序列呢?顯然，這取決于共軛狀態(tài)的連線在圈內(nèi)有多少個(gè)交點(diǎn)，有了共軛狀態(tài)表，只需按定理1統(tǒng)計(jì)出交點(diǎn)的個(gè)數(shù)，就是能生成的子序列的個(gè)數(shù)了。

實(shí)驗(yàn)結(jié)果:經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)，相同級數(shù)的本原多項(xiàng)式對應(yīng)的線性移位寄存器的共軛狀態(tài)在圈內(nèi)的交點(diǎn)數(shù)是相同的，例如前面講的以f(x)=1+x2+x5為反饋函數(shù)的移位寄存器，其共軛狀態(tài)在圈內(nèi)的交點(diǎn)數(shù)為35，若反饋函數(shù)換為f(x)=1+x3+x5，其共軛狀態(tài)在圈內(nèi)的交點(diǎn)數(shù)也是35，其他的五階本原多項(xiàng)式的情況也是如此。表3給出的是通過實(shí)驗(yàn)得到的級數(shù)為5－10級的線性移位寄存器共軛狀態(tài)在圈內(nèi)的交點(diǎn)數(shù)(子序列個(gè)數(shù))。

表3 共軛狀態(tài)交點(diǎn)數(shù)Tab.3 The number of intersect points

我們知道，n階線性移位寄存器所能產(chǎn)生的m序列(由不同的本原多項(xiàng)式產(chǎn)生)的數(shù)目遠(yuǎn)小于m序列的周期N，但從表3可以看出，一個(gè)本原多項(xiàng)式衍生出的子序列的數(shù)目則遠(yuǎn)遠(yuǎn)大于它的周期，這些子序列保留了m序列的優(yōu)秀偽隨機(jī)特征。

4.2 子序列的生成

下面以定理的形式給出生成m子序列的一般方法。

定理2:若［k，p] 是一對共軛狀態(tài)，［m，n] 是另一對共軛狀態(tài)，若k＜m＜p＜n，或m＜k＜ n ＜ p，則在移位寄存器的反饋函數(shù)中加上(模2加)第m項(xiàng)和第k項(xiàng)的特征小項(xiàng)后，該移位寄存器的狀態(tài)圖將形成一個(gè)新的長度為2n－1的大圈。對應(yīng)此大圈將產(chǎn)生一個(gè)新的不同于原來的序列。

證明:k＜m＜p＜n，或m＜k＜ n ＜ p保證了兩對共軛狀態(tài)在“圈”必有交點(diǎn)。移位寄存器的反饋函數(shù)中加上(模2加)第m項(xiàng)和第k項(xiàng)的特征小項(xiàng)，意味著在上述四個(gè)狀態(tài)后面的反饋函數(shù)值取反，即交換了次狀態(tài)，重新形成了新的大“圈”，證畢。

簡單地講，交換共軛狀態(tài)的后續(xù)狀態(tài)就是在狀態(tài)生成過程中，遇到共軛狀態(tài)中的一個(gè)就將原反饋函數(shù)值取反［7－8]。

程序?qū)崿F(xiàn)的思路是:指定反饋移位寄存器的級數(shù)，輸入相應(yīng)的本原多項(xiàng)式的系數(shù)，從任一初始狀態(tài)出發(fā)，將全部狀態(tài)生成并按順序儲存，根據(jù)共軛狀態(tài)的特點(diǎn)自動生成共軛狀態(tài)表，給定一對共軛狀態(tài)，判斷是否符合交換條件，若符合交換條件，再次生成狀態(tài)表時(shí)在該狀態(tài)的下一個(gè)狀態(tài)輸出前通過異或“1”改變原有的反饋函數(shù)值。這中間可以用序號引用該狀態(tài)［9－10]。

本文根據(jù)上述思想設(shè)計(jì)了程序，只要改變幾個(gè)常數(shù)就可以生成任意級數(shù)本原多項(xiàng)式的全部m子序列或其中一個(gè)子序列，運(yùn)行非常方便，非常適用在需要大量偽隨機(jī)序列的場合。

5 結(jié)論

1)本文解決了“如何判斷兩對共軛狀態(tài)在圈內(nèi)有交點(diǎn)”這一形成子序列的關(guān)鍵問題。解決問題的思路簡潔，非常便于程序?qū)崿F(xiàn)。

2)本文介紹的方法可以在本原多項(xiàng)式的基礎(chǔ)上可方便地產(chǎn)生大量的m子序列，為進(jìn)一步研究這些子序列的性能奠定了基礎(chǔ)，也必將進(jìn)一步擴(kuò)展偽隨機(jī)序列在測量、通信、流密碼等領(lǐng)域中的廣泛應(yīng)用。

［1] 呂 虹，段穎妮，管必聰，等.第一類m子序列的構(gòu)造［J] .電子學(xué)報(bào)，2007(10):2029－2032.

［2] LV HONG.Design and implementation of a maximal length nonlinear pseudorandom sequence［C] .Proceedings of the 2009 International Conference on Computer and Communications Security.2009:12 －16.

［3] 謝深泉.De Bruijn序列間的映射及升級算法［J] .計(jì)算機(jī)工程與應(yīng)用，2007(22):12－15.

［4] 謝深泉.De Bruijn序列查尋表標(biāo)簽的定值構(gòu)造法［J] .計(jì)算機(jī)工程與應(yīng)用，2008(19):37－40.

［5] LAN JINGJING，GOH WANG LING，KONG ZHI HUI，et al.A random number generator for low power cryptographic application［C] .Proceedings of the 2010 International Soc.Design Conference，ISOCC 2010，328－331

［6] 林智慧，陳綏陽，王元一.m序列及其在通信中的應(yīng)用［J] .現(xiàn)代電子技術(shù)，2009(09):49－52.

［7] 蘇紹璟，伍文君，黃芝平，等.含錯(cuò)m序列本原多項(xiàng)式的高階統(tǒng)計(jì)測定算法［J] .兵工學(xué)報(bào)，2010(12):1593－1597.

［8] 張曉林，佟婧，李佑虎.高階統(tǒng)計(jì)分析的m序列檢測新方法［J] .哈爾濱工程大學(xué)學(xué)報(bào)，2010(03):386－390.

［9] 賈銀潔，趙麗娟，許鵬飛.擴(kuò)頻系統(tǒng)中偽隨機(jī)碼發(fā)生器的實(shí)現(xiàn)［J] .現(xiàn)代計(jì)算機(jī)(專業(yè)版)，2008(05):72－74.

［10] 熊睿佳，胡萬利.偽隨機(jī)m序列特性及C語言實(shí)現(xiàn)［J] .工程地球物理學(xué)報(bào)，2011(01):110－112.