Covering code: Difference between revisions

Revision as of 12:29, 28 October 2012

Latest revision as of 15:14, 18 June 2024

(18 intermediate revisions by 16 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''

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

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 lower[[upper and upperlower [[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 '''football pools problem''', based on [[football pool]] betting, where the aim is to predictcome theup resultswith ofa <math>betting system over ''n</math>'' football matches as a home winthat, drawregardless orof awaythe winoutcome, or tohas at leastmost predict''R'' 'misses'. <math>Thus, for ''n-1</math>'' of themmatches with multipleat bets.most one So this looks for'miss', a trinaryternary covering, ''K''<mathsub>3</sub>K_3(''n'',1)</math>., is sought.

If <math>n=\tfrac12 (3^k-1)</math> then 3<mathsup>3^{''n''-''k}''</mathsup> are needed, so for <math>''n'' = 4, ''k'' = 2</math>, 9 are needed; for <math>''n'' = 13, ''k'' = 3</math>, 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;"

! ''n''

! | 1

Line 48:

! | 14

|-

! ''K''<mathsub>3</sub>K_3(''n'',1)</math>

| '''1'''

| '''3'''

Line 63:

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

Line 73 ⟶ 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 82 ⟶ 113:

==References==

{{reflist|colwidth=30em}}

<references/>

== External links ==