De Bruijn torus

A De Bruijn torus. Each 2-by-2 binary matrix can be found within it exactly once.

In combinatorial mathematics, a De Bruijn torus, named after Nicolaas Govert de Bruijn, is an array of symbols from an alphabet (often just 0 and 1) that contains every m-by-n matrix exactly once. It is a torus because the edges are considered wraparound for the purpose of finding matrices. Its name comes from the De Bruijn sequence, which can be considered a special case where n is 1 (one dimension).

One of the main open questions regarding De Bruijn tori is whether a De Bruijn torus for a particular alphabet size can be constructed for a given m and n. It is known that these always exist when n = 1, since then we simply get the De Bruijn sequences, which always exist. It is also known that "square" tori exist whenever m = n and even (for the odd case the resulting tori cannot be square). [1] [2] [3]

The smallest possible binary "square" de Bruijn torus, depicted above right, denoted as (4,4;2,2)2 de Bruijn torus (or simply as B2), contains all 2×2 binary matrices.

B2

Apart from "translation", "inversion" (exchanging 0s and 1s) and "rotation" (by 90 degrees), no other (4,4;2,2)2 de Bruijn tori are possible - this can be shown by complete inspection of all 216 binary matrices (or subset fulfilling constrains such as equal numbers of 0s and 1s) . [4]

Larger example: B4

An example of the next possible binary "square" de Bruijn torus, (256,256;4,4)2 (abbreviated as B4), has been explicitly constructed.[5]

The image below shows an example of a (256,256;4,4)2 de Bruijn torus / array, where the zeroes have been encoded as black and the ones as white pixels respectively.

Practical consideration for construction of de Bruijn tori B6 & B8

The paper in which an example of the (256,256;4,4)2 de Bruijn torus / array was constructed contained over 10 pages filled essentially only with 0s and 1s, even though the font size was reduced compared with the main text, each row of the array printed over 3 lines.

The subsequent possible binary "square" de Bruijn torus, containing all binary 6×6 matrices, would have 236 = 68,719,476,736 entries, yielding a square array of dimension 262,144x262,144, this would be denoted a (262144,262144;6,6)2 de Bruijn torus / array or simply as B6. It should be possible to construct an example, which would fit onto a moderate computer (printing it out where each entry would be represented by a pixel of size 0.1 mm would require an area of approx 26×26 [square metre]s).

The object B8, containing all binary 8×8 matrices, with a total of 264 = 18,446,744,073,709,551,616 entries, denoted (4294967296,4294967296;8,8)2 is currently too large for even a supercomputer, requiring of order 18 Exabytes, outside a 64-bit address space (assuming 1 byte of storage for each element, in theory only 1 bit would be sufficient for each element, only of order 2 Exabytes would be required, which is still 3 orders of magnitude larger than total memory / storage of some of the largest computers as of late 2013).

See also

References

  1. ↑ Fan, C. T.; Fan, S. M.; Ma, S. L.; Siu, M. K. (1985). "On de Bruijn arrays.". Ars Combinatoria A 19: 205–213.
  2. ↑ Chung, F.; Diaconis, P.; Graham, R. (1992). "Universal cycles for combinatorial structures.". Discrete Mathematics 110 (1): 43–59. doi:10.1016/0012-365x(92)90699-g.
  3. ↑ Jackson, Brad; Stevens, Brett; Hurlbert, Glenn (Sep 2009). "Research problems on Gray codes and universal cycles". Discrete Mathematics 309 (17): 5341–5348. doi:10.1016/j.disc.2009.04.002.
  4. ↑ Eggen, Bernd R. (1990). "The Binatorix B2.". Private communication.
  5. ↑ Shiu, Wai-Chee (1997). "Decoding de Bruijn arrays constructed by the FFMS method.". Ars Combinatoria 47 (17): 33–48.

External links

This article is issued from Wikipedia - version of the Saturday, January 16, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.