
Accession Number : AD0704111
Title : NOTES ON COMBINATORICS: A NEW LOWER BOUND FOR COVERINGS BY ROOK DOMAINS,
Corporate Author : RAND CORP SANTA MONICA CALIF
Personal Author(s) : Johnson,S. M.
Report Date : MAR 1970
Pagination or Media Count : 32
Abstract : Let (V sub k, sup n) be the set of all ntuples a sub 1, a sub 2, ..., a sub n where each a sub i ranges over 0, 1, ... k1. These can be considered as coordinate vectors of points in an ncube 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 errorcorrecting 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)
Descriptors : (*COMBINATORIAL ANALYSIS, THEOREMS), (*CODING, ERRORS), SET THEORY, TOPOLOGY
Subject Categories : Theoretical Mathematics
Cybernetics
Distribution Statement : APPROVED FOR PUBLIC RELEASE