Covering Sequences and Covering-Sequences Codes
Information Theory
Summary
The authors study special cyclic sequences where every group of n consecutive symbols forms a code with specific coverage properties called covering radius R. They focus on creating these sequences and sets of sequences with short lengths and efficient coverage using Hamming codes, especially for small radii. Their methods work well for alphabets with sizes that are prime powers and can be extended to build codes with larger radii too. This helps in designing sequences that are close to the best possible length for these coverage properties.
Authors
Tuvi Etzion
Abstract
An $(n,R)$-covering sequence is a cyclic sequence whose consecutive $n$-tuples form a code of length $n$ and covering radius $R$. An $(n,m,R)$-covering-sequences code is a set of cyclic sequences of length $m$, whose consecutive $n$-tuples form a code of length $n$ and covering radius $R$. These codes are the best building blocks for $(n,R)$-covering sequences. We show, for small radii, how the Hamming code can be used to construct such sequences of short length and such codes with a relatively small number of sequences and a total number of codewords. Sequences with small radius whose length approaches asymptotically to optimality are constructed, especially for an alphabet of prime power size large enough. With the same construction, interesting codes are also constructed for larger radii.