2003/10/24 by Fan Chung, Joshua Cooper, Chung, Fan +2
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Coding theory and cryptography #cs.IT #math.CO #math.IT #msc:05B99
paper · pdf · doi:10.48550/arxiv.math/0310385
18 pages, 0 figures, submitted to RSA
arxiv created 2003/10/28 · arxiv updated 2009/12/01
A de Bruijn covering code is a q-ary string S so that every q-ary string is at most R symbol changes from some n-word appearing consecutively in S. We introduce these codes and prove that they can have length close to the smallest possible covering code. The proof employs tools from field theory, probability, and linear algebra. We also prove a number of ``spectral'' results on de Bruijn covering codes. Included is a table of the best known bounds on the lengths of small binary de Bruijn covering codes, up to R=11 and n=13, followed by several open questions in this area.