[科普中國]-德布萊英序列

德布萊英序列(de Bruijn sequence)亦稱完全循環(huán)，是一類特殊的組合序列，一個(gè)循環(huán)是一個(gè)依圓周順序的序列a?a?…ar，即a1在ar之后，且a2…ara1，…，ara1…ar-1都是與a?a?…ar相同的循環(huán)。

基本介紹設(shè)n是正整數(shù)，N=2n，一個(gè)由數(shù)碼0和1組成的循環(huán)a?a?…aN，即，若子序列就是所有可能的N個(gè)由數(shù)碼0和1組成的有序序列b?b?…bn，則稱該循環(huán)是一個(gè)完全循環(huán)或德布萊英序列，例如n=1時(shí)，循環(huán)01;n=2時(shí)，循環(huán)0011，n=3時(shí)，循環(huán)00010111和00011101均為德布萊英序列。關(guān)于德布萊英序列的主要問題是：對任意正整數(shù)n，長為N=2n的德布萊英序列是否存在?若存在，有多少個(gè)?德布萊英定理斷言：對每個(gè)正整數(shù)n，恰存在次冪個(gè)長為N=2n的完全循環(huán)。事實(shí)上，每個(gè)長為N=2n的德布萊英序列恰與德布萊英圖Gn中的一條完全回路相對應(yīng)1。

De Bruijn序列的應(yīng)用與性質(zhì)簡介De Bruijn序列是一類重要的非線性移位寄存器序列，它在通信及密碼等領(lǐng)域內(nèi)有著極為廣泛的應(yīng)用，復(fù)雜度是刻劃這類序列特性的一個(gè)重要概念。具有良好偽隨機(jī)性質(zhì)的二元序列廣泛應(yīng)用于通信、密碼學(xué)等多個(gè)領(lǐng)域中，例如在流密碼中我們就需要好的二元序列來做為密鑰流。分析和構(gòu)造具有良好性質(zhì)的二元序列一直是序列研究中的重要問題。

二元de Bruijn序列是一種特殊的周期為2n的序列，滿足任意一個(gè)二元n長向量都在de Brujn序列的一個(gè)周期中恰出現(xiàn)一次。 De Bruijn序列具有許多很好的偽隨機(jī)性質(zhì)，在圖論、DNA存儲技術(shù)、通信與密碼學(xué)中都有重要應(yīng)用。De Bruijn序列雖然看起來非常簡單，但對它的深入分析卻是非常困難的，尋找de Bruijn序列的新的刻畫和性質(zhì)，以及尋找新的能更有效地生成更多的de Bruijn序列的算法一直是 de Bruijn序列的研究重點(diǎn)。

一個(gè)二元n階de Bruijn序列s是一個(gè)周期為2n的序列，滿足任意一個(gè)二元n長向量或n元組，都在S的一個(gè)周期中出現(xiàn)恰好一次。

De Bruijn序列具有許多良好的性質(zhì)：

1)大周期，2n，它是n階FSR能夠生成的序列的最大周期；

2)平衡性，0和1都出現(xiàn)2n-1次；

3)n元組平衡性，每個(gè)二元n長向量都出現(xiàn)一次；

4)大線性復(fù)雜度，它的線性復(fù)雜度c(s)滿足2n-1+n≤c(s)≤2n-1；

5)De Brujn序列的個(gè)數(shù)非常多，總個(gè)數(shù)為。

因此，de Bruijn序列在圖論、DNA排序存儲技術(shù)、通信與密碼學(xué)等多個(gè)領(lǐng)域中都有重要應(yīng)用2。

德布萊英定理德布萊英定理是波利亞定理的推廣，若兩置換群A和B分別作用于兩有限集X={x1，x2，…，xn}和Y={y1，y2，…ym}，則可定義冪群BA={(α，β)|α∈A，β∈B}對函數(shù)集的作用為。若有，則稱是等價(jià)的，記為，~為一等價(jià)關(guān)系。于是，YX被分為若干等價(jià)類之并，這些等價(jià)類稱為函數(shù)式樣或函數(shù)軌道，德布萊英定理斷言：函數(shù)式樣的個(gè)數(shù)等于1

式中群A的循環(huán)指標(biāo)為

其中β的型為。

哈拉里(F.Harary)推廣了德布萊英定理1。

設(shè)Y為可數(shù)集，Y至少含2元，定義權(quán)函數(shù)為非負(fù)整數(shù)集；又定義函數(shù)f的權(quán)

設(shè)k∈R，Y的子集，且|Yk|是有限的，。若B(Yi)={β(y)|β∈B，y∈Yi}，則函數(shù)集YX被冪群BA作用所分出的各個(gè)式樣中的函數(shù)有等權(quán)的充分必要條件是B(Yi)=Yi，i∈R，若條件B(Yi)=Yi，滿足i∈R，則可定義式樣F的權(quán)為w(F)=w(f)，其中f∈F，記β=βi，式中βi(y)=β(y)，這里y∈Yi，若權(quán)為k的式樣為Ck個(gè)，則式樣依權(quán)展開的生成函數(shù)為

于是

式中為A的循環(huán)指標(biāo)，

βi的型為。

德布萊英圖德布萊英圖是一種重要的圖，是由(0，1)序列衍生的圖.由數(shù)碼0和1組成的序列稱為一個(gè)(0，1)序列，r稱為該序列的長.長為n-1的(0，1)序列共計(jì)2n-1個(gè).設(shè)每個(gè)這樣的(0，1)序列(c1，c2，…，cn-1)與一個(gè)頂點(diǎn)pi相對應(yīng)，這里1≤i≤2n-1.設(shè)每個(gè)長為n的(0，1)序列(b1，b2，…，bn-1，bn)與一個(gè)起點(diǎn)為(b1，b2，…，bn-1)、終點(diǎn)為(b2，b3，…，bn)的有向弧相對應(yīng).稱具有頂點(diǎn)集{pi：i=1，2，…，2n-1}和上述對應(yīng)有向弧集的有向圖為一個(gè)德布萊英圖，記為Gn.圖示為G3.Gn為有向連通圖，且每個(gè)頂點(diǎn)處恰有兩條入弧和兩條出弧.通過給定有向圖中每一有向弧恰一次的回路，稱為該圖的一條有向完全回路.Gn中的有向完全回路與長為N=2n的德布萊英序列一一對應(yīng)，德布萊英(N.G.de Bruijn)證明：Gn恰有

條有向完全回路。

本詞條內(nèi)容貢獻(xiàn)者為:

王海俠 - 副教授 - 南京理工大學(xué)