M序列反饋函數(shù)多項(xiàng)式表示的快速構(gòu)造方法

關(guān)杰，周琮偉

（解放軍信息工程大學(xué)三院，河南 鄭州 450001）

1 引言

一個(gè)n級(jí)移位寄存器至多產(chǎn)生周期為2n的序列，通常稱達(dá)到最大周期2n的序列為M序列，又叫De Bruijn序列。關(guān)于LFSR的圈結(jié)構(gòu)已經(jīng)可以完全刻畫，并且知道最大周期的2n-1的序列由其特征多項(xiàng)式為二元域上的本原多項(xiàng)式產(chǎn)生，此時(shí)，稱周期為2n-1的序列為m序列。相較于m序列，M序列有著更好的線性復(fù)雜度和自相關(guān)性質(zhì)，一直以來其構(gòu)造問題是序列密碼理論的研究熱點(diǎn)。由于NFSR的圈結(jié)構(gòu)沒有較好的刻畫手段，故其構(gòu)造的經(jīng)典方法一直以來局限于圖論的反樹和因子關(guān)聯(lián)圖法[1]，小項(xiàng)表示的圈剪接篩法[2]和由一個(gè)M序列通過對(duì)稱[3]、派生[4]和遞歸[5]等得到一類M序列。近期，國外學(xué)者關(guān)于M序列的構(gòu)造主要有“改進(jìn)版”的Martin算法[6]以及關(guān)于D-同態(tài)遞歸構(gòu)造的最新研究成果[7]。而國內(nèi)學(xué)者關(guān)于M序列構(gòu)造的新思路和研究主要有“編織法”[8]，利用復(fù)合函數(shù)所代表的寄存器因子關(guān)聯(lián)圖的研究構(gòu)造M序列[9～13]以及針對(duì)大級(jí)數(shù)的并圈構(gòu)造[14]。以上這些構(gòu)造方法大致可以分為兩類，即同級(jí)直接生成的“并圈法”以及小級(jí)數(shù)遞歸生成大級(jí)數(shù)的“遞歸法”。但是“并圈法”生成的M序列往往需要大量的統(tǒng)計(jì)、判斷和檢驗(yàn)，并且得到的M序列往往是以小項(xiàng)表示；而“遞歸法”往往得到的M序列個(gè)數(shù)較少且M序列往往與小級(jí)數(shù)的初始序列具有較大相關(guān)性。

因此，針對(duì)以上M序列在實(shí)際構(gòu)造中存在的問題，本文提出了一類可以實(shí)際應(yīng)用，且以多項(xiàng)式表示的M序列反饋函數(shù)的快速構(gòu)造方法。

2 預(yù)備知識(shí)

以下是本文用到的定義和符號(hào)說明。

Gf：以f為反饋函數(shù)的n級(jí)移位寄存器的狀態(tài)圖。

對(duì)偶變換D：設(shè)為f產(chǎn)生的GF(2)上任意一條周期為T的序列，令“+”為GF(2)上的加法運(yùn)算，則aT+1,…)。

對(duì)稱變換R：

組合變換RD：a1+1,… )。

Ai：f0(x2,…,xn)中所有i(0 ≤i≤n-1)次項(xiàng)的集合為Ai，特別地，零次項(xiàng)為 1以及最高次項(xiàng)為x2…xn。

常見的反饋函數(shù)有2種表示方法，即小項(xiàng)表示和多項(xiàng)式表示。在實(shí)際應(yīng)用中，更實(shí)用的是用多項(xiàng)式表示的反饋函數(shù)，因?yàn)槔枚囗?xiàng)式表示的反饋函數(shù)其構(gòu)造M序列無論從軟件和硬件實(shí)現(xiàn)的角度都更為方便快捷。文獻(xiàn)[15]給出了圈結(jié)構(gòu)不含枝即非奇異的n級(jí)反饋函數(shù)，其用多項(xiàng)式表示3種函數(shù)變換的對(duì)應(yīng)表達(dá)式。

定理 1[15]設(shè)非奇異n級(jí)反饋函數(shù)的多項(xiàng)式表示為f=x1+f0(x2,… ,xn)，若分別用Df、Rf和RDf表示以D(Gf)、R(Gf)和RD(Gf)為狀態(tài)圖的n級(jí)移位寄存器反饋反饋函數(shù)，則

1946年，De Bruijn從圖論的角度證明了產(chǎn)生M序列的非線性移位寄存器的個(gè)數(shù)等于而非奇異移位寄存器的個(gè)數(shù)恰好等于但是至今人們都無法證明M序列的非線性移位寄存器以2n的長度劃分了整個(gè)非奇異移位寄存器，即猜想若將整個(gè)非奇異移位寄存器對(duì)應(yīng)的反饋函數(shù)看作一個(gè)群，而M序列的反饋函數(shù)可以看作是個(gè)數(shù)為2n的陪集的代表元。20世紀(jì)80年代，高鴻勛[16]在以圈剪接篩法的基礎(chǔ)上提出了一個(gè)非奇異反饋函數(shù)為M序列反饋函數(shù)的充要條件，但對(duì)于生成全部n(n≥ 5)級(jí)M序列來講沒有實(shí)際意義。

本文直接引用文獻(xiàn)[15]中關(guān)于M序列反饋函數(shù)多項(xiàng)式表示的一個(gè)必要條件來說明隨機(jī)尋找到一個(gè)M序列反饋函數(shù)的數(shù)據(jù)復(fù)雜度。

引理 1[15]在M序列反饋函數(shù)f0的多項(xiàng)式表示中，有以下性質(zhì)。

1) 最高次項(xiàng)x2…xn這一項(xiàng)一定出現(xiàn)。

2) 項(xiàng)數(shù)一定是奇數(shù)。

3) 1這一項(xiàng)一定出現(xiàn)。

4) 一次項(xiàng)x2,…,xn不能全部出現(xiàn)。

由于考慮將1和x2…xn這2項(xiàng)排除，則剩余可能出現(xiàn)的項(xiàng)的個(gè)數(shù)即為 2n-1- 2 。在此基礎(chǔ)上將2n-1- 2 種可能出現(xiàn)的項(xiàng)進(jìn)行一個(gè)分類，即定義Ai(1 ≤i≤n-2)，則可能產(chǎn)生M序列反饋函數(shù)的個(gè)數(shù)為 22n-1-2。又因?yàn)轫?xiàng)數(shù)一定是奇數(shù)，則可能產(chǎn)生M序列的反饋函數(shù)的個(gè)數(shù)可以降到 22n-1-3。如果從線性項(xiàng)x2,…,xn不能全部出現(xiàn)的角度考慮，則可能產(chǎn)生M序列反饋函數(shù)的個(gè)數(shù)為假設(shè)M序列的反饋函數(shù)服從均勻分布，則實(shí)際利用引理 1尋找到一個(gè)M序列反饋函數(shù)的數(shù)據(jù)復(fù)雜度約為O(2n-3)。

文獻(xiàn)[15]給出了利用對(duì)偶變換D、對(duì)稱變換R和組合變換RD構(gòu)造M序列的結(jié)論。如引理2所示。

引理2[15]f是M序列的反饋函數(shù)，則Df、Rf和RDf也是M序列的反饋函數(shù)。當(dāng)n≥ 3 時(shí)，f≠Df、f≠Rf；當(dāng)n為偶數(shù)時(shí)，f、Df、Rf、RDf這4個(gè)函數(shù)兩兩互異。

由于在實(shí)際應(yīng)用中并不需要生成全部的M序列反饋函數(shù)，更多的時(shí)候是需要生成具有某些構(gòu)造特點(diǎn)的多項(xiàng)式表示的反饋函數(shù)。本文的工作即是利用由m序列構(gòu)造M序列反饋函數(shù)的結(jié)構(gòu)特性，經(jīng)上述 3種函數(shù)變換得到一類M序列反饋函數(shù)多項(xiàng)式表示的快速構(gòu)造方法，為了更好地說明對(duì)偶變換D、對(duì)稱變換R以及組合變換RD在構(gòu)造M序列反饋函數(shù)中的應(yīng)用，接下來，給出2個(gè)關(guān)于m序列的結(jié)論。

3 由函數(shù)變換證明的2個(gè)結(jié)論

本文由函數(shù)變換發(fā)現(xiàn)了m序列個(gè)數(shù)及其特征多項(xiàng)式的一些性質(zhì)，并從另外一個(gè)角度證明了如下結(jié)論。

引理3[17]當(dāng)n≥ 3 ，總為偶數(shù)。

證明 當(dāng)n≥ 3 時(shí)，由引理 2知，Rf形成的必然是一條新的m序列，則f≠Rf，因此，由Rf形成的特征多項(xiàng)式必然異于f的本原多項(xiàng)式，而二元域上的本原多項(xiàng)式的總數(shù)為因此，當(dāng)必然為偶數(shù)，證畢。

定理2 當(dāng)n為偶數(shù)且n≥ 3 時(shí)，不存在形式為的本原三項(xiàng)式。

證明 當(dāng)n為偶數(shù)且n≥ 3 時(shí)，對(duì)于特征多項(xiàng)式

4 函數(shù)變換及函數(shù)派生在構(gòu)造M序列反饋函數(shù)中的應(yīng)用

4.1 函數(shù)變換在構(gòu)造M序列反饋函數(shù)中的應(yīng)用

在實(shí)際構(gòu)造M序列的過程中，人們很自然地考慮從m序列出發(fā)，即考慮在m序列長度為n-1的0游程中添加一個(gè)0得到M序列，這也符合對(duì)M序列的游程統(tǒng)計(jì)。這種情況構(gòu)造的M序列反饋函數(shù)其實(shí)是在m序列的反饋函數(shù)表達(dá)式中添加一個(gè)小項(xiàng)當(dāng)然將小項(xiàng)表示轉(zhuǎn)化為多項(xiàng)式表示中，發(fā)現(xiàn)得到的M序列反饋函數(shù)滿足引理1的性質(zhì)，考慮該M序列反饋函數(shù)的對(duì)偶函數(shù)時(shí)，其對(duì)偶函數(shù)也應(yīng)該為M序列的反饋函數(shù)，據(jù)此給出了一類M序列反饋函數(shù)f快速構(gòu)造的多項(xiàng)式表示的形式，即形式1。

形式 1 在m序列的反饋函數(shù)q的基礎(chǔ)上添加這2項(xiàng)，即

容易看出，具有形式1的多項(xiàng)式表示的反饋函數(shù)f滿足引理1，從而可以推出m序列的項(xiàng)數(shù)為偶數(shù)項(xiàng)，否則與f中出現(xiàn)1這一項(xiàng)相矛盾。

同時(shí)考慮對(duì)稱函數(shù)Rf和RDf，當(dāng)n≥ 3 ，由f對(duì)稱所形成的必然是新的一條M序列，所以勢(shì)必由f可以得到一個(gè)新的滿足M序列的反饋函數(shù)Rf，觀察其結(jié)構(gòu)可知，仍然是在m序列的反饋函數(shù)上添加 1,x2…xn這2項(xiàng)，其與引理3的結(jié)論是相對(duì)應(yīng)的，同理可得RDf與Df具有相同結(jié)構(gòu)。據(jù)此，可以快速構(gòu)造個(gè)M序列反饋函數(shù)。

如果本文將x1,1,x2…xn這3項(xiàng)單列，指出任意由形式1構(gòu)造的M序列反饋函數(shù)的對(duì)偶函數(shù)Df具有定理3的形式。

定理3 任意由形式1構(gòu)造的M序列反饋函數(shù)f的對(duì)偶函數(shù)Df具有以下形式。

1) 包含x1,1,x2…xn這3項(xiàng)。

2) 包含f在集合Ai(1 ≤i≤n-2)中所有未出現(xiàn)的項(xiàng)。

證明 由于f=q+1+x2…xn=x1+f0(x2,…,xn)，則由定理1知，Df包含項(xiàng)，其多項(xiàng)式展開式中包含f0(x2,…,xn)中所有i(1 ≤i≤n-2)次項(xiàng)的集合為Ai以及 1,x2…xn。

由于f0(x2,…,xn)中的線性項(xiàng)共有奇數(shù)項(xiàng)，故Df一定包含x1,1,x2…xn這3項(xiàng)，且其余項(xiàng)為f在集合Ai(1 ≤i≤n-2)中所有未出現(xiàn)的項(xiàng)，故式(1)和式(2)得證。證畢。

為方便理解，本文給出定理3的一個(gè)實(shí)例。

例1 當(dāng)n= 4時(shí)，f=x1+1+x2x3x4+x4，下面給出Df。

由于原函數(shù)在Ai(1 ≤i≤2)中未出現(xiàn)的項(xiàng)有

x2,x3,x2x3,x2x4,x3x4，因此

同時(shí)，發(fā)現(xiàn)Df+f中的函數(shù)項(xiàng)即是集合Ai(1 ≤i≤n-2)中所有出現(xiàn)的 2n-1- 2 項(xiàng)，因此，可以立即得到推論1。

推論1對(duì)于任意由形式1構(gòu)造的M序列反饋函數(shù)f和Df，g為任意M序列反饋函數(shù)，則f+Df+g具有如下形式。

1) 包含x1,1,x2…xn這3項(xiàng)。

2) 包含g在集合Ai(1 ≤i≤n-2)中所有未出現(xiàn)的項(xiàng)。

4.2 函數(shù)派生在M構(gòu)造序列反饋函數(shù)中的應(yīng)用

根據(jù)之前對(duì)基于由m序列構(gòu)造M序列的分析可知，如果僅從A1選擇奇數(shù)項(xiàng)，只能是形式1構(gòu)造出的個(gè)M序列反饋函數(shù)f，于是，設(shè)想以此為基礎(chǔ)加上若干偶數(shù)項(xiàng)可以構(gòu)造新的M序列反饋函數(shù)。本先給出文獻(xiàn)[15]中一個(gè)關(guān)于函數(shù)派生的結(jié)論，文獻(xiàn)[15]中的證明比較煩瑣，下面，利用文獻(xiàn)[18]中狀態(tài)圖的連線與交點(diǎn)的賦值定義給出簡(jiǎn)化證明。

定理4[15]若f是n級(jí)M序列的反饋函數(shù)，則以下2個(gè)式子也是M序列的反饋函數(shù)。

證明 文獻(xiàn)[18]指出，對(duì)于Gf狀態(tài)圖，任一2對(duì)共軛狀態(tài)的連線的交點(diǎn)的賦值和指的是加上2個(gè)n- 1 維的小項(xiàng)其中，與分別是2對(duì)共軛狀態(tài)。由圈剪接的思想[15]可知，f加上賦值和也是M序列的反饋函數(shù)。而2對(duì)共軛狀態(tài)的連線要相交，必然在Gf中一對(duì)共軛狀態(tài)之間有另一對(duì)共軛狀態(tài)的其中一個(gè)。對(duì)于狀態(tài)(0,0,1,…,1,1)來說，若其后繼狀態(tài)為(0,1,1,…,1,0)，由于((0,1,1,… ,1),(1,1,… ,1 ,1))這條弧必然存在，則狀態(tài)(0,1,1,…,1)的先導(dǎo)必然為(1,0,1,1,…,1)，且同時(shí)(1,1,…,1,1)的后繼必然為(1,1,…,1,0)，故形成這樣一條長弧((0,0,1,…,1,1),(0,1,1,…,1 ,0),…,(1 ,0,1,1,…,1),(0,1,1,…,1),(1,1,…,1,1),(1,1,…,1,0))，則說明共軛狀態(tài)(0,0,1,…,1,1),(1,0,1,1,…,1)和(0,1,1,…,1,0),(1,1,…,1,0)的連線必然相交；若其后繼狀態(tài)為(0,1,1,…,1)，則狀態(tài)(0,1,1,…,1,0)的先導(dǎo)必然為(1,0,1,1,…,1)，故形成這樣一條長弧((1,0,1,1,…,1),(0,1,1,…,1,0),…,(0,0,1,…,1,1),(0,1,1,… ,1),(1,1,…,1,1),(1,1,…,1,0))，則說明共軛狀態(tài)(0,0,1,…,1,1),(1,0,1,1,…,1)和(0,1,1,…,1,0),(1,1,…,1,0)的連線必然相交。綜上可知也是M序列的反饋函數(shù)。同理可證也是M序列的反饋函數(shù)，證畢。

下面，利用定理4的結(jié)論，給出了新的M序列反饋函數(shù)的4種形式

本文首先利用定理4的式(1)，即f是任意以形式 1構(gòu)造的M序列反饋函數(shù)，則也是M序列反饋函數(shù)。

由此，可將f′描述成以下多項(xiàng)式表示的形式，即形式2。

形式 2 在形式 1生成的f基礎(chǔ)上添加這2項(xiàng)，即

而此時(shí)的f′正好滿足從A1選擇奇數(shù)項(xiàng)，An-2選擇偶數(shù)項(xiàng)。同時(shí)，考慮Rf′和Df′，易知Rf′還是屬于與f′相同的一類M序列反饋函數(shù)，而

因此，Df′還可以描述成以下多項(xiàng)式表示的形式，即形式3。

形式 3 在m序列的反饋函數(shù)的基礎(chǔ)上添加轉(zhuǎn)化成多項(xiàng)式表示后，即在形式1生成的f基礎(chǔ)上添加Aj(1 ≤j≤n-2)中排除后剩余的項(xiàng)。

易知，當(dāng)n＞ 3 時(shí)，Df′與f,Df不同。據(jù)此可以快速構(gòu)造個(gè)M序列反饋函數(shù)，分別是f,Df,f′,Df′。

接下來，再次利用定理4的式(2)，即f是M序列反饋函數(shù)，則

也是M序列反饋函數(shù)。若考慮此時(shí)的Rf′和Df′，則由f′的結(jié)構(gòu)可知，Rf′還是屬于與f′相同的一類M序列反饋函數(shù)。當(dāng)n≥ 5 時(shí)，以及f′就與f,Df,f′,Df′不同。此時(shí)根據(jù)推論1，f′,Df′還可以描述成以下多項(xiàng)式表示的形式，即形式4。

形式4 除了有公共的x1,1,x2…xn這3項(xiàng)外，其余項(xiàng)為Df′,f′在集合Ai(1≤i≤n-2)中所有未出現(xiàn)的項(xiàng)。

對(duì)于這類M序列反饋函數(shù)考慮函數(shù)之間相等的情況時(shí)，僅可能是f+X2=Df+X1與f+X1=Df+X2，此時(shí)的f與Df的小項(xiàng)表示必然是僅有一項(xiàng)不同，且不同的項(xiàng)為X2和X1，剩余的項(xiàng)必然是成對(duì)的互為對(duì)偶的項(xiàng)。因此，考慮到函數(shù)之間相等的情況是可能存在的，但出現(xiàn)的概率和個(gè)數(shù)較少，所以實(shí)際上這類方法可以構(gòu)造約個(gè)M序列反饋函數(shù)。最后，可以用圖1來總結(jié)這類快速構(gòu)造方法生成的M序列反饋函數(shù)，其中，

4.3 一類M序列反饋函數(shù)的快速構(gòu)造算法

為了說明這類M序列的構(gòu)造方法可以在實(shí)際中快速生成以多項(xiàng)式表示的反饋函數(shù)，本文給出算法形式，如算法1所示。該算法分為離線和在線階段，并且為了存儲(chǔ)以多項(xiàng)式表示的反饋函數(shù)，將Ai(0 ≤i≤n-1)中的每一元素對(duì)應(yīng)到n-1維的二元數(shù)組向量構(gòu)成的集合

例如，常數(shù)1對(duì)應(yīng)向量(0,…,0)，x2對(duì)應(yīng)向量(1,0,…,0)，x2…xn對(duì)應(yīng)向量(1,…,1)，CBA表示集合A在B中的補(bǔ)集。

算法1 一類M序列反饋函數(shù)的快速構(gòu)造算法

離線階段

對(duì)于給定級(jí)數(shù)n(n≥ 5)時(shí)，以向量形式存儲(chǔ)Ai(0 ≤i≤n-1)中所有元素，并記全體n-1維的二元向量集合為U。對(duì)于給定的m序列的反饋函數(shù)，給出其線性項(xiàng)在A1中的向量集合Q，則在在線階段只需求出M序列反饋函數(shù)中f0的對(duì)應(yīng)向量集合，將集合中元素相加再加上x1，即可得到M序列反饋函數(shù)。

在線階段

Step1 輸入n級(jí)m序列的反饋函數(shù)中線性項(xiàng)的向量集合Q。

Step2 以形式1表示的M序列反饋函數(shù)中f0的對(duì)應(yīng)向量集合F0為

Step3 以定理 3表示的M序列反饋函數(shù)中Df0的對(duì)應(yīng)向量集合DF0為

Step4 以形式2表示的M序列反饋函數(shù)中f0′的對(duì)應(yīng)向量集合F0′為

Step5 以形式 3表示的M序列反饋函數(shù)中Df0′的對(duì)應(yīng)向量集合DF0′為

Step6 以形式 4表示的M序列反饋函數(shù)中f0′,Df0′的對(duì)應(yīng)向量集合F0′,DF0′為

Step7M序列反饋函數(shù)中f0+X1+X2,Df0+X1+X2的對(duì)應(yīng)向量集合為

圖1 一類M序列反饋函數(shù)的快速構(gòu)造算法

分析該算法可知，由于離線階段存儲(chǔ)了所有多項(xiàng)式以次數(shù)為序的項(xiàng)數(shù)集合，存儲(chǔ)復(fù)雜度即為則在線階段，對(duì)于求一個(gè)給定集合在有序集合中的補(bǔ)集，只需要遍歷輸出該有序集合的部分元素即可，因此，時(shí)間復(fù)雜度為O(2n-1)。對(duì)比直接利用“并圈法”得到的以小項(xiàng)表示的M序列反饋函數(shù)，在其轉(zhuǎn)化成多項(xiàng)式表示上所需要的時(shí)間復(fù)雜度將大大降低。同時(shí)，本文也是首次給出以多項(xiàng)式表示的M序列反饋函數(shù)的構(gòu)造算法，下面，本文將簡(jiǎn)要分析該算法給出的這類M序列反饋函數(shù)的重量性質(zhì)。

5 新的M序列反饋函數(shù)的重量性質(zhì)

由于M序列反饋函數(shù)的結(jié)構(gòu)總可以表示成，因此，M序列反饋函數(shù)的重量指的是f0的重量或f0小項(xiàng)表示的項(xiàng)數(shù)，即為w(f0)。在文獻(xiàn)[15]給出了M序列小項(xiàng)表示的反饋函數(shù)的一個(gè)必要條件，有以下結(jié)論。

定理5[15]當(dāng)n≥ 3 時(shí)，對(duì)于Z(n)- 1 與

之間的一切奇數(shù)都有以這奇數(shù)為重量的M序列反饋函數(shù)存在，其中，

根據(jù)定理5，實(shí)際上，本文限制了w(f0)的取值，并且w(f0)的取值是M序列反饋函數(shù)在實(shí)際應(yīng)用中的重要參考指標(biāo)，因此，接下來，考慮快速構(gòu)造方法生成的M序列反饋函數(shù)的重量w(f0)。

首先，可以合理限定m序列的反饋函數(shù)為二項(xiàng)式，即表示為x1+xi，則通過形式1生成的M序列反饋函數(shù)f0=xi+1+x2…xn轉(zhuǎn)化成小項(xiàng)表示后，其項(xiàng)數(shù)為w(f0)=2n-2+1 。當(dāng)n較大時(shí)，Z(n)和Z?(n)都遠(yuǎn)遠(yuǎn)小于2n-2，因此，w(f0) 的取值大概在重量區(qū)間的中間。由于函數(shù)變換不改變w(f0)的取值，以及這種函數(shù)派生方式重量的增減幅度為2或4，因此，新的M序列反饋函數(shù)w(f0)為以下取值之一：

其次，考慮m序列的反饋函數(shù)為四項(xiàng)式，即在二項(xiàng)式的基礎(chǔ)上添加2個(gè)線性項(xiàng)。由于w(f0)從另一個(gè)角度可以看成f0=1的n-1維向量個(gè)數(shù)，新添加的2個(gè)線性項(xiàng)的取值（即該線性項(xiàng)等于0或1）使f0=1的情況個(gè)數(shù)與原有二項(xiàng)式比較不變，因此，此時(shí)n-1維向量滿足f0=1的個(gè)數(shù)不變，即此時(shí)通過形式 1生成的M序列反饋函數(shù)的w(f0)取值為以此類推，通過形式1生成的M序列反饋函數(shù)w(f0) 取值為 2n-2+1[19]，此時(shí)，新的M序列反饋函數(shù)w(f0)為以下取值之一：

綜上所述，可以得到以下結(jié)論。

結(jié)論M序列反饋函數(shù)f（其中，f為圖 1所示的8類M序列反饋函數(shù)）的重量w(f0)的取值必然在以下集合中：

6 結(jié)束語

由m序列構(gòu)造M序列反饋函數(shù)一直以來是實(shí)際應(yīng)用中常見的構(gòu)造方法，本文充分利用m序列構(gòu)造M序列反饋函數(shù)的結(jié)構(gòu)特性，結(jié)合函數(shù)變換以及函數(shù)派生，得到了一類個(gè)數(shù)較多且多項(xiàng)式表示和小項(xiàng)表示的重量都可以確定的M序列反饋函數(shù)。這種構(gòu)造豐富了由m序列構(gòu)造M序列反饋函數(shù)的方法，并且給出了其他項(xiàng)數(shù)和重量條件的反饋函數(shù)，克服了單一由m序列構(gòu)造M序列反饋函數(shù)的構(gòu)造缺陷，在實(shí)際應(yīng)用中有更多可供選擇的以多項(xiàng)式表示的M序列反饋函數(shù)。由于在構(gòu)造過程中，多項(xiàng)式表示的方法還過于煩瑣，是否還存在類似形式1的項(xiàng)數(shù)較少的M序列反饋函數(shù)的構(gòu)造方法，是下一步研究的目標(biāo)。

參考文獻(xiàn)：

[1]中國科學(xué)院數(shù)學(xué)研究所代數(shù)組. 關(guān)于M序列反饋函數(shù)的構(gòu)造方法[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),1977,4:11-22.Institute of Mathematics,Chinese Academy of Sciences. The methods of constructingM-sequence feedback functions[J]. Acta Mathematicae Applicatae Sinica,1977,4:11-22.

[2]康慶德. GF(2)上M序列的構(gòu)造方法[J]. 通信學(xué)報(bào),1983(4): 2-10.KANG Q D. The methods of constructingM-sequence over GF(2)[J].Journal on Communications,1983(4): 2-10.

[3]熊榮華.M序列反饋函數(shù)的構(gòu)造方法Ⅰ[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào),1986(2):227-236.XIONG R H. On methods of constructing the feedback functions ofMsequences I[J]. Acta Mathematicae Applicatae Sinica,1986(2): 227-236.

[4]朱士信.M序列反饋函數(shù)的派生方法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),1991(4): 138-144.ZHU S X. Methods for the derivation of feedback functions ofMse-quences[J]. Journal of Hefei University of Technology,1991(4):138-144.

[5]章照止,羅喬林. 產(chǎn)生M序列的一個(gè)遞推算法[J]. 系統(tǒng)科學(xué)與數(shù)學(xué),1987(4): 335-343.ZHANG Z Z,LUO Q L. A recursive algorithm for the generation of De Bruijn sequences[J]. Journal of System Science and Mathematical Science Chinese Series,1987(4): 335-343.

[6]SAWADA J,WILLIAMS A,WONG D. A surprisingly simple de Bruijn sequence construction[J]. Discrete Mathematics,2016,339(1):127-131.

[7]ABBAS A. Stretching De Bruijn sequences[J]. Designs Codes &Cryptography,2017,85(2):381-394.

[8]高楊,劉松華,王中孝. 一種基于“編織法”的De Bruijn序列構(gòu)造算法[J]. 電子學(xué)報(bào),2018,46(1): 48-54.GAO Y,LIU S H,WANG Z X. A De Bruijn sequence construction algorithm based on “interleaving” construction method[J]. Acta Electronica Sinica,2018,46(1): 48-54.

[9]LI C,ZENG X,LI C,et al. Construction of De Bruijn sequences from LFSRs with reducible characteristic polynomials[J]. IEEE Transactions on Information Theory,2015,62(1):610-624.

[10]CHANG Z,EZERMAN M F,LING S,et al. Construction of De Bruijn sequences from product of two irreducible polynomials[J].Cryptography & Communications,2018,10(2):251-275.

[11]LI M,JIANG Y,LIN D. The adjacency graphs of some feedback shift registers[J]. Designs Codes & Cryptography,2016,82(3):1-19.

[12]LI M,LIN D. The adjacency graphs of LFSRs with primitive-like characteristic polynomials[J]. IEEE Transactions on Information Theory,2017,63(2):1325-1335.

[13]LI M,LIN D. De Bruijn sequences,adjacency graphs and cyclotomy[J].IEEE Transactions on Information Theory,2017,PP(99): 1.

[14]DONG J,PEI D. Construction for De Bruijn sequences with large stage[J]. Designs Codes & Cryptography,2016:1-16.

[15]萬哲先,代宗鐸,劉木蘭,等. 非線性移位寄存器[M]. 北京:科學(xué)出版社,1978.WAN Z X,DAY Z D,LIU M L,et al. Non-linear shift register[M].Beijing: Science Press,1978.

[16]高鴻勛. 非奇函數(shù)是 M 序列反饋函數(shù)的一個(gè)充要條件[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào),1984(1): 9-10.GAO H X. A necessary and sufficient condition for nonsingular function to be feedback function of M-sequences[J]. Acta Mathematicae Applicatae Sinica,1984(1): 9-10.

[17]萬哲先. 代數(shù)與編碼[M]. 北京:科學(xué)出版社,1976.WAN Z X. Algebra and coding[M]. Beijing: Science Press,1976.

[18]高鴻勛. 求全部n級(jí)M序列及其反饋函數(shù)的一個(gè)方法與證明[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào),1979(4): 316-324.GAO H X. A method and proof of finding all n-stage of M-sequences and their feedback functions[J]. Acta Mathematicae Applicatae Sinica,1979(4): 316-324.

[19]許軍進(jìn),尹克震. M序列反饋函數(shù)重量與項(xiàng)數(shù)的分析[J]. 杭州電子科技大學(xué)學(xué)報(bào),2007(1): 24-28.XU J J,YI K Z. Analysis on weights and terms of feedback functions for Sequences[J]. Journal of Hangzhou Dianzi University,2007(1):24-28.