Title :
On the quadratic spans of DeBruijn sequences
Author :
Chan, Agnes H. ; Games, Richard A.
Author_Institution :
Mitre Corp., Bedford, MA, USA
fDate :
7/1/1990 12:00:00 AM
Abstract :
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. 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. An upper bound for the quadratic span of a DeBruijn sequence of span n is given; 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
Keywords :
binary sequences; DeBruijn sequences; feedback shift register; lower bound; periodic binary sequence; quadratic span; upper bound; Binary sequences; Circuit testing; Communication systems; Costs; Cryptography; Feedback; Information theory; Random sequences; Shift registers; Spread spectrum communication;
Journal_Title :
Information Theory, IEEE Transactions on