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

Given a code C, invariant linear forms are used to study the designs afforded by codewords of a fixed weight. The most important theorem relating codes and designs is due to Assmus and Mattson [J. Combin. Theory, 6 (1969), pp. 122–151], and this theorem is extended in different ways. For extremal self dual codes over the fields $\mathbb{F}_2 $ and $\mathbb{F}_3 $, it is proved that the t-designs afforded by the codewords of any fixed weight exhibit extra regularity with respect to $( t + 2 )$-sets. The same is true for the design afforded by the codewords of minimum weight in an extremal self-dual code over $\mathbb{F}_4 $. The invariant linear forms are also used to construct Boolean designs with several block sizes, extending previous work by Safavi-Naini and Blake [Utilitas Math., 14 (1978), pp. 49–63], [Ars Combin., 7 (1979), pp. 135–151], [Inform. and Control, 42 (1986), pp. 261–282].

Predictor polynomials corresponding to nested Toeplitz matrices are known to be connected by the Szego-Levinson recurrence relation. A generalization of that result, where the relevant reduction process for Toeplitz matrices (of decreasing order) is defined by an elementary one-parameter linear transformation, is addressed. The descending and ascending versions of the corresponding generalized Szego-Levinson recurrence relations are discussed in detail. In particular, these relations are shown to be essentially the same as the extraction formulas for canonical Schur and Brune sections in the Dewilde-Dym (1984) recursive solution of the lossless inverse scattering problem. Some extensions of the Levinson algorithm for linear prediction and of the Schur-Cohn algorithm for polynomial stability test are presented.>

The authors consider the problem of designing multiresolution transforms that are adapted to the given image signal, in the sense that they maximize the coding gain at each resolution level. A simple alternating optimization algorithm is derived for solving this problem in the framework of the lattice realization of para-unitary quadrature mirror filters. The resulting large coding scheme is discussed in some detail, and its performance is compared with that of the discrete cosine transform (JPEG) technique and with that of some nonadapted multiresolution transforms.>

Consideration is given to the problem of designing a signal-adapted two-band filtering system that has the perfect reconstruction property for application to multiresolution signal coding. A natural optimization criterion for this problem is introduced, and an iterative algorithm for computing optimal filters in lattice form is described. Some simulation results for the application of the technique to image coding are presented.>

Let w/sub 1/=d,w/sub 2/,...,w/sub s/ be the weights of the nonzero codewords in a binary linear (n,k,d) code C, and let w'/sub 1/, w'/sub 2/, ..., w'/sub 3/, be the nonzero weights in the dual code C1. Let t be an integer in the range 0or=d+4 then either the words of any nonzero weight w/sub i/ form a (t+1)-design or else the codewords of minimal weight d form a (1,2,...,t,t+2)-design. If in addition C is self-dual with all weights divisible by 4 then the codewords of any given weight w/sub i/ form either a (t +1)-design or a (1,2,...,t,t+2)-design. The proof avoids the use of modular forms.>

Given an $m \times n$ sign matrix S, an $m \times n$ real matrix A is said to be a realization of S if the sign of the $(i,j)$-entry of A equals the $(i,j)$-entry of S. This paper deals with the problem of finding low rank realization matrices A. It is motivated by a minimization problem in multilayer perceptrons. The subject is approached by means of the Farkas lemma, which allows characterization of the sign matrices realizable with a given rank. Based on this result and on some other standard techniques of matrix algebra such as the cyclic Fourier transform, low rank realizations are obtained for sign matrices having certain nice combinatorial structures. Furthermore, the paper includes an elementary lower bound on the rank and a counting of realizable sign vectors.

It is shown that the split Levinson algorithm, the split Schur algorithm, and the split lattice algorithm to compute the reflection coefficients of the optimal linear prediction filter for a discrete-time stationary stochastic process can be extended to the more general case of the joint process estimation problem. The new algorithms are essentially based on well-defined recurrence relations for symmetric prediction filters and symmetric estimation filters. They are more economical than the standard methods in terms of storage space and number of arithmetic operations.>

The zeros of a predictor polynomial are shown to belong to the numerical range of a linear operator associated with the particular prediction problem considered. Application of this result to the autocorrelation and postwindowed cases shows that the predictor polynomials enjoy a well-defined stability margin which depends in particular on the length of the data sequence. The generalization of these results to the multichannel case is also discussed.

This paper performs a detailed analysis of the zero location of linear predictor polynomials and in particular determines a precise stability margin for some classical predictors such as the autocorrelation and the postwindowed cases. It is shown that an adequate mathematical tool in this context is the concept of numerical range or field of values of a matrix associated with the prediction problem.

The following two problems are dealt with: P1) finding the smallest rate,R, of a binary code of lengthnadmitting a prescribed covering radius\rho n; P2) discovering whether a majority of codes with any rate larger thanRadmits the given covering radius. For the class of unrestricted (nonlinear) codes a solution to both problems is obtained by an elementary averaging argument. The solution to P1 isR = 1 - H(\rho) + O(n^{-1} \log n)and the answer to P2 is positive. As for the more interesting class of linear codes, Goblick's extension method shows that the solution to P1 is the same as in the unrestricted case; in contrast, P2 seems to remain an open question. A simple derivation of Goblick's result is presented, and a discussion is made of the positive conjecture concerning P2 for linear codes.

It is shown that the Karhunen-Loève transform problem can be formulated as a matrix approximation problem with Hilbert-Schmidt error norm. On the other hand, the Courant-Fischer minimax theorem provides a characterization for the best matrix approximation when the spectral norm is used. It appears that the optimality conditions of the Karhunen-Loève problem lead to the selection of a particular solution among the set of solutions to the Courant-Fischer problem.

The partial trigonometric moment problem is shown to provide a unifying framework for several speech modelling techniques, such as the classical LPC antoregressive model, the line spectral pairs and composite sinusoidal waves models, and the Toeplitz eigenvector model for formant extraction, From a mathematical viewpoint, this moment problem can be identified to an extension problem in the class of impedance functions or equivalently in the class of nonnegative definite Toeplitz matrices.

A polynomial approach to the generalized Levinson algorithm based on the Toeplitz distance concept is given. It turns out that most properties of the standard Levinson algorithm admit natural generalizations, including the three-term recurrence relations, the Christoffel-Darboux formula, and the reflection coefficients (Schur-Szegö parameters) obtainable from the data via an extension of the Schur algorithm. The theory of\sum-lossless transfer functions is shown to play the same illuminating role in the problem as the theory of Szegö orthogonal polynomials in the standard Levinson algorithm.

The paper is concerned with the generalized Levinson algorithm based on the displacement rank concept. It turns out that this algorithm for inverting an arbitrary positive definite matrix can be approached from two different mathematical viewpoints : the theory of Σ-lossless transfer functions on the one hand and the matrix version of the standard Levinson algorithm applied to an appropriate block-Toeplitz embedding of the given matrix on the other hand.

The problem of the explicit construction of encoders achieving Shannon's capacity and admitting a simple decoding algorithm is considered. A solution based on Justesen's idea of variable concatenated codes is given for the case of a symmetric memoryless channel with an input alphabet of prime power order, under the assumption that the information messages are equiprobable. This construction remains good for a nonsymmetric channel provided the encoding rate is smaller than a well-defined "pseudocapacity." In case the channel is regular, it is shown that the error probability after decoding is an exponentially decreasing function of the block length for any encoding rate less than the channel capacity.

By use of known bounds on constant-weight binary codes, new uppper bounds are obtained on the cardinality of binary codes correcting asymmetric errors. Some constructions are exhibited that come close to these bounds. For single-error-correcting codes some constructions are derived from the Steiner systemS(5, 6,12), and for double-error-correcting codes some constructions are derived from the Nordstrom-Robinson code.

No abstract

A detailed study is made of positive definite half-plane Toeplitz systems and of the corresponding least-squares inverse approximaion problems. The general question is to minimize a given functional over the space of two-variable functions with a prescribed half-plane support. For some particular supports, such as those considered by Marzetta, the minimizing functions enjoy remarkable recurrence, stability, and convergence properties. Simple derivations of these properties are given and various new results are obtained. As an application, it is shown how the half-plane spectral factor of a given magnitude function can be inversely approximated by stable pseudepolynomials.

LetMbe a binary autoregressive source to be encoded within a specified Hamming distortion\delta. A binaryn-tuple is called\sigma-central if it is at distance\leq n(\delta + \sigma)from at least2^{nH(\delta - \sigma)}typical sequences produced by the sourceM. It is first shown that, in the region where the Shannon rate-distortion bound is achieved, there exist "good codes" consisting only of\sigma-central words. Next, the characterization problem is studied; the basic conjecture is that a central sequence is well-characterized by its level, which is the Hamming weight of an image sequence. The problem is solved for the memoryless source. In general, ifN(k,r)is defined to be the mean number of typicaln-tuples at distance\leq r = n \deltafrom then-tuples of levelk=n \xi, then it is shown thatn^{-l} \log N(k,r)becomes arbitrarily close toH(\delta)for an explicitly determined unique value of\xi.

LetAandBbe matrices over a finite fieldGF(q), with same column size n, having linearly independent rows. The problem is to find an optimal estimate of the "information"uB^{T}from the partial "syndrome"vA^{T}, with the conditionuA^{T} = 0, for a transmissionu \rightarrow vofn-tuples on aq-ary totally symmetric memoryless channel. The best estimate has the formvB^{T}-f(vA^{T}), wheref(x)is the value ofymaximizing a so-called decision function\Delta (x,y). Explicit expressions are obtained for\Delta; they allow computation of the critical probabilities of the channel. The theory is applied to multidimensional orthogonal check set decoding.

A simple approach to recent generalizations of BCH and Goppa codes, viewed as subfield subcodes of modified Reed-Solomon codes, is presented. The orthogonal complements of these codes are characterized, and generalized versions of some previous results about minimum distance and decoding are obtained.

Using a polynomial approach to linear codes, one derives necessary and sufficient conditions for cyclicq-ary codes to be invariant under the general linear group of substitutions over an extension field ofGF(q). The important class of polynomial codes, introduced by Kasami, Lin, and Peterson, satisfy the conditions and several new results are obtained about some of these codes.

A new infinite class of cyclic codes is studied. Codes of this class can be decoded in a step-by-step manner, using` majority logic. Some previously known codes fall in this class, and thus admit simpler decoding procedures. As random error-correcting codes, the codes are nearly as powerful as the Bose-Chaudhuri codes.