{{Short description|Set of "near" codewords in coding theory}} In coding theory, a '''covering code''' is a set of elements (called ''codewords'') in a space, with the property that every element of the space is within a fixed distance of some codeword.

== Definition ==

Let <math>q\geq 2</math>, <math>n\geq 1</math>, <math>R\geq 0</math> be integers. A code <math>C\subseteq Q^n</math> over an alphabet ''Q'' of size |''Q''| = ''q'' is called ''q''-ary ''R''-covering code of length ''n'' if for every word <math>y\in Q^n</math> there is a codeword <math>x\in C</math> such that the Hamming distance <math>d_H(x,y)\leq R</math>. In other words, the spheres (or balls or rook-domains) of radius ''R'' with respect to the Hamming metric around the codewords of ''C'' have to exhaust the finite metric space <math>Q^n</math>. The covering radius of a code ''C'' is the smallest ''R'' such that ''C'' is ''R''-covering. Every perfect code is a covering code of minimal size.

== Example ==

''C'' = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} is a 5-ary 2-covering code of length 4.<ref>{{cite journal |author=P.R.J. Östergård |title=Upper bounds for ''q''-ary covering codes |journal=IEEE Transactions on Information Theory |volume=37 |year=1991 |pages=660-664}}</ref>

== Covering problem ==

The determination of the minimal size <math>K_q(n,R)</math> of a ''q''-ary ''R''-covering code of length ''n'' is a very hard problem. In many cases, only upper and lower bounds are known with a large gap between them. Every construction of a covering code gives an upper bound on ''K''<sub>''q''</sub>(''n'',&nbsp;''R''). Lower bounds include the sphere covering bound and Rodemich's bounds <math>K_q(n,1)\geq q^{n-1}/(n-1)</math> and <math>K_q(n,n-2)\geq q^2/(n-1)</math>.<ref>{{cite journal |author=E.R. Rodemich |title=Covering by rook-domains |journal=Journal of Combinatorial Theory |volume=9 |year=1970 |pages=117-128}}</ref> The covering problem is closely related to the packing problem in <math>Q^n</math>, i.e. the determination of the maximal size of a ''q''-ary ''e''-error correcting code of length ''n''.

== Football pools problem == A particular case is the '''football pools problem''', based on football pool betting, where the aim is to come up with a betting system over ''n'' football matches that, regardless of the outcome, has at most ''R'' 'misses'. Thus, for ''n'' matches with at most one 'miss', a ternary covering, ''K''<sub>3</sub>(''n'',1), is sought.

If <math>n=\tfrac12 (3^k-1)</math> then 3<sup>''n''-''k''</sup> are needed, so for ''n'' = 4, ''k'' = 2, 9 are needed; for ''n'' = 13, ''k'' = 3, 59049 are needed.<ref>{{cite journal |last1=Kamps |first1=H.J.L. |last2=van Lint |first2=J.H. |title=The football pool problem for 5 matches |journal=Journal of Combinatorial Theory |date=December 1967 |volume=3 |issue=4 |pages=315–325 |doi=10.1016/S0021-9800(67)80102-9 |url=http://alexandria.tue.nl/repository/freearticles/593454.pdf |access-date=9 November 2022 |language=en}}</ref> The best bounds known as of 2011<ref>{{cite web |title=Bounds on K3(n, R) (lower and upper bounds on the size of ternary optimal covering codes) |url=http://old.sztaki.hu/~keri/codes/3_tables.pdf |website=SZÁMÍTÁSTECHNIKAI ÉS AUTOMATIZÁLÁSI KUTATÓINTÉZET |access-date=9 November 2022 |archive-url=https://web.archive.org/web/20221027203847/http://old.sztaki.hu/~keri/codes/3_tables.pdf |archive-date=27 October 2022 |language=en |url-status=live}}</ref> are

{| class="wikitable" style="text-align:center;" ! ''n'' ! | 1 ! | 2 ! | 3 ! | 4 ! | 5 ! | 6 ! | 7 ! | 8 ! | 9 ! | 10 ! | 11 ! | 12 ! | 13 ! | 14 |- ! ''K''<sub>3</sub>(''n'',1) | '''1''' | '''3''' | '''5''' | '''9''' | '''27''' | 71-73 | 156-186 | 402-486 | 1060-1269 | 2854-3645 | 7832-9477 | 21531-27702 | '''59049''' | 166610-177147 |- ! ''K''<sub>3</sub>(''n'',2) | | '''1''' | '''3''' | '''3''' | '''8''' |15-17 | 26-34 | 54-81 | 130-219 | 323-555 | '''729''' | 1919-2187 | 5062-6561 | 12204-19683 |- ! ''K''<sub>3</sub>(''n'',3) | | | '''1''' | '''3''' | '''3''' | '''6''' | 11-12 | 14-27 | 27-54 | 57-105 | 117-243 | 282-657 | 612-1215 | 1553-2187 |}

== Applications == The standard work<ref>{{cite book |author=G. Cohen, I. Honkala, S. Litsyn, A. Lobstein |title=Covering Codes |publisher=Elsevier |year=1997 |isbn=0-444-82511-8}}</ref> on covering codes lists the following applications.

*Compression with distortion *Data compression *Decoding errors and erasures *Broadcasting in interconnection networks *Football pools<ref>{{cite journal |author=H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård |title=Football pools — a game for mathematicians |journal=American Mathematical Monthly |volume=102 |year=1995 |pages=579-588}}</ref> *Write-once memories *Berlekamp-Gale game *Speech coding *Cellular telecommunications *Subset sums and Cayley graphs

==References==

{{reflist|colwidth=30em}}

== External links == * [http://www.infres.enst.fr/~lobstein/biblio.html Literature on covering codes] * [http://www.sztaki.hu/~keri/codes/index.htm Bounds on <math>K_q(n,R)</math>]

Category:Coding theory