產生m子序列的一種實用算法

方俊初，呂 虹，張愛雪

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

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

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

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

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

1 建立一種映射關系

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 應用

4.1 子序列個數的統(tǒng)計

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

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

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

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

4.2 子序列的生成

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

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

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

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

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

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

5 結論

1)本文解決了“如何判斷兩對共軛狀態(tài)在圈內有交點”這一形成子序列的關鍵問題。解決問題的思路簡潔，非常便于程序實現。

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

［1] 呂 虹，段穎妮，管必聰，等.第一類m子序列的構造［J] .電子學報，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] .計算機工程與應用，2007(22):12－15.

［4] 謝深泉.De Bruijn序列查尋表標簽的定值構造法［J] .計算機工程與應用，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序列及其在通信中的應用［J] .現代電子技術，2009(09):49－52.

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

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

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

［10] 熊睿佳，胡萬利.偽隨機m序列特性及C語言實現［J] .工程地球物理學報，2011(01):110－112.