My recent paper presented at Artificial Intelligence and Security Workshop, Chicago, 2011.
Abstract:
A binary de Bruijn sequence of order n is a cyclic sequence of period 2n, in which each n-bit pattern appears exactly once. These sequences are commonly used in random number generation and symmetric key cryptography particularly in stream cipher design, 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 a 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.
1 comment:
Dear Meltem S. T.,
I am interesting in generating orthogonal De Bruijn sequences (the corresponding Hamiltonian cycles are arc-disjoint). My back-tracking method is very slow. In my paper: http://arxiv.org/pdf/1003.1520v2.pdf
I gave a conjecture on this. Maybe your method can be useful in generation such sequences. If you are intrested in this, my email address is in the paper.
With best regards
Zoltan K.
Post a Comment