基于de Bruijn图的M序列递归升级构造方法

郭 辉，柏 森，阳 溢，宋 斌，李淑云

(1．重庆通信学院信息工程系，重庆400035;2．应急通信重庆市重点实验室，重庆400035;3．解放军66019部队，北京100093)

1 概述

M序列是由非线性反馈移位寄存器产生的周期最长的序列，也称为de Bruijn序列。由于M序列具有伪随机性、周期性、均衡性、相位相加性、自相关等特性［1-4］，并且随着级数的增大，M序列的数量呈指数级增多，因而被广泛应用在卫星保密通信［1］、扩频通信抗干扰［2］、系统识别［3］、信息隐藏［4］等方面。虽然目前有了一些生成M序列的方法，但对M序列的研究还不很成熟，关于它的生成方法及性能尚无完整的理论分析。

目前，M序列的生成方法主要有生成树法［5］、并圈法［6-8］、查询表标签法［9-10］、计算机搜索算法［11-12］等。值得注意的是文献［13-15］提出了M序列的升级算法。文献［13］提出了一种查询表标签的升级算法，通过给定的n级M序列的查询表标签，采用合成的方法构造出n+1级M序列的查询表标签，从而产生n+1级M序列。但查询表标签的构造较复杂，实现有一定的难度。文献［14-15］给出了二元n级M序列的升级算法，在已知低级M序列反馈函数条件下，求高级M序列的反馈函数。文献［16］给出了求反馈函数的升级算法，通过定义环F2+μF2上的n级de Bruijn图到n－1级de Bruijn图的满同态映射D，证明一个由环F2+μF2上n－1级M序列的反馈函数产生n级M序列反馈函数的升级算法定理。文献［17］给出了k元n级de Bruijn序列的反馈函数的一个升级算法，该算法定义了k个从k元n级de Bruijn图到k元n－1级de Bruijn图的满同态映射，利用这些同态映射，从一个n－1级k元de Bruijn序列的反馈函数直接生成k个k元n级de Bruijn序列的反馈函数;进而给出了一个从二元n－2r级de Bruijn序列反馈函数直接生成二元n级de Bruijn序列的反馈函数。

上述升级算法只在理论上进行了分析，而没有给出具体的实验结果。这些算法存在的局限性:或是不能生成全部的M序列;或算法复杂度高，且当n较大时，运行效率较低;或是不能生成任意级数任意数量的M序列。由于高级M序列数量巨大，生成全部的M序列需要大量的时间。文献［18-20］对快速生成一条M序列进行了研究。遗传算法［18］把M序列作为一种特殊的旅游销售员问题(TSP)，并尝试找到最佳的观光路径。首先，用随机式或探索式二种方法之一产生初始的观光路线集合。其次，利用公式计算集合中节点的2个相邻节点与此节点的长度之和，长度大于2的节点相互交换位置，直到产生最理想的或者没有最理想的观光路线为止。最后，重复以上2种操作500次，输出产生的所有最理想的观光路线集合。当n较大时，只能产生一条M序列，文中把遗传算法看做生成一条M序列的方法。存在的局限性:(1)由于算法中产生初始观光路线的方法为随机方式，所以不一定产生n级的所有M序列，且产生的M序列不具有唯一性。(2)当级数较大时，算法效率较低。文献［19-20］给出了 Prefer-one和Prefer-opposite算法，Prefer-one算法［15］采用的是直接添值方法，产生一个n级M序列，首先设置n个0，后面添加1，如果任意相邻的n位没有出现与之相同的数，则添加数保留，否则添加0。直到添加1或者0没有新的数值出现，算法结束。存在局限性:(1)形式固定，M序列添加的前n位一定是1;(2)只能产生一条M序列。Prefer-opposite算法［20］也是采用直接添值的方法，添值为上一位的相反数。首先设置n个0，后面添加最后一位0的相反数1，如果任意相邻的n位没有出现与之相同的数，则添加数保留，否则添加和最后一位相同的数。直到添加1或者0没有新的数值出现，算法结束。本文算法存在的局限性:(1)算法不能产生全1的状态;(2)形式固定，M序列最后n位一定是1;(3)只能产生一条M序列。2种算法相比，Prefer-one算法产生的M序列前部分1的数量要多，对于级数n=59的 M序列，前106位90%为1。Preferopposite算法产生的M序列倾向于1和0的平衡，对于级数n在10～20之间，M序列的前1/4位0和1的比例更接近50%。

本文在图论知识的基础上，给出一种随机生成一条二元高级M序列的方法。首先任意给出一条二元n级M序列，此M序列转换为二元n级de Bruijn图中的一条Hamilton回路;其次求图中此Hamilton回路的补路，补路由自环和不同长度圈组成，补路中自环和各圈随机选取一个点，按照此点在原Hamilton回路中的位置插入自环和各圈，从而得到n级de Bruijn图的Euler回路。最后，由Euler回路构造成n+1级M序列。按照此方法，依次递归，求出所需的高级M序列。

2 Hamilton，Euler回路与M 序列的关系

2．1 de Bruijn图的构造方法

二元n级de Bruijn图是二元n级M序列的所有可能状态转移的一种图像表示。要构造一个二元n级de Bruijn图，简单表示为 Gn(2)，设n≥2，Z2={0，1}，构造有向图Gn(2)。首先要确定图的顶点数和顶点值，一个二元n级M序列共有2n个状态，把每个状态(b1，b2，…，bn)(bi∈Z2)作为特殊有向图Gn(2)中的一个顶点。进而，对2个顶点B=(b1，b2，…，bn)和 C=(c1，c2，…，cn)，如果 B 的后 n －1位依次为 C 的前 n－1 位，即(b2，b3，…，bn)=(c1，c2…，cn－1)，则图中便引一条弧 B→C，并且为这条弧添加一个标记，即这条弧为(b1b2…bncn)=(b1c1c2…cn)。所以特殊有向图Gn(2)中共有2n个顶点，并且以每个顶点vi为始(终)点的弧数目均为2，即顶点vi的出度和入度均为2。图1和图2分别为构造的有向图G2(2)和G3(2)。

图1 有向图G2(2)

图2 有向图G3(2)

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

经过图G中每个顶点一次且仅一次的回路称为G的Hamilton回路。在Gn(2)图中，一个有限非空序列Γ=v0e1v1e2v2…ekvk，它的项交替地为顶点和弧，使得对 1≤i≤k，ei的端点是 vi－1和 vi，顶点 v0和 vk分别为起点和终点，则称Γ是从v0到vk的一条通路，若除起点v0和终点vk外，其他顶点各异且历经了每一个顶点，则称Γ为图Gn(2)的Hamilton回路。

经过连通图G的每条弧一次且仅一次的回路称为Euler回路，或者Euler闭迹。在Gn(2)图中，一个有限非空序列Γ=e0v0e1v1e2…vkek，它的项交替地为弧和顶点，并经过所有弧一次且仅一次，且弧ek的终点vk为e0的起点则称Γ为Euler回路。在图中弧和顶点有着紧密的联系，弧也可以由顶点来表示。例如在图1中一条弧，可以用顶点表示为00→01。在Gn(2)图中每个顶点的出度和入度都为2，一个Euler回路还可以表示为一个有限非空序列Γ=v0e0v1e1…vkekv0，它经过每条弧一次且仅一次，经过每个顶点两次，又回到原来的顶点。如图1中，一条Euler回路为弧，可以用顶点表示为00→00→01→10→01→11→11→10→00。

2．3 Hamilton回路、Euler回路与M序列的关系

在Gn(2)图中，一条Hamilton回路为二元n级M序列，一条Euler回路为二元n+1级M序列［21］。例如:在图 1中，00→01→11→10→00为一条Hamilton 回路，它的顶点依次为 00，01，11，10，通过提取每个顶点的最高位的值，可以得到一个二元2级M序列 0011。一条 Eular回路为弧序列，它经过的弧依次为，提取每条弧的最高位的值得到二元3级M序列00010111，此 Euler回路由顶点表示为:00→00→01→10→01→11→11→10→00，它的顶点一次为00，00，01，10，01，11，11，10 提取每个顶点的最高位的值得到二元3级M序列00010111。由上可知，由一条二元n级M序列求二元n+1级M序列，等同于已知二元n级Gn(2)图中的一条Hamilton回路求与之相关的Euler回路。

3 生成M序列的递归升级算法

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

已知图Gn(2)中的一条Hamilton回路，求与此Hamilton回路相关的Euler回路(顶点表示)，只需要求出此Hamilton回路的补路，并在相应位置插入补路即可。如图3所示，实线部分为一条Hamilton回路，只需要求出此Hamilton回路未历经的弧，即求出此Hamilton回路的补路，在对应位置插入补路即可求出Euler回路。

图3 有向图G3(2)的一条Hamilton回路

(1)求Hamilton回路的补路。首先，任意设置一个顶点为补路的起点。其次，此顶点的后继顶点为未在Hamilton回路中直接连接的、且有有向弧直接连通的另一个顶点(如图3虚线部分所示)，查找方法为此顶点在Hamilton回路中的后继顶点最后一位与1异或而得到补路的后继顶点，依次递归，直到形成回路为止。如果此回路的长度小于2n，任意设置一个未出现在补路的顶点为起始点求补路，直到形成回路，按照此方法直到各回路的长度和为2n次方为止。通过观察和验证发现，Hamilton回路的补路共由两部分组成:一部分为自环(长度为1的圈)，全0和全1顶点有自环;另一部分为圈，除自环外其他顶点组成不同长度的圈(当n大于5时，圈的个数逐步增多)。如图3，是一个二元3级de Bruijn图，它的一条Hamilton回路(实线所示)000→001→010→101→011→111→110→100→000。此 Hamilton回路的补路(虚线所示)为:自环有000→000和111→111，圈为一条长度为6的回路001→011→110→101→010→100→001。

(2)Euler回路的求法。按照上述方法求出补路，通过插值方法把所求补路添加到Hamilton回路中得到Euler回路。插值方法是在补路中的自环和各圈中任找一个顶点，在Hamilton回路中找到对应点插入自环和各圈即得到Euler回路。如图3所示，已知一条 Hamilton回路000→001→010→101→011→111→110→100→000，求得补路，自环有000→000和111→111，圈为一条长度为6的回路001→011→110→101→010→100→001。自环只有一个点直接插入得到的顶点序列为:000→000→001→010→101→011→111→111→110→100→000，圈为一条有6个顶点的回路，每一个顶点在对应的位置插入圈都可以得到一条不同的Euler回路，假设选择的顶点为011，在顶点序列中找到顶点011，在此位置插入以顶点011开始的圈，得到的顶点序列为000→000→001→010→101→011→110→101→010→100→001→011→111→111→110→100→000，此顶点序列即为Euler回路。

补路中每个圈的插值方式共有a(圈顶点个数)种，各圈共有各圈顶点数的乘积种不同的插值方式，所以一条Hamilton回路可以产生Euler回路的个数由补路中各圈顶点个数的乘积决定。在图3中，补路的圈只有一个，圈顶点的个数为6，所以可以产生6条Euler回路。例如:一个二元4级M序列000010 1111001101，在二元4级de Bruijn图中转换为一条Hamilton回路，求得补路为:自环为:0000→0000和1111→1111;圈为:(1)0001→0011→0111→1110→1101→1011→0110→1100→1000→0001;(2)0010→0100→1001→0010;(3)0101→1010→0101。各圈的顶点个数分别为9，3和2，所以此Hamilton回路可以产生54条Euer回路。

3．2 递归升级算法的基本思想及步骤

3．2．1 递归升级算法的基本思想

从2．3节可以看出，求一条低级M序列是比较简单的。在已知一条低级M序列的条件下，如何通过递归升级的方法构造高级M序列。本文的基本思想是:已知一条低级M序列，将其转换为在de Bruijn图中一条Hamilton回路，通过求补路的方法求出补路，按随机插值的方式，在Hamilton回路中插入补路得到Euler回路，构成二元n+1级M序列，依次递归升级构造高级M序列。具体过程如下:首先，任意给出一条低级二元n级M序列，并在二元n级de Bruijn图中画出此M序列的Hamilton回路，为了便于计算，各顶点值用十进制表示。其次，求出此Hamilton回路的补路(按照3．1节的方法求出)。最后，补路中各圈随机选取一个顶点，并在Hamilton回路中找到此顶点，补路中各圈在对应位置插入Hamilton回路中，在全0顶点和全1顶点位置对应插入全0和全1的自环，得到Euler回路，构成二元n+1级M序列。按照此方法依次递归生成所要的高级M序列。

随机插值方法主要是为了解决补路中各圈的顶点选取问题。首先，确定补路各圈的个数以及各圈中顶点的个数;然后，依次用随机函数产生一个0到1的随机数，各圈的顶点数乘以对应的随机数，并取整即得到各圈中选取顶点的位置，找出此顶点。

3．2．2 递归升级算法步骤

本文算法步骤如下:

Step1任意给出一条M序列，由M序列的长度l求出所给M序列的级数m。输入n的值，此为所求M序列的级数。

Step2如果n大于m继续下面的操作;否则，停止。

Step3依次列出M序列的2m个状态序列，并转换为十进制，状态序列用L表示。

Step4任意设置状态值v1为第1个顶点，在L中找到v1点的后续状态v'2，v'2的最后一位和1异或，得到的值为v2，重复上述操作，直到vn=v1。如果求得的状态序列长度小于2m，设置一个所求状态序列中未出现的状态值vi为另一条状态序列的起始点，按照上面的方法，求出各状态序列，直到生成的状态序列的长度和为2m为止。

Step5M序列的补路随机插值在状态序列L中，构成Euler回路的状态序列。依次用随机函数产生0到1的随机数，乘以对应的顶点序列的顶点数，并取整，得到各序列的选取状态值的位置，找到此状态值，并在L中找到该状态值，在状态位置插入相应的状态序列，得到的状态序列为FB。

Step6提取FB的前2m个状态值的最高位，得到m+1级M序列。m=m+1，返回Step2。

4 实验结果及分析

4．1 实验结果

仿真计算机为 XP操作系统，CPU主频为2．79 GHz，内存1．75 GB，用 Matlab 仿真软件编程测试。假设给出的一个二元2级M序列0011，利用递归升级构造法随机生成一条n级M序列，当级数n=11，12，…，20时，算法运行结果如表1所示。表中，“码长”表示M序列中0，1的个数，“空间大小”为生成的n－1级M序列可以生成n级M序列的个数，“耗时”为生成n级M序列所需时间。

实验结果表明，本文算法能够随机生成一条高级M序列，而不用生成全部的M序列，大大节约了时间和资源。产生的M序列随机性强，每一个n级M序列可以生成多条n+1级的M序列，依次递归产生的高级M序列会增多，样本空间巨大，产生的一条M序列采用随机的方式在样本空间中选取，随机性强。

表1 递归升级算法生成的n级M序列

4．2 与其他算法的比较

当M序列的级数n＞10，本文算法与遗传算法［18］、Prefer-one 算法［20］、Prefer-opposite 算法［21］在成功率、有效性、空间大小进行比较，如表2所示。

表2 递归升级算法和其他算法比较

本文算法优点如下:

(1)成功率高，成功率为100%。任意一条M序列都能通过在de Bruijn图中求补路的方法求出补路的自环和各圈，用插值的方法能够产生高一级的M序列。

(2)有效性大于20级。当n＞20时，生成一条高级M序列的时间较长，理论上算法可以产生任意级数的高级M序列。

(3)样本空间大。每级的M序列求得的补路中圈的个数及各圈的顶点数可能不同，所以不能从算法中直接求出空间的大小，但一条M序列可以多条高一级的M序列，多条高级M序列依次递归，产生的M序列的数量也是巨大的。

4．3 随机性测试

本文采用美国国家标准和技术研究所的NIST SP800-22 测试标准［22］，用 sts-2．1．1 测试软件对递归升级算法生成的M序列进行随机性能测试。测试标准共包含15个测试项，当p－value≥0．01时，测试的M序列被认为是随机的。测试序列为任意生成的一条二元20级M序列，共有1 048 576个码元，测试结果如表3所示。

表3 NIST SP800-22测试结果

测试结果表明:提出的递归升级算法生成M序列的各测试值都大于0．01，满足随机性的要求，且多项值在0．5以上，随机性能较好。Frequency Test的测试值为1，表明整个序列中0和1的个数相等，在序列中所占比例各为0．5;Runs Test的测试值为1，表明序列中0游程和1游程的个数相等，与理想的随机序列的期望值相一致;Serial Test的测试值为1，表明序列有较好的均匀性，对于每一个长度为m的子序列，不同模式的子序列出现的概率是相等的;Approximate Entropy Test测试的检验手段是看线性反馈移位寄存器的长度，随机序列的特点是有较长的线性反馈移位寄存器，线性反馈移位寄存器太小说明序列为非随机的，测试值为1，说明序列有较长的线性反馈移位寄存器长度，复杂度较高。

5 算法时间复杂度分析

本节从M序列的构造过程对时间复杂度进行分析。在求高级M序列的过程中，需要从低级逐级递归到高级，时间复杂度为O(n)=n，问题规模为n。在求M序列的状态序列过程中，采用的是按顺序求值的方法，时间复杂度为 O(n)=2nn。在求M序列补路的过程中，采用顺序查找的方法，时间复杂度为O(n)=2n+1。在求Euler回路的过程中，采用随机插值的方式，时间复杂度O(n)=2n。则算法复杂度O(n)=n22n+n2n+1+n2n，为指数复杂度。虽然算法效率不够好，但对于高级M序列具有较大的问题规模，且解决难度较大的情况下，该算法的复杂度能够满足解决M序列生成问题。可得出结论，本文算法的复杂度能够有效地生成M序列。

6 结束语

本文根据de Bruijn图中Hamilton回路和Euler回路的关系，给出了M序列的递归升级算法，算法简单有效，易于实现，在图像加密等领域有一定的应用前景。但该算法也存在算法复杂度高的不足，针对该问题，下一步的主要工作是研究一种更加有效生成M序列的方法以及M序列在信息安全领域的应用。

［1］ 袁俊华，邵 伟．M序列码的特性及在GPS导航通信保密中的作用［J］．内燃机与动力装置，2009，(S1):47-50．

［2］ 赵宗民．基于63位 M序列的扩频通讯系统的设计［D］．天津:天津大学，2007．

［3］ 向晓燕，孟凡斌，张书真．M序列在系统辨识中的应用［J］．信息与电脑:理论版，2010，(11):29．

［4］ 刘志军．基于 M序列与 Word文档的信息隐藏算法［J］．通信技术，2009，42(7):113-115．

［5］ 万哲先，代宗铎，刘木兰，等．非线性移位寄存器［M］．北京:科学出版社，1978．

［6］ 金 玥，余海峰．产生2元 M序列的一个新算法［J］．合肥学院学报:自然科学版，2007，17(3):4-5．

［7］ 芮义鹤．二元deBruijn序列的一个生成算法［J］．合肥工业大学学报:自然科学版，2009，32(1):139-141．

［8］ 朱士信．产生M序列的一个递推算法［J］．信息安全与通信保密，1995，6(3):18．

［9］ 谢深泉．de Bruijn序列查寻表标签的定值构造法［J］．计算机工程与应用，2008，44(19):37-40．

［10］ 谢深泉．de Bruijn序列查寻表标签的末位基准构造法［J］．小型微型计算机系统，2009，30(9):1819-1823．

［11］ 赵群依，刘顺兰，王江柱．一种de Bruijn序列的高效生成算法［J］．通信技术，2007，10(11):302-303，402．

［12］ 王 诚，吴 蕾．任意长度的 M 序列的生成［J］．西安电子科技大学学报，2001，28(1):129-132．

［13］ 谢深泉．生成de Bruijn序列的升级算法［J］．计算机工程，2008，34(24):213-215．

［14］ 张 霞，吴 波．环F_2+uF_2上de Bruijn序列的一个有效升级算法［J］．中国科学技术大学学报，2009，39(6):594-598．

［15］ 朱士信，孙 琳．k元 de Bruijn序列的反馈函数的一个升级算法［J］．电子学报，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］ 冯克勤．数论与密码［M］．北京:科学出版社，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．