Covering code

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In coding theory, a covering code is an object satisfying a certain mathematical property: A code of length n over Q is an R-covering code if for every word of $Q n$ there is a codeword such that their Hamming distance is $\le R$ .

Definition

Let $q\geq 2$ , $n\geq 1$ , $R\geq 0$ be integers. A code $C\subseteq Q^n$ over an alphabet Q of size |Q| = q is called q-ary R-covering code of length n if for every word $y\in Q^n$ there is a codeword $x\in C$ such that the Hamming distance $d_H(x,y)\leq R$ . In other words, the spheres (or balls or rook-domains) of radius R with respect to the Hamming metric around the codewords of C have to exhaust the finite metric space $Q n$ . 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.¹

Covering problem

The determination of the minimal size $K q (n, R)$ of a q-ary R-covering code of length n 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’s bounds $K_q(n,1)\geq q^{n-1}/(n-1)$ and $K_q(n,n-2)\geq q^2/(n-1)$ .² The covering problem is closely related to the packing problem in $Q n$ , i.e. the determination of the maximal size of a q-ary e-error correcting code of length n.

Applications

The standard work³ on covering codes lists the following applications.

Compression with distortion
Data compression
Decoding errors and erasures
Broadcasting in interconnection networks
Football pools⁴
Write-once memories
Berlekamp-Gale game
Speech coding
Cellular telecommunications
Subset sums and Cayley graphs

References

^ P.R.J. Östergård, Upper bounds for q-ary covering codes, IEEE Transactions on Information Theory, 37 (1991), 660-664
^ E.R. Rodemich, Covering by rook-domains, Journal of Combinatorial Theory, 9 (1970), 117-128
^ G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997) ISBN 0-444-82511-8
^ H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård, Football pools - a game for mathematicians, American Mathematical Monthly, 102 (1995), 579-588

External links

Return to Fuhz Home - This article covering Covering code is enhanced for the visually impaired.

Article from Wikipedia. All text is available under the terms of the GNU Free Documentation License - Our Privacy Policy - Thanks Auto Blog Commenter

[0] P.R.J. Östergård, Upper bounds for q-ary covering codes, IEEE Transactions on Information Theory, 37 (1991), 660-664

[1] E.R. Rodemich, Covering by rook-domains, Journal of Combinatorial Theory, 9 (1970), 117-128

[2] G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997) ISBN 0-444-82511-8

[3] H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård, Football pools - a game for mathematicians, American Mathematical Monthly, 102 (1995), 579-588

1

2

3

4