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. 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. Let q ≥ 2 {displaystyle qgeq 2} , n ≥ 1 {displaystyle ngeq 1} , R ≥ 0 {displaystyle Rgeq 0} be integers.A code C ⊆ Q n {displaystyle Csubseteq Q^{n}} over an alphabet Q of size |Q| = q is calledq-ary R-covering code of length nif for every word y ∈ Q n {displaystyle yin Q^{n}} there is a codeword x ∈ C {displaystyle xin C} such that the Hamming distance d H ( x , y ) ≤ R {displaystyle d_{H}(x,y)leq R} .In other words, the spheres (or balls or rook-domains) of radius Rwith respect to the Hamming metric around the codewords of C have to exhaustthe finite metric space Q n {displaystyle 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. C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} is a 5-ary 2-covering code of length 4. The determination of the minimal size K q ( n , R ) {displaystyle 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(n, R).Lower bounds include the sphere covering bound and Rodemich’s bounds K q ( n , 1 ) ≥ q n − 1 / ( n − 1 ) {displaystyle K_{q}(n,1)geq q^{n-1}/(n-1)} and K q ( n , n − 2 ) ≥ q 2 / ( n − 1 ) {displaystyle K_{q}(n,n-2)geq q^{2}/(n-1)} .The covering problem is closely related to the packing problem in Q n {displaystyle Q^{n}} , i.e. the determination of the maximal size of a q-ary e-error correcting code of length n. 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 = 1 2 ( 3 k − 1 ) {displaystyle n={ frac {1}{2}}(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. The best bounds known as of 2011 are The standard work on covering codes lists the following applications.