World Library  
Flag as Inappropriate
Email this Article

Covering code

Article Id: WHEBN0017579850
Reproduction Date:

Title: Covering code  
Author: World Heritage Encyclopedia
Language: English
Subject: Coding theory
Collection: Coding Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Covering code

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.

Contents

  • Definition 1
  • Example 2
  • Covering problem 3
  • Football pools problem 4
  • Applications 5
  • References 6
  • External links 7

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.[1]

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 upper and lower bounds are known with a large gap between them. Every construction of a covering code gives an upper bound on Kq(nR). 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).[2] 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.

Football pools problem

A particular case is the football pools problem, based on football pool betting, where the aim is to predict the results of n football matches as a home win, draw or away win, or to at least predict n - 1 of them with multiple bets. Thus a ternary covering, K3(n,1), is sought.

If n=\tfrac12 (3^k-1) then 3n-k are needed, so for n = 4, k = 2, 9 are needed; for n = 13, k = 3, 59049 are needed.[3] The best bounds known as of 2011[4] are

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14
K3(n,1) 1 3 5 9 27 71-73 156-186 402-486 1060-1269 2854-3645 7832-9477 21531-27702 59049 166610-177147
K3(n,2) 1 3 3 8 15-17 26-34 54-81 130-219 323-555 729 1919-2187 5062-6561 12204-19683
K3(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[5] on covering codes lists the following applications.

References

  1. ^ P.R.J. Östergård, Upper bounds for q-ary covering codes, IEEE Transactions on Information Theory, 37 (1991), 660-664
  2. ^ E.R. Rodemich, Covering by rook-domains, Journal of Combinatorial Theory, 9 (1970), 117-128
  3. ^ http://alexandria.tue.nl/repository/freearticles/593454.pdf
  4. ^ http://www.sztaki.hu/~keri/codes/3_tables.pdf
  5. ^ G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997) ISBN 0-444-82511-8
  6. ^ 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

  • Literature on covering codes
  • K_q(n,R)Bounds on
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.