Title :
Linear inequalities for covering codes. I. Pair covering inequalities
Author_Institution :
Dept. of Electr. Eng. Syst., Univ. of Southern California, Los Angeles, CA, USA
fDate :
5/1/1991 12:00:00 AM
Abstract :
The lower bounds on K(n,R), minimum number of codewords of any binary code of length n, and covering radius R are improved. A new technique combining the Hamming association scheme and the results of a classic problem of covering pairs by k-tuples is introduced. The new lower bounds are obtained by studying various linear inequalities satisfied by covering codes, and such an inequality is derived. The lower bounds for K(n,R) are studied for some special values of n and R, which serve as examples showing how the methods developed are applied to concrete cases.
Keywords :
error correction codes; Hamming association scheme; binary code; covering codes; covering pairs; covering radius; k-tuples; linear inequalities; lower bounds; minimum number of codewords; pair covering inequalities; Binary codes; Concrete; Error correction codes; History; Linear code; Technological innovation; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on
