Covering code explained

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.

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 calledq-ary R-covering code of length nif 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 Rwith respect to the Hamming metric around the codewords of C have to exhaustthe 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 = 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 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)} .^[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 come up with a betting system over n football matches that, regardless of the outcome, has at most R 'misses'. Thus, for n matches with at most one 'miss', a ternary covering, K₃(n,1), is sought.

If

n = \tfrac 12 ( 3 ^{k-1)} then 3^n-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.

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

External links

• Literature on covering codes
• Bounds on K _{q(n,R)}

Notes and References

1. P.R.J. Östergård . Upper bounds for q-ary covering codes . . 37 . 1991 . 660-664.
2. E.R. Rodemich . Covering by rook-domains . . 9 . 1970 . 117-128.
3. Kamps . H.J.L. . van Lint . J.H. . The football pool problem for 5 matches . Journal of Combinatorial Theory . December 1967 . 3 . 4 . 315–325 . 10.1016/S0021-9800(67)80102-9 . 9 November 2022 . en.
4. Web site: Bounds on K3(n, R) (lower and upper bounds on the size of ternary optimal covering codes) . SZÁMÍTÁSTECHNIKAI ÉS AUTOMATIZÁLÁSI KUTATÓINTÉZET . 9 November 2022 . https://web.archive.org/web/20221027203847/http://old.sztaki.hu/~keri/codes/3_tables.pdf . 27 October 2022 . en . live.
5. Book: G. Cohen, I. Honkala, S. Litsyn, A. Lobstein . Covering Codes . . 1997 . 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 . . 102 . 1995 . 579-588.