KIAM Main page Web Library  •  Publication Searh  Русский 

Article, 1998
V.S.Pless and W.C.Huffman, Eds., Amsterdam: Elsevier, vol. 1, 499-648
Authors: Levenshtein V.I.
Universal bounds for codes and designs, in Handbook of Coding Theory
This chapter of Handbook of Coding Theory deals with packing and some related problems for a class of polynomial metric spaces X including finite and compact infinite ones, in particular, Hamming space, Johnson space, the unit Euclidean sphere, and real, complex and quaternionic projective spaces. We are interested in bounds on parameters of finite subsets (codes) C of X which are universal in the following sense. First the bounds are valid for any code C ⊆ X as distinguished from the existential bounds valid only for some codes. Moreover they are valid for any polynomial metric space X, in particular, for the above mentioned metric spaces. The method considered for obtaining universal bounds is based on a description of all nonnegative definite functions F(x,y) on X which depend only on the distance d(x,y) using a system of orthogonal polynomials. Every such function gives a universal upper bound on the size |C| of a code C ⊆ X with minimal distance d(C) between its distinct points. The problem is to choose such a nonnegative definite function which gives rise to the best bound.
polynomial spaces, code, design, universal bounds, linear programming, orthogonal polynomials.
Publication language: english,  pages: 149
Research direction:
Mathematical problems and theory of numerical methods
English source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Levenshtein V. I.,  KIAM RAS