二元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的个数。……