Covering code

From Wikipedia, the free encyclopedia

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 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 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 {1}{2}}(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
K₃(n,1)	1	3	5	9	27	71-73	156-186	402-486	1060-1269	2854-3645	7832-9477	21531-27702	59049	166610-177147
K₃(n,2)		1	3	3	8	15-17	26-34	54-81	130-219	323-555	729	1919-2187	5062-6561	12204-19683
K₃(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

References

^ P.R.J. Östergård (1991). "Upper bounds for q-ary covering codes". IEEE Transactions on Information Theory. 37: 660–664.
^ E.R. Rodemich (1970). "Covering by rook-domains". Journal of Combinatorial Theory. 9: 117–128.
^ Kamps, H.J.L.; van Lint, J.H. (December 1967). "The football pool problem for 5 matches" (PDF). Journal of Combinatorial Theory. 3 (4): 315–325. doi:10.1016/S0021-9800(67)80102-9. Retrieved 9 November 2022.
^ "Bounds on K3(n, R) (lower and upper bounds on the size of ternary optimal covering codes)" (PDF). SZÁMÍTÁSTECHNIKAI ÉS AUTOMATIZÁLÁSI KUTATÓINTÉZET. Archived (PDF) from the original on 27 October 2022. Retrieved 9 November 2022.
^ G. Cohen, I. Honkala, S. Litsyn, A. Lobstein (1997). Covering Codes. Elsevier. ISBN 0-444-82511-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård (1995). "Football pools — a game for mathematicians". American Mathematical Monthly. 102: 579–588.{{cite journal}}: CS1 maint: multiple names: authors list (link)

External links

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 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 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 {1}{2}}(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
K₃(n,1)	1	3	5	9	27	71-73	156-186	402-486	1060-1269	2854-3645	7832-9477	21531-27702	59049	166610-177147
K₃(n,2)		1	3	3	8	15-17	26-34	54-81	130-219	323-555	729	1919-2187	5062-6561	12204-19683
K₃(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

References

^ P.R.J. Östergård (1991). "Upper bounds for q-ary covering codes". IEEE Transactions on Information Theory. 37: 660–664.
^ E.R. Rodemich (1970). "Covering by rook-domains". Journal of Combinatorial Theory. 9: 117–128.
^ Kamps, H.J.L.; van Lint, J.H. (December 1967). "The football pool problem for 5 matches" (PDF). Journal of Combinatorial Theory. 3 (4): 315–325. doi:10.1016/S0021-9800(67)80102-9. Retrieved 9 November 2022.
^ "Bounds on K3(n, R) (lower and upper bounds on the size of ternary optimal covering codes)" (PDF). SZÁMÍTÁSTECHNIKAI ÉS AUTOMATIZÁLÁSI KUTATÓINTÉZET. Archived (PDF) from the original on 27 October 2022. Retrieved 9 November 2022.
^ G. Cohen, I. Honkala, S. Litsyn, A. Lobstein (1997). Covering Codes. Elsevier. ISBN 0-444-82511-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård (1995). "Football pools — a game for mathematicians". American Mathematical Monthly. 102: 579–588.{{cite journal}}: CS1 maint: multiple names: authors list (link)

External links

Literature on covering codes
Bounds on K q ( n , R ) {\displaystyle K_{q}(n,R)}

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

[2] E.R. Rodemich (1970). "Covering by rook-domains". Journal of Combinatorial Theory. 9: 117–128.

[3] Kamps, H.J.L.; van Lint, J.H. (December 1967). "The football pool problem for 5 matches" (PDF). Journal of Combinatorial Theory. 3 (4): 315–325. doi:10.1016/S0021-9800(67)80102-9. Retrieved 9 November 2022.

[4] "Bounds on K3(n, R) (lower and upper bounds on the size of ternary optimal covering codes)" (PDF). SZÁMÍTÁSTECHNIKAI ÉS AUTOMATIZÁLÁSI KUTATÓINTÉZET. Archived (PDF) from the original on 27 October 2022. Retrieved 9 November 2022.

[5] G. Cohen, I. Honkala, S. Litsyn, A. Lobstein (1997). Covering Codes. Elsevier. ISBN 0-444-82511-8.{{cite book}}: CS1 maint: multiple names: authors list (link)

[6] H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård (1995). "Football pools — a game for mathematicians". American Mathematical Monthly. 102: 579–588.{{cite journal}}: CS1 maint: multiple names: authors list (link)

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

[2] E.R. Rodemich (1970). "Covering by rook-domains". Journal of Combinatorial Theory. 9: 117–128.

[3] Kamps, H.J.L.; van Lint, J.H. (December 1967). "The football pool problem for 5 matches" (PDF). Journal of Combinatorial Theory. 3 (4): 315–325. doi:10.1016/S0021-9800(67)80102-9. Retrieved 9 November 2022.

[4] "Bounds on K3(n, R) (lower and upper bounds on the size of ternary optimal covering codes)" (PDF). SZÁMÍTÁSTECHNIKAI ÉS AUTOMATIZÁLÁSI KUTATÓINTÉZET. Archived (PDF) from the original on 27 October 2022. Retrieved 9 November 2022.

[5] G. Cohen, I. Honkala, S. Litsyn, A. Lobstein (1997). Covering Codes. Elsevier. ISBN 0-444-82511-8.{{cite book}}: CS1 maint: multiple names: authors list (link)

[6] H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård (1995). "Football pools — a game for mathematicians". American Mathematical Monthly. 102: 579–588.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[1]

[2]

[3]

[4]

[5]

[6]