Double Eulerian cycles on de Bruijn digraphs
Krahn, Gary William
MetadataShow full item record
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.
Approved for public release, distribution 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 ...
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 ...
Extended Closed-form Expressions for the Robust Symmetrical Number System Dynamic Range and An Efficient Algorithm for its Computation Pace, Phillip E.; Stanica, Pantelimon; Luke, Brian L.; Tedesso, Thomas W. (2014);The robust symmetrical number system (RSNS) is a number theoretic transform based on N > 2 sequences that can extract the maximum amount of information from symmetrical folding waveforms. The sequences, based on coprime ...