Covering code: Difference between revisions

Revision as of 19:24, 24 May 2008

Latest revision as of 15:14, 18 June 2024

(35 intermediate revisions by 28 users not shown)

Line 1:

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.

{{context}}

== 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-''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''K''_''q''(''n'',&nbsp;''R'').

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’sRodemich'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_correctionError 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''₃(''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''₃(''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''₃(''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''₃(''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 |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|Cayley graphsgraph]]s

==References==

{{reflist|colwidth=30em}}

<references/>

== Weblinks ==

== 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:Discrete mathematics]]

[[Category:Coding theory]]