Covering code: Difference between revisions

Revision as of 22:18, 14 November 2020

Latest revision as of 15:14, 18 June 2024

(10 intermediate revisions by 8 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.

== Definition ==

Line 6:

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''

Line 16:

== 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'',&nbsp;''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 correction|error correcting]] code of length ''n''.

== Football pools problem ==

A particular case is the '''[https://poolfixtures.com/ football pools problem]''', based on [[football pool]] betting, where the aim is to predictcome theup resultswith ofa betting system over ''n'' football matches as a home winthat, drawregardless orof awaythe winoutcome, or tohas at leastmost predict {{nowrap|''nR'' -'misses'. 1}}Thus, offor them''n'' matches with multipleat bets.most one Thus'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://wwwold.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;"

Line 75:

| 130-219

| 323-555

| [[Ternary Golay code|'''729''']]

| 1919-2187

| 5062-6561

Line 98:

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

Line 104:

*[[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

Line 113:

==References==

{{reflist|colwidth=30em}}

<references/>

== External links ==