Let b be a code of length n over a field F, with automorphism group G; b/sub w/ denotes the subset of codewords of weight w. The goal is to classify the vectors of F/sup n/ into orbits under G and to determine their distances from the various subcodes b/sub w/. This is done for the first-order Reed-Muller, Nordstrom-Robinson, and Hamming codes of length 16, the Golay and shortened Golay codes of lengths 22, 23, 24, and the ternary Golay code of length 12.>

It is shown that the minimal distance d of a binary self-dual code of length n>or=74 is at most 2((n+6)/10). This bound is a consequence of some new conditions on the weight enumerator of a self-dual code obtained by considering a particular translate of the code, called its shadow. These conditions also enable one to find the highest possible minimal distance of a self-dual code for all n>or=60; to show that self-dual codes with dor=22, with d>or=8 exist precisely for n=24, 32 and n>or=26, and with d>or=10 exist precisely for n>or=46; and to show that there are exactly eight self-dual codes of length 32 with d=8. Several of the self-dual codes of length 34 have trivial group (this appears to be the smallest length where this can happen).>

Two kinds of algorithms are considered.1)If *** is a binary code of lengthn, a "soft decision" decoding algorithm for *** changes an arbitrary point ofR^{n}into a nearest codeword (nearest in Euclidean distance).2)Similarly, a decoding algorithm for a lattice\LambdainR^{n}changes an arbitrary point ofR^{n}into a closest lattice point. Some general methods are given for constructing such algorithms, ami are used to obtain new and faster decoding algorithms for the Gosset latticeE_{8}, the Golay code the Leech lattice.

Lexicographic codes, or lexicodes, are defined by various versions of the greedy algorithm. The theory of these codes is closely related to the theory of certain impartial games, which leads to a number of surprising properties. For example, lexicodes over an alphabet of sizeB=2^{a}are closed under addition, while ifB = 2^{2^{a}}the lexicodes are closed under multiplication by scalars, where addition and multiplication are in the nim sense explained in the text. Hamming codes and the binary Golay codes are lexieodes. Remarkably simple constructions are given for the Steiner systemsS(5,6,12)andS(5,8,24). Several record-breaking constant weight codes are also constructed.

A lower bound is proposed for the mean-squared error of ann-dimensional vector quantizer with a large number of output points.

It is an interesting open question whether a self-dual quaternary(24,12,10)codeCexists. It was shown by Conway and Pless that the only primes which can be orders of permutations in the group ofCare 11, 7, and 3. In this correspondence we eliminate 11 and 7 not only as permutations but also as orders of monomials in the group ofC. This is done by reducing the problems to the consideration of several codes and finding low weight vectors in these codes.

In an earlier paper the authors described a very fast method which, for the root latticesA_{n}, D_{n}, E_{n}, their duals and certain other lattices, finds the closest lattice point to an arbitrary point of the underlying space. If the lattices are used as codes for a Gaussian channel, the algorithm provides a fast decoding procedure, or if they are used as vector quantizers the algorithm performs the analog-to-digital conversion efficiently. The present paper offers a solution to the inverse problem for the same lattices (the encoding problem for channel codes or the digital-to-analog part of quantizing), namely, given an integerk, to find the kth code vector, and to the closely related problem of finding the indexkof a given code vector.

If a point is picked at random inside a regular simplex, octahedron,600-cell, or other polytope, what is its average squared distance from the centroid? Inn-dimensional space, what is the average squared distance of a random point from the closest point of the latticeA_{n}(orD_{n}, E_{n}, A_{n}^{\ast} or D_{n}^{\ast})?The answers are given here, together with a description of the Voronoi (or nearest neighbor) regions of these lattices. The results have applications to quantization and to the design of signals for the Gaussian channel. For example, a quantizer based on the eight-dimensional lattice E8 has a mean-squared error per symbol of0.0717 \cdotswhen applied to uniformly distributed data, compared with0.08333 \cdotsfor the best one-dimensional quantizer.

For each of the latticesA_{n}(n \geq 1), D_{n}(n \geq 2), E_{6}, E_{7}, E_{8}, and their duals a very fast algorithm is given for finding the closest lattice point to an arbitrary point. If these lattices are used for vector quantizing of uniformly distributed data, the algorithm finds the minimum distortion lattice point. If the lattices are used as codes for a Gaussian channel, the algorithm performs maximum likelihood decoding.

All self-dual codes over GF(3) and GF(4) of length 16 are found. The self-dual codes of shorter length are described in a concise and systematic notation. A number of new techniques ("promotion" and "demotion," "tag olng? and "subtraction") are given for constructing codes. Finally, several new extremal self-dual codes are given which have length greater than 16.