imported>Maxal: Formatting

2024-06-18T15:14:50Z

Formatting

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 [[Code word (communication)|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 [[ball (mathematics)|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>{{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''''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>{{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 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 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''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>{{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''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
|-
! ''K''3(''n'',2)
|
| '''1'''
| '''3'''
| '''3'''
| '''8'''
|15-17
| 26-34
| 54-81
| 130-219
| 323-555
| [[Ternary Golay code|'''729''']]
| 1919-2187
| 5062-6561
| 12204-19683
|-
! ''K''3(''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]]
*[[Code|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 graph]]s

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

Covering code - Revision history

imported>Maxal: Formatting