Covering code: Difference between revisions

Revision as of 03:50, 9 November 2022

Latest revision as of 15:14, 18 June 2024

(3 intermediate revisions by 2 users not shown)

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

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