方俊初，張愛雪，呂 虹

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

m序列用途廣泛，子序列是由m序列衍生出的一種序列［1－3］。子序列很多［4－5］，對這部分子序列研究的難點在于當(dāng)級數(shù)變化時，交換同樣的共軛狀態(tài)對的后繼狀態(tài)，還能否得到子序列。目前只能根據(jù)共軛狀態(tài)對的特點用不同方法予以證明，文獻［3］中指出符合條件的一對共軛狀態(tài)并用直觀的方法予以證明，文獻［6］中用“模3取余法”證明了一些符合條件的共軛狀態(tài)對。本文研究的是實踐中發(fā)現(xiàn)的另一對符合條件的共軛狀態(tài)對，根據(jù)其狀態(tài)的構(gòu)成特點，將移位寄存器的狀態(tài)和反饋按奇數(shù)位和偶數(shù)位分開，分別研究它們對反饋值的影響，并選取級數(shù)不同的幾個子序列，對它們的偽隨機特性進行了研究，為它們的應(yīng)用奠定了基礎(chǔ)。

1 一種類m序列(子序列)的實現(xiàn)

經(jīng)觀察，在n變化的過程中，狀態(tài)1010…101，其共軛狀態(tài)與0101…010，及其共軛狀態(tài)在狀態(tài)圖上始終處于交錯狀態(tài)，也就是滿足生成子序列的條件，下面從理論上予以證明。

1.1 m序列移位寄存器抽頭位置的表示方法

生成m序列的線性移位寄存器如圖1所示(下面簡稱m序列移位寄存器)，它是由n位移位寄存器、若干個模2加法器組成的線性反饋網(wǎng)絡(luò)及時鐘發(fā)生電路構(gòu)成。模2加法器的輸入通過系數(shù)與移位寄存器的各位狀態(tài)相聯(lián)，ci=1表示此線接通，該位狀態(tài)參與反饋運算;ci=0則表示該位斷開，不參與反饋運算［1］。常將形成m序列時參與反饋的抽頭位置用一個集合表示，如表1所示。

表1 級數(shù)n=5、6時的反饋位置Tab.1 Feedback for stage n=5 and n=6 register

表中［2，5］即表示對應(yīng)的本原多項式為f(x)=1+x2+x5，也就是圖 1 中c2=c5=1，c1=c3=c4=0。為下面描述方便，將每一個這樣的集合統(tǒng)稱為X。

根據(jù)m序列的特點可以用反證法來證明這個結(jié)論，若反饋抽頭個數(shù)為奇數(shù)，則當(dāng)移位寄存器進入全“1”狀態(tài)即“111……11”時，其反饋信號必然為“1”，其下一個狀態(tài)仍然是“111……11”，進入死循環(huán)，不能產(chǎn)生m序列。因而m序列移位寄存器的抽頭個數(shù)一定為偶數(shù)，不可能是奇數(shù)。

1.2 狀態(tài)轉(zhuǎn)換過程的證明

定理1:狀態(tài)1010…101，其共軛狀態(tài)與0101…010，及其共軛狀態(tài)在“圈”內(nèi)必然呈交錯狀態(tài)，具體地說是，級數(shù)n為奇數(shù)時，一對共軛狀態(tài)1010…101、1010…100和另一對共軛狀態(tài)0101…010、0101…011必然成交叉狀態(tài);級數(shù)n為偶數(shù)時一對共軛狀態(tài)1010…10、1010…11和另一對共軛狀態(tài)0101…01、0101…00必然形成交叉狀態(tài)，要證明上面的結(jié)論，需要從下面四個方面證明狀態(tài)的轉(zhuǎn)換過程:

(1)在n=2k+1(k=1、2……)的情況下，若X中有奇數(shù)個奇數(shù)位，則必然有這樣狀態(tài)轉(zhuǎn)換過程:1010…100→0101…010→1010…101……

證明:在n=2k+1(k=1、2……)的情況下，若X中有奇數(shù)個奇數(shù)，根據(jù)引理1，其中必然有奇數(shù)(也可能為零)個偶數(shù)。也就是反饋線是由奇數(shù)個奇數(shù)位和奇數(shù)(也可能為零)個偶數(shù)位組成的。狀態(tài)“1010…100”最高位是奇數(shù)位且為“0”其余皆為“1”，最高位是必然參與反饋的，則剩下的偶數(shù)個奇數(shù)位全為“1”，“模2加”后結(jié)果為“0”，因為偶位全為“0”，不管有幾位參與反饋，結(jié)果都是“0”，總之，狀態(tài)“1010…100”對應(yīng)的反饋是“0”，從而進入下一個狀態(tài)“0101…010”，此時奇數(shù)位皆為“0”，偶數(shù)位皆為“1”，其中奇數(shù)個偶數(shù)位參與反饋得反饋值為“1”，移位寄存器進入下一狀態(tài)“1010…101”。

(2)在n=2k+1(k=1、2……)的情況下，若X中有偶數(shù)個奇數(shù)位，則必然有這樣的狀態(tài)轉(zhuǎn)換過程:0101…011→1010…101→0101…010……

證明:在n=2k+1(k=1、2……)的情況下，若X中有偶數(shù)個奇數(shù)位，則必然有偶數(shù)個偶數(shù)位，狀態(tài)“0101…011”的偶數(shù)位皆為“1”，參與反饋的偶數(shù)個偶數(shù)位“模2加”后結(jié)果為“0”，奇數(shù)位中最高位“1”必然參與反饋而其它奇數(shù)位全為“0”，即可得狀態(tài)“0101…011”對應(yīng)的反饋值為“1”，進入下一狀態(tài)“1010…101”，此時偶數(shù)位全為“0”，“模2加”后結(jié)果為“0”，奇數(shù)位全為“1”，其中的偶數(shù)個參與反饋(必然包括最高位)，決定了反饋值為“0”，進入下狀態(tài)“0101…010”。

(3)在n=2k(k=1、2……)的情況下，若X中有奇數(shù)個偶數(shù)位，則必然有這樣狀態(tài)轉(zhuǎn)換過程:1010…11→0101…01→1010…10……

沉水植物是水體生態(tài)系統(tǒng)的主要初級生產(chǎn)者之一[5]，不僅自身具有氮、磷吸收能力，也是水體生物多樣性賴以維持的基礎(chǔ)，具有維護整個湖泊生態(tài)系統(tǒng)結(jié)構(gòu)與功能的能力，因此恢復(fù)和構(gòu)建沉水植被群落是水體富營養(yǎng)化治理的重要措施[6]。但沉水植被短時間內(nèi)成功恢復(fù)或者重建是比較困難的，受水位波動大、截污不徹底、水體透明度低等因素制約較多，因此人工快速大面積恢復(fù)的難度較大[7-9]。筆者選取湖州仙山湖北湖和南湖入庫河流近岸水域，采用不同種植方式對4種沉水植物的存活率及生長情況進行研究，旨在探索出不同沉水植物在不同環(huán)境特征下的種植技術(shù)，為沉水植物群落的恢復(fù)或重建提供技術(shù)支撐。

證明:在n=2k(k=1、2……)的情況下，若X中有奇數(shù)個偶數(shù)位，也必然有奇數(shù)(也可能為零)個奇數(shù)位。狀態(tài)“1010…11”中奇數(shù)位全為“1”，即奇數(shù)位的反饋值為“1”，偶數(shù)位中只最高位是“1”，其他均為“0”，注意到最高位必然參與反饋，因而偶數(shù)位的反饋值也為“1”，這樣，狀態(tài)“1010…11”對應(yīng)的反饋值就是“0”，移位寄存器進入下一狀態(tài)“0101…01”，這時的奇數(shù)位全為“0”，偶數(shù)位全為“1”，其中奇數(shù)個偶數(shù)位參與反饋決定了反饋值為“1”，移位寄存器進入下狀態(tài)“1010…10”。

(4)在n=2k(k=1、2……)的情況下，若X中有偶數(shù)個偶數(shù)位，則必然有這樣狀態(tài)轉(zhuǎn)換過程:0101…00→1010…10→0101…01……

證明:在n=2k(k=1、2……)的情況下，若X中有偶數(shù)個偶數(shù)位，也必然有偶數(shù)(也可能為零)個奇數(shù)位。狀態(tài)“0101…00”中奇數(shù)位全為“0”，即奇數(shù)位的反饋值為“0”，偶數(shù)位中除最高位外全為“1”，最高位必然參與反饋，這樣偶數(shù)個偶數(shù)位形成的反饋值為“1”，因而狀態(tài)“0101…00”所對應(yīng)的反饋就是“1”，移位寄存器進入下一狀態(tài)“1010…10”，此時，偶數(shù)位全為“0”，即偶數(shù)個偶數(shù)位形成的反饋分量是“0”，而奇數(shù)位全為“1”，其中的偶數(shù)個奇數(shù)位參與反饋，形成的反饋分量是“0”，因而狀態(tài)“1010…10”對應(yīng)的反饋值是“0”，進入下一狀態(tài)“0101…01”。

1.3 反饋函數(shù)的提取及生成的非線性序列

這類子序列的優(yōu)點是級數(shù)不同時，其反饋函數(shù)有統(tǒng)一的實現(xiàn)方法。

實現(xiàn)子序列，就要改變原有m序列移位寄存器的反饋函數(shù)，方法是在原有f(x)基礎(chǔ)上附加一個函數(shù)g(x)，形成新的反饋函數(shù)f'(x)，形式如下

f'(x)=f(x)⊕g(x) (1)

其中g(shù)(x)只有在指定的共軛狀態(tài)時取值“1”，否則為“0”，從而改變了f(x)在此狀態(tài)處對應(yīng)的反饋值，也就改變了狀態(tài)轉(zhuǎn)移順序。

例如，階數(shù)n=6時，取原本多項式1+x+x6，即反饋函數(shù)是f(x)=x1⊕x6，得到的m序列為:

子序列的反饋函數(shù)是f'(x)=f(x)⊕，得到的新的序列(子序列)為:

2 子序列與原序列的特性比較

2.1 周期性及結(jié)構(gòu)特點

子序列是在m序列移位寄存器的基礎(chǔ)上，只改變某些狀態(tài)的轉(zhuǎn)換順序，沒有增加和減少原有狀態(tài)，所以子序列和原m序列具有相同的碼元結(jié)構(gòu)。例如上述序列原序列(2)和子序列(3)，具有相同的周期63，其中“1”的個數(shù)都為32，“0”的個數(shù)都為31。

2.2 游程特性

將序列(2)和序列(3)按游程分段，結(jié)果如下:

它們的游程分布情況見表2。

從表中可見，子序列和原序列具有相同的游程結(jié)構(gòu)，即n階m序列一個周期中共有游程2n－1個，其中長度為1的游程占，長度為2的占長度為3的占，長度為n及n－1的游程特殊，都只有一個［7－8］。

2.3 自相關(guān)特性

對于一周期為p的二元序列，其自相關(guān)特性定義為:

其中η(*)表示映射

Matlab環(huán)境下，對m序列和其子序列的自相關(guān)特性進行測試。

表2 游程分布情況統(tǒng)計Tab.2 Statistic for the run length

由圖2可見，(1)m序列是線性序列，其自相關(guān)特性具有典型的二值特性。子序列是非線性序列，其自相關(guān)特性不同于m序列，呈現(xiàn)多值特性;(2)子序列也具有非常尖銳的自相關(guān)特性，圖中可見其主峰值為1，副峰值隨階數(shù)n增大而明顯減小;(3)進一步實驗表明，當(dāng)級數(shù)增大一定程度時，子序列的自相關(guān)特性十分接近于m序列的自相關(guān)特性［9］。

3 總結(jié)

基于本文給出的這一共軛狀態(tài)對一定能獲得相應(yīng)的子序列，特性測試表明，這一類子序列是良好的偽隨機序列。不足之處在于對子序列的自相關(guān)特性尚不能給出準(zhǔn)確的數(shù)學(xué)表達式，只能通過測試的方法得出其趨勢。

［1］肖國鎮(zhèn)，梁傳甲，王育民.偽隨機序列及其應(yīng)用［M］.北京:國防工業(yè)出版社，1985.

［2］尹曉琪.偽隨機序列及其在通信加密中的應(yīng)用［J］.現(xiàn)代電子技術(shù)，2005(19):42－44.

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

［4］方俊初，呂虹，張愛雪.產(chǎn)生m子序列的一種實用算法［J］.河北工程大學(xué)學(xué)報:自然科學(xué)版，2012，29(4):79－83.

［5］方俊初，呂虹.由m序列生成非線性序列的C語言實現(xiàn)［J］.河南科技大學(xué)學(xué)報:自然科學(xué)版，2013，34(6):47－50.

［6］呂虹，張愛雪，方俊初，等.基于母函數(shù)的非線性反饋函數(shù)及其子序列研究［J］.電子學(xué)報，2012，40(10):2128－2132.

［7］GAO ZHIHAN，F(xiàn)U FANGWEI.The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequence［J］.Theoretical Computer Science，2010(411):3883 －3893.

［8］LVHONG.Design and Implementation of A Maximal Length Nonlinear Pseudorandom Sequence［C］//Proceedings of the 2009 International Conference on Computer and Commun－ications Security.2009:64 －67.

［9］GUANG GONG.Cryptographic properties of the welch －gong trans － formation sequence generators［J］.IEEE Transactionson Information Theory，2002，48(11):2837－2846.