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

方俊初，呂 虹，張愛雪

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

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

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

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

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

1 建立一種映射關系

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

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

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

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

2 共軛狀態的表示方法

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

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

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

表1 狀態表實例Tab.1 An example of state table

表2 共軛狀態表Tab.2 Conjugated state table

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

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

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

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

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

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

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

4 應用

4.1 子序列個數的統計

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

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

表3 共軛狀態交點數Tab.3 The number of intersect points

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

4.2 子序列的生成

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

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

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

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

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

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

5 結論

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

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序列本原多項式的高階統計測定算法［J] .兵工學報，2010(12):1593－1597.

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

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

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