Double Eulerian cycles on de Bruijn digraphs

Download
Author
Krahn, Gary William
Date
1994-06Advisor
Fredricksen, Harold
Metadata
Show full item recordAbstract
A binary de Bruijn sequence has the property that every n-tuple is distinct on a given period of length 2". An efficient algorithm to generate a class of classi- cal de Bruijn sequences is given based upon the distance between cycles within the Good - de Bruijn digraph. The de Bruijn property on binary sequences is shown to be a randomness property of the ZERO and ONE run sequences. Utilizing this randomness we find additional new structure in de Bruijn sequences. We analyze binary sequences that are not de Bruijn but instead possess the sufficient structure so that every distinct binary n-tuple can be systematically "combed" out of the se- quence. These complete or nonclassical de Bruijn sequences are a generalization of the well-known de Bruijn cycle. Our investigation focuses on binary sequences, called double Eulerian cycles, that define a cycle along a graph (digraph) visiting each edge (arc) exactly twice. A new algorithm to generate a class of double Eulerian cycles on graphs and digraphs is found. Double Eulerian cycles along the binary Good - de Bruijn digraph are partitioned by the run structure of their defining sequences. This partition allows for a statistical analysis to determine the relative size of the set of complete cycles defined by the sequences we study. A measure that categorizes double Eulerian cycles along graphs (digraphs) by the distance between the two visitations of each edge (arc) is provided. An algorithm to generate double Eulerian cycles of minimum measure is given.
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
Covering the de Bruijn graph
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 ... -
On the distribution of complexity for de Bruijn sequences
Holdahl, Robert LaVern (Monterey, California. Naval Postgraduate School, 1983-06);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 ... -
CHAOTIC COMBINER FOR LINEAR FEEDBACK SHIFT REGISTER SEQUENCES
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 ...