NOTES ON COMBINATORICS: A NEW LOWER BOUND FOR COVERINGS BY ROOK DOMAINS,
Abstract
Let (V sub k, sup n) be the set of all n-tuples a sub 1, a sub 2, ..., a sub n where each a sub i ranges over 0, 1, ... k-1. These can be considered as coordinate vectors of points in an n-cube with k points on a side. The Hamming metric d(x,y) is defined to be the number of coordinates in which x and y differ. A Hamming sphere about x of radius r (or a rook domain) is the set of all y in (V sub k, sup n) such that d(x,y) = or < r. In previous papers the author has refined estimates of how many nonintersecting Hamming spheres can be packed into the space. This gave greatly improved upper bounds on the size of error-correcting coes, a subject of growing importance in the problem of error free transmission of information subject to noise. In the present paper somewhat analogous methods are used to the dual problem of improving lower bounds on the number sigma(n,r,k) of rook domains or Hamming spheres which are needed to cover the whole space, where now the spheres may intersect. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1970
- Accession Number
- AD0704111
Entities
People
- S. M. Johnson
Organizations
- RAND Corporation