en>Boodlepounce: link

2012-01-08T22:48:33Z

link

New page

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 (mathematics)|metric]] around the codewords of ''C'' have to exhaust
the [[Wikt:finite|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>P.R.J. Östergård, Upper bounds for ''q''-ary covering codes, ''[[IEEE Transactions on Information Theory]]'', 37 (1991), 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 lower and upper [[bounds]] are known with a large gap between them.
Every construction of a covering code gives an upper bound on ''K''''q''(''n'', ''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>E.R. Rodemich, Covering by rook-domains, ''[[Journal of Combinatorial Theory]]'', 9 (1970), 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 detection and correction|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 predict the results of ''n'' football matches as a home win, draw or away win, or to at least predict {{nowrap|''n'' - 1}} of them with multiple bets. Thus a ternary covering, ''K''3(''n'',1), is sought.

If <math>n=\tfrac12 (3^k-1)</math> then 3''n''-''k'' are needed, so for ''n'' = 4, ''k'' = 2, 9 are needed; for ''n'' = 13, ''k'' = 3, 59049 are needed.<ref>http://alexandria.tue.nl/repository/freearticles/593454.pdf</ref> The best bounds known as of 2011<ref>http://www.sztaki.hu/~keri/codes/3_tables.pdf</ref> are

{| class="wikitable"
! ''n''
! | 1
! | 2
! | 3
! | 4
! | 5
! | 6
! | 7
! | 8
! | 9
! | 10
! | 11
! | 12
! | 13
! | 14
|-
! ''K''3(''n'',1)
| '''1'''
| '''3'''
| '''5'''
| '''9'''
| '''27'''
| 71-73
| 156-186
| 402-486
| 1060-1269
| 2854-3645
| 7832-9477
| 21531-27702
| '''59049'''
| 166610-177147
|}

== Applications ==
The standard work<ref>G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, ''Covering Codes'', [[Elsevier]] (1997) ISBN 0-444-82511-8</ref> on covering codes lists the following applications.

*Compression with [[distortion]]
*[[Data compression]]
*[[Code|Decoding]] errors and erasures
*[[Broadcasting]] in interconnection networks
*[[Football pools]]<ref>H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård, Football pools - a game for mathematicians, ''[[American Mathematical Monthly]]'', 102 (1995), 579-588</ref>
*Write-once memories
*Berlekamp-Gale game
*[[Speech coding]]
*Cellular [[telecommunications]]
*[[Subset]] sums and [[Cayley graph]]s

==References==

<references/>

== 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]]

Bs space - Revision history

en>Boodlepounce: link