NIST logo

Publication Citation: Evolutionary Construction of de Bruijn Sequences

NIST Authors in Bold

Author(s): Meltem Sonmez Turan;
Title: Evolutionary Construction of de Bruijn Sequences
Published: July 20, 2012
Abstract: A binary de Bruijn sequence of order n is a cyclic sequence of period 2^n, in which each n-bit pattern appears exactly once. These sequences are commonly used in applications such as stream cipher design, pseudo-random number generation, 3-D pattern recognition, network modeling, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as special type of traveling salesman tours and tries to find optimal solutions to this special type of the traveling salesman problem (TSP). We present some experimental results for n<=14.
Conference: 4th Workshop on Artificial Intelligence and Security
Proceedings: Proceedings of the 4th ACM Workshop on Security and Artificial Intelligence
Pages: pp. 81 - 86
Location: Chicago, IL
Dates: October 21, 2011
Keywords: De Bruijn sequences; genetic algorithms; traveling salesman problem
Research Areas: Math, Computer Security
PDF version: PDF Document Click here to retrieve PDF version of paper (352KB)