De Bruijn sequence
From Wikipedia, the free encyclopedia
In combinatorial mathematics, a k-ary De Bruijn sequence B(k, n) of order n, named after the Dutch mathematician Nicolaas Govert de Bruijn, is a cyclic sequence from a given alphabet A of size k for which every possible subsequence of length n in A is present exactly once. It's pronounced "de-broyn".
Such a sequence has the following properties:
- Each B(k, n) has length kn
- There are
distinct De Bruijn sequences B(k, n).
Contents |
[edit] Examples
Taking A = {0,1}, there are two distinct B(2,3): 00010111 and 00011101, one being the reverse of the other.
Two of the 2048 possible B(2,5) in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011.
A digital door lock with a 4 digits code would have B(10,4) solutions with length 10000. Therefore, only 10000 + 3 = 10003 (as the solutions are cyclic) presses are needed to open the lock. Trying all codes separately would require 
presses.
[edit] Construction
The De Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional De Bruijn graph over k symbols (or equivalently, a Eulerian cycle of a (n − 1)-dimensional de Bruijn graph), or via finite fields.
[edit] Example
Each edge in this 3-dimensional de Bruijn graph corresponds to a sequence of four digits: the three digits that label the vertex that the edge is leaving followed by the one that labels the edge. If one traverses the edge labeled 1 from 000, one arrives at 001, thereby indicating the presence of the subsequence 0001 in the de Bruijn sequence. To traverse each edge exactly once is to use each of the 16 four-digit sequences exactly once.
For example, suppose we follow the following Eulerian path:
- 000, 000, 001, 011, 111, 111, 110, 101, 011,
-
- 110, 100, 001, 010, 101, 010, 100, 000.
This corresponds to the following de Bruijn sequence:
- 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1
The eight vertices appear in the sequence in the following way:
- {0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 1
- 0 {0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1
- 0 0 {0 0 1} 1 1 1 0 1 1 0 0 1 0 1
- 0 0 0 {0 1 1} 1 1 0 1 1 0 0 1 0 1
- 0 0 0 0 {1 1 1} 1 0 1 1 0 0 1 0 1
- 0 0 0 0 1 {1 1 1} 0 1 1 0 0 1 0 1
- 0 0 0 0 1 1 {1 1 0} 1 1 0 0 1 0 1
- 0 0 0 0 1 1 1 {1 0 1} 1 0 0 1 0 1
- 0 0 0 0 1 1 1 1 {0 1 1} 0 0 1 0 1
- 0 0 0 0 1 1 1 1 0 {1 1 0} 0 1 0 1
- 0 0 0 0 1 1 1 1 0 1 {1 0 0} 1 0 1
- 0 0 0 0 1 1 1 1 0 1 1 {0 0 1} 0 1
- 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0} 1
- 0 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1}
- ... 0} 0 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ...
- ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 0 {1 ...
...and then we return to the starting point. Each of the eight 3-digit sequences (corresponding to the eight vertices) appears exactly twice, and each of the sixteen 4-digit sequences (corresponding to the 16 edges) appears exactly once.
[edit] Usage
The sequence can be used to shorten a brute-force attack on a PIN-like code lock that does not have an Enter key and accepts the last n digits entered.
The symbols of a De Bruijn sequence written around a circular object (possibly a wheel of a robot) can be used to identify its angle by examining the n consecutive symbols facing a fixed point.
[edit] De Bruijn torus
A De Bruijn torus is a toriodial array with the property that every k-ary m-by-n matrix occurs exactly once.
It is not necessary that the array be expressed toriodially; the array can be mapped into a 2-dimensional array. Because it is toriodial it "wraps around" on all 4 sides.
Such a pattern can be used for two-dimensional positional encoding. Position can be determined by examining the m-by-n matrix directly adjacent to the sensor, and calculating its position on the De Bruijn torus.
[edit] See also
[edit] References
- de Bruijn, N. G. "A Combinatorial Problem." Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758–764, 1946.
- Hurlbert, G.; and G. Isaak (1993). "On the De Bruijn torus problem" (PDF). J. Comb. Th. (A) 64 (1): 50–62.
