赵益诚

摘 要：De Bruijn序列具有很好的性质，在密码和通信领域中有着重要的应用。本文详细研究了二元de Bruijn序列，给出了关于de Bruijn序列的新结果，并且给出了一种非常简单的构造de Bruijn序列的新方法。

关键词：二元序列；de Bruijn序列；移位算子

Abstract：De Bruijn sequences have good properties and are widely used in many domains such as cryptography and communication. In this paper， binary de Bruijn sequences are deeply studied and some new results are deduced. Also one new method to easily generate binary de Bruijn sequences is provided.

Key words：Binary sequences；de Bruijn sequences；shift operator

具有良好伪随机性质的二元序列广泛应用于通信、密码学等多个领域中[ 1，2 ]，例如在流密码中我们就需要好的二元序列来做为密钥流。分析和构造具有良好性质的二元序列一直是序列研究中的重要问题。

二元de Bruijn序列是一种特殊的周期为2n的序列，满足任意一个二元n长向量都在de Bruijn序列的一个周期中恰出现一次[ 3 ]。De Bruijn序列具有许多很好的伪随机性质，在图论、DNA存储技术、通信与密码学中都有重要应用。De Bruijn序列虽然看起来非常简单，但对它的深入分析却是非常困难的，寻找de Bruijn序列的新的刻画和性质，以及寻找新的能更有效地生成更多的de Bruijn序列的算法一直是de Bruijn序列的研究重点。

本文将主要研究二元de Bruijn序列的性质，给出了关于二元de Bruijn总个数的一个非常简单的新证明。另外，我们还推导出关于de Bruijn序列的一个非常重要的必要条件，我们推断这个必要条件应该也是充分的。最后我们还给出了一个非常简单的根据已有de Bruijn序列构造高阶de Bruijn序列的新方法。

1 De Bruijn序列的性质

本文主要考慮二元序列s=s0，s1，s2，…，其中分量取值于二元域F2={0，1}。如果存在一个正整数N满足si+N=si对所有非负整数i都成立，则我们称序列s具有周期N。这时我们设定s=（s0，s1，s2，…，sN-1）。

我们令wt（s）表示序列s的重量，即序列s的一个周期中1的个数。序列s的线性复杂度c（s）定义为满足下面方程的最小正整数L：

sj+d1sj-1+···+dLsj-L=0

对所有大于等于L的j都成立，其中系数d1，…，dL属于F2。

对于一个序列s=（s0，s1，s2，…，sN-1），它的移位算子（Shift Operator）L定义为：

Ls=（s1，s2，…，sN-1，s0）

序列s=（s0，s1，s2，…，sN-1）中，s0=（s0，s1，…，sn-1）称为序列s的n阶初始状态（initial state），而si=（si，si+1，…，si+n-1），i=0，1，…，N-1，称为序列s的第i个状态，其中元素的下标需要模N。

事实上，任何序列都可以通过反馈移位寄存器（Feedback Shift Rigester，简记为FSR）来生成。

当给定一个初始状态s0=（s0，s1，…，sn-1）时，FSR将生成一个序列s=s0，s1，s2，…，满足：

sn+i =f（si，si+1，…，si+n-1），i=0，1，…

其中f为对应的反馈函数。

文献[4]证明了FSR生成的序列都是周期的当且仅当f能表示成：

f（x0，x1，…，xn-1）=x0+g（x1，…，xn-1），

其中g是某个n-1阶的布尔函数。此时，这些不同的周期序列也被称为圈（Cycle）。

一个二元n阶de Bruijn序列s是一个周期为2n的序列，满足任意一个二元n长向量或n元组（a0，a1，…，an-1）∈F2n，都在S的一个周期中出现恰好一次。

De Bruijn序列具有许多良好的性质[ 3 ]：

1）大周期，2n，它是n阶FSR能够生成的序列的最大周期；

2）平衡性，0和1都出现2n-1次；

3）n元组平衡性，每个二元n长向量都出现一次；

4）大线性复杂度，它的线性复杂度c（s）满足2n-1+n≤c（s）≤2n-1；

5）De Bruijn序列的个数非常多，总个数为2。

因此，de Bruijn序列在图论、DNA排序存储技术[ 5 ]、通信与密码学[ 6 ]等多个领域中都有重要应用。

令N=2n。关于de Bruijn序列的总个数的推导，原始论文中是根据图的方法得出的。

在这里我们给出一种新的简单方法来证明这个结果。

定理1：二元n阶de Bruijn序列的总个数为2。

证明：二元n阶de Bruijn序列中，每个二元n长向量恰出现一次，因此每个二元n-1长向量恰出现二次。

在构造de Bruijn序列时，首先任意给定一个n-1长向量，则它的下一个元素有两种选择，0或1。此时我们有两种选择，假定选0。而在以后这个n-1长向量下次再出现时，它的下一个元素只能选取1。

根据这个规律，任意一个n-1长向量的下一个元素都有2选择，所以我们可以构造出2个不同的de Bruijn序列。

由于对于一个de Bruijn序列s，它的移位：

Lis，i=0，1，…，N-1

其实是同一个序列或圈，所以我们就可证明该定理。□

可见，我们这里给出的证明非常简单，只是利用了序列中n长和n-1长向量的分布和个数就可推导出de Bruijn序列的总个数。

下面我们给出de Bruijn序列的一个充要条件。

定理2：给定一个任意的de Bruijn序列s。

令f（x）=an-1xn-1+an-2xn-2+···+a1x+a0∈F2[x]是任意一个次数不超过n-1的多项式，其中ai∈F2且不全为0。则我们有：

wt（f（L）s）=wt（an-1Ln-1s+an-2Ln-2s+···+a1Ls+a0s）=2n-1。

证明：对于一个给定的de Bruijn序列s，我们按照如下方法构造一个n×2n的二元阵列：令Lis做为阵列的第i列，i=0，1，…，n-1。此时这个阵列具有如下形式：

s0 s1 … sn-1

s1 s2 … sn

s2 s3 … sn+1

……

sN-2 sN-1 … sn-3

sN-1 s0 … sn-2

这个阵列的2n行恰好是de Bruijn序列的所有2n个状态，也就是所有2n个不同的二元n长向量。

易知，an-1Ln-1s+an-2Ln-2s+···+a1Ls+a0s的重量等于阵列对应列的和的序列的重量，也等于多项式：

an-1xn-1+an-2xn-2+···+a1x1+a0x0， （x0，x1，…xn-1）∈F2n

的重量，总是2n-1。

事实上，我们通过实例检验，如果一个序列满足对任意次数不超过n-1的多项式都满足：

wt（f（L）s）=wt（an-1Ln-1s+an-2Ln-2s+···+a1Ls+a0s）=2n-1。

则该序列一定是一个de Bruijn序列。遗憾的是，这个充分性的证明比较困难，到现在为止还没完全证明。我们以一个猜想的形式给出这个结果。

一个周期为2n的二元序列s是de Bruijn序列当且仅当对任意一个次数不超过n-1的多项式：

f（x）=an-1xn-1+an-2xn-2+···+a1x+a0∈F2[x]

其中ai∈F2且不全为0，都满足：

wt（f（L）s）=wt（an-1Ln-1s+an-2Ln-2s+···+a1Ls+a0s）=2n-1。

2 De Bruijn序列的构造

在这一节中，我们主要给出一种根据已知的n阶de Bruijn序列来构造n+1阶de Bruijn序列的简单的方法。

一种常用的生成de Bruijn序列的方法是“并圈法”（Cycle Joining Method）。根据一个n阶FSR，取遍所有不同的输入，会产生一些不同的圈，即不同的周期序列。

對于两个圈s1和s2，如果分别存在一个状态a=（a0，a1，…，an-1）和b=（b0，b1，…，bn-1），如果满足：

a0=b0+1，ai=bi，i=1，2，…，n-1，

我们称这两个状态是共轭的。如果我们交换这两个状态的后继状态，则这两个圈将会并成一个大圈。继续这个过程，当最后只剩一个圈时，则这个圈将是一个n阶de Bruijn序列。

下面我们就用并圈法根据一个已知的n阶de Bruijn序列来构造n+1阶de Bruijn序列。

给定一个n阶de Bruijn序列s=（s0，s1，s2，…，sN-1），其中N=2n，n≥2。我们根据它利用下面的方法来构造两个序列：

u=（u0，u1，…，uN-1）和u+1=（u0+1，u1+1，…，uN-1+1），

其中，ui=s0+s1+···+si，i=0，1，…，N-1。

首先，因为de Bruijn序列s中1的个数为2n-1，且n≥2，为偶数，所以根据序列u的构造方法，我们有ui=ui+N对所有i都成立，即u和u+1的周期也为N。

又因为序列s的左右两半不完全一样，所以序列u的左右两半也不完全一样，因此N就是u和u+1的最小周期。

另外，给定序列u的一个n+1阶状态vi=（vi，vi+1，…，vi+n），根据构造方法，我们有：

sj+1= vj+1+vj=（vj+1+1）+（vj+1），j=i，…，i+n-1。

所以给定一个de Bruijn序列s的一个n阶状态，我们可以根据这个关系确定两个n+1阶状态，且这两个状态不能属于一个圈，否则对应圈的周期一定小于N。所以它们分别属于不同的圈u和u+1。

因此，我们推导出：根据de Bruijn序列s的2n个不同的n阶状态，我们可以确定所有可能的2n+1个n+1阶状态，且这些n+1阶状态分别属于两个圈u和u+1。然后我们寻找一个共轭对，我们就可以构造出一个新的n+1阶de Bruijn序列。注意共轭对总是存在的，并且对于不同的共轭对，所得新的de Brujn序列也是不同的。

例：我们给定一个3阶de Bruijn序列（00010111）。根据上面方法，我们构造两个互补的周期为8的序列（00011010）和（11100101）。

通过搜索，我们可以发现6个共轭对：

（0001），（1001）；

（0011），（1011）；

（0110），（1110）；

（1101），（0101）；

（1010），（0010）；

（0100），（1100）。

我們就可以构造出6个不同的4阶de Bruijn序列：

（10100001 01111001），

（01000011 11001011）；

（10000110 01011110），

（00001101 11100101）；

（00011010 11110010），

（00110100 10111100）。

可以检验，这6个4阶de Bruijn序列是不同的。

可见我们给出的构造新的de Bruijn序列的方法非常简单，根据一个已知的de Bruijn序列，我们可以很快地构造出多个不同的高阶de Bruijn序列。所以我们的构造方法是非常有应用价值的。

3 结论

在这篇论文中，我们主要研究了二元de Bruijn序列的深刻性质，给出了关于de Bruijn序列的总个数的一个非常简单的证明。

另外我们还推导出了一个关于de Bruijn序列的必要条件。这个条件看起来也是充分的，不过需要进一步的证明。如果这个条件是充要条件，则这个结果就是de Bruijn序列的一个新的刻画，具有非常重要的理论意义。

最后，我们还根据我们推导出的结果给出了一种非常简单的利用已有de Bruijn序列来构造多个高阶de Bruijn序列的方法。论文中的结果在de Bruijn序列的研究中具有重要应用。

参考文献：

[1] A. J. Menezes，P. C. Van Oorschot，and S. A. Vanstone，Handbook of Applied Cryptography.Boca Raton，FL：CRC Press，1996.

[2] R. A. Ruppel， Analysis and Design of Stream Ciphers. New York： Springer-Verlag，1986.

[3] H. Fredricksen， “A survey of full length nonlinear shift register cycle algorithms，”SIAM Review，vol.24，no.2，pp.195-221，1982.

[4] S. W. Golomb， Shift Register Sequences. Laguna Hills： Aegean Park Press，1981.

[5] P.A.Pevzner，H.Tang，and M.S.Waterman，“An Eulerian path approach to DNA fragment assembly，” Proc. Natl. Acad. Sci. USA，vol. 98， no. 17， pp. 9748-9753，Aug.2001.

[6] S.Spinsante and E.Gambi，“De Bruijn binary sequences and spread spectrum applications： A marriage possible？” IEEE Aerosp. Electron. Syst. Mag.，vol.28，no.11，pp.28-39，Nov.2013.