A cylinder anchored at two distinct points of the lattice Znis called a strut if its interior does not contain a lattice point. We address the problem of constructing struts of maximal radius in Zn. Our main result is a general construction technique, which we call the lifting construction, which produces a sequence of struts that are optimal in the limit. We also tighten a previous result of ours - an achievable lower bound on the volume of a strut. The problem is motivated by a nonlinear analog communication problem. We demonstrate, through simulation, improvements in performance that are obtained using our construction.

We present a novel technique for encoding and decoding constant weight binary vectors that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and then analyze its complexity. The complexity depends on the weight of the vector, rather than on the block length as in other algorithms. This approach is advantageous when the weight is smaller than the square root of the block length.

We present a novel technique for encoding and decoding constant weight binary codes that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and analyze its complexity. The complexity of the proposed algorithm depends on the weight of the code, rather than on the block length as in previous algorithms. This approach is advantageous when the weight is smaller than the square root of the block length.

Two subspaces of a vector space are here called "nonintersecting" if they meet only in the zero vector. Motivated by the design of noncoherent multiple-antenna communications systems, we consider the following question. How many pairwise nonintersecting M/sub t/-dimensional subspaces of an m-dimensional vector space V over a field F can be found, if the generator matrices for the subspaces may contain only symbols from a given finite alphabet A/spl sube/F? The most important case is when F is the field of complex numbers C; then M/sub t/ is the number of antennas. If A=F=GF(q) it is shown that the number of nonintersecting subspaces is at most (q/sup m/-1)/(q/sup Mt/-1), and that this bound can be attained if and only if m is divisible by M/sub t/. Furthermore, these subspaces remain nonintersecting when "lifted" to the complex field. It follows that the finite field case is essentially completely solved. In the case when F=C only the case M/sub t/=2 is considered. It is shown that if A is a PSK-configuration, consisting of the 2/sup r/ complex roots of unity, the number of nonintersecting planes is at least 2/sup r(m-2)/ and at most 2/sup r(m-1)-1/ (the lower bound may in fact be the best that can be achieved).

This paper describes the construction of codewords and subspaces are nonintersecting over the finite field. When the alphabet is a finite field, constructions are lifted to the complex field to obtain maximal diversity differential space-time codes for the noncoherent multiple antenna problems. The construction of codewords (i.e. nonintersecting subspaces) subjects to the constraint that the elements of the codewords use symbols from a fixed, small PSK constellation.

A preliminary report on our investigations into the existence of spherical t-designs on the unit sphere /spl Omega//sub 4/ in 4-dimensional Euclidean space. Tables are given of the putatively best t-designs with up to 100 points. Some general constructions are proposed and explicit constructions are given for N-point strength t designs with N=4p and t=min{p-1,5}, N=6p and t=min{p-1,7}, and N=12p and t=min{p-1,11}, for all p /spl ges/ 1.

Good codes for transmitting a continuous-alphabet source over an AWGN channel can be constructed using simple dynamical systems. The trajectories of the dynamical systems that we consider are curves in /spl Ropf//sup N/, and we use these curves as signal sets for a modulation system. In this paper we consider the problem of choosing the parameters of the dynamical system such that the length of its trajectory is maximized subject to a constraint on the minimum distance between its "folds". We provide some general results on the construction of such curves and show how to select the parameters optimally in the case N=6. This is done by reducing the problem to one of choosing a vector (1, a, b) in /spl Zopf//sup 3/ for which a high packing density is obtained for the lattice /spl Lambda//sub p/ obtained by projecting /spl Zopf//sup 3/ into the plane orthogonal to (1, a, b). Two approaches are used to prove the central result of the paper.

We consider the design of asymmetric multiple description lattice quantizers that cover the entire spectrum of the distortion profile, ranging from symmetric or balanced to successively refinable. We present a solution to a labeling problem, which is an important part of the construction, along with a general design procedure. The high-rate asymptotic performance of the quantizer is also studied. We evaluate the rate-distortion performance of the quantizer and compare it to known information-theoretic bounds. The high-rate asymptotic analysis is compared to the performance of the quantizer.

We consider Zador's (1963, 1966, 1982) asymptotic formula for the distortion-rate function for a variable-rate vector quantizer in the high-rate case. This formula involves the differential entropy of the source, the rate of the quantizer in bits per sample, and a coefficient G which depends on the geometry of the quantizer but is independent of the source. We give an explicit formula for G in the case when the quantizing regions form a periodic tiling of n-dimensional space, in terms of the volumes and second moments of the Voronoi cells. As an application we show, extending earlier work of Kashyap and Neuhoff (see ibid, vol.47, p.2538-2383, 2001) that even a variable-rate three-dimensional quantizer based on the "A15" structure is still inferior to a quantizer based on the body-centered cubic lattice. We also determine the smallest covering radius of such a structure.

The performance of a turbo code with short block length depends critically on the interleaver design. There are two major criteria in the design of an interleaver: the distance spectrum of the code and the correlation between the information input data and the soft output of each decoder corresponding to its parity bits. This paper describes a new interleaver design for turbo codes with short block length based on these two criteria. A deterministic interleaver suitable for turbo codes is also described. Simulation results compare the new interleaver design to different existing interleavers.

The problem of designing a multiple-description vector quantizer with lattice codebook /spl Lambda/ is considered. A general solution is given to a labeling problem which plays a crucial role in the design of such quantizers. Numerical performance results are obtained for quantizers based on the lattices A/sub 2/ and Z/sup i/, i=1, 2, 4, 8, that make use of this labeling algorithm. The high-rate squared-error distortions for this family of L-dimensional vector quantizers are then analyzed for a memoryless source with probability density function (PDF) p and differential entropy h(p)

We consider the design of asymmetric multiple description lattice quantizers that cover the entire spectrum of the distortion profile, ranging from symmetric or balanced to successively refinable. We present a solution to a labeling problem, which is an important part of the construction, along with a general design procedure. This procedure is illustrated using a ZZ/sup 2/ lattice. We also evaluate its rate-distortion performance and compare it to known information theoretic bounds.

The performance of a Turbo code depends on the interleaver design. There are two major criteria that can be considered in the design of an interleaver. Distance spectrum properties of the code and the correlation of the extrinsic information with the input data are the two major criteria in designing an interleaver. This paper describes a new interleaver design based on these two criteria. Simulation results compare the new interleaver design to different existing interleavers. The distance spectrum properties of the Turbo code are compared for different interleaver choices. A new solution to the interleaver edge effects is proposed here.

We consider the problem of designing a lattice-based multiple description vector quantizer for a two-channel diversity system. The design of such a quantizer can be reduced to the problem of assigning pair labels to points of a vector quantizer codebook. A general labeling procedure based on the structure of the lattice is presented, along with detailed results for the hexagonal lattice: algorithms, asymptotic performance, and numerical simulations. Asymptotically, when compared with the lattice Z, the resulting quantizer achieves the standard second-moment gain of the hexagonal lattice for the central distortion, and, surprisingly, achieves the two-dimensional sphere gain for the side distortion.

Upper and lower bounds are presented for the maximal possible size of mixed binary/ternary error-correcting codes. A table up to length 13 is included. The upper bounds are obtained by applying the linear programming bound to the product of two association schemes. The lower bounds arise from a number of different constructions.

The problem of finding quantum error correcting codes is transformed into the problem of finding additive codes over the field GF(4) which are self-orthogonal with respect to a certain trace inner product. Many new codes and new bounds are presented, as well as a table of upper and lower bounds on such codes of length up to 30 qubits.

The 12-dimensional Coxeter-Todd lattice can be obtained by lifting the ternary Golay code to a code over the integers mod 9 and applying Construction A.

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z/sub 4/, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z/sub 4/ domain implies that the binary images have dual weight distributions. The Kerdock and "Preparata" codes are duals over Z/sub 4/-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and "Preparata" codes are Z/sub 4/-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z/sub 4/, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the "Preparata" code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z/sub 4/, but extended Hamming codes of length n/spl ges/32 and the Golay code are not. Using Z/sub 4/-linearity, a new family of distance regular graphs are constructed on the cosets of the "Preparata" code.>

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.>

A table of binary constant weight codes of length n>

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).>

Let G be the automorphism group of the four-dimensional cube, a group of order $2^4 \cdot 4! = 384$. The binary codes associated with the 32-dimensional permutation representation of G on the edges of the cube are investigated. There are about 400 such codes, one of which is a $[32, 17, 8]$ code, having twice as many codewords as the $[32, 16, 8]$ extended quadratic residue code.

Any code C with covering radius R must satisfy a set of linear inequalities that involve the Lloyd polynomial L/sub R/(x); these generalize the sphere bound. Syndrome graphs associated with a linear code C are introduced to help keep track of low-weight vectors in the same coset of C (if there are too many such vectors C cannot exist). Illustrations show that t(17, 10)=3 and t(23, 15)=3 where t(n, k) is the smallest covering radius of any (n, k) code.>

A new technique is proposed for constructing trellis codes. which provides an alternative to Ungerboeck's method of "set partitioning." The new codes use a signal constellation consisting of points from ann-dimensional lattice\Lambda, with an equal number of points from each coset of a sublattice\Lambda '. One part of the input stream drives a generalized convolutional code whose outputs are cosets of\Lambda ', while the other part selects points from these cosets. Several of the new codes are better than those previously known.

A new class of codes for data compression is described that combines permutations with the fast Hadamard transform (FHT). It was invented for digital speech compression based on linear predictive coding (LPC), but may be useful for other data compression applications. One particular code with rate\frac{1}{2}is considered: a16-bit code for a block length of32samples. All coding and decoding steps are fast, so that real-time applications with cheap hardware can be anticipated.

An 8-state trellis code is described that uses a signal constellation from the 8-dimensional Gosset lattice E8. It can be used for example to transmit data at 9.6, 14.4, and 19.2 kbits/s with a nominal coding gain of close to 6 dB.

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) \leq K(n, R)holds for sufficiently largen.

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.

The Berlekamp–Massey algorithm takes a sequence of elements from a field and finds the shortest linear recurrence (or linear feedback shift register) that can generate the sequence. In this paper we extend the algorithm to the case when the elements of the sequence are integers modulo m, where m is an arbitrary integer with known prime decomposition.

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

The covering radius is given for all binary cyclic codes of length less than or equal to31. Many of these codes are optimal in the sense of having the smallest possible covering radius of any linear code of that length and dimension.

The covering radiusRof a code is the maximal distance of any vector from the code. This work gives a number of new results concerningt[n, k], the minimal covering radius of any binary code of lengthnand dimensionk. For examplet[n, 4]andt[n, 5]are determined exactly, and reasonably tight bounds ont[n, k]are obtained for anykwhennis large. These results are found by using several new constructions for codes with small covering radius. One construction, the amalgamated direct sum, involves a quantity called the norm of a code. Codes with norm\leq 2 R + 1are called normal, and may be combined efficiently. The paper concludes with a table giving bounds ont[n, k]forn \leq 64.

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.

It is shown that if the automorphism group of a binary self-dual code satisfies a certain condition then the code contains words of weight congruent to2modulo4. In particular, no cyclic binary self-dual code can have all its weights divisible by four. The number of cyclic binary self-dual codes of length n is determined, and the shortest nontrivial code in this class is shown to have length14.

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.

A partial classification is given of the self-dual codes of length 24 over GF (3). The main results are as follows: there are exactly two codes with minimum Hamming distanced=9; most of the codes haved=6and are indecomposable; one code withd=6has a trivial automorphism group (this is the first such self-dual code that has been found); the codes generated by the59inequivalent24 \times 24Hadamard matrices have been investigated and there appear to be only nine inequivalent codes (two withd=9and seven withd=6); and in all there are27decomposable codes, at least96indecomposable codes withd=6, and the total number of inequivalent codes is at least140.

The theta function of a sphere packing gives the number of centers at each distance from the origin. The theta functions of a number of important packings (A_{n},D_{n},E_{n}, the Leech lattice, and others) and tables of the first fifty or so of their coefficients are given in this paper.

LetA(n,2\delta,w)denote the maximum number of codewords in any binary code of lengthn, constant weightw, and Hamming distance2\deltaSeveral lower bounds forA(n,2\delta,w)are given. Forwand\deltafixed,A(n,2\delta,w) \geq n^{W-\delta+l}/w!andA(n,4,w)\sim n^{w-l}/w!asn \rightarrow \infty. In most cases these are better than the "Gilbert bound." Revised tables ofA(n,2 \delta,w)are given in the rangen \leq 24and\delta \leq 5.

Self-orthogonal ternary codes of minimum weight3may be analyzed in a straightforward manner using the theory of glueing introduced in earlier papers. The present paper describes a method for studying codes of minimum weight6: the supports of the words of weight6form what is called a center set. Associated with each center set is a graph, and all the graphs that can arise in this way are known. These techniques are used to classify the ternary self-dual codes of length20: there are24inequivalent codes,17of which are indecomposable. Six of the codes have minimum weight6.

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.

Improved bounds forA(n,d), the maximum number of codewords in a (linear or nonlinear) binary code of word lengthnand minimum distanced, and forA(n,d,w), the maximum number of binary vectors of lengthn, distanced, and constant weightwin the rangen \leq 24andd \leq 10are presented. Some of the new values areA

The weight enumerator of a code is the polynomial \begin{equation} W(x,y)= \sum_{r=0}^n A_r x^{n-r} y^r, \end{equation} wherendenotes the block length andA_r, denotes the number of codewords of weightr. LetCbe a self-dual code overGF(q)in which every weight is divisible byc. Then Gleason's theorem states that 1) ifq= 2 andc= 2, the weight enumerator ofCis a sum of products of the polynomialsx^2 + y^2andx^2y^2 (x^2 - y^2 )^2ifq= 2 andc= 4, the weight enumerator is a sum of products ofx^8 + 14x^4 y^4 + y^8andx^4 y^4 (x^4 - y^4)^4; and 3) ifq= 3 andc= 3, the weight enumerator is a sum of products ofx^4 + 8xy^3andy^3(x^3 - y^3)^3. In this paper we give several proofs of Gleason's theorem.

Gleason has recently shown that the weight enumerators of binary and ternary self-dual codes are polynomials in two given polynomials. In this paper it is shown that classical invariant theory permits a straightforward and systematic proof of Gleason's theorems and their generalizations. The joint weight enumerator of two codes (analogous to the joint density function of two random variables) is defined and shown to satisfy a MacWilliams theorem. Invariant theory is then applied to generalize Gleason's theorem to the complete weight enumerator of self-dual codes overGF(3), the Lee metric enumerator overGF(5)(given by Klein in 1884!) and overGF(7)(given by Maschke in 1893!), the Hamming enumerator overGF(q), and overGF(4)with all weights divisible by 2, the joint enumerator of two self-dual codes overGF(2), and a number of other results.

In this paper constructions are given for combining two, three, or four codes to obtain new codes. The Andryanov-Saskovets construction is generalized. It is shown that the Preparata double-error-correcting codes may be extended by about (block length)^{1/2}symbols, of which only one is a check symbol, and thate-error-correcting BCH codes may sometimes be extended by (block !ength)^{1/e}symbols, of which only one is a check symbol. Several new families of linear and nonlinear double-error-correcting codes are obtained. Finally, an infinite family of linear codes is given withd/n = \frac{1}{3}, the first three being the(24,2^12, 8)Golay code, a(48,2^15, 16)code, and a(96,2^18, 32)code. Most of the codes given have more codewords than any comparable code previously known to us.

In this paper, we establish the following result. Theorem:A_i, the number of codewords of weightiin the second-order binary Reed-Muller code of length2^mis given byA_i = 0unlessi = 2^{m-1}or2^{m-1} \pm 2^{m-l-j}, for somej, 0 \leq j \leq [m/2], A_0 = A_{2^m} = 1, and \begin{equation} \begin{split} A_{2^{m-1} \pm 2^{m-1-j}} = 2^{j(j+1)} &\{\frac{(2^m - 1) (2^{m-1} - 1 )}{4-1} \} \\ .&\{\frac{(2^{m-2} - 1)(2^{m-3} -1)}{4^2 - 1} \} \cdots \\ .&\{\frac{(2^{m-2j+2} -1)(2^{m-2j+1} -1)}{4^j -1} \} , \\ & 1 \leq j \leq [m/2] \\ \end{split} \end{equation} \begin{equation} A_{2^{m-1}} = 2 \{ 2^{m(m+1)/2} - \sum_{j=0}^{[m/2]} A_{2^{m-1} - 2^{m-1-j}} \}. \end{equation}

A construction is given that combines an(n, M_1, d_1)code with an(n, M_2, d_2 = [\frac{1}{2}(d_1 + 1)])code to form a(2n, M_1 M_2, d_1)code. This is used to construct a new family of nongroup single-error correcting codes of all lengthsnfrom2^mto 3 ·2^{m-1} - 1, for everym \geq 3. These codes have more codewords than any group code of the same length and minimum distance. A number of other nongroup codes are also obtained. Examples of the new codes are (16,2560,3) and (16,36,7) codes, both having more codewords than any comparable group code.