Association schemes and coding theory 论文

摘要

This paper contains a survey of association scheme theory (with its algebraic and analytical aspects) and of its applications to coding theory (in a wide sense). It is mainly concerned with a class of subjects that involve the central notion of the distance distribution of a code. Special emphasis is put on the linear programming method, inspired by the MacWilliams transform. This produces upper bounds for the size of a code with a given minimum distance, and lower bounds for the size of a design with a given strength. The most specific results are obtained in the case where the underlying association scheme satisfies certain well-defined "polynomial properties;" this leads one into the realm of orthogonal polynomial theory. In particular, some "universal bounds" are derived for codes and designs in polynomial type association schemes. Throughout the paper, the main concepts, methods, and results are illustrated by two examples that are of major significance in classical coding theory, namely, the Hamming scheme and the Johnson scheme. Other topics that receive special attention are spherical codes and designs, and additive codes in translation schemes, including Z/sub 4/-additive binary codes.