On the distribution of complexity for de Bruijn sequences
Loading...
Authors
Holdahl, Robert LaVern
Subjects
de Bruijn
complexity
complexity
Advisors
Fredricksen, H.
Date of Issue
1983-06
Date
June 1983
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
Binary sequences have had application in communication systems for many years. Shift registers have been used in their generation, because of the ease and economy of their operation. For certain applications, nonlinear feedback functions are used by shift registers of span n to generate sequences of lengths up to 2 .
The sequences of maximum length 2 and their generation are the subject of this thesis. In particular the ways of generating these sequences using nonlinear feedback shift registers and their correlation to linear feedback shift registers are described. Complexity is the term given to the length of the shortest linear feedback shift register generating a maximum length 2 sequence.
Games and Chan [Ref. I] have given considerable study to the subject of complexity. Some of the problems they left are discussed further in this paper. It will be shown that the complexity of a de Bruijn sequence (S) is the same as the complexity of its reverse (r S) , complement (5~) , and
Sequences (S) for which r S = S~ are termed RC sequences. It is shown that RC sequences
exist for every odd n>_3 . In addition a lower bound will be established for the number of RC sequences occurring for each odd n.
Type
Thesis
Description
Series/Report No
Department
Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.