基于de Bruijn圖的M序列遞歸升級(jí)構(gòu)造方法

郭 輝，柏 森，陽 溢，宋 斌，李淑云

(1．重慶通信學(xué)院信息工程系，重慶400035;2．應(yīng)急通信重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400035;3．解放軍66019部隊(duì)，北京100093)

1 概述

M序列是由非線性反饋移位寄存器產(chǎn)生的周期最長的序列，也稱為de Bruijn序列。由于M序列具有偽隨機(jī)性、周期性、均衡性、相位相加性、自相關(guān)等特性［1-4］，并且隨著級(jí)數(shù)的增大，M序列的數(shù)量呈指數(shù)級(jí)增多，因而被廣泛應(yīng)用在衛(wèi)星保密通信［1］、擴(kuò)頻通信抗干擾［2］、系統(tǒng)識(shí)別［3］、信息隱藏［4］等方面。雖然目前有了一些生成M序列的方法，但對M序列的研究還不很成熟，關(guān)于它的生成方法及性能尚無完整的理論分析。

目前，M序列的生成方法主要有生成樹法［5］、并圈法［6-8］、查詢表標(biāo)簽法［9-10］、計(jì)算機(jī)搜索算法［11-12］等。值得注意的是文獻(xiàn)［13-15］提出了M序列的升級(jí)算法。文獻(xiàn)［13］提出了一種查詢表標(biāo)簽的升級(jí)算法，通過給定的n級(jí)M序列的查詢表標(biāo)簽，采用合成的方法構(gòu)造出n+1級(jí)M序列的查詢表標(biāo)簽，從而產(chǎn)生n+1級(jí)M序列。但查詢表標(biāo)簽的構(gòu)造較復(fù)雜，實(shí)現(xiàn)有一定的難度。文獻(xiàn)［14-15］給出了二元n級(jí)M序列的升級(jí)算法，在已知低級(jí)M序列反饋函數(shù)條件下，求高級(jí)M序列的反饋函數(shù)。文獻(xiàn)［16］給出了求反饋函數(shù)的升級(jí)算法，通過定義環(huán)F2+μF2上的n級(jí)de Bruijn圖到n－1級(jí)de Bruijn圖的滿同態(tài)映射D，證明一個(gè)由環(huán)F2+μF2上n－1級(jí)M序列的反饋函數(shù)產(chǎn)生n級(jí)M序列反饋函數(shù)的升級(jí)算法定理。文獻(xiàn)［17］給出了k元n級(jí)de Bruijn序列的反饋函數(shù)的一個(gè)升級(jí)算法，該算法定義了k個(gè)從k元n級(jí)de Bruijn圖到k元n－1級(jí)de Bruijn圖的滿同態(tài)映射，利用這些同態(tài)映射，從一個(gè)n－1級(jí)k元de Bruijn序列的反饋函數(shù)直接生成k個(gè)k元n級(jí)de Bruijn序列的反饋函數(shù);進(jìn)而給出了一個(gè)從二元n－2r級(jí)de Bruijn序列反饋函數(shù)直接生成二元n級(jí)de Bruijn序列的反饋函數(shù)。

上述升級(jí)算法只在理論上進(jìn)行了分析，而沒有給出具體的實(shí)驗(yàn)結(jié)果。這些算法存在的局限性:或是不能生成全部的M序列;或算法復(fù)雜度高，且當(dāng)n較大時(shí)，運(yùn)行效率較低;或是不能生成任意級(jí)數(shù)任意數(shù)量的M序列。由于高級(jí)M序列數(shù)量巨大，生成全部的M序列需要大量的時(shí)間。文獻(xiàn)［18-20］對快速生成一條M序列進(jìn)行了研究。遺傳算法［18］把M序列作為一種特殊的旅游銷售員問題(TSP)，并嘗試找到最佳的觀光路徑。首先，用隨機(jī)式或探索式二種方法之一產(chǎn)生初始的觀光路線集合。其次，利用公式計(jì)算集合中節(jié)點(diǎn)的2個(gè)相鄰節(jié)點(diǎn)與此節(jié)點(diǎn)的長度之和，長度大于2的節(jié)點(diǎn)相互交換位置，直到產(chǎn)生最理想的或者沒有最理想的觀光路線為止。最后，重復(fù)以上2種操作500次，輸出產(chǎn)生的所有最理想的觀光路線集合。當(dāng)n較大時(shí)，只能產(chǎn)生一條M序列，文中把遺傳算法看做生成一條M序列的方法。存在的局限性:(1)由于算法中產(chǎn)生初始觀光路線的方法為隨機(jī)方式，所以不一定產(chǎn)生n級(jí)的所有M序列，且產(chǎn)生的M序列不具有唯一性。(2)當(dāng)級(jí)數(shù)較大時(shí)，算法效率較低。文獻(xiàn)［19-20］給出了 Prefer-one和Prefer-opposite算法，Prefer-one算法［15］采用的是直接添值方法，產(chǎn)生一個(gè)n級(jí)M序列，首先設(shè)置n個(gè)0，后面添加1，如果任意相鄰的n位沒有出現(xiàn)與之相同的數(shù)，則添加數(shù)保留，否則添加0。直到添加1或者0沒有新的數(shù)值出現(xiàn)，算法結(jié)束。存在局限性:(1)形式固定，M序列添加的前n位一定是1;(2)只能產(chǎn)生一條M序列。Prefer-opposite算法［20］也是采用直接添值的方法，添值為上一位的相反數(shù)。首先設(shè)置n個(gè)0，后面添加最后一位0的相反數(shù)1，如果任意相鄰的n位沒有出現(xiàn)與之相同的數(shù)，則添加數(shù)保留，否則添加和最后一位相同的數(shù)。直到添加1或者0沒有新的數(shù)值出現(xiàn)，算法結(jié)束。本文算法存在的局限性:(1)算法不能產(chǎn)生全1的狀態(tài);(2)形式固定，M序列最后n位一定是1;(3)只能產(chǎn)生一條M序列。2種算法相比，Prefer-one算法產(chǎn)生的M序列前部分1的數(shù)量要多，對于級(jí)數(shù)n=59的 M序列，前106位90%為1。Preferopposite算法產(chǎn)生的M序列傾向于1和0的平衡，對于級(jí)數(shù)n在10～20之間，M序列的前1/4位0和1的比例更接近50%。

本文在圖論知識(shí)的基礎(chǔ)上，給出一種隨機(jī)生成一條二元高級(jí)M序列的方法。首先任意給出一條二元n級(jí)M序列，此M序列轉(zhuǎn)換為二元n級(jí)de Bruijn圖中的一條Hamilton回路;其次求圖中此Hamilton回路的補(bǔ)路，補(bǔ)路由自環(huán)和不同長度圈組成，補(bǔ)路中自環(huán)和各圈隨機(jī)選取一個(gè)點(diǎn)，按照此點(diǎn)在原Hamilton回路中的位置插入自環(huán)和各圈，從而得到n級(jí)de Bruijn圖的Euler回路。最后，由Euler回路構(gòu)造成n+1級(jí)M序列。按照此方法，依次遞歸，求出所需的高級(jí)M序列。

2 Hamilton，Euler回路與M 序列的關(guān)系

2．1 de Bruijn圖的構(gòu)造方法

二元n級(jí)de Bruijn圖是二元n級(jí)M序列的所有可能狀態(tài)轉(zhuǎn)移的一種圖像表示。要構(gòu)造一個(gè)二元n級(jí)de Bruijn圖，簡單表示為 Gn(2)，設(shè)n≥2，Z2={0，1}，構(gòu)造有向圖Gn(2)。首先要確定圖的頂點(diǎn)數(shù)和頂點(diǎn)值，一個(gè)二元n級(jí)M序列共有2n個(gè)狀態(tài)，把每個(gè)狀態(tài)(b1，b2，…，bn)(bi∈Z2)作為特殊有向圖Gn(2)中的一個(gè)頂點(diǎn)。進(jìn)而，對2個(gè)頂點(diǎn)B=(b1，b2，…，bn)和 C=(c1，c2，…，cn)，如果 B 的后 n －1位依次為 C 的前 n－1 位，即(b2，b3，…，bn)=(c1，c2…，cn－1)，則圖中便引一條弧 B→C，并且為這條弧添加一個(gè)標(biāo)記，即這條弧為(b1b2…bncn)=(b1c1c2…cn)。所以特殊有向圖Gn(2)中共有2n個(gè)頂點(diǎn)，并且以每個(gè)頂點(diǎn)vi為始(終)點(diǎn)的弧數(shù)目均為2，即頂點(diǎn)vi的出度和入度均為2。圖1和圖2分別為構(gòu)造的有向圖G2(2)和G3(2)。

圖1 有向圖G2(2)

圖2 有向圖G3(2)

2．2 Hamilton，Euler回路及其表示方法

經(jīng)過圖G中每個(gè)頂點(diǎn)一次且僅一次的回路稱為G的Hamilton回路。在Gn(2)圖中，一個(gè)有限非空序列Γ=v0e1v1e2v2…ekvk，它的項(xiàng)交替地為頂點(diǎn)和弧，使得對 1≤i≤k，ei的端點(diǎn)是 vi－1和 vi，頂點(diǎn) v0和 vk分別為起點(diǎn)和終點(diǎn)，則稱Γ是從v0到vk的一條通路，若除起點(diǎn)v0和終點(diǎn)vk外，其他頂點(diǎn)各異且歷經(jīng)了每一個(gè)頂點(diǎn)，則稱Γ為圖Gn(2)的Hamilton回路。

經(jīng)過連通圖G的每條弧一次且僅一次的回路稱為Euler回路，或者Euler閉跡。在Gn(2)圖中，一個(gè)有限非空序列Γ=e0v0e1v1e2…vkek，它的項(xiàng)交替地為弧和頂點(diǎn)，并經(jīng)過所有弧一次且僅一次，且弧ek的終點(diǎn)vk為e0的起點(diǎn)則稱Γ為Euler回路。在圖中弧和頂點(diǎn)有著緊密的聯(lián)系，弧也可以由頂點(diǎn)來表示。例如在圖1中一條弧，可以用頂點(diǎn)表示為00→01。在Gn(2)圖中每個(gè)頂點(diǎn)的出度和入度都為2，一個(gè)Euler回路還可以表示為一個(gè)有限非空序列Γ=v0e0v1e1…vkekv0，它經(jīng)過每條弧一次且僅一次，經(jīng)過每個(gè)頂點(diǎn)兩次，又回到原來的頂點(diǎn)。如圖1中，一條Euler回路為弧，可以用頂點(diǎn)表示為00→00→01→10→01→11→11→10→00。

2．3 Hamilton回路、Euler回路與M序列的關(guān)系

在Gn(2)圖中，一條Hamilton回路為二元n級(jí)M序列，一條Euler回路為二元n+1級(jí)M序列［21］。例如:在圖 1中，00→01→11→10→00為一條Hamilton 回路，它的頂點(diǎn)依次為 00，01，11，10，通過提取每個(gè)頂點(diǎn)的最高位的值，可以得到一個(gè)二元2級(jí)M序列 0011。一條 Eular回路為弧序列，它經(jīng)過的弧依次為，提取每條弧的最高位的值得到二元3級(jí)M序列00010111，此 Euler回路由頂點(diǎn)表示為:00→00→01→10→01→11→11→10→00，它的頂點(diǎn)一次為00，00，01，10，01，11，11，10 提取每個(gè)頂點(diǎn)的最高位的值得到二元3級(jí)M序列00010111。由上可知，由一條二元n級(jí)M序列求二元n+1級(jí)M序列，等同于已知二元n級(jí)Gn(2)圖中的一條Hamilton回路求與之相關(guān)的Euler回路。

3 生成M序列的遞歸升級(jí)算法

3．1 圖Gn(2)中的Euler回路

已知圖Gn(2)中的一條Hamilton回路，求與此Hamilton回路相關(guān)的Euler回路(頂點(diǎn)表示)，只需要求出此Hamilton回路的補(bǔ)路，并在相應(yīng)位置插入補(bǔ)路即可。如圖3所示，實(shí)線部分為一條Hamilton回路，只需要求出此Hamilton回路未歷經(jīng)的弧，即求出此Hamilton回路的補(bǔ)路，在對應(yīng)位置插入補(bǔ)路即可求出Euler回路。

圖3 有向圖G3(2)的一條Hamilton回路

(1)求Hamilton回路的補(bǔ)路。首先，任意設(shè)置一個(gè)頂點(diǎn)為補(bǔ)路的起點(diǎn)。其次，此頂點(diǎn)的后繼頂點(diǎn)為未在Hamilton回路中直接連接的、且有有向弧直接連通的另一個(gè)頂點(diǎn)(如圖3虛線部分所示)，查找方法為此頂點(diǎn)在Hamilton回路中的后繼頂點(diǎn)最后一位與1異或而得到補(bǔ)路的后繼頂點(diǎn)，依次遞歸，直到形成回路為止。如果此回路的長度小于2n，任意設(shè)置一個(gè)未出現(xiàn)在補(bǔ)路的頂點(diǎn)為起始點(diǎn)求補(bǔ)路，直到形成回路，按照此方法直到各回路的長度和為2n次方為止。通過觀察和驗(yàn)證發(fā)現(xiàn)，Hamilton回路的補(bǔ)路共由兩部分組成:一部分為自環(huán)(長度為1的圈)，全0和全1頂點(diǎn)有自環(huán);另一部分為圈，除自環(huán)外其他頂點(diǎn)組成不同長度的圈(當(dāng)n大于5時(shí)，圈的個(gè)數(shù)逐步增多)。如圖3，是一個(gè)二元3級(jí)de Bruijn圖，它的一條Hamilton回路(實(shí)線所示)000→001→010→101→011→111→110→100→000。此 Hamilton回路的補(bǔ)路(虛線所示)為:自環(huán)有000→000和111→111，圈為一條長度為6的回路001→011→110→101→010→100→001。

(2)Euler回路的求法。按照上述方法求出補(bǔ)路，通過插值方法把所求補(bǔ)路添加到Hamilton回路中得到Euler回路。插值方法是在補(bǔ)路中的自環(huán)和各圈中任找一個(gè)頂點(diǎn)，在Hamilton回路中找到對應(yīng)點(diǎn)插入自環(huán)和各圈即得到Euler回路。如圖3所示，已知一條 Hamilton回路000→001→010→101→011→111→110→100→000，求得補(bǔ)路，自環(huán)有000→000和111→111，圈為一條長度為6的回路001→011→110→101→010→100→001。自環(huán)只有一個(gè)點(diǎn)直接插入得到的頂點(diǎn)序列為:000→000→001→010→101→011→111→111→110→100→000，圈為一條有6個(gè)頂點(diǎn)的回路，每一個(gè)頂點(diǎn)在對應(yīng)的位置插入圈都可以得到一條不同的Euler回路，假設(shè)選擇的頂點(diǎn)為011，在頂點(diǎn)序列中找到頂點(diǎn)011，在此位置插入以頂點(diǎn)011開始的圈，得到的頂點(diǎn)序列為000→000→001→010→101→011→110→101→010→100→001→011→111→111→110→100→000，此頂點(diǎn)序列即為Euler回路。

補(bǔ)路中每個(gè)圈的插值方式共有a(圈頂點(diǎn)個(gè)數(shù))種，各圈共有各圈頂點(diǎn)數(shù)的乘積種不同的插值方式，所以一條Hamilton回路可以產(chǎn)生Euler回路的個(gè)數(shù)由補(bǔ)路中各圈頂點(diǎn)個(gè)數(shù)的乘積決定。在圖3中，補(bǔ)路的圈只有一個(gè)，圈頂點(diǎn)的個(gè)數(shù)為6，所以可以產(chǎn)生6條Euler回路。例如:一個(gè)二元4級(jí)M序列000010 1111001101，在二元4級(jí)de Bruijn圖中轉(zhuǎn)換為一條Hamilton回路，求得補(bǔ)路為:自環(huán)為:0000→0000和1111→1111;圈為:(1)0001→0011→0111→1110→1101→1011→0110→1100→1000→0001;(2)0010→0100→1001→0010;(3)0101→1010→0101。各圈的頂點(diǎn)個(gè)數(shù)分別為9，3和2，所以此Hamilton回路可以產(chǎn)生54條Euer回路。

3．2 遞歸升級(jí)算法的基本思想及步驟

3．2．1 遞歸升級(jí)算法的基本思想

從2．3節(jié)可以看出，求一條低級(jí)M序列是比較簡單的。在已知一條低級(jí)M序列的條件下，如何通過遞歸升級(jí)的方法構(gòu)造高級(jí)M序列。本文的基本思想是:已知一條低級(jí)M序列，將其轉(zhuǎn)換為在de Bruijn圖中一條Hamilton回路，通過求補(bǔ)路的方法求出補(bǔ)路，按隨機(jī)插值的方式，在Hamilton回路中插入補(bǔ)路得到Euler回路，構(gòu)成二元n+1級(jí)M序列，依次遞歸升級(jí)構(gòu)造高級(jí)M序列。具體過程如下:首先，任意給出一條低級(jí)二元n級(jí)M序列，并在二元n級(jí)de Bruijn圖中畫出此M序列的Hamilton回路，為了便于計(jì)算，各頂點(diǎn)值用十進(jìn)制表示。其次，求出此Hamilton回路的補(bǔ)路(按照3．1節(jié)的方法求出)。最后，補(bǔ)路中各圈隨機(jī)選取一個(gè)頂點(diǎn)，并在Hamilton回路中找到此頂點(diǎn)，補(bǔ)路中各圈在對應(yīng)位置插入Hamilton回路中，在全0頂點(diǎn)和全1頂點(diǎn)位置對應(yīng)插入全0和全1的自環(huán)，得到Euler回路，構(gòu)成二元n+1級(jí)M序列。按照此方法依次遞歸生成所要的高級(jí)M序列。

隨機(jī)插值方法主要是為了解決補(bǔ)路中各圈的頂點(diǎn)選取問題。首先，確定補(bǔ)路各圈的個(gè)數(shù)以及各圈中頂點(diǎn)的個(gè)數(shù);然后，依次用隨機(jī)函數(shù)產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)，各圈的頂點(diǎn)數(shù)乘以對應(yīng)的隨機(jī)數(shù)，并取整即得到各圈中選取頂點(diǎn)的位置，找出此頂點(diǎn)。

3．2．2 遞歸升級(jí)算法步驟

本文算法步驟如下:

Step1任意給出一條M序列，由M序列的長度l求出所給M序列的級(jí)數(shù)m。輸入n的值，此為所求M序列的級(jí)數(shù)。

Step2如果n大于m繼續(xù)下面的操作;否則，停止。

Step3依次列出M序列的2m個(gè)狀態(tài)序列，并轉(zhuǎn)換為十進(jìn)制，狀態(tài)序列用L表示。

Step4任意設(shè)置狀態(tài)值v1為第1個(gè)頂點(diǎn)，在L中找到v1點(diǎn)的后續(xù)狀態(tài)v'2，v'2的最后一位和1異或，得到的值為v2，重復(fù)上述操作，直到vn=v1。如果求得的狀態(tài)序列長度小于2m，設(shè)置一個(gè)所求狀態(tài)序列中未出現(xiàn)的狀態(tài)值vi為另一條狀態(tài)序列的起始點(diǎn)，按照上面的方法，求出各狀態(tài)序列，直到生成的狀態(tài)序列的長度和為2m為止。

Step5M序列的補(bǔ)路隨機(jī)插值在狀態(tài)序列L中，構(gòu)成Euler回路的狀態(tài)序列。依次用隨機(jī)函數(shù)產(chǎn)生0到1的隨機(jī)數(shù)，乘以對應(yīng)的頂點(diǎn)序列的頂點(diǎn)數(shù)，并取整，得到各序列的選取狀態(tài)值的位置，找到此狀態(tài)值，并在L中找到該狀態(tài)值，在狀態(tài)位置插入相應(yīng)的狀態(tài)序列，得到的狀態(tài)序列為FB。

Step6提取FB的前2m個(gè)狀態(tài)值的最高位，得到m+1級(jí)M序列。m=m+1，返回Step2。

4 實(shí)驗(yàn)結(jié)果及分析

4．1 實(shí)驗(yàn)結(jié)果

仿真計(jì)算機(jī)為 XP操作系統(tǒng)，CPU主頻為2．79 GHz，內(nèi)存1．75 GB，用 Matlab 仿真軟件編程測試。假設(shè)給出的一個(gè)二元2級(jí)M序列0011，利用遞歸升級(jí)構(gòu)造法隨機(jī)生成一條n級(jí)M序列，當(dāng)級(jí)數(shù)n=11，12，…，20時(shí)，算法運(yùn)行結(jié)果如表1所示。表中，“碼長”表示M序列中0，1的個(gè)數(shù)，“空間大小”為生成的n－1級(jí)M序列可以生成n級(jí)M序列的個(gè)數(shù)，“耗時(shí)”為生成n級(jí)M序列所需時(shí)間。

實(shí)驗(yàn)結(jié)果表明，本文算法能夠隨機(jī)生成一條高級(jí)M序列，而不用生成全部的M序列，大大節(jié)約了時(shí)間和資源。產(chǎn)生的M序列隨機(jī)性強(qiáng)，每一個(gè)n級(jí)M序列可以生成多條n+1級(jí)的M序列，依次遞歸產(chǎn)生的高級(jí)M序列會(huì)增多，樣本空間巨大，產(chǎn)生的一條M序列采用隨機(jī)的方式在樣本空間中選取，隨機(jī)性強(qiáng)。

表1 遞歸升級(jí)算法生成的n級(jí)M序列

4．2 與其他算法的比較

當(dāng)M序列的級(jí)數(shù)n＞10，本文算法與遺傳算法［18］、Prefer-one 算法［20］、Prefer-opposite 算法［21］在成功率、有效性、空間大小進(jìn)行比較，如表2所示。

表2 遞歸升級(jí)算法和其他算法比較

本文算法優(yōu)點(diǎn)如下:

(1)成功率高，成功率為100%。任意一條M序列都能通過在de Bruijn圖中求補(bǔ)路的方法求出補(bǔ)路的自環(huán)和各圈，用插值的方法能夠產(chǎn)生高一級(jí)的M序列。

(2)有效性大于20級(jí)。當(dāng)n＞20時(shí)，生成一條高級(jí)M序列的時(shí)間較長，理論上算法可以產(chǎn)生任意級(jí)數(shù)的高級(jí)M序列。

(3)樣本空間大。每級(jí)的M序列求得的補(bǔ)路中圈的個(gè)數(shù)及各圈的頂點(diǎn)數(shù)可能不同，所以不能從算法中直接求出空間的大小，但一條M序列可以多條高一級(jí)的M序列，多條高級(jí)M序列依次遞歸，產(chǎn)生的M序列的數(shù)量也是巨大的。

4．3 隨機(jī)性測試

本文采用美國國家標(biāo)準(zhǔn)和技術(shù)研究所的NIST SP800-22 測試標(biāo)準(zhǔn)［22］，用 sts-2．1．1 測試軟件對遞歸升級(jí)算法生成的M序列進(jìn)行隨機(jī)性能測試。測試標(biāo)準(zhǔn)共包含15個(gè)測試項(xiàng)，當(dāng)p－value≥0．01時(shí)，測試的M序列被認(rèn)為是隨機(jī)的。測試序列為任意生成的一條二元20級(jí)M序列，共有1 048 576個(gè)碼元，測試結(jié)果如表3所示。

表3 NIST SP800-22測試結(jié)果

測試結(jié)果表明:提出的遞歸升級(jí)算法生成M序列的各測試值都大于0．01，滿足隨機(jī)性的要求，且多項(xiàng)值在0．5以上，隨機(jī)性能較好。Frequency Test的測試值為1，表明整個(gè)序列中0和1的個(gè)數(shù)相等，在序列中所占比例各為0．5;Runs Test的測試值為1，表明序列中0游程和1游程的個(gè)數(shù)相等，與理想的隨機(jī)序列的期望值相一致;Serial Test的測試值為1，表明序列有較好的均勻性，對于每一個(gè)長度為m的子序列，不同模式的子序列出現(xiàn)的概率是相等的;Approximate Entropy Test測試的檢驗(yàn)手段是看線性反饋移位寄存器的長度，隨機(jī)序列的特點(diǎn)是有較長的線性反饋移位寄存器，線性反饋移位寄存器太小說明序列為非隨機(jī)的，測試值為1，說明序列有較長的線性反饋移位寄存器長度，復(fù)雜度較高。

5 算法時(shí)間復(fù)雜度分析

本節(jié)從M序列的構(gòu)造過程對時(shí)間復(fù)雜度進(jìn)行分析。在求高級(jí)M序列的過程中，需要從低級(jí)逐級(jí)遞歸到高級(jí)，時(shí)間復(fù)雜度為O(n)=n，問題規(guī)模為n。在求M序列的狀態(tài)序列過程中，采用的是按順序求值的方法，時(shí)間復(fù)雜度為 O(n)=2nn。在求M序列補(bǔ)路的過程中，采用順序查找的方法，時(shí)間復(fù)雜度為O(n)=2n+1。在求Euler回路的過程中，采用隨機(jī)插值的方式，時(shí)間復(fù)雜度O(n)=2n。則算法復(fù)雜度O(n)=n22n+n2n+1+n2n，為指數(shù)復(fù)雜度。雖然算法效率不夠好，但對于高級(jí)M序列具有較大的問題規(guī)模，且解決難度較大的情況下，該算法的復(fù)雜度能夠滿足解決M序列生成問題。可得出結(jié)論，本文算法的復(fù)雜度能夠有效地生成M序列。

6 結(jié)束語

本文根據(jù)de Bruijn圖中Hamilton回路和Euler回路的關(guān)系，給出了M序列的遞歸升級(jí)算法，算法簡單有效，易于實(shí)現(xiàn)，在圖像加密等領(lǐng)域有一定的應(yīng)用前景。但該算法也存在算法復(fù)雜度高的不足，針對該問題，下一步的主要工作是研究一種更加有效生成M序列的方法以及M序列在信息安全領(lǐng)域的應(yīng)用。

［1］ 袁俊華，邵 偉．M序列碼的特性及在GPS導(dǎo)航通信保密中的作用［J］．內(nèi)燃機(jī)與動(dòng)力裝置，2009，(S1):47-50．

［2］ 趙宗民．基于63位 M序列的擴(kuò)頻通訊系統(tǒng)的設(shè)計(jì)［D］．天津:天津大學(xué)，2007．

［3］ 向曉燕，孟凡斌，張書真．M序列在系統(tǒng)辨識(shí)中的應(yīng)用［J］．信息與電腦:理論版，2010，(11):29．

［4］ 劉志軍．基于 M序列與 Word文檔的信息隱藏算法［J］．通信技術(shù)，2009，42(7):113-115．

［5］ 萬哲先，代宗鐸，劉木蘭，等．非線性移位寄存器［M］．北京:科學(xué)出版社，1978．

［6］ 金 玥，余海峰．產(chǎn)生2元 M序列的一個(gè)新算法［J］．合肥學(xué)院學(xué)報(bào):自然科學(xué)版，2007，17(3):4-5．

［7］ 芮義鶴．二元deBruijn序列的一個(gè)生成算法［J］．合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2009，32(1):139-141．

［8］ 朱士信．產(chǎn)生M序列的一個(gè)遞推算法［J］．信息安全與通信保密，1995，6(3):18．

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

［10］ 謝深泉．de Bruijn序列查尋表標(biāo)簽的末位基準(zhǔn)構(gòu)造法［J］．小型微型計(jì)算機(jī)系統(tǒng)，2009，30(9):1819-1823．

［11］ 趙群依，劉順蘭，王江柱．一種de Bruijn序列的高效生成算法［J］．通信技術(shù)，2007，10(11):302-303，402．

［12］ 王 誠，吳 蕾．任意長度的 M 序列的生成［J］．西安電子科技大學(xué)學(xué)報(bào)，2001，28(1):129-132．

［13］ 謝深泉．生成de Bruijn序列的升級(jí)算法［J］．計(jì)算機(jī)工程，2008，34(24):213-215．

［14］ 張 霞，吳 波．環(huán)F_2+uF_2上de Bruijn序列的一個(gè)有效升級(jí)算法［J］．中國科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2009，39(6):594-598．

［15］ 朱士信，孫 琳．k元 de Bruijn序列的反饋函數(shù)的一個(gè)升級(jí)算法［J］．電子學(xué)報(bào)，2006，34(6):1066-1068．

［16］ Annexstein F S．Generating de Bruijn Sequences:An Efficient Implementation［J］．IEEE Transactionson Computers，1997，46(2):198-200．

［17］ Chang T，Park B．An Efficient Implementation of the D-homomorphism for Generation of de Buijn Sequences［J］．IEEE Transactions on Information Theory，1999，45(4):1280-1283．

［18］ Sonmez T M．Evolutionary Construction ofde Bruijn Sequences［C］//Proceedings of the 4th ACM Workshop on Security and Artificial Intelligence．New York，USA:ACM Press，2011:81-86．

［19］ Alhakim A M．A Simple Combinatorial Algorithm for de Bruijn Sequences［J］．American Mathematical Monthly，2010，117(8):728-732．

［20］ Fredricksen H．A Survey of Full Length Nonlinear Shift Register Cycle Algorithms［J］．SIAM Review，1982，24(2):195-221．

［21］ 馮克勤．?dāng)?shù)論與密碼［M］．北京:科學(xué)出版社，2007．

［22］ Rukhin A，Soto J，Nechvatal J，et al．A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications［M］．Mclean，USA:Booz-Allen and Hamilton Inc．，2001．