ON THE QUADRATIC SPANS OF DEBRUIJN SEQUENCES

被引：16

作者：

CHAN, AH ^{[1
]}

GAMES, RA ^{[1
]}

机构：

[1] MITRE CORP,MATH RES & APPLICAT GRP,BEDFORD,MA 01730

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 1990年 / 36卷 / 04期

关键词：

D O I：

10.1109/18.53741

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The quadratic span of a periodic binary sequence is defined to be the length of the shortest quadratic feedback shift register (FSR) that generates it. This notion generalizes the usual notion of the linear span, which is used to analyze the complexity of pseudorandom sequences. An algorithm for computing the quadratic span of a binary sequence is described. The required increase in quadratic span is determined for the special case of when a discrepancy occurs in a linear FSR that generates an initial portion of a sequence. The quadratic spans of binary DeBruijn sequences are investigated. It is shown that the quadratic span of a DeBruijn sequence of span n is bounded above by 2n-1-(n 2) and this bound is attained by the class of DeBruijn sequences obtained from m -sequences. It is easy to see that a lower bound is n + 1, but a lower bound of n +2 is conjectured. The distributions of quadratic spans of DeBruijn sequences of span 3, 4, 5, and 6 are presented. © 1990 IEEE

引用

页码：822 / 829

页数：8

共 8 条

[1] ON THE COMPLEXITIES OF DEBRUIJN SEQUENCES [J].