IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO.

6, OCTOBER 1998 2477

Association Schemes and Coding Theory

Philippe Delsarte and Vladimir I. Levenshtein, Associate Member, IEEE

(Invited Paper)

Abstract—This paper contains a survey of association scheme say that association scheme theory is as old as Frobenius’
theory (with its algebraic and analytical aspects) and of its representation theory of finite groups (see [11]).
applications to coding theory (in a wide sense). It is mainly In combinatorics, an association scheme is defined in terms
concerned with a class of subjects that involve the central notion
of the distance distribution of a code. Special emphasis is put on of certain regularity properties. In the “group case,” the associ-
the linear programming method, inspired by the MacWilliams ation scheme structure arises from certain symmetry properties,
transform. This produces upper bounds for the size of a code which directly induce the desired regularity properties. Thus
with a given minimum distance, and lower bounds for the size following Bannai and Ito, we may say that association scheme
of a design with a given strength. The most specific results are theory is a “group theory without groups” [10]. Such a
obtained in the case where the underlying association scheme
satisfies certain well-defined “polynomial properties;” this leads distinction between regularity and symmetry can be found
one into the realm of orthogonal polynomial theory. In particular, in several subjects. An important example, which belongs to
some “universal bounds” are derived for codes and designs association scheme theory, is the distinction between distance-
in polynomial type association schemes. Throughout the paper, regular graphs and distance-transitive graphs [26].
the main concepts, methods, and results are illustrated by two The association scheme approach was introduced in coding
examples that are of major significance in classical coding theory,
namely, the Hamming scheme and the Johnson scheme. Other theory in 1973 [37] to deal with a collection of topics involving
topics that receive special attention are spherical codes and the notion of the “distance distribution” of a code (see [35]
designs, and additive codes in translation schemes, including and [36]). One of the main subjects is the general concept of a
4 -additive binary codes. -design or a code with “dual distance” and a universal
Index Terms— Association schemes, codes and designs, du- (lower) bound on the size of -designs. (Term “universal”
ality, linear programming, orthogonal polynomials, polynomial means here that the bound is valid for all -designs in all
schemes, translation schemes, universal bounds. association schemes under consideration.) This allows one to
explain the unified nature of different combinatorial objects
I. INTRODUCTION and bounds. If a covering radius of a code in a metric
space characterizes a degree of the approximation of any

A SSOCIATION scheme theory is part of what is now

called algebraic combinatorics [10], [54]. It has two main
origins. Association schemes were introduced in statistical
element of
of
by elements of , then the “dual distance”
characterizes an approximation degree of by
the whole.” This idea turned out to be very useful for some
“at
(combinatorial) design theory by Bose and Shimamoto [23], problems of numerical analysis [45] and cryptography [122]
and the appropriate algebraic setting was given by Bose and and was extended to any finite and compact infinite metric
Mesner [21]. In fact, the subject can be traced back to a paper spaces in [81]. Another important topic is the problem of
by Bose and Nair in 1939 [22]. finding a universal (upper) bound on the size of a code with
The second origin is group theory and, more precisely, minimum distance or, briefly, a -code (see [82] and
character theory of finite groups, developed by Frobenius, [88]). Short introductions to “association schemes and coding
Schur, and Burnside. For example, as pointed out by Ban- theory” were given by Sloane [155] and by Goethals [55].
nai and Ito [10], a paper by Hoheisel in 1939 derives the The same subject is treated in detail in a recent paper by
orthogonality relations for group characters by a method Camion [32].
belonging to “association scheme theory” (before the appear- One of the most significant (although elementary) dis-
ance of association schemes in combinatorics) [61]. Another coveries was the fact that the MacWilliams transform1 of
pioneering contribution in this area is a paper by Kawada the distance distribution of any code is nonnegative as the
on character algebras [67] (see [10]). In fact, one may even mean value of nonnegative definite functions (matrices) over
the code [35], [37]. This “innocent appearing result” (to
quote Welch, McEliece, and Rumsey [131]) has far-reaching
Manuscript received December 2, 1997; revised March 6, 1998. The work of consequences. The method of obtaining bounds for -codes
V. I. Levenshtein was supported by the Russian Foundation for Basic Research
under Grant 98-01-00146 and by the Civilian Research and Development based on nonnegative definite functions depending
Foundation under Grant RM1-346. on distance , i.e., , has been
P. Delsarte is with the Department of Computing Science and Engineering,
Catholic University of Louvain, Louvain-la-Neuve, Belgium.
V. I. Levenshtein is with the Keldysh Institute for Applied Mathematics, 1 Recall that the MacWilliams identities relate the weight distribution of
Russian Academy of Science, 125047 Moscow, Russia. a linear code (over a finite field) with that of its orthogonal code by a
Publisher Item Identifier S 0018-9448(98)05287-0. well-defined linear transform (over the reals) [86], [87].

0018–9448/98$10.00  1998 IEEE

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2478 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

applied by Blichfeldt [19], Rankin [97], and Sidelnikov [110], onality relations. (In the case of the Hamming scheme, we
[111]. However, for association schemes (and some of their have , where is the Krawtchouk
generalizations) there is a description of all such functions. polynomial of degree .) It appears that the -numbers
This makes it possible to apply a linear programming method are the eigenvalues of the adjacency matrix
for finding the best universal bound for -codes (and -designs There is an important formal duality in the theory, called
as well) [35], [37]. For a class of association schemes of the Krein duality, which permutes the roles of the matrix and
important interest for coding theory, the corresponding linear pointwise products in the Bose–Mesner algebra [8], [42], [95].
programs can be treated as extremum problems for systems This duality is a rich source of research ideas: “trying to make
of orthogonal polynomials. Thus any choice of a permissible the theory closed under duality.”
polynomial gives rise to a universal bound for -codes. In A code in an association scheme is a nonempty subset
1977, McEliece, Rodemich, Rumsey, and Welch (MRRW) of the point set (with the inherited relations ). The
[90] proposed a polynomial which gives an improvement of inner distribution2 of is the -tuple where
the best asymptotic bound obtained before in [111]. One year counts the ordered pairs of code points with
later, another polynomial was proposed [73]; it gives rise to In this general context, the “innocent appearing
a universal bound for -codes that improves upon the MRRW result” alluded to above is the fact that the -transform of the
bound and is attained for many cases in different spaces inner distribution is nonnegative, in the sense that
although it gives the same asymptotic result. It turned out is a nonnegative real number (for This is
[77], [112] that this polynomial is an optimal solution of the the basis of the linear programming method to find upper
corresponding extremum problem in the class of polynomials bounds for -codes and lower bounds for -designs in an
of a restricted degree. This progress in bounding -codes association scheme [37]. “Duality” between -codes and -
allowed one to improve bounds on the Shannon reliability designs manifests itself in the fact that any linear programming
function [107] for some probabilistic channels (see [65]). bound for -codes gives a linear programming bound for
In classical coding theory, dealing with codes in a Hamming -designs and conversely [80]. Explicit universal bounds for
scheme, the MacWilliams transform involves a family of codes and designs in some classes of association schemes have
orthogonal polynomials [121] known as the Krawtchouk poly- been obtained by use of this approach [37], [73], [76], [77],
nomials [68]. Surprisingly enough, this fact was not uncovered [81].
before 1972 [35], although the “polynomial property” of the Certain parts of the theory can be developed further, when
MacWilliams transform was pointed out by MacWilliams appropriate restrictive assumptions are imposed on the - or -
herself in 1963 [86]. The importance of the role played by numbers. An association scheme is said to be a -polynomial
Krawtchouk polynomials in coding theory is well recognized scheme if the -numbers can be represented in the form
nowadays [78], [82], [88]. It can be explained by the fact where is a real polynomial of degree in
that these polynomials give the eigenvalues of the distance and are distinct real numbers. The orthogonality
relation matrices of the Hamming scheme [37]. This was first relations on the -numbers show that is a system
proved implicitly by Vere-Jones in the binary case [128]. A of orthogonal polynomials. There is a similar (dual) definition
thorough investigation of the group-theoretic significance of and a similar result for a -polynomial scheme (involving the
the Krawtchouk polynomials was given by Dunkl [46]. -numbers instead of the -numbers) [37].
The familiar “block codes of length over a -ary al- The -polynomial property has a clear interpretation:
phabet,” which belong to classical coding theory, can be contains the pairs of points that are at distance apart in
called “codes in the Hamming (association) scheme ” the “generator graph” In other words, is a
The general association scheme approach provides us naturally distance-regular graph. This subject was introduced by Biggs
with a considerable extension of the theory in that it applies in 1969 (see [18]); it is treated in great detail by Brouwer,
to “codes” and “designs” in any association scheme [37], Cohen, and Neumaier [26]. The dual notion of a -polynomial
[39]. This combinatorial structure consists of a nonempty scheme is equally interesting and has been investigated by
finite set endowed with a collection of binary relations several authors [10], [54], [71], [72], [77], [81], [93], [94],
having strong regularity properties. The adja- [126]. It should be noted, however, that this notion does not
cency matrices of the graphs generate a commutative have a simple “combinatorial meaning.”
and associative algebra (over the complex numbers) both for The theory of -polynomial schemes can be extended so as
the matrix product and the pointwise product. This is called to include “continuous analogs” such as the Euclidean sphere
the Bose–Mesner algebra of the association scheme. It has and the projective space in a unified framework [48], [54],
two distinguished bases: the basis consisting of the adjacency [65], [77], [81], [93], [116], [119]. In particular, the linear
matrices , and the basis consisting of the irreducible idem- programming method can be applied to derive upper bounds
potent matrices By definition, there exist well-defined for spherical codes with a given minimum distance and lower
complex numbers and such that bounds for spherical designs with a given strength (see [45],
[77], [81], [116], and [135]).
If the point set is endowed with the structure of
an Abelian group and if the relations are “translation-
The -numbers and the -numbers play a promi- 2 A related notion is the outer distribution, which enumerates the Ri -
nent role in the theory. They satisfy some well-defined orthog- associates of each point x 2 X in the code Y:

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2479

invariant” with respect to that group, then the association b) For the converse
scheme is said to be a translation scheme (with respect
to the given group). This notion is equivalent to that of a
of belongs to
commutative Schur ring, investigated in detail by Tamaschke
c) There exist integer numbers , called intersection
[123]. There exists a dual translation scheme (with respect
numbers, with , such that, for each pair
to the dual group of ). If is an additive code in ,
, the number of points with and
i.e., a subgroup of , then there is a natural definition of
is equal to the constant (for ).
an annihilator code in the dual scheme. (The relation
between and generalizes the relation between a linear Condition b) induces a pairing over , defined by
The number is denoted by and is called
code in Hamming scheme and its orthogonal code )
the valency (or the degree) of the directed graph ; it
The inner distributions of the codes and are related
counts the points with , for any fixed
by generalized MacWilliams identities, in the sense that they
Clearly, and
are the -transform and -transform of each other (within
In most coding-theoretic applications, the definition above
scaling) [32], [37], [42].
can be made more restrictive. The association scheme
Thus the theory of translation schemes is quite interesting in
is said to be symmetric if all its relations are symmetric.
that it provides the formal Krein duality with an actual duality
Thus condition b) is replaced by
interpretation. Furthermore, in this restricted context, there is
b) for each
a simple criterion to check whether a given additive code
In other words, a symmetric association scheme has a trivial
carries a “subscheme” of the translation scheme , and to
pairing, i.e., for all (Notice that the identity
characterize the dual scheme of (see [37] in the case of the in c) can be omitted in the symmetric case, since it becomes
Hamming scheme). a consequence of the other requirements.)
This paper aims at giving a self-contained account of those In particular, a -class association scheme is
parts of association scheme theory that are especially relevant equivalent to a strongly regular graph [20], [105] in the
to coding theory (in a wide sense), along the lines of the symmetric case, and to a skew conference matrix in the
present introduction. nonsymmetric case [13], [56].
Section II contains the basic definitions; it is focused on Note that we can consider an association scheme
the Bose–Mesner algebra and its formal duality. Section III with an ordering of as a space with
introduces the subject of codes (and designs) in an association the function which is defined as follows:
scheme, with special emphasis on the notions of the inner and
outer distributions. This also includes the linear programming if and only if (1)
approach and a duality in bounding the sizes of codes and In the symmetric case this function has, in particular, the
designs based on the existence of two orthogonality conditions. properties if and only if and
Section IV gives up-to-date bounds on fundamental parameters , but, in general, does not satisfy the triangle in-
of codes and designs in - and/or -polynomial schemes. Two equality and hence is not a distance function. On the other
extremum problems for systems of orthogonal polynomials are hand, a metric space with a distance function
considered and their optimal solutions are used to describe which takes values from is a symmetric -class association
the best known linear programming bounds. The results for scheme with if and only if for any
-polynomials schemes are extended to the case of the unit and , the number
Euclidean sphere. For - and -polynomial schemes, three
(2)
pairs of universal bounds and main asymptotic results are
presented. Section V deals with translation schemes and their depends only on and In fact, we state that this is
additive codes; it includes an introduction to -additive true for the first two examples below.
binary codes.
Example 1: Let be the th Cartesian power of
II. BASIC NOTIONS a finite alphabet , with Let
denote the Hamming distance function
A. Definitions and Examples
Let be a finite set of “points,” with For an
integer , consider a set of Then with is a symmetric -
nonempty binary relations on (i.e., ), forming class association scheme, called the Hamming scheme and
a partition of the Cartesian square of denoted by It appears as the natural framework of the
For integers and with , we shall use the classical theory of “block codes” [82], [88]. When is a
notation for the integer interval and put prime power, can be endowed with the structure of the
finite field In this case, where
is the Hamming weight function, given by
Definition 1: The pair is said to be an -class More generally, this applies
association scheme if to the case where has the structure of an additive Abelian
a) is the diagonal, i.e., group. (No multiplicative operation is required here.)

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2480 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

Example 2: Let be the set of binary -tuples of a fixed by The directed graph is represented by its
weight , with Thus adjacency matrix , defined by
for
(3)
for
For , define Definition 2: Let be an -class association scheme
(see Definition 1). The Bose–Mesner algebra of , de-
noted by , is the complex vector space generated by the
and
adjacency matrices , that is,
(4)
Then is a symmetric -class association scheme, called
From the fact that is a partition of and from condition
the Johnson scheme and denoted by It is a “subscheme” of
a), it follows that contains the all-one matrix and the unit
the binary Hamming scheme with
matrix , since
The Johnson scheme plays a useful role in combinatorial
coding theory. (5)
Example 3: Let and Condition b) says that is closed under conjugation
The composition of a point in is the integer -tuple and under transposition , whence under
defined by conjugate transposition , since
(6)

Assume that is an Abelian group. Define a set of binary Condition c) says that is closed under matrix multiplication,
relations on as follows. A pair in belongs to and that multiplication in is commutative, since
a certain relation if and only if the difference has a
specified composition. Then is an -class association (7)
scheme, with called the composition scheme.
It is symmetric when for all , i.e., when is an This shows that the -dimensional vector space
elementary Abelian -group (of order ). In particular, defined by (4) has the structure of a commutative algebra
the composition scheme with reduces to the binary (over ). As indicated in Definition 2 (with some anticipation
Hamming scheme in the use of the term “algebra”), is usually referred to
There are several other families of association schemes that as the Bose–Mesner algebra (or adjacency algebra) of the
have interesting applications in coding theory. Let us mention association scheme (see [21]).
five of them: i) the association scheme relative to the split For a symmetric association scheme, we have
weight enumerator [42], [88]; ii) the Lee scheme [124]; iii) the for all In this case, we can define the Bose–Mesner algebra
nonbinary Johnson scheme [1], [124], [125]; iv) the association over the reals, i.e., replace by in (4).
scheme of matrices over a finite field [41] (which has The adjacency algebra is known to be semi-simple. This
applications in crisscross error correcting codes [52], [102]); means that there exists a unitary matrix of order that
v) the association scheme of skew-symmetric matrices reduces each matrix to a diagonal form
over a finite field [43]. In the last two cases, the relations As a consequence, possesses a unique basis of
are defined from the rank metric over the matrix set irreducible idempotent matrices which are
Of course, there exist applications of association schemes mutually orthogonal
outside the area of coding theory (in a wide sense). It is
especially worth saying that association schemes have recently for (8)
found considerable interest in spin model theory (a branch of In particular, The rank of will be denoted
mechanical statistics). The idea is due to Jaeger (see [63] and by , and the numbers will be referred
the references therein). to as the multiplicities of the association scheme By
Finally, let us mention some constructions that produce definition, has eigenvalues and with multiplicities
association schemes from other association schemes. In par- and Notice that and
ticular, there is the notion of the extension [37], product [54], Considering the inner product
and merging [32] of association schemes.
(9)
B. The Bose–Mesner Algebra
It proves very useful to investigate a combinatorial structure for complex functions defined on one can represent
such as an association scheme by matrix algebra meth- the matrix in the form
ods. Let denote the set of square complex matrices
of order , where rows and columns are labeled with (10)
the points , and the entry of is denoted

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2481

where is an arbitrary orthonormal basis Example 1 (continued): For given values of (the
of the linear space generated by the columns of (It is “length”) and (the “alphabet size”), and for , we
orthonormal with respect to (9).) define the Krawtchouk polynomial as follows [68]:
Definition 3: The -numbers of an -class association
scheme are the complex numbers , with (16)
defined from the expansion of the adjacency matrices
in the basis of the irreducible idempotent matrices of
the algebra , i.e., Clearly, is a polynomial of degree in The -
numbers and the -numbers of are the values assumed by
the Krawtchouk polynomials at the integer points
for (11) More precisely

Analogously, the -numbers of are the complex num- (17)

bers , with defined from the inverse expansion,
The valencies and multiplicities are
within the normalizing factor , i.e.,
Example 2 (continued): For given values of (the
for (12) “length”) and (the “weight”), the valencies and multiplicities
of the Johnson scheme are given by

These numbers play a major role in the theory. It follows

from (11) that the -number is the eigenvalue of
relative to the -dimensional space spanned by the
columns of In particular, (valency of ). For we define the Hahn polynomial3 and the
Notice that (rank of ). In view to (3) and (1), dual Hahn polynomial as follows [66]:
(12) can be written in the form

(13) (18)
If the association scheme is symmetric, then its
-numbers and -numbers are real.
Let denote the linear space of complex (or real in
the symmetric case) functions defined on In particular, the
-numbers and the -numbers are values of the - (19)
functions and -functions which
form two bases of This implies that any function Clearly, is a polynomial of degree in It is easily
has a unique expansion over either of these bases seen that is a polynomial of degree in
The -numbers and the -numbers of can be determined
(14) (see [37]) from these polynomials by

(20)
The following result expresses the well-known orthogonal-
ity relations for the -functions and -functions. It appears as C. Formal Duality
a consequence of (8), basically.
The adjacency matrices and the idempotent matrices
Theorem 1: The -functions play dual roles in the theory. This formal duality, which
are pairwise-orthogonal on with respect to the multiplic- interchanges the -numbers and the -numbers, will be referred
ities and the -functions to as the Krein duality [8]. Let us examine this subject in some
are pairwise-orthogonal on with respect to the valencies detail. The Bose–Mesner algebra is closed not only under
More precisely ordinary matrix multiplication , but also under
pointwise (or Hadamard) multiplication
defined by This stems from
the fact that the adjacency matrices are “idempotent” and
“mutually orthogonal” with respect to the pointwise product

for (21)

In view of the fact that the relations (11) and (12) are inverse The formal Krein duality under discussion permutes the
of each other, the -numbers and the -numbers are related by roles of the matrix product and the pointwise product. Thus
(15) 3 In fact, these are the Hahn polynomials of spherical type.

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2482 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

the identities (8) and (21) are dual of each other. As duals of D. The Group Case and Generalizations
(5) and (6), we have In Examples 1–3 of Section II-A, the regularity properties
defining the association scheme structure are induced by some
symmetry properties, i.e., by a certain “group of automor-
phisms.” We now say a few words on this subject (see [10],
[58], and [132]). Let be a transitive permutation group
where is a well-defined pairing over For a
acting on the point set It induces a partition of into
symmetric association scheme, this pairing is trivial:
a well-defined set of orbits (By
for all
definition, such an orbit contains the images
Let us stress the fact that the idempotent matrices are
Hermitian and nonnegative definite, since their eigenvalues of a fixed pair under all mappings ).
are and . (It can be viewed as a dual of the property of The resulting structure satisfies conditions a)– c) of
adjacency matrices, having entries and .) an association scheme, except possibly the “commutativity
The following property is essential for the linear program- condition” In any case, the adjacency matrices
ming method introduced in Section III below. form the basis of a subalgebra of (It is called the
Hecke algebra.) This algebra is commutative if and only if
Theorem 2: For any function the matrix (for all ).
is Hermitian and nonnegative definite if and
only if Example 1 (continued): Let be the permutation group on
Next, we examine the dual of identity (7), that is, generated by two types of mappings:
i) a permutation on the coordinates;
ii) in each coordinate position, a permutation on the
(22)
alphabet symbols.
This group has order , and it is transitive on The
The numbers defined from (22) are usually called the Krein corresponding structure is the Hamming scheme
parameters; they are the duals of the intersection numbers In particular, the binary Hamming scheme arises from the
In particular, and when Thus the (complete) monomial group of degree , containing
multiplicities are the duals of the valencies Notice that the matrices of order that have one nonzero element, equal
is a Hermitian nonnegative definite matrix according to , in each row and each column.
to (10). Hence, by (13) and Theorem 2 the Krein parameters
satisfy (see [55] and [101]). Example 2 (continued): Let be the symmetric group
By use of (7) and (22) we deduce that the intersection num- of degree , containing the permutations on coordinates.
bers and the Krein parameters are the linearization It acts in a natural way on the set of binary -tuples of
factors relative to the -numbers and to the -numbers weight The corresponding structure is the Johnson
, respectively, in the sense that scheme
The notion of an association scheme can be gener-
(23) alized, by omitting the commutativity requirement
A further extension is obtained by relaxing the “homogeneity
condition” a) in Definition 1. In general, it is only required
(24) that the diagonal relation be a union of
some relations belonging to the set Thus we arrive at a
combinatorial structure called a coherent configuration
Two -class association schemes and , with
[59] (equivalent to a cellular ring [50]). The group theoretic
, are formal dual of each other if the -numbers of
counterpart of this general structure is obtained by leaving out
are the -numbers of , and conversely, i.e.,
the transitivity assumption.
(25) Certain infinite metric spaces occur as analogs of association
schemes that are important in coding theoretic applications.
A necessary condition for an association scheme to have a We call distance-transitive (or two-point homogeneous [130])
formal dual is that its Krein parameters be integers (since they a connected compact metric space with the distance function
are the intersection numbers of the dual). and the isometry group , if for any
the equality implies the existence of
Example 1 (continued): In view of (17), the Hamming some such that and As an
scheme is formally self-dual. In fact, it is actually self- example of a distance-transitive space we mention the unit
dual in the strong sense of “duality in translation schemes”
Euclidean sphere in (considered in more detail in
(see Section V below).
Section IV-E) whose isometry group consists of all orthogonal
Example 2 (continued): The Johnson scheme has no matrices of order A distance-transitive space has many
formal dual. However, the general Krein duality applies; it strong properties [9], [53], [65], [120], [129]. The isometry
permutes the Hahn and dual Hahn polynomials. group of acts transitively on and hence there exists

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2483

a unique normalized invariant measure and Note that the definition and all properties of distance-
for any measurable and If transitive spaces are also correct for finite metric spaces, and
is the diameter of , then for any (real) any finite distance-transitive metric space is an -class
and (cf. (2)) symmetric association scheme with
depends only on and For any invariant function and equal to the number of nonzero values of
on (this means that for In particular, the Hamming and Jonhson spaces are distance-
any ) there exists a function on such that transitive. The fact that in the case of finite spaces
Continuous invariant functions (compare (10) with (27)) is explained by the
on form a commutative algebra with respect to the distinctness between the product and convolution of matrices.
operations of addition and convolution
III. CODES AND DESIGNS
In coding theory and related subjects, an association scheme
In the linear space of continuous functions on with (such as the Hamming scheme) should mainly be viewed as
the inner product a “structured space” in which the objects of interest (such as
codes, or designs) are living.
(26) Let be a nonempty subset of the point set of an
association scheme Then will be called a code
(cf. (9)), the unitary representation of defined as in (In certain contexts, is preferably called a
follows: , decomposes into a countable design.) We now introduce the important concept of the inner
direct sum of pairwise inequivalent irreducible representations distribution of a code.
acting on (mutually orthogonal) subspaces
of continuous functions. Each subspace has a A. Inner Distribution
finite dimension consists of constants and Definition 4: The inner distribution of a code in an -
and is invariant (i.e., if , then for any class association scheme is the rational -tuple
). The invariant functions (cf. (10)) where counts the pairs of points in
that belong to the relation Formally
(27)
for (29)
where is an arbitrary orthonormal
(with respect to (26)) basis of , form a basis of consisting A code in the Hamming scheme is nothing but a
of irreducible idempotents, which are mutually orthogonal -ary code of length The inner distribution of is its
(Hamming) distance distribution. In effect, counts the
pairs of codewords with
Coding theorists are often interested in a code having a
The corresponding “ -functions” on such that
specified set of admissible distances (in particular: a specified
are real and satisfy the following minimum distance). In the general framework of association
orthogonality and normalization conditions:
schemes, this notion extends as follows.
(28) Definition 5: Let be a subset of A code in
is called a -code if all pairs of distinct points in belong
where is the measure on such that to the admissible relation In terms of the inner
(this does not depend on ). For any distribution, this becomes for each
element of , the series Consider, for a while, the familiar situation where is a
linear code of length over the field (in the Hamming
scheme). Then the distance distribution of reduces to its
weight distribution: counts the codewords with
From the linear code we can define its
with orthogonal code (often called the dual code), that is,
for all

converges to on Moreover, for these functions The weight distributions of and are related by the
an analog of Theorem 2 is valid and MacWilliams identities [86], [87]. These are well-defined linear
the linearization factors are nonnegative. All (infinite) relations involving the Krawtchouk polynomials (16). (We
compact distance transitive spaces have been classified in shall go back to this subject in Section V.)
[130] as the unit Euclidean spheres , the projective spaces As a result, the “Krawtchouk–MacWilliams transform” of
in dimensions over and quaternions the distance (or weight) distribution of a linear code
and the Cayley projective plane. yields nonnegative real numbers, which can be interpreted as

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2484 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

the components of the distance distribution of the Example 2 (continued): In , an -design is a

orthogonal code It turns out that this nonnegativity result combinatorial -design (see [37]). This is a collection of
can be extended to arbitrary codes (in a Hamming scheme), blocks of size , out of a point set of size , such that all
even though the orthogonal code notion is lost. Moreover, as -subsets of the -set are contained in the same number of
shown below, the result extends to codes in any association blocks [15], [62]. There is a close connection between coding
scheme. theory and design theory [3], [5]. It is interesting to point
out that a three-parameter class of Hahn polynomials (larger
Definition 6: Let denote the -numbers of an -class
than the “spherical class” involved in the -numbers) plays a
association scheme (with ). The -transform of a
significant role in the theory of combinatorial -designs [133],
complex -tuple is the complex -tuple
[134] and in an extension thereof [28].
given by
B. The Linear Programming Method
for (30) Theorem 3 strongly suggests using linear programming
to find bounds on the size of a code characterized by
some linear constraints on its inner distribution In
Note that this definition of the -transform in fact depends
particular, this method leads to upper bounds for -codes and
on the choice of an ordering of the functions (or the matrices
to lower bounds for -designs. We shall use the “nonstandard
), From Theorem 1 and (15) it follows that
forms” of the linear programming problem. For simplicity
we assume, in this subsection, that is a symmetric
(31) association scheme, which implies that the - and -numbers
are real. For the problems that we are considering here, this
entails no loss of generality. While simultaneously considering
Moreover (see (14)), for any -functions and -functions it is convenient to use the letter
instead of either or , and use for the other one. For any
(32) with the expansion we put
if
(33) For any , we say that has the property
if

Theorem 3 (Generalized MacWilliams Inequalities [37]): for

Let be the inner distribution of a code in , for
and let be its -transform. Then (i.e., and has the property if
) for each
The proof is quite easy since, in view of (13) and (10), for
for
Let

(34)
where the minimum is taken over all functions
This also shows that is an averaging parameter of with the property and
a code In this connection note that for all

The -transform of the inner distribution of a code will where the maximum is taken over all functions
sometimes be referred to as the “dual (inner) distribution” of with the property It should be noted that both
extremum problems are linear programming problems, because
Definition 7: Let be a subset of A code in without loss of generality one can assume that and
is called a -design if the -transform of its inner distribution then
satisfies for each
Example 1 (continued): In , an -design is an
orthogonal array of strength (see [37] and [40]). This means
that the restriction of to any set of coordinates shows all The following two results are obtained, respectively, with
-tuples of alphabet symbols appearing the same number of the help of (32) and (33) with and One
times [98]. Orthogonal arrays are closely related to “resilient also makes use of
functions” and to “correlation-immune functions” which occur (by Theorem 3), if
in some cryptography applications [16], [33], [79], [113], when is a -code, and if
[122]. when is a -design.

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2485

Theorem 4 [37]: If is a -code and has the Theorem 6 [80]: For any symmetric association scheme
property , then and any
(35)
If is a -design and has the property , C. Outer Distribution and Fundamental Parameters of Codes
then
The inner distribution of a code is concerned with the
(36) mutual relations or “distances” between the code points which
are values of the function We shall omit the quotes
In each case, equality holds if and only if when, for a symmetric association scheme
satisfies the triangle inequality and hence is a distance function.
Let denote the set of distinct values of the function
Theorem 5 [37]: If is a -code and has when Note that
the property , then
(37)
and define
If is a -design and has the property ,
then
For simplicity, we shall consider codes in an -class
(38) association scheme , such that Then
In each case, equality holds if and only if we can state that both and are not empty. Define
the following fundamental parameters of a code [36]:
• the minimum “distance” ;
The necessary and sufficient conditions for these bounds to • the (minimum) dual “distance” ;
be sharp have many useful consequences, a nice example being • the degree ;
the (generalized) Lloyd condition for perfect codes [17], [37], • the dual degree .
[70], [84], [101], [117]. Note that Theorems 4 and 5 imply that Together with we will also consider
the functions for which or • the (maximum) strength
holds are optimal solutions of the corresponding extremum Moreover, we consider two auxiliary parameters
problems.
if
Coding theorists are especially interested in applying The-
otherwise,
orems 4 and 5 to the class of codes with a specified minimum
distance , which are -codes in and It was shown and
in [35] that the classical “elementary bounds” such as the if
Hamming, Plotkin, and Singleton bounds occur as simple otherwise.
cases of these theorems. In the next section we give bounds For given integers and (with and
which are obtained with the help of optimal solutions of some ), a code is called a -code if and a -design
extremum problems for systems of orthogonal polynomials. if These notions are special cases of a -code and
Combinatorial proofs of some of these bounds are unknown. a -design, respectively, for and The
It should be noted that the bounds of Theorems 4 and 5 can examples of -designs in the Hamming and Johnson schemes
be improved by the same linear programming method if one are examined in Section III-A above. The given definitions
knows an additional information about and clearly show the dual character of the notions of -codes and
(not only their nonnegativity). It was successfully used in -designs. Let denote the maximum size of a
the analysis of concrete codes (see [14], [27], and [88]). -code in and let denote the minimum size
In conclusion of this subsection we verify that there exists a of a -design in A -code in is called
duality in bounding the sizes of -codes and -designs [78], maximal if and a -design in
[80]. For any and (which is again either or is called minimal if
), we define an -dual function to as follows: Now we introduce a definition that involves the relations
(“distances”) between the code and the whole ambient
(39) set
Definition 8: The outer distribution of a code in an -
Using Theorem 1 and (15) one can show that class association scheme is the matrix
and hence , whose entry equals
and has the property or if and only if
has, respectively, the property or In particular,
this implies the equivalence of the bounds (35) and (37) and Some fundamental properties of a code are defined in
also (36) and (38). terms of the rows of its

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2486 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

outer distribution A code is called distance-invariant if IV. POLYNOMIAL SCHEMES

for any and completely distance-
regular if for any such that A. Orthogonal Polynomials
where
In the examples of the Hamming and Johnson schemes (and
in several other interesting cases), the -numbers and the
-numbers are representable by polynomials of degree
and , respectively, in an “appropriate variable” (see Section
When is a linear code over (in the Hamming scheme), II-B). This leads us to investigate the class of association
the rows of the outer distribution are the weight schemes that enjoy either of these “polynomial properties”
distributions of the coset codes (or both of them).
It is easily seen that can be expressed linearly
Definition 9:
in terms of the inner distribution of Let us give the
i) A symmetric -class association scheme is -
“ -transform version” of this expression. Consider the -
polynomial, with respect to a function , if
transform of each row of the outer distribution This
there exist real polynomials of degree
produces the matrix , with
such that for any
Theorem 7 [37]: The -transform of the outer distri- ii) A symmetric -class association scheme is -
bution is related to the -transform of the inner polynomial, with respect to a function , if there
distribution by exist real polynomials of degree
such that for any
It can be proved that these functions and must be
linear functions of the first - and -functions and
As an immediate consequence, the rank of is equal to (respectively), which take different values and
Furthermore, we obtain for different such that and
We will use the following functions
and :

whence for any This can also

be deduced from (34) as follows: If then (41)

Then and
When the function or is decreasing on we will
extend it to a continuous decreasing function on (usually
(40) the latter is defined by the same formula). In this case,
the corresponding function given by (41) is a decreasing
continuous mapping from onto and it is called
Some interesting problems in classical coding theory are standard.
concerned with the covering radius of a code (in the It follows directly from Theorem 1 and (15) that
Hamming scheme) (see [6], [31], [34], and [64]). By definition, and are systems
of orthogonal polynomials with the following orthogonality
conditions:

(42)
where

(43)

(Thus for a linear code, is the maximum weight of coset and the properties:
leaders.) This definition is extended to any association scheme
if one replaces by The covering (44)
radius can be found from the outer distribution of ,
since is the smallest such that These orthogonal systems and are uniquely determined
Notice that generally cannot be determined from by three-term recurrence relations [49] of the form
the inner (distance) distribution of ; however, some upper
bounds on can be obtained from these data [37], [51],
[118], [127]. (See also Sections IV-C and IV-D below.)

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2487

where determined from only five independent numbers [72]. The

same author [71] has shown that the polynomials and
relative to - and -polynomial schemes belong to
a well-defined five-parameter class of orthogonal polynomi-
Definition 9 depends on the ordering of the relations and als of the generalized hypergeometric type [114], known
of the idempotents , respectively. For this reason, a given as the Askey–Wilson polynomials [2]. His result produces
association scheme may possess more than one -polynomial closed-form expressions for the -numbers and the -numbers.
structure and more than one -polynomial structure (see [10]). Furthermore, it characterizes the Askey–Wilson polynomials
The algebraic notion of a -polynomial scheme is equiv- as those orthogonal polynomials having “duals.”
alent [37] to the combinatorial notion of a distance-regular For a code in a -polynomial scheme, a polynomial is
graph, defined as follows. Let be a simple connected called an annihilator for if for all
finite graph of diameter For , define as the An annihilator of minimal degree (i.e., degree ) is
set of pairs such that and are at distance called minimal and denoted by if
apart in , and let If is For a code in a -polynomial scheme, a polynomial
an association scheme, then is said to be distance- is called a dual annihilator for if for all
regular [26]. Thus if is a -polynomial scheme, then A dual annihilator of minimal degree (i.e.,
(see (1)) is a distance function. Note that a symmetric degree ) is called dual minimal and denoted by
association scheme with a distance function need if In particular, if for and
not be -polynomial. (An example is provided by the “ordered or
Hamming scheme” [89].) On the other hand, the algebraic
notion of a -polynomial scheme has no simple combinatorial (45)
interpretation, except in some important special cases where
can be embedded in a certain “lattice-type structure”
then and For any nonempty
[38], [39], [94]. Nevertheless, there exist some useful general
and any denote by the polynomial of degree
characterizations of -polynomial schemes [54], [126]. There
uniquely defined by the conditions:
is an elementary criterion for the -polynomial property in
for any Any function on can be represented
terms of the intersection numbers, namely, and
by the interpolation polynomial of degree
for This characterizes the “distance In particular, for any we have
structure” in a clear manner. Similarly, a criterion for the
-polynomial property is and for
Example 1 (continued): For the Hamming scheme ,
(17) holds and In the case of a -polynomial association scheme
(where is either or ), we can rephrase the linear
programming bounds of Theorems 4 and 5 in terms of ex-
Hence, is - and -polynomial with respect to the tremum problems for the system of orthogonal polynomials.
standard function , systems and coincide Denote by the set of real polynomials of degree at
and consist of the polynomials most in For any , let be the
coefficients of the (unique) expansion of over the system
, i.e., Put if
Example 2 (continued): For the Johnson scheme (17) Note that gives a one-to-one
holds and mapping of onto with and
for any (see (14) and Definition 9). We
restrict our attention to the case of -codes and -designs
(i.e., codes with dual “distance” or more), which corresponds
Hence, is -polynomial with respect to the standard
to the case of -codes and -designs for We
function
say that has the property if
has the property (respectively,
). Let where the minimum is
and -polynomial with respect to the standard function taken over all polynomials with the property
Systems and are defined by means Similarly, let where the maximum
of and is taken over all polynomials with the property
Since for , we have
(46)
The number of independent parameters of an -class -
polynomial or -polynomial scheme is equal to and we can use Theorems 4–6 to estimate the size of -codes
In contrast with this observation, Leonard has proved that and -designs with the help of the above extremum
all parameters of a - and -polynomial scheme can be problems for the system

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2488 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

Without going into any detail, let us finally point out that (The system consists of polynomials since
the classical examples of - and -polynomial schemes are weights become zero.) We put
induced by some classical permutation groups (see Section II-
D). Extensive research work has been devoted, in this context,
to the subject of “orthogonal polynomials and permutation Let be the largest zero of the polynomial If
groups” [48], [119]. is standard we can uniquely define the numbers by
We will omit the indices in the
B. Adjacent Systems of Orthogonal Polynomials notations when
and Two Extremum Problems
Example 1 (continued): Let be the Krawtchouk
Some important estimates on fundamental parameters of
polynomial of degree defined by (16) and let be its
codes are expressed in terms of values connected with systems
smallest zero. For the Hamming scheme
of orthogonal polynomials which are adjacent to the systems
and Consider two functions and on We assume
that the first function (change of variable) takes the values
and maps into the interval , where
and the second (weight) function has the properties
and We call the change of variable standard
if it can be represented as a continuous decreasing function
on the whole interval It is known [49], [121] that the and , and hence
orthogonality conditions
(50)
(47) In particular,

uniquely define a system of polynomials

of degree with some positive values We denote
by and the functions and for the system In Example 2 (continued): Let and be the
particular, for the systems and we have (see (42) and (43)) polynomials of degree defined, respectively, by (18) and
(19), and let and be their smallest zeros. For
We assume that satisfies the Krein condition: for any the Johnson scheme
there exist nonnegative real numbers such
that
and is proportional to Hence

By (23) and (24) this is fulfilled for the systems and For
the system and any we define the kernel function and

Now we consider two extremum problems for the system

of orthogonal polynomials under consideration. For any
For any we consider a weight function on , the -problem consists in finding
such that

(48)
where the maximum is taken over all polynomials
where the constant is chosen so that such that and for A
polynomial having these properties for which
is called an optimal solution of the
-problem. These properties are in general stronger than
since they include nonnegativity of on the whole
The initial change of variable and the new weight function interval (not only at points and
uniquely define a system a restriction on its degree. This implies that for any -
of polynomials of degree by means of the following polynomial ( is either or ) association scheme
conditions:
(51)
(49) From now on we assume that and denote arbitrary
numbers such that and

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2489

Theorem 8 [103]: For any the where the minimum is taken over all polynomials
polynomial such that and for A
polynomial having these properties for which
is called an optimal solution of the
of degree is the unique (up to a constant factor) optimal -problem. Note that for these properties as
solution of the -problem and compared to say nothing about nonnegativity of
for , include a stronger condition than
for , and introduce a restriction to the degree
of the polynomials. Note that this restriction means that,
in the -problem, polynomials whose degree does not
One can show that is a positive-valued increasing exceed the number of the half-open interval containing
function in and admits another expression are considered. This also holds in the case of the -
problem since is partitioned into the half-open intervals
, and is the number of the half-open
interval containing

For odd and the polynomials Theorem 9 [77], [81]: For any real number
let and Then the polynomial
(55)
of degree is an optimal solution of the
were first used in 1973 in [37] to obtain a lower bound on the -problem. The function is equal to
size of -designs (see Theorem 19 below). In the general
case Theorem 8 was applied to this end in [47].
Example 1 (continued): For the Hamming scheme and
positive-valued and continuous, grows with , and takes the
following values at the left ends of these half-open intervals:
(52)
(56)

Example 2 (continued): For the Johnson scheme and We give some additional facts on the polynomials
For the polynomial is the unique (up to a
constant factor) optimal solution of the -problem. For
(53) we have and the polynomial
has factor For we have
and is also divisible by In both
(54) cases the polynomial is an optimal
polynomial for the -problem as well. Moreover, for
Now we formulate the second extremum problem for the the polynomial is proportional
system with a standard function It is known [103] that to the optimal solution of the -
the largest zeros of the polynomials satisfy problem. These facts and Theorems 8 and 9 follow from the
the following inequalities: following main theorem which (as we shall see below) also
determines the inner distribution of optimal codes and designs.
Theorem 10 [77], [81]: For any the
where it is assumed that and polynomial
This means that the half-open interval
is partitioned into the half-open intervals and (57)
Enumerate in succession all with and has simple zeros
these half-open intervals from the left to the right by positive
integers. For any real number denote by
the number of the (unique) half-open interval containing
where and with equality holding if and
Let when or
only if or and Moreover, for any
and let if and if
polynomial of degree at most the
Then it is clear that following equality holds:
For any number , the -problem
consists in finding (58)

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2490 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

where for Example 2 (continued): In the case of the Johnson scheme

, when belongs to the half-open intervals

are positive, and in the case

the function for , respectively,

with equality holding if and only if (here is omitted equals the expression given at the bottom of this page. This
in the notation ). is obtained with the help of the optimal polynomial
Example 1 (continued): In the case of the Hamming for the -problem of the first, second, and third degree
scheme for any there exist and (see [76]).
such that In order to prove that for the optimal polynomial
for the -problem has the property and
hence the inequality holds, one must
check that all coefficients of its expansion over system
are nonnegative. Note that in the case by Theorem 2
Then for can be
the latter means that the symmetric matrix
expressed by the following formula:
for -polynomial association scheme is nonnegative
definite. Now it is known [77], [81] that all coefficients
are positive when (or
has odd degree ), in particular, for ,
and also when Moreover, the same is
where In particular, when the number belongs true for all if the system satisfies the strengthened
to the half-open intervals Krein condition: for any the coefficients of
the expansion of over
the system are positive. It is known that the system
satisfies the strengthened Krein condition for decomposable -
polynomial schemes [77]. The class of decomposable schemes
contains some known infinite families of - and -polynomial
association schemes, in particular, and It seems to
be true that all coefficients are also
positive when belongs to the open interval
this, respectively, gives the values Unfortunately, this question is still open for Thus
for any system under consideration

(59)

if (see (56)), and for any

(60)

if satisfies the strengthened Krein condition.

The known earlier bounds for a -code can be described
which are obtained with the help of the optimal polynomials in terms of polynomials which have the -property
of the first, second, and third degree. for

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2491

for and hence imply 3) If , then is distance-invariant and

In particular, the bounds due to Blichfeldt [19], Rankin [97],
Plotkin and Johnson (see [88]) are in fact based on the
polynomial with which for any and
provides The Sidelnikov results [110], 4) If is standard and , then
[111] are obtained with the help of polynomials
for a suitable choice of an integer In [90] (and
later in [65] for the Euclidean sphere) the polynomials with equality if and only if and
(61) is dual-minimal for
A simple proof of Theorem 11 is based on the fact that for
were used, where the integer is defined by any , (33) with and
The polynomials (55) were found with the help of gives
the Lagrange method and presented in [73]. Some extremum
properties of these polynomials were found in [112] and they
were essentially used to prove the optimality of (55) for the
-problem (see Theorems 10 and 9).
The solutions of the - and -problems can also (63)
be applied to codes and designs in the Cartesian product of
copies of a -polynomial association scheme with
Therefore, if is a dual annihilator for such that
the distance or on
and , then The polynomials
In particular, for the case of the distance
on , this allows one to estimate the Shannon capacity [106]
of a graph (see [85], [91], and
[104], and also [79]).
In the remainder of this section, considering a code in an
-class - and/or -polynomial scheme we shall assume for (see (45)) have these properties and give rise to the first and
simplicity that second statements. The third statement is obtained if one uses
the polynomial of degree in (63) and
C. Codes and Designs in -Polynomial Schemes takes (31) into account. To prove the last statement note that
Throughout this subsection, we consider an -class - the left-hand side of (63) equals zero for
polynomial scheme In this case (see (1)) is
a distance function and can be considered as a metric
since (see (48) and (49) for ) and
space with the metric It follows that
for any code the metric spheres (balls) Moreover, by the second statement
and if
We can apply similar arguments to the rows of the outer
distribution which has rank by Theorem 7.
of radius centered at the code points do not intersect
Considering in (33) and
when is equal to the packing radius
with a dual annihilator for we find that
and cover when is equal to the covering radius
This gives the following sphere-packing and sphere-covering
(64)
bounds for any code in :

In particular, for the dual minimal polynomial we

(62) have

Thus we have A code for which

is called perfect. A code is perfect if and only if
or, equivalently, the spheres
and for any integer and
form a partition of
From the existence of polynomials which are dual annihila-
tors for codes we can derive some inequalities between their
we have
fundamental parameters.
Theorem 11: For any code in an -class -polynomial
scheme
1) with Since in both cases depends only on
2) equality implies , this allows one to compute the outer distribution of a
where code from a “small set of data.”

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2492 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

Theorem 12 [37]: Each column of the outer distribution Theorem 14 [80], [81]: Let be a code in a -polynomial
of is a linear combination of the all- scheme with the standard function If ,
one vector and the first columns the then
coefficients of which are determined by the inner distribution.
Thus the first entries of any row (67)
of the outer distribution of a code are not all equal to zero with equality if and only if and
and they uniquely determine the remaining entries of the row. is a dual minimal polynomial for where
This has some interesting consequences presented in [37]. In and
particular Thus the bounds (66) and (67) can be attained only simulta-
neously and in this case is a maximal -code for
and a minimal -design for Note that (65) gives
a lower bound on the size of a code with a given number of
and, hence, for any dual “distances.” Probably a stronger inequality
(68)
(65)
holds which (together with (66)) would imply statement 2)
of Theorem 11. Then all bounds (66)–(68) can be attained
Moreover, if , then the first entries only simultaneously. In any case, this is true for perfect codes
of any row are all zero except for (odd ). The inequality (68) was proved for the Hamming
when For , the entry scheme in [78] but it is an open problem in the general case.
is uniquely determined from (64). In particular, this gives The following statement extends Theorem 14 from the case
when (see (56)) to the general case under the
(see Example 1 below). Therefore, is completely regular if additional restriction that satisfies the strengthened Krein
condition. Therefore, we do not repeat the necessary and
Note that from (33) it also follows that for any sufficient conditions for this special case.
there exists such that
Theorem 15 [80], [81]: Let be a -polynomial scheme
with standard and assume that satisfies the strengthened
Krein condition. Then for any code
(69)
This fact was used in [69], [83], and [118] for obtaining with equality in the case if and only if
asymptotic upper bounds for the covering radius of linear and the polynomial (57) with
codes when the dual distance grows linearly is dual minimal for where
with This approach is based on the inequalities
Note that codes for which the bounds of Theorems
13–15 are attained belong to the class of codes satisfying
(cf. statement 2) of Theorem 11).
which are satisfied by all linear codes ; it makes use There exists the following characterization of codes in this
of the Chebyshev polynomials, characterized by the fact that class.
they exhibit the smallest deviation from zero.
We now give the linear programming bounds which follow Theorem 16 [77]: Let be a code in a -polynomial
from solutions of the above extremum problems for the system scheme with the standard function such that
(see (46), (51), (59), and (60)).
and hence
Theorem 13: Let be any code in a -polynomial scheme Then if and only if
Then and
is dual minimal for and if and only if
(66) and the
polynomial (57) with is dual minimal for
with equality if and only if and Note that for the class of codes in a -polynomial scheme
is a dual minimal polynomial for where defined by the condition the
and only parameter (or ) uniquely determines all funda-
In particular, for odd Theorem 13 gives the mental parameters, the inner distribution, its -transform (or
sphere-packing bound (left-hand side of (62)) and implies that “dual distribution”), and the outer distribution of the code
is dual minimal for any perfect code Indeed, by Theorem 16 we know the dual minimal polynomial
The latter is the (generalized) Lloyd theorem for perfect codes and hence the set of integers
[17], [37]. which are dual distances, From Theorem

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2493

10 and statement 3) of Theorem 11 it follows (by use of the Example 2 (continued): Apply (66) and (67) to a code
polynomial in (58)) that for any code in the in the Johnson scheme for which or
class Since and

(70)

where The inner

distribution of and, in particular, the parameters
can be found with the help of (31). Moreover, all codes (see (53)), we have or , respectively.
in this class are distance-invariant and completely distance- Consider a code for which either of these bounds is
regular. This allows us to compute the outer distribution of attained. It must have the following properties:
with the help of (64) as was explained above. Note that from and
Theorem 16 it follows that the condition on a dual minimal
polynomial in Theorems 13–15 is a consequence of the first
condition and can be omitted.
Example 1 (continued): Apply these results to a code in
the Hamming scheme for which or
Because
Since

and
Using statement 3) of Theorem 11 and
(31) we can find that
and
(see (50) and (52)), we have or , Again in this case is completely distance-
respectively, by (66) and (67). Consider a code for which regular, since , and one can compute the
either of these bounds is attained. Any such is a maximal outer distribution of the code In fact, a code having
-code and a minimal -design, and must have the following the above properties exists and is unique; it is the “octade
properties: and code” formed by all vectors of Hamming weight in the
extended Golay code (see [88]).
More sophisticated applications can be found in [6], [36],
[37], and [76].

D. Codes and Designs in -Polynomial Schemes

Let us consider codes in an -class -polynomial scheme
Using (32) with where are some
Since annihilators for a code one can obtain the following dual
Using statement 3) of Theorem 11 (or (70)) and (31) we analog of Theorem 11.
can find that
Theorem 17: For any code in an -class -polynomial
and
scheme
for all (This means that must be formally self-
dual.) Finally, and hence is completely 1)
distance-regular. By use of the method explained above, we 2) equality implies
can mechanically compute the outer distribution of the code where
The following table gives the entries for ,
and for all
dist 3) If , then is distance-invariant and

for any and

4) If is standard and , then

In fact, a code having the above properties exists and is (71)

unique (within equivalence); it is the extended binary Golay
code (see [88]). Thus our table gives the with equality if and only if and
weight distribution of all cosets of is minimal for

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2494 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

Many results concerning codes in -polynomial schemes Let be the set consisting of the nonempty
are based on the existence of the representation relations (those with ). Then
is called the restriction of to It can be shown
(72) that if then is an -
class -polynomial scheme [37]. This theorem is a kind of
“dual” of the result mentioned in Section IV-C about com-
(see (10) and (13)). In particular, let us emphasize the follow- pletely distance-regular codes. The intersection numbers of
ing important “dual” analog of (65). this scheme can be computed with the help of the polynomials
Theorem 18 (The Absolute Bound [37]): For any code in and
a -polynomial scheme Next, we give linear programming bounds which follow
from solutions of the above extremum problems for the system
(see (46), (51), (59), and (60)). Recall that the repre-
(73)
sentation (72) was used to prove that for the decomposable
-polynomial schemes (in particular, for the Hamming and
The proof of Theorem 18 is based on the fact that the Johnson schemes) the system satisfies the strengthened
functions belong to the space Krein condition [77].
generated by the functions
Theorem 19 [37], [47]: For any code in a -polynomial
equal to when and hence are linearly independent
scheme
functions in
In fact, the fundamental parameters of a code are (75)
determined from the sequence and
its -transform (see Section III-C). Analogously, for any with equality if and only if and
, we can consider the sequence is a minimal polynomial for where
and define the corresponding parameters; in particular, and
Note that, by (40), The well-known Rao bound [98] for -designs (or-
for any , and, similarly to statement 2) of thogonal arrays) in the Hamming scheme and the Ray-
Theorem 17, for any Chaudhuri–Wilson bound [99] for -designs (block designs) in
Therefore, if we assume that and , the Johnson scheme are special cases of (75) for these schemes
then For the polynomial (see (52) and (54)). A design which satisfies equality in (75)
is called a tight -design where The subject of
tight -designs in the Johnson scheme has been introduced by
Ray-Chaudhuri and Wilson [99] and has been investigated by
of degree we have (see (48) and (49) for
several authors (see especially [7], [134], and the references
), and the use of and
therein). In particular, the polynomial is
in (32) shows that
minimal for any tight -design. This is (a generalized version
of) the Ray-Chaudhuri–Wilson theorem for tight designs [99];
it is a “dual” of the Lloyd theorem for perfect codes [37],
[101].
under our assumption. If is standard, then
Theorem 20 [73], [77]: Let be a code in a -polynomial
if with equality in at most points
scheme with the standard function If
while
then
(76)
This implies that for any code in a -polynomial scheme
with standard such that with equality if and only if and
is a minimal polynomial for where
(74) and
Analogously, the bounds (75) and (76) can be attained only
with equality if and only if there exists a point such simultaneously and in this case is a minimal -design for
that is a polynomial of minimal degree which and a maximal -code for Note that
equals zero at for each the absolute bound (73) gives an upper bound on the size of a
The inequality (74) for the Hamming scheme is due to code with a given number of “distances.” Probably a stronger
Tietäväinen [127]. For the general case it was given together inequality
with the necessary and sufficient condition for its attain-
ability in [51]. Note that (71) and (74) give the following (77)
upper bounds on the minimum distance and covering radius
of a -design : holds which (together with (75)) would imply statement 2) of
Theorem 17. Then all bounds (75)–(77) can be attained only
simultaneously. In any case, this is true for tight -designs with

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2495

even (odd ). The inequality (77) was proved in [77] for distance-invariant and form -class -polynomial schemes
all decomposable -polynomial schemes (in particular, for the whose intersection numbers are determined with the help of
Hamming and Johnson schemes), but it is an open problem in the polynomials and (see [37, Theorem 5.25]
the general case. or [81, Theorem 3.21]). Note that from Theorem 22 it follows
The following statement extends Theorem 20 from the case that the condition on a minimal polynomial in Theorems 19–21
(see (56)) to the general case under the is a consequence of the first condition and can be omitted.
additional restriction that satisfies the strengthened Krein
condition. Therefore, we do not repeat the necessary and E. Bounds for Spherical Codes and Designs
sufficient conditions for this special case.
The results of Section IV-D are applicable to infinite
Theorem 21 [73], [77]: Let be a -polynomial distance-transitive spaces (see Section II-D). The unit sphere
scheme with standard and assume that satisfies the
strengthened Krein condition. Then for any code in
(78)
is a distance-transitive space with the Euclidean distance
with equality in the case if and only
if and the polynomial (57) with
is minimal for where

For the Hamming and Johnson schemes the bound (78)

in the first interval when coincides and the isometry group consisting of all orthogonal
with the well-known Plotkin and Johnson bounds, respectively matrices of order Any finite set (called a
(see [88] and the calculation of in Section IV-B). spherical code) is characterized by the finite set of
For , (78) improves upon these bounds. (We distinct nonzero values of when It allows
remind that (78) is true in the second interval and in all us to define for any spherical code the minimum distance
odd intervals without the restriction of the strengthened Krein and the degree , and also
condition.) the parameter which equals if the diameter of
Note that codes for which the bounds of Theorems belongs to , and equals zero otherwise. We can also
19–21 are attained belong to the class of codes satisfying measure the distance between by the angle
(cf. statement 2) of Theorem 17) and where
forming -class -polynomial schemes. There exists the
following characterization of codes in this class.
Theorem 22 [77]: Let be a code in a -polynomial
scheme with the standard function such that and denote by the minimum angular distance between
distinct points of It is clear that
and hence The normalized invariant measure on is the normalized
surface area of Let be the surface area of

Then if and only if

and and let be the surface area of It
is a minimal polynomial for ; and if and only is well known that and
if and the
polynomial (57) with is minimal for
For the class of codes in a -polynomial scheme
defined by the condition , the only (79)
parameter (or ) uniquely determines all fundamental
parameters, the inner and dual distributions of the code , where and is the gamma
and also the intersection numbers of the -polynomial scheme function. The inner and outer distributions of a spherical code
formed by Indeed, by Theorem 22 we know the minimal are given by the values
polynomial and hence the set
of integers which are “distances,” From
Theorem 10 and statement 3) of Theorem 17 it follows (by
use of the polynomial in (58)) that for any code and, for any
in the class

Note that and , considered as functions of

where The dual , differ from zero only at a finite set of points
distribution of is computed by (30). Codes in the class are For any function which has this property (in particular, for

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2496 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

and ) we can define its -transform as the Theorem 23 (The DGS Bound [45]): For a code
infinite sequence where let Then

(82)

As in the case of association schemes we can define (see

Section III-C) the set , the dual distance of with equality if and only if
and its strength Spherical -designs Note that if is the largest zero of and is
(i.e., ) were introduced in [45], in connection with an the largest zero of , then
approximation formula for the evaluation of multidimensional and that satisfies the strengthened Krein condition.
integrals over of the following form:
Theorem 24 [73], [74]: For a code , let
(80) and Then
does not exceed

The code is a -design if and only if the approx-

imation formula (80) becomes equality for all functions (83)
which are polynomials in coordinates of
of degree at most Thus is the
minimum number of nodes in the approximation formula under and, in particular, if , then
consideration.
Now we verify that is “ -polynomial” with respect (84)
to the standard change of variable (this
means that is a decreasing continuous function such that
). Indeed, from (28) and (79) it follows The bound (83) is attained if and only if
that the orthogonality and normalization conditions

The class of spherical codes for which the bounds of

(81) Theorems 23 and 24 are attained is described by Theorem 22;
uniquely define polynomials of degree such that these codes carry -polynomial subschemes. Many examples
and hence can be found in [45], [74], and [77]. In particular, the tight -
design in containing 240 points and the tight -design in
containing 196 560 points are the maximal codes with the
In the case of the subspace consists of all homoge- angular distance 60 ; they allow one to determine the kissing
neous harmonic polynomials in of numbers in dimensions and [74], [96].
degree and has the dimension The following asymptotic bound follows from (84). How-
ever, it was obtained earlier with the help of the MRRW
polynomials (61).

Thus Theorem 25 (The KL Bound [65]): For any fixed

and

where

It should be noted that Theorems 23 and 24 give the best

linear programming bounds in the class of polynomials of
are the Jacobi polynomials normalized by restricted degree. The necessary and sufficient conditions for
(The Jacobi polynomials with are called optimality of for the -problem without this
the Gegenbauer polynomials.) All results of Section IV-D are restriction were found in [24] and [25], together with an
valid for spherical codes except for statement 1) of Theorem 17 improvement of (83) in some range when these conditions
whose proof uses the finiteness of association schemes. (The are not fulfilled. On the other hand, in [135] there was found
absolute bound for was proved in [45] in the strong form a continuous function having the properties for
(77).) In particular, the - and -problems and their and ; this yields
solutions are valid for countable systems (compare (47) with an improvement of the DGS bound (82) for -designs if is
(81)) and give rise to the following two results. sufficiency large.

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2497

Theorem 26 [135]: For any spherical design (see (42)–(44)) one can check that the -dual of is the
polynomial and hence
(85) has the properties and This shows that

In a certain sense, the sphere-packing bound

and the bound (85) are analogs of the bounds (62) and (69) and implies the first pair of universal bounds [81]
for -polynomial schemes.
The projective spaces in dimensions over and
quaternions also are -polynomial; the Each of these bounds is attained if and only if
corresponding systems are systems of Jacobi polynomials In this case, is an annihilator and is
and satisfy the strengthened Krein condition. Elements of these a dual annihilator for
spaces can be considered as lines going through the origin. The For the Hamming scheme and the Johnson scheme ,
results of Section IV-D are applicable to codes and designs in the first pair of universal bounds takes the following forms:
the projective spaces which were studied earlier in [44], [60],
[65], and [77]. The bounds for codes in the projective spaces (87)
have been successfully used to estimate “crosscorrelation” of
codes [65], [75], [76], [109].
(88)
F. Universal Bounds for Codes and Designs in - and
-Polynomial Schemes—Asymptotic Results
respectively. These bounds for codes are called the Singleton
In this subsection we consider a code in an -class -
and Johnson bounds [88], and codes satisfying equality in (87)
and -polynomial scheme and tacitly suppose that the
or (88) are called MDS-codes and Steiner systems, respectively
functions and are standard. Of course, all results of
[88], [15]. In particular, (87) is attained for the Reed–Solomon
Sections IV-C and IV-D are applicable. We give three pairs of
codes and (88) is attained for the “octade” code (together with
universal bounds for codes and designs in such schemes. The
the four other bounds (66), (67), (75), and (76)).
term “universal” reflects the fact that these bounds are valid
From the results of Sections IV-C and IV-D we deduce the
for all codes in all schemes under consideration.
second pair of universal bounds [37]
First, for a - and -polynomial association scheme we
extend the duality in bounding the optimal sizes of -codes
(89)
and -designs to the polynomial case. For any
and (we use for either or , and use for the other
one), we define an -dual polynomial to as follows: with equality in the left- and right-hand side if and only if
and ,
respectively.
Finally, if the systems and satisfy the strengthened
Krein condition, the results of Sections IV-C and IV-D imply
(cf. (39)). Analogously, using (42)–(44) one can show that the third pair of universal bounds [78], [81]

(90)

and hence with equality (when and ) in the left- and

right-hand side if and only if and
, respectively.
The characterization of the codes for which the bounds in
and has the property or if and only if
(89) and (90) are attained is given by Theorems 16 and 22. A
has the property or , respectively. In particular,
list of the known codes in the Hamming and Johnson schemes
for any the following equalities hold [80]:
for which (90) is attained can be found in [77] and [78].
(86) For finding asymptotic results the following special cases
of bounds (89) and (90) are useful:
As an example, consider the polynomial defined by
(45) and note that for according to if
the assumption that is standard. Using the orthogonality
(91)
condition and the property
if

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2498 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

and hence, for and , where

if and , the second bound in (92) gives
(92) rise to the asymptotic bound
if

In particular, in the case of the Hamming scheme , if

and , then In the typical situation the second bounds in (91) and (92)
(which follow from the third pair of universal bounds) are
better than the first ones when the parameter is sufficiently
large and become worse when is small. In particular, this is
where
true for the bound (93) which for sufficiently small is worse
than the Hamming asymptotic bound

(see [90] and [78]). Notice that is a decreasing continu-

ous function on which coincides with its inverse
function, that is, Therefore, if is fixed and This raises the problem of “smoothing” these bounds. A
similar problem of bounding the Shannon reliability function
for probabilistic channels was considered in [108] where the
straight-line bound was found. The principle of the multiple
then the second bounds in (91) and (92) give rise to the first packing (applicable to the translation schemes, see Section V)
form of the MRRW bound for codes [90] gives the Bassalygo–Elias inequality [12]

(93) (96)
and the following asymptotic bound for designs [78]:
where , and the straight-line bound for [69]
(94)

where

where A consequence of (95) and (96) for

is the Shannon entropy. In the case of the Johnson scheme
if and where
and then
is the second form of the MRRW bound for codes [90]

where, for any

where and is defined above.

This becomes better than (95) with when
is a decreasing continuous function which maps the interval The argument that leads to (96) does not apply to the
onto (see [90] and [81]). The inverse function minimal design problem. However, a similar result is valid in
can be expressed in the following explicit form: terms of the linear programming bounds. Rodemich (see [100],
[42]) used the fact that any nonnegative-definite function
on is nonnegative-definite on (subset) as
well and proved the following analog of (96) for objective
functions of linear programming bounds:
Therefore, if and where
and then the second bound (97)
in (91) gives rise to the asymptotic bound [90]
Combination of (97) with (86) for and
(95) gives the following results [80]:

where On the other hand, as was shown (98)

in [81], if and , where
and then
(99)

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2499

In particular, (99) and (95) (considered as a bound on The homomorphisms of the group to the group
for are referred to as the (irreducible) characters of
(Henceforth we often write instead of .) The set
of characters of has the structure of an Abelian group,
isomorphic to itself; this character group is called the dual
give the following asymptotic bound [80]: of and is denoted by We shall use a bracket notation for
characters, that is, , for and
(100) The group characters satisfy the orthogonality relations

where
The essential difficulty in extending the second form of the
MRRW bound to the case is caused by the fact that the It is possible to identify with so as to have the symmetry
natural generalization of (96) connects with subschemes of property for all
the association scheme considered in Example 3 which are not From the -class translation scheme we define a
-polynomial. Some results in this direction were obtained in partition of the group into
[1] and [125]. blocks This implies
Finally, in addition to the (nonconstructive) results (96)–(99) and (for the pairing ). The relation can
which give bounds for the Hamming space from bounds be recovered from the block as follows:
for the Johnson space, let us point out a “constructive” (101)
relationship between codes and designs in the Hamming and
Johnson schemes. It is the celebrated Assmus–Mattson theorem It can be shown that there exists a unique partition
[4], which allows one to obtain good combinatorial designs of the dual group into blocks
and constant-weight codes from certain codes in the binary , with and with the following property. For
Hamming scheme. A strengthening of this result can be found , define and by
in [29].
(102)
V. TRANSLATION SCHEMES
Then is constant over each block and is constant
A. Definitions and Preliminaries over each block More precisely
Certain association schemes are invariant under “transla-
for (103)
tions,” of the form Examples are
the Hamming scheme and the composition scheme, described for (104)
in Section II-A (Examples 1 and 3). We shall examine the
appropriate generalization, under the name of “translation where the numbers and are the -numbers and the
-numbers of
schemes,” borrowed from [26]. A comprehensive treatment
The partition (of ) will be called the dual of the
of that subject is given by Camion [32]. The material of this
partition (of ). From we define a partition of
section is mainly taken from [42].
like in (101). More precisely, with
Definition 10: Let be a finite Abelian group, and let
be an -class association scheme. Assume that
is -invariant, i.e.,
It can be shown that is a translation scheme with
if then respect to the dual group From (102) it follows that
the -numbers of are the -numbers of and
for all Then is said to be a translation conversely. Thus with an obvious notation, we have the duality
scheme with respect to the group relations and , given in (25). In
particular, and
We briefly examine the Hamming scheme from this
In the context of the Krein duality (Section II-C), this
viewpoint. Let be Abelian groups of order ,
leads us to introduce the following definition of duality for
and consider their direct product It is
translation schemes. It is equivalent to a concept introduced
clear that is a translation scheme with respect to any of
by Tamaschke for commutative Schur rings [123].
these group structures.
This simple example shows that a given association scheme Definition 11: Let be a translation scheme, with
may be a translation scheme with respect to several respect to a given Abelian group , and let
group structures. Further explanation of the phenomenon will be the corresponding partition of The translation
be given in Section V-C. scheme , with respect to the dual group and
For a translation scheme, the -numbers and the -numbers corresponding to the dual partition of
(Definition 3) can be determined as follows. , is called the dual of the translation scheme

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2500 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

An interesting treatment of duality in translation schemes implies As a consequence of the orthogonality

is given by Godsil, in relation with the theory of equitable relations on group characters, we obtain
partitions [54].
if
As an example, consider once again the Hamming scheme (105)
if
, together with the Abelian group structure
In this case, the block in consists of the -ary
If is a linear code of length over (in the usual sense),
-tuples of weight (i.e., those having nonzero components).
then , the orthogonal of This stems from the fact
Let us identify the dual group with It turns out that the
that the characters of are given by
dual partition coincides with the weight partition Thus
for a suitable ordering, we have for all which
shows that the Hamming scheme is self-dual. The formulas
(103) and (104) lead to the expressions (17) of the - and
-numbers in terms of the Krawtchouk polynomials. for all Here, denotes the trace from the field
Similarly, the composition scheme (Example 3 in Section II- to its prime subfield In the binary case, ,
A) is a self-dual translation scheme. There are other interesting this reduces to
families of that type [41], [43], [89]. Some examples of The next result is a generalization of the MacWilliams
translation schemes that are not self-dual can be found in [30] identities on the weight distributions of a linear code and its
and [37]. orthogonal. It produces a clear interpretation of Theorem 3
in the restricted framework of additive codes in translation
B. Additive Codes in a Translation Scheme schemes. The proof is based on (103)–(105).
As a generalization of the classical notion of a linear code Theorem 27 (Generalized MacWilliams Identities [37],
over a field alphabet (in Hamming scheme), we shall examine [42]): The inner distribution of
additive codes in a translation scheme. is proportional to the -transform of the inner distribution
of More precisely
Definition 12: A code in a translation scheme
is said to be additive if is a subgroup of the underlying
Abelian group
Consider the inner distribution of an ad- As a consequence, the fundamental parameters (see Section
ditive code (see Definition 5). It follows from (101) that III-C) of a code in a translation scheme are related
counts the code points belonging to the block in the to those of its annihilator code by
partition , that is,

for Finally, let us examine the outer distribution of an

additive code (see Definition 8). In view of (101), noting
Next, we define the “annihilator code” of an additive code that , we obtain
by generalizing the usual notion of the orthogonal code of
a linear code in Hamming scheme. (The terminology is not for
standard, but “annihilator” seems preferable to “orthogonal,”
This means that the -row of is the distribution of
in the general setting.)
the coset code with respect to the partition
Definition 13: Let be an additive code in a translation For the outer distribution of the annihilator code ,
scheme The annihilator code of (with respect to we similarly have with
the given group ) is the code in the dual translation and As an extension of Theorem 27 we obtain
scheme defined by the following expression for the -transform of the outer
distribution rows:
for all
(106)
It is clear that is an additive code in Similarly,
for an additive code in , we define its annihilator
code to be By use of (106) we can derive a remarkable result (Theorem
28 below) that allows us to decide whether a given additive
for all code carries a (translation) subscheme of , and to
characterize the dual of this subscheme. Note that by Theorems
This is an additive code in For double annihilators, 7 and 27 the rank of the outer distribution of is equal
we simply have to
Definition 14: Let be an additive code of degree
in a translation scheme If the restriction
The character group of is related to by is an association scheme (with classes), then it is
(the group of coset codes with ). This called a subscheme of

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2501

Theorem 28 [37]: Given an additive code of degree , , namely,

the restriction is a subscheme of if and only
if the outer distribution of the annihilator code has
distinct rows.
In this case, the dual scheme of the translation scheme In effect, for we obtain
is where consists of
the relations on defined as follows: a pair
of coset codes belongs to a given relation
if and only if the outer distribution row is a
fixed -tuple (among the possibilities).
For example, Theorem 28 applies to the extended binary
Golay code examined in Section IV-C. Recall that is self- In terms of the usual binary alphabet , this induces the
orthogonal: The code has degree , cyclic permutation of the binary ordered pairs,
and the outer distribution of its orthogonal has with
five distinct rows. The -class association scheme
carried by is mentioned at the end of Section IV-D. Since
is -polynomial, its dual scheme , carried (107)
by the factor group , is -polynomial. It is the As a conclusion, contains two regular Abelian sub-
“distance scheme” for the cosets of the extended binary Golay groups: not only the elementary Abelian group
code (see [26, p. 361]). (consisting of the diagonal matrices), but also the cyclic group
The reader familiar with the Golay code may be interested generated by
in a more sophisticated example. Take to be the perfect Note that the cyclic permutation in (107) corresponds to
binary Golay code of length (and dimension ). This the Gray map between and , that is,
code has degree The orthogonal code can be This map underlies the
shown to be completely regular; its outer distribution has “concrete approach” to -additive binary codes [57].
eight distinct rows corresponding to the eight values Let us now turn to the general case of with By
(see [26, p. 362]). considering partitions of the coordinate positions in blocks
of size or , we obtain a whole class of regular Abelian
C. -Additive Binary Codes subgroups of of the form
Important research work has been devoted recently to the with
class of binary codes that are additive over , the cyclic
group of order (see especially [57] and [92]). This subsection Each of the groups (together with a corresponding co-
aims at showing how that subject fits into the framework of ordinate partition) provides with a translation scheme
association scheme theory. structure, and gives rise to a well-defined class of additive
From a group-theoretic viewpoint, translation schemes can (binary) codes (see Definition 12).
be presented as follows. Let denote the automor- Let be an additive code with respect to , and let
phism group of a given association scheme Assume be the annihilator code of (see Definition 13). In view of
that contains an Abelian subgroup which is Theorem 27, the inner distributions of and (which are
regular on , in the sense that is transitive on and has their ordinary weight distributions) are related to each other
order This provides the point set with the structure by the MacWilliams identities in the usual sense.
of an Abelian group , isomorphic to , through the The “homogeneous cases” are , which yields the
definition class of linear binary codes, and (for even ), which
yields the class of -additive binary codes [57]. In the latter
for all case, the annihilator code of is the natural orthogonal
code over the cyclic group
where is a fixed point in It is clear that is A very interesting example is provided by the Kerdock
a translation scheme with respect to (see Definition codes and their -orthogonals which are the “Preparata
10). In fact, the “translation structures” of correspond codes” (see [57]). Quotes are used here because is not
exactly to the regular Abelian subgroups of exactly the same as the official Preparata code, although they
Consider the binary Hamming scheme (see Example both have the same essential properties and, in particular, the
2 in Section II-D). Its automorphism group is the monomial same distance distribution. This example is quite remarkable
group (or hyperoctahedral group) of degree (and order for the following reason. It has been known for a long time that
). As we shall see, contains several regular Abelian the weight distributions of the Kerdock and Preparata codes are
subgroups. the MacWilliams transform of each other, although these codes
For , the monomial group (of order ), is are nonlinear (over The result in [57] alluded to above
the symmetry group of the square It contains an says that is -additive, and it identifies the -orthogonal
element of order that cyclically permutes the four vertices of as a certain “Preparata code”

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2502 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

Note Added in Proof pp. 1261–1268, 1991.

[30] A. R. Calderbank and J.-M. Goethals, “On a pair of dual subschemes of
It is worth pointing out that the class of additive (binary) H q
the Hamming scheme n ( ),” Europ. J. Comb., vol. 6, pp. 133–147,
codes considered at the end of Section V-C coincides with the 1985.
[31] A. R. Calderbank and N. J. A. Sloane, “Inequalities for covering codes,”
class of additive propelinear codes investigated by Rifà and IEEE Trans. Inform. Theory, vol. 34, pp. 1276–1280, 1988.
Pujol [136]. [32] P. Camion, “Codes and association schemes,” in Handbook of Coding
Theory, V. S. Pless and W. C. Huffman, Eds. Amsterdam, The
Netherlands: Elsevier, 1998.
REFERENCES [33] P. Camion, C. Carlet, P. Charpin, and N. Sendrier, “On correlation-
immune functions,” in Advances in Cryptology–CRYPTO’91, Lecture
[1] M. Aaltonen, “A new upper bound on nonbinary block codes,” Discr. Notes in Computer Science No. 676, J. Feigenbaum, Ed. New York:
Math., vol. 83, pp. 139–160, 1990. Springer-Verlag, 1991, pp. 86-100.
[2] R. Askey and J. Wilson, “A set of orthogonal polynomials that generalize [34] G. D. Cohen, M. G. Karpovsky, H. F. Mattson, Jr., and J. R. Schatz,
the Racah coefficients or 6 0j symbols,” SIAM J. Math. Anal., vol. 10, “Covering radius—Survey and recent results,” IEEE Trans. Inform.
pp. 1008–1016, 1979. Theory, vol. IT-31, pp. 328–343, 1985.
[3] E. F. Assmus, Jr., and J. D. Key, Designs and Their Codes. Cambridge, [35] P. Delsarte, “Bounds for unrestricted codes, by linear programming,”
U.K.: Cambridge Univ. Press, 1992. Philips Res. Repts., vol. 27, pp. 272–289, 1972.
[4] E. F. Assmus, Jr., and H. F. Mattson, Jr., “New 5-designs,” J. Combin. [36] , “Four fundamental parameters of a code and their combinatorial
Theory, vol. 6, pp. 122–151, 1969. significance,” Inform. Contr., vol. 23, pp. 407–438, 1973.
[5] , “Coding and combinatorics,” SIAM Rev., vol. 16, pp. 349–388, [37] , “An algebraic approach to the association schemes of coding
1974. theory,” Philips Res. Repts. Suppl., vol. 10, 1973.
[6] E. F. Assmus, Jr., and V. Pless, “On the covering radius of extremal [38] t
, “Association schemes and -designs in regular semilattices,” J.
self-dual codes,” IEEE Trans. Inform. Theory, vol. IT-29, pp. 359–363, Combin. Theory Ser. A, vol. 20, pp. 230–243, 1976.
1983. [39] , “Pairs of vectors in the space of an association scheme,” Philips
[7] E. Bannai, “On tight designs,” Quart. J. Math. Oxford, vol. 28, pp. Res. Repts., vol. 32, pp. 373–411, 1977.
433–448, 1977. [40] t
, “Hahn polynomials, discrete harmonics, and -designs,” SIAM
[8] , “Tannaka–Krein duality for association schemes,” Linear Alge- J. Appl. Math., vol. 34, pp. 157–166, 1978.
bra Appl., vol. 46, pp. 83–90, 1982. [41] , “Bilinear forms over a finite field, with applications to coding
[9] , “Orthogonal polynomials in coding theory and algebraic com- theory,” J. Combin. Theory Ser. A, vol. 25, pp. 226–241, 1978.
binatorics,” in Orthogonal Polynomials, P. Nevai, Ed. Norwell, MA: [42] , “Application and generalization of the MacWilliams transform
Kluwer, 1990, pp. 25–53. in coding theory,” in Proc. 15th Symp. Information Theory in the Benelux
[10] E. Bannai and T. Ito, Algebraic Combinatorics I. Association Schemes. (Louvain-la-Neuve, Belgium, 1994), pp. 9–44.
Menlo Park, CA: Benjamin/Cummings, 1984. [43] P. Delsarte and J.-M. Goethals, “Alternating bilinear forms over
[11] , “Current research on algebraic combinatorics,” Graphs Combin., q
GF ( ),” J. Combin. Theory Ser. A, vol. 19, pp. 26–50, 1975.
vol. 2, pp. 287–308, 1986. [44] P. Delsarte, J.-M. Goethals, and J. J. Seidel, “Bounds for systems
[12] L. A. Bassalygo, “New upper bounds for error correcting codes,” Probl. of lines, and Jacobi polynomials,” Philips Res. Repts., vol. 30, pp.
Inform. Transm., vol. 1, no. 4, pp. 32–35, 1965. 913 –1053 , 1975.
[13] V. Belevitch, “Conference networks and Hadamard matrices,” Ann. Soc. [45] , “Spherical codes and designs,” Geom. Dedicata, vol. 6, pp.
Scient. Bruxelles, vol. 82, pp. 13–32, 1968. 363–388, 1977.
[14] M. R. Best and A. E. Brouwer, “The triply shortened binary Hamming [46] C. F. Dunkl, “A Krawtchouk polynomial addition theorem and wreath
code is optimal,” Discr. Math., vol. 17, pp. 235–245, 1977. products of symmetric groups,” Indiana Univ. Math. J., vol. 25, pp.
[15] T. Beth, D. Jungnickel, and H. Lenz, Design Theory. Manheim, 335–358, 1976.
Germany: Bibl. Institut-Wissenschaftsverlag, 1985.
[16] J. Bierbrauer, K. Gopalakrishnan, and D. R. Stinson, “Bounds for
[47] t
, “Discrete quadrature and bounds on -design,” Mich. Math. J.,
vol. 26, pp. 81–102, 1979.
resilient functions and orthogonal arrays,” in Advances in Cryptol- [48] , “Orthogonal functions on some permutation groups,” in Proc.
ogy–CRYPTO’94, Lecture Notes in Computer Science No. 839, Y. G. Symp. Pure Math. 34 (Providence, RI: Amer. Math. Soc., 1979), pp.
Desmedt, Ed. New York: Springer-Verlag, 1994, pp. 247–256. 129–147.
[17] N. L. Biggs, “Perfect codes in graphs,” J. Combin. Theory Ser. B, vol.
[49] A. Erdélyi, W. Magnus, F. Oberhettinger, and F. G. Tricomi, Higher
15, pp. 289–296, 1973.
Transcendental Functions, vol. 2. New York: McGraw-Hill, 1953.
[18] , Algebraic Graph Theory. Cambridge, U.K.: Cambridge Univ.
[50] I. A. Faradz̆ev, A. A. Ivanov, and M. H. Klin, “Galois correspondence
Press, 1974.
[19] H. F. Blichfeldt, “The minimum value of quadratic forms and the closest between permutation groups and cellular rings (association schemes),”
packing of spheres,” Math. Ann., vol. 101, pp. 605–608, 1929. Graphs Combin., vol. 6, pp. 303–332, 1990.
[20] R. C. Bose, “Strongly regular graphs, partial geometries and partially [51] G. Fazekas and V. I. Levenshtein, “On upper bounds for code distance
balanced designs,” Pacific J. Math., vol. 13, pp. 389–419, 1963. and covering radius of designs in polynomial metric spaces,” J. Combin.
[21] R. C. Bose and D. M. Mesner, “On linear associative algebras corre- Theory Ser. A, vol. 70, pp. 267–288, 1995.
sponding to association schemes of partially balanced designs,” Ann. [52] E. M. Gabidulin, “Theory of codes with maximum rank distance,” Probl.
Math. Statist., vol. 30, pp. 21–38, 1959. Inform. Transm., vol. 21, no. 1, pp. 1–12, 1985.
[22] R. C. Bose and K. R. Nair, “Partially balanced incomplete block [53] R. Gangolli, “Positive definite kernels on homogeneous spaces and
designs,” Sankhyā, vol. 4, pp. 337–372, 1939. certain stochastic processes related to Levy’s Brownian motion of
[23] R. C. Bose and T. Shimamoto, “Classification and analysis of partially several parameters,” Ann. Inst. Henri Poincaré, vol. 3, pp. 121–226,
balanced incomplete block designs with two associate classes,” J. Amer. 1967.
Statist. Assoc., vol. 47, pp. 151–184, 1952. [54] C. D. Godsil, Algebraic Combinatorics. New York: Chapman & Hall,
[24] P. G. Boyvalenkov, D. P. Danev, and S. P. Bumova, “Upper bounds on 1993.
the minimum distance of spherical codes,” IEEE Trans. Inform. Theory, [55] J.-M. Goethals, “Association schemes,” in Algebraic Coding Theory and
vol. 42, pp. 1576–1581, 1996. Applications, CISM Courses and Lectures No. 258, G. Longo, Ed. New
[25] P. Boyvalenkov and D. Danev, “On linear programming bounds for York: Springer-Verlag, 1979, pp. 243–283.
codes in polynomial metric spaces,” to be published in Probl. Inform. [56] J.-M. Goethals and J. J. Seidel, “Orthogonal matrices with zero diago-
Transm. nal,” Canad. J. Math., vol. 19, pp. 1001–1010, 1967.
[26] A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular [57] A. R. Hammons, Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane,
Graphs. Berlin, Germany: Springer-Verlag, 1989. Z
and P. Solé, “The 4 -linearity of Kerdock, Preparata, Goethals, and
[27] A. E. Brouwer and T. Verhoeff, “An updated table of minimum-distance related codes,” IEEE Trans. Inform. Theory, vol. 40, pp. 301–319, 1994.
bounds for binary linear codes,” IEEE Trans. Inform. Theory, vol. 39, [58] D. G. Higman, “Intersection matrices for finite permutation groups,” J.
pp. 662–675, 1993. Algebra, vol. 6, pp. 22–42, 1967.
t
[28] A. R. Calderbank and P. Delsarte, “Extending the -design concept,” [59] , “Coherent configurations. Part I: Ordinary representation the-
Trans. Amer. Math. Soc., vol. 338, pp. 941–952, 1993. ory,” Geom. Dedicata, vol. 4, pp. 1–32, 1975.
[29] A. R. Calderbank, P. Delsarte, and N. J. A. Sloane, “A strengthening t
[60] S. G. Hoggar, “ -designs in projective spaces,” Europ. J. Combin., vol.
of the Assmus–Mattson theorem,” IEEE Trans. Inform. Theory, vol. 37, 3, pp. 233–254, 1982.

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
DELSARTE AND LEVENSHTEIN: ASSOCIATION SCHEMES AND CODING THEORY 2503

[61] G. Hoheisel, “Über Charaktere,” Monatsch. Math. Phys., vol. 48, pp. vol. 1, no. 4, pp. 123–139, 1989 (in Russian). English translation in
448–456, 1939. Discr. Math. Appl., vol. 1, pp. 365–384, 1991.
[62] D. R. Hughes and F. C. Piper, Design Theory. Cambridge, U.K.: [93] A. Neumaier, “Distances, graphs and designs,” Europ. J. Combin., vol.
Cambridge Univ. Press, 1985. 1, pp. 163–174, 1980.
[63] F. Jaeger, “On spin models, triply regular association schemes, and [94] , “Combinatorial configurations in terms of distances,” Memo-
duality,” J. Algebraic Combin., vol. 4, pp. 103–144, 1995. randum 81-09 (Wiskunde), Eindhoven Univ. Technol., Eindhoven, The
[64] H. Janwa, “Some new upper bounds on the covering radius of binary Netherlands, 1980.
linear codes,” IEEE Trans. Inform. Theory, vol. 35, pp. 110–122, 1989. [95] , “Duality in coherent configurations,” Combinatorica, vol. 9, pp.
[65] G. A. Kabatyanskii and V. I. Levenshtein, “Bounds for packings on a 59–67, 1989.
sphere and in space,” Probl. Inform. Transm., vol. 14, no. 1, pp. 1–17, [96] A. M. Odlyzko and N. J. A. Sloane, “New bounds on the number of
1978. unit spheres that can touch a unit sphere in n dimensions,” J. Combin.
[66] S. Karlin and J. L. McGregor, “The Hahn polynomials, formulas and Theory Ser. A, vol. 26, pp. 210–214, 1979.
an application,” Scripta Math., vol. 26, pp. 33–46, 1961. [97] R. A. Rankin, “The closest packing of spherical caps in n dimensions,”
[67] Y. Kawada, “Über den Dualitätssatz der Charaktere nichtcommutativer Proc. Glasgow Math. Assoc., vol. 2, pp. 139–144, 1955.
Gruppen,” Proc. Phys. Math. Soc. Japan (3), vol. 24, pp. 97–109, 1942. [98] C. R. Rao, “Factorial experiments derivable from combinatorial arrange-
[68] M. Krawtchouk, “Sur une généralisation des polynômes d’Hermite,” C. ments of arrays,” J. Roy. Statist. Soc., vol. 9, pp. 128–139, 1947.
R. Acad. Sci. Paris, vol. 189, pp. 620–622, 1929. [99] D. K. Ray-Chaudhuri and R. M. Wilson, “On t-designs,” Osaka J. Math.,
[69] T. Laihonen and S. Litsyn, “On upper bounds for minimum distance vol. 12, pp. 737–744, 1975.
and covering radius of non-binary codes,” Des., Codes Cryptogr., vol. [100] E. R. Rodemich, “An inequality in coding theory,” presented at the
14, pp. 71–80, 1998. Annu. Amer. Math. Soc. Meet., San Antonio, TX, Jan. 1980.
[70] H. W. Lenstra, Jr., “Two theorems on perfect codes,” Discr. Math., vol. [101] C. Roos, “On metric and cometric association schemes,” Delft Progr.
3, pp. 125–132, 1972. Rep., vol. 4, pp. 191–220, 1979.
[71] D. A. Leonard, “Orthogonal polynomials, duality, and association [102] R. M. Roth, “Maximum-rank array codes and their application to
schemes,” SIAM J. Math. Anal., vol. 13, pp. 656–663, 1982. crisscross error correction,” IEEE Trans. Inform. Theory, vol. 37, pp.
[72] , “Metric, co-metric association schemes,” in Combinatorics, 328–336, 1991.
Graph Theory and Computing, Proc. 15th Southeast. Conf. (Louisiana [103] I. Schoenberg and G. Szegö, “An extremum problem for polynomials,”
State Univ., Congr. Numerantium 44, 1984), pp. 277–282. Composito Math., vol. 14, pp. 260–268, 1960.
[73] V. I. Levenshtein, “On choosing polynomials to obtain bounds in [104] A. A. Schrijver, “A comparison of the bounds of Delsarte and Lovász,”
packing problems,” in Proc. 7th All-Union Conf. Coding Theory and IEEE Trans. Inform. Theory, vol. IT-25, pp. 425–429, 1979.
Information Transmission, Part II (Moscow, Vilnius, 1978), pp. 103–108 [105] J. J. Seidel, “Strongly regular graphs,” in Surveys in Combinatorics,
(in Russian). London Math. Soc. Lecture Notes Series No. 38, B. Bollobàs, Ed.
[74] , “On bounds for packings in n-dimensional Euclidean space,” Cambridge, U.K.: Cambridge Univ. Press, 1979, pp. 157–180.
Sov. Math.–Dokl., vol. 20, no. 2, pp. 417–421, 1979. [106] C. Shannon, “The zero error capacity of a noisy channel,” IRE Trans.
[75] , “Bounds on the maximal cardinality of a code with bounded Inform. Theory, vol. 2, pp. 8–19, 1956.
modulus of the inner product,” Sov. Math.–Dokl., vol. 25, no. 2, pp. [107] , “Probability of error for optimal codes in Gaussian channel,”
526–531, 1982. Bell Syst. Tech. J., vol. 38, pp. 611–656, 1959.
[76] , “Bounds for packings of metric spaces and some of their [108] C. Shannon, R. G. Gallager, and E. R. Berlekamp, “Lower bounds to
applications,” Probl. Cybern., vol. 40. Moscow, USSR: Nauka, 1983, error probability for coding on discrete memoryless channels,” Inform.
pp. 43–110 (in Russian). Contr., vol. 10, pp. 65–103 and 522–552, 1967.
[77] , “Designs as maximum codes in polynomial metric spaces,” Acta [109] V. M. Sidelnikov, “On mutual correlation of sequences,” Sov.
Applic. Math., vol. 29, pp. 1–82, 1992. Math.–Dokl., vol. 12, no. 1, pp. 197–201, 1971.
[78] , “Krawtchouk polynomials and universal bounds for codes and [110] , “New bounds for densest packings of spheres in n-dimensional
designs in Hamming spaces,” IEEE Trans. Inform. Theory, vol. 41, pp. Euclidean space,” Math. USSR Sbornik, vol. 24, pp. 147–157, 1974.
1303–1321, 1995. [111] , “Upper bounds on the number of points of a binary code with
[79] , “Split orthogonal arrays and maximum independent resilient a specified code distance,” Probl. Inform. Transm., vol. 10, no. 2, pp.
systems of functions,” Des., Codes Cryptogr., vol. 12, pp. 131–160, 124–131, 1974.
1997. [112] , “Extremal polynomials used in bounds of code volume,” Probl.
[80] , “Equivalence of Delsarte’s bounds for codes and designs in Inform. Transm., vol. 16, no. 3, pp. 174–186, 1980.
symmetric association schemes, and some applications,” Discr. Math, [113] T. Siegenthaler, “Correlation immunity of nonlinear combining function
to be published. for cryptographic applications,” IEEE Trans. Inform. Theory, vol. IT-30,
[81] , “Universal bounds for codes and designs,” in Handbook of pp. 776–780, 1984.
Coding Theory, V. S. Pless and W. C. Huffman, Eds. Amsterdam, [114] L. J. Slater, Generalized Hypergeometric Functions. Cambridge, U.K.:
The Netherlands: Elsevier, 1998. Cambridge Univ. Press, 1966.
[82] J. H. van Lint, Coding Theory. Berlin, Germany: Springer-Verlag, [115] N. J. A. Sloane, “An introduction to association schemes and coding
1982. theory,” in Theory and Application of Special Functions, R. A. Askey,
[83] S. Litsyn and A. Tietäväinen, “Upper bounds on the covering radius of Ed. New York: Academic, 1975, pp. 225–260.
a code with a given dual distance,” Europ. J. Combin., vol. 173, pp. [116] , “Recent bounds for codes, sphere packings and related problems
265–270, 1996. obtained by linear programming and other methods,” Contemp. Math.,
[84] S. P. Lloyd, “Binary block coding,” Bell Syst. Tech. J., vol. 36, pp. vol. 9, pp. 153–185, 1982.
517–535, 1957. [117] P. Solé, “A Lloyd theorem in weakly metric association schemes,”
[85] L. Lovász, “On the Shannon capacity of a graph,” IEEE Trans. Inform. Europ. J. Combin., vol. 10, pp. 189–196, 1989.
Theory, vol. IT-25, pp. 1–7, 1979. [118] P. Solé and P. Stokes, “Covering radius, codimension, and dual distance
[86] F. J. MacWilliams, “Combinatorial problems of elementary group the- width,” IEEE Trans. Inform. Theory, vol. 39, pp. 1195–1203, 1993.
ory,” Ph.D. dissertation, Dept. Math., Harvard Univ., Cambridge, MA, [119] D. Stanton, “Orthogonal polynomials and Chevalley groups,” in Special
1962. Functions: Group Theoretical Aspects and Applications, R. A. Askey,
[87] , “A theorem on the distribution of weights in a systematic code,” Ed. Dordrecht, The Netherlands: Reidel, 1984, pp. 87–128.
Bell Syst. Tech. J., vol. 42, pp. 79–94, 1963. [120] , “An introduction to group representations and orthogonal poly-
[88] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting nomials” in Orthogonal Polynomials, P. Nevai, Ed. Norwell, MA:
Codes. New York: North-Holland, 1977. Kluwer, 1990, pp. 419–433.
[89] W. J. Martin and D. R Stinson, “Association schemes for ordered [121] G. Szegö, Orthogonal Polynomials. New York: Amer. Math. Soc.,
orthogonal arrays and (T ; M; S )-nets,” preprint. 1959.
[90] R. J. McEliece, E. R. Rodemich, H. Rumsey, Jr., and L. R. Welch, [122] D. R. Stinson, “Combinatorial designs and cryptography” in Surveys
“New upper bounds on the rate of a code via the Delsarte–MacWilliams in Combinatorics, 1993, K. Walter, Ed. Cambridge, U.K.: Cambridge
inequalities,” IEEE Trans. Inform. Theory, vol. IT-23, pp. 157–166, Univ. Press, 1993, pp. 257–287.
1977. [123] O. Tamaschke, “Zur Theorie der Permutationsgruppen mit regulärer
[91] R. J. McEliece, E. R. Rodemich, and H. C. Rumsey, Jr., “The Lovász Untergruppe I,” Math. Z., vol. 80, pp. 328–354, 1963.
bound and some generalizations,” J. Comb., Inform. Syst. Sci., vol. 3, [124] H. Tarnanen, “An approach to construct constant weight and Lee codes
pp. 134–152, 1978. by using the method of association schemes,” Ann. Univ. Turku Ser. A
[92] A. A. Nechaev, “The Kerdock code in a cyclic form” Diskret. Math., I, vol. 182, 1982.

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.
2504 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998

[125] H. Tarnanen, M. J. Aaltonen, and J.-M. Goethals, “On the nonbinary [131] L. R. Welch, R. J. McEliece, and H. Rumsey, Jr., “A low-rate improve-
Johnson scheme,” Europ. J. Combin., vol. 6, pp. 279–285, 1985. ment on the Elias bound,” IEEE Trans. Inform. Theory, vol. IT-20, pp.
[126] P. Terwilliger, “A characterization of P - and Q-polynomial association 676–678, 1974.
schemes,” J. Combin. Theory Ser. A, vol. 45, pp. 8–26, 1987. [132] H. Wielandt, Finite Permutation Groups. New York: Academic, 1964.
[127] A. A. Tietäväinen, “An upper bound on the covering radius as a [133] R. M. Wilson, “Inequalities for t-designs,” J. Comb. Theory Ser. A, vol.
function of the dual distance,” IEEE Trans. Inform. Theory, vol. 36, 34, pp. 313–324, 1983.
pp. 1472–1474, 1990. [134] , “On the theory of t-designs,” in Enumeration and Designs, D.
[128] D. Vere-Jones, “Finite bivariate distributions and semigroups of non-
negative matrices,” Quart. J. Math. Oxford (2), vol. 22, pp. 247–270, M. Jackson and S. A. Vanstone, Eds. New York: Academic, 1984, pp.
1971. 19–49.
[129] N. Vilenkin, Special Functions and the Theory of Group Representation. [135] V. A. Yudin, “Lower bounds for spherical designs,” Izvestiya: Matem-
Providence, RI: Amer. Math. Soc., 1968. atika, vol. 61, no. 3, pp. 673–683, 1997.
[130] H. Wang, “Two-point homogeneous spaces,” Ann. Math., vol. 55, pp. [136] J. Rifà and J. Pujol, “Translation-invariant propelinear codes,” IEEE
177–191, 1952. Trans. Inform. Theory, vol. 43, pp. 590–598, Mar. 1997.

Authorized licensed use limited to: Herzeliya IDC. Downloaded on January 20,2024 at 06:49:20 UTC from IEEE Xplore. Restrictions apply.