二元DeBruijn序列的性質和構造

趙益誠

摘 要：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.