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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Bryant, Roy Dale (Monterey, California. Naval Postgraduate School, 1986-03);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 ...
Pseudorandom number generators for mobile devices: an examination and attempt to improve randomness Larsson, Ola (Monterey, California: Naval Postgraduate School, 2013-09);This thesis examines the quality of pseudorandom number generation for cryptographic purposes in general and the generation of such numbers in a mobile device (Android phone), in particular, since we expected to find ...
MacLennan, Bruce J. (Monterey, California. Naval Postgraduate School, 1981-11); NPS-52-81-015A method for measuring the complexity of control structures is presented. It is based on the size of a grammar describing the possible execution sequences of the control structure. This method is applied to a number of ...