Covering code: Article and Information about Covering code

Covering code - Fuhz Articles
Visually Impaired Edition.

Covering code article, this Fuhz page will hopefully provide the answers to the who, what where and why on the Covering code topic.
At the bottom of the page we often provide links to external documents relating to Covering code which may also help your research. Every effort is made to ensure the content on this page is as accurate and error free as possible, however whenever researching information that requires the utmost accuracy such as a term paper it is always best to cross reference facts with numerous sources.

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

1 Definition
2 Example
3 Covering problem
4 Applications
5 References
6 External links

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