Premium
De Bruijn cycles for covering codes
Author(s) -
Chung Fan,
Cooper Joshua N.
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20033
Subject(s) - de bruijn sequence , string (physics) , de bruijn graph , code (set theory) , discrete mathematics , mathematics , combinatorics , table (database) , computer science , set (abstract data type) , mathematical physics , data mining , programming language
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 size close to the smallest possible covering code. The proof employs tools from field theory, probability, and linear algebra. 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. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004