On the quadratic spans of DeBruijn sequences

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 speci...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 1990-07, Vol.36 (4), p.822-829
Main Authors: Chan, A.H., Games, R.A.
Format: Article
Language:English
Subjects:
Applied sciences
Binary sequences
Circuit testing
Communication systems
Costs
Cryptography
Exact sciences and technology
Feedback
Information theory
Information, signal and communications theory
Random sequences
Shift registers
Spread spectrum communication
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
ISSN:0018-9448
1557-9654
DOI:10.1109/18.53741