De Bruijn sequence
A de Bruijn sequence is a word of an alphabet A with k symbols with the following property: every possible word of length n formed from the symbols in A appeared as a continuous substring of B, and B is the shortest word with this property. n is called the order of B. Here are several B that emerge by cyclic permutation of the symbols apart, not distinguished. So a de Bruijn sequence contains all words of length n consisting of k symbols ( in coherent form ) exactly once, the word being considered cyclical, that is, the symbols at the end may be continued with those at the beginning to form a part of a word.
Bulk
De - Bruijn sequences exist for each. One example is for ( alphabet of two symbols, 0 and 1) and the De - Bruijn sequence. This reflects all words of length before. For there are two possible de Bruijn sequences: and. Each De - Bruijn sequence has length, and there are various de Bruijn sequences of order n
De - Bruijn sequences can be represented graphically as Euler paths or paths of a Hamilton - De Bruijn graph. These are directed graphs whose nodes all words of length n from the alphabet with k symbols represent, and whose nodes are connected if these words overlap. For example, and all nodes are connected to each other and on.
De - Bruijn sequences have, for example, applications in the design of card tricks in cryptography, genetics, at telegraph, error-correcting codes, computer memory hashing and robot vision. You may also be produced by shift register sequences.
Generalization
Analog objects can be defined and constructed for higher dimensions d, specially the case d = 2 has been studied by several authors, and this is de Bruijn torus.
It is a matrix with entries from an alphabet (often only the two symbols 0 and 1), the (also: sub- matrices) all possible m × n sub-matrices containing exactly once. Opposite sides of the matrix are identified with each other, hence the name Torus. For n = 1 we obtain de Bruijn sequences as a special case.
(, 2, 4.4 2) If we restrict ourselves to quadratic binary Tori, can be 2 de Bruijn tori that contain all the 2 × 2 binary submatrices easily construct. The next square de Bruijn torus is ( 256,256, 4, 4) 2 and was designed by W.-C. Shiu inductively constructed.
Higher De - Bruijn tori are not yet known, for example, for all 6 × 6 binary submatrices (236 = 68,719,476,736 possibilities ) would be needed ( 262,144.262144, 6, 6) 2, which is just within the range of realizable: if the representation 0.1mm per pixel ( matrix entry ) is required, one would need an area of approximately 26 × 26 square meters.
Naming
De - Bruijn sequences are named after Nicolaas Govert de Bruijn, who also published in 1946 and 1951 with Tatjana van AARDENNE - Ehrenfest. De Bruijn in turn indicates that they were = 2 treated by Camille Flye Sainte -Marie in 1894, first in case k. But first de Bruijn sequences appeared in ancient India in connection with Sanskrit prosody. There were also other publications before De Bruijn, so MH Martin ( in the context of dynamics), IJ Good ( 1946), Karl Popper ( 1934), NM Korobov, by the telegraph engineer Émile Baudot (1888 ) and sorcerers, they were also known, but they were often mistakenly called by these Gray codes.