On the distribution of complexity for de Bruijn sequences
Holdahl, Robert LaVern
MetadataShow full item record
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
Gutzler, Alexander (Monterey, CA; Naval Postgraduate School, 2020-03);Cryptography is widely used by everybody in day-to-day activities. Many cryptographic algorithms rely on pseudorandom number sequences. One of the quickest methods of pseudorandom number generation is using linear feedback ...
Fredricksen, Harold (SIAM (Society for Industrial and Applied Mathematics), 1982-04);Shift registers have been used to generate sequences of O’s and l’s for over thirty years. A wide variety of applications has been made of these sequences. Principally, communications have made use of the sequences ...
Bryant, Roy Dale (Monterey, California. Naval Postgraduate School, 1986);Random-like sequences of 0's and l's are generated efficiently by binary shift registers. The output of n-stage shift registers viewed as a sequence of binary n-tuples also give rise to a special graph called the de Bruijn ...