2015/05/15 by Victoria Horan, Brett Stevens, Horan, Victoria +1 · 1 voice
Mathematics · Engineering · Computer Science · #Advanced Combinatorial Mathematics #graph theory and CDMA systems #Coding theory and cryptography
paper · pdf · doi:10.48550/arxiv.1505.04065
The de Bruijn torus (or grid) problem looks to find an n-by-m binary matrix in which every possible j-by-k submatrix appears exactly once. The existence and construction of these binary matrices was determined in the 70's, with generalizations to d-ary matrices in the 80's and 90's. However, these constructions lacked efficient decoding methods, leading to new constructions in the early 2000's. The new constructions develop cross-shaped patterns (rather than rectangular), and rely on a concept known as a half de Bruijn sequence. In this paper, we further advance this construction beyond cross-shape patterns. Furthermore, we show results for universal cycle grids, based off of the one-dimensional universal cycles introduced by Chung, Diaconis, and Graham, in the 90's. These grids have many applications such as robotic vision, location detection, and projective touch-screen displays.