Linear complexity of de Bruijn sequences - Old and new results

作     者：Etzion, T 

作者机构：Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Univ So Calif Dept Elect Engn Syst Los Angeles CA 90089 USA 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE Trans. Inf. Theory)

年 卷 期：1999年第45卷第2期

页      面：693-698页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：complexity distribution de Bruijn sequences Games and Chan algorithm linear complexity minimal complexity 

摘      要：The linear complexity of a de Bruijn sequence is the degree of the shortest linear recursion which generates the sequence. It is well known that the complexity of a binary de Bruijn sequence of length 2(n) is bounded below by 2(n-1) + n and above by 2(n-1) for n greater than or equal to 3. We briefly survey the known knowledge in this area. Same new results are also presented, in particular, it is shown that for each interval of length 2(right perpendicular log n left perpendicular + 1), in the above range, there exist binary de Bruijn sequences of length 2(n) with linear complexity in the interval.