Constructions of Covering Sequences and Arrays

Abstract

An $(n,R)$-covering sequence is a cyclic sequence whose consecutive $n$-tuples form a code of length $n$ and covering radius $R$. Using several construction methods improvements of the upper bounds on the length of such sequences for $n\le 20$ and $1\le R\le 3$, are obtained. The definition is generalized in two directions. An $(n,m,R)$-covering sequence code is a set of cyclic sequences of length $m$ whose consecutive $n$-tuples form a code of length~$n$ and covering radius $R$. The definition is also generalized to arrays in which the $m\times n$ sub-matrices form a covering code with covering radius $R$. We prove that asymptotically there are covering sequences that attain the sphere-covering bound up to a constant factor.