| De Bruijn Sequence |
Article Index for De Bruijn |
Website Links For Bruijn |
Information AboutDe Bruijn Sequence |
| CATEGORIES ABOUT DE BRUIJN SEQUENCE | |
| combinatorics | |
|
In Mathematics , especially Combinatorics , a ''k''-ary de Bruijn sequence ''B''(''k'', ''n'') of order ''n'', named after 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. Such a sequence has the following properties:
EXAMPLES Taking , there are two distinct : 00010111 and 00011101, one being the reverse of the other. Two of the 2048 possible in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011. A digital door lock with a 4 digits code would have 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. CONSTRUCTION The de Bruijn sequences can be constructed by taking an Eulerian Cycle of a De Bruijn Graph , or via Finite Field s. 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 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 consecutive symbols facing a fixed point. SEE ALSO REFERENCES
EXTERNAL LINKS
|
|
|