On de Bruijn Rings and families of almost perfect maps

Abstract

De Bruijn tori, also called perfect maps, are two-dimensional periodic arrays of letters drawn from a given finite alphabet, such that each possible pattern of a given shape (m,n) appears exactly once within one period of the torus. It is still unknown if de Bruijn tori of some certain size exist, like e.g. square shaped de Bruijn Tori with odd m=n in {3,5,7} and an even alphabet size k. However, in certain applications like positional coding, sub-perfect maps are sufficient, i.e. one does not need every possible (m,n)-pattern to appear, as long as a sufficient large number of such patterns is captured and every pattern occurs at most once. We show, that given any m=n and a square alphabet size k², one can efficiently construct a sub-perfect map which is almost perfect, i.e. of almost maximal size. We do this by introducing de Bruijn rings, i.e. sub-perfect maps of minimal height, and providing an efficient construction method for them. We extend our results to non-square torus shapes and arbitrary non-prime alphabet sizes.