Coding Theory – Covering Codes

Assume that C is a binary code of length n, i.e., any nonempty subset consisting of some binary words of length n. The distance between two codewords is defined to be the number of coordinates in which they differ. The covering radius of a code C is the smallest integer R such that every binary vector of length n is within distance R from at least one codeword.

The study of covering radius includes a number of problems. We want, e.g., to find explicit constructions of codes with small covering radius, and to obtain both lower and upper bounds on the minimum cardinality of a code with given length and covering radius. We wish to estimate the covering radius when the dual distance is known, and determine the covering radius of known code families. We have also studied other covering properties of codes, e.g., the multicovering radius problem, which is connected to cryptography and stream ciphers. All of these problems are discussed in the monograph [2].

References:

1. Alexei Ashikhmin, Iiro Honkala, Tero Laihonen, and Simon Litsyn, On relations between covering radius and dual distance, IEEE Transactions on Information Theory, 45(6):1808-1816, 1999.
2. Gérard Cohen, Iiro Honkala, Simon Litsyn, and Antoine Lobstein, Covering Codes, North-Holland Mathematical Library 54, Elsevier, 1997.
3. Iiro Honkala and Andrew Klapper, Bounds for the multicovering radii of Reed-Muller codes with applications to stream ciphers, Designs, Codes and Cryptography, 23:131-145, 2001.
4. Iiro Honkala and Andrew Klapper, Multicovering bounds from relative covering radii, SIAM J. Discr. Math. 15:228-234, 2002.
5. Markku K. Kaikkonen and Petri Rosendahl: New covering codes from an ADS-like construction, IEEE Trans. Inform. Theory 49: 1809-1812, 2003.
6. Tero Laihonen, Estimates on the Covering Radius When the Dual Distance is Known, Ph.D. Thesis, University of Turku, TUCS Dissertations 11, 1998.
7. Tero Laihonen and Simon Litsyn, New bounds on covering radius as a function of dual distance, SIAM Journal on Discrete Mathematics, 12(2):243-251, 1999.