This paper is mainly a semi-tutorial introduction to elementary algebraic topology and its applications to Ising-type models of statistical physics, using graphical models of linear and group codes. It contains new material on systematic (n, k) group codes and their information sets; normal realizations of homology and cohomology spaces; dual and hybrid models; and connections with system-theoretic concepts, such as observability, controllability, and input/output realizations.

The Conti-Boston factorization theorem (CBFT) for linear tail-biting trellis realizations is extended to group realizations with a new and simpler proof, based on a controller granule decomposition of the behavior and known controllability results for group realizations. Further controllability results are given; e.g., a trellis realization is controllable if and only if its top (controllability) granule is trivial.

This paper develops a fundamental theory of realizations of linear and group codes on general graphs using elementary group theory, including basic group duality theory. Principal new and extended results include: normal realization duality; analysis of systems-theoretic properties of fragments of realizations and their connections; minimal Leftrightarrow trim and proper theorem for cycle-free codes; results showing that all constraint codes except interface nodes may be assumed to be trim and proper, and that the interesting part of a cyclic realization is its 2-core; notions of observability and controllability for fragments, and related tests; and relations between state-trimness and controllability, and dual state-trimness and observability.

This paper investigates properties of realizations of linear or group codes on general graphs that lead to local reducibility. Trimness and properness are dual properties of constraint codes. A linear or group realization with a constraint code that is not both trim and proper is locally reducible. A linear or group realization on a finite cycle-free graph is minimal if and only if every local constraint code is trim and proper. A realization is called observable if there is a one-to-one correspondence between codewords and configurations, and controllable if it has independent constraints. A linear or group realization is observable if and only if its dual is controllable. A simple counting test for controllability is given. An unobservable or uncontrollable realization is locally reducible. Parity-check realizations are controllable if and only if they have independent parity checks. In an uncontrollable tail-biting trellis realization, the behavior partitions into disconnected sub-behaviors, but this property does not hold for nontrellis realizations. On a general graph, the support of an unobservable configuration is a generalized cycle.

This paper investigates tail-biting trellis realizations for linear block codes. Intrinsic trellis properties are used to characterize irreducibility on given intervals of the time axis. It proves beneficial to always consider the trellis and its dual simultaneously. A major role is played by trellis properties that amount to observability and controllability of trellis fragments of various lengths. For fragments of length less than the minimum span length of the code it is shown that fragment observability and fragment controllability are equivalent to irreducibility. For reducible trellises, a constructive reduction procedure is presented. The considerations also lead to a characterization for when the dual of a trellis allows a product factorization into elementary (“atomic”) trellises.

This paper is concerned with the local reducibility properties of linear realizations of codes on finite graphs. Trimness and properness are dual properties of constraint codes. A linear realization is locally reducible if any constraint code is not both trim and proper. On a finite cycle-free graph, a linear realization is minimal if and only if every constraint code is both trim and proper. A linear realization is called observable if it is one-to-one, and controllable if all constraints are independent. Observability and controllability are dual properties. An unobservable or uncontrollable realization is locally reducible. A parity-check realization is uncontrollable if and only if it has redundant parity checks. A tail-biting trellis realization is uncontrollable if and only if its trajectories partition into disconnected subrealizations. General graphical realizations do not share this property.

It is shown that a trellis realization can be locally reduced if it is not state-trim, branch-trim, proper, observable, and controllable. These conditions are not sufficient for local irreducibility. Making use of notions that amount to “almost unobservability/uncontrollability”, a necessary and sufficient criterion of local irreducibility for tail-biting trellises is presented.

Given a discrete-time linear systemC, a shortest basis forCis a set of linearly independent generators forCwith the least possible lengths. A basisBis a shortest basis if and only if it has the predictable span property (i.e., has the predictable delay and degree properties, and is non-catastrophic), or alternatively if and only if it has the subsystem basis property (for any intervalJ, the generators inBwhose span is inJis a basis for the subsystemCJ). The dimensions of the minimal state spaces and minimal transition spaces ofCare simply the numbers of generators in a shortest basisBthat are active at any given state or symbol time, respectively. A minimal linear realization forCin controller canonical form follows directly from a shortest basis forC, and a minimal linear realization forCin observer canonical form follows directly from a shortest basis for the orthogonal systemC⊥. This approach seems conceptually simpler than that of classical minimal realization theory.

A conceptual framework involving partition functions of normal factor graphs is introduced, paralleling a similar recent development by Al-Bashabsheh and Mao. The partition functions of dual normal factor graphs are shown to be a Fourier transform pair, whether or not the graphs have cycles. The original normal graph duality theorem follows as a corollary. Within this framework, MacWilliams identities are found for various local and global weight generating functions of general group or linear codes on graphs; this generalizes and provides a concise proof of the MacWilliams identity for linear time-invariant convolutional codes that was recently found by Gluesing-Luerssen and Schneider. Further MacWilliams identities are developed for terminated convolutional codes, particularly for tail-biting codes, similar to those studied recently by Bocharova, Hug, Johannesson, and Kudryashov.

Shearer and McEliece showed that there is no MacWilliams identity for the free distance spectra of orthogonal linear convolutional codes. We show that on the other hand there does exist a MacWilliams identity between the generating functions of the weight distributions per unit time of a linear convolutional code C and its orthogonal code C⊥, and that this distribution is as useful as the free distance spectrum for estimating code performance. These observations are similar to those made recently by Bocharova et al.; however, we focus on terminating by tail-biting rather than by truncation.

Starting from Shannon's celebrated 1948 channel coding theorem, we trace the evolution of channel coding from Hamming codes to capacity-approaching codes. We focus on the contributions that have led to the most significant improvements in performance versus complexity for practical applications, particularly on the additive white Gaussian noise channel. We discuss algebraic block codes, and why they did not prove to be the way to get to the Shannon limit. We trace the antecedents of today's capacity-approaching codes: convolutional codes, concatenated codes, and other probabilistic coding schemes. Finally, we sketch some of the practical applications of these codes.

Rate-(n-2)/n unrestricted and CSS-type quantum convolutional codes with up to 4096 states and minimum distances up to 10 are constructed as stabilizer codes from classical self-orthogonal rate-1/n F4-linear and binary linear convolutional codes, respectively. These codes generally have higher rate and less decoding complexity than comparable quantum block codes or previous quantum convolutional codes. Rate-(n-2)/n block stabilizer codes with the same rate and error-correction capability and essentially the same decoding complexity are derived from these convolutional codes via tail-biting

Simple rate-1/3 single-error-correcting unrestricted and CSS-type quantum convolutional codes are constructed from classical self-orthogonal F4-linear and F2-linear convolutional codes, respectively. These quantum convolutional codes have higher rate than comparable quantum block codes or previous quantum convolutional codes, and are simple to decode. A block single-error-correcting [9,3,3] tail-biting code is derived from the unrestricted convolutional code, and similarly a [15,5,3] CSS-type block code from the CSS-type convolutional code

Ever since the first dial-up modems appeared in the 1960s, their obsolescence has been repeatedly predicted. However, contrary to such predictions, dial-up modems thrived in the 1980s and 1990s as a result of the slow rollout of residential digital services and the unprecedented growth of internet and remote access. Since the first 300 b/s dial-up modem standard (V.21), modem speeds have increased steadily. Most recently, International Telecommunications Union (ITU) Recommendation V.90 (1998) takes advantage of the direct digital-network connection of an internet service provider (ISP) remote-access server to achieve speeds of more than 50 kb/s downstream (from ISP to a user). However, for upstream transmission (from a user to ISP), V.90 employs the older V.34 modulation (1994), which typically delivers on the order of 30 kb/s. A new ITU modem standard called V.92 increases upstream rates to above 40 kb/s, again by taking advantage of pulse code modulation connections. In this paper, we present the transmission scheme that has been adopted for V.92. It involves a generalization of Tomlinson-Harashima precoding. We predict that V.92 will be the last dial-up modem standard. However, we have to wonder whether we might be falling into the same trap into which many others have fallen in the past. The future will be the judge!.

Fundamental results concerning the dynamics of abelian group codes (behaviors) and their duals are developed. Duals of sequence spaces over locally compact abelian (LCA) groups may be defined via Pontryagin duality; dual group codes are orthogonal subgroups of dual sequence spaces. The dual of a complete code or system is finite, and the dual of a Laurent code or system is (anti-)Laurent. If C and C/sup /spl perp// are dual codes, then the state spaces of C act as the character groups of the state spaces of C/sup /spl perp//. The controllability properties of C are the observability properties of C/sup /spl perp//. In particular, C is (strongly) controllable if and only if C/sup /spl perp// is (strongly) observable, and the controller memory of C is the observer memory of C/sup /spl perp//. The controller granules of C act as the character groups of the observer granules of C/sup /spl perp//. Examples of minimal observer-form encoder and syndrome-former constructions are given. Finally, every observer granule of C is an "end-around" controller granule of C.

Behavioral realizations of linear codes or systems usually involve observed variables, hidden variables (states), and constraints. We study realizations that also involve syndrome variables, which are hidden variables that must equal zero in any valid trajectory. Syndrome realizations arise naturally in parity-check or transform realizations of codes, and more generally as duals of state realizations. The dual of a syndrome realization has a nice form in which state and syndrome variables trade places. On the other hand, it is shown that syndrome realizations are essentially the same as the restricted state realizations of Forney, G.D., Jr. (see IEEE Trans. Inf. Theory, vol.47, p.520-48, 2001), which, in some respects, appear to be more fundamental.

Cycle-free graphical realizations of linear codes generalize trellis realizations. Given a linear code C and a cycle-free graph topology, there exists a well-defined minimal realization for C on that graph in which each constraint is a linear code with a well-defined length and dimension. The constraint complexity of the realization is defined as maximum dimension of any constraint code. There exists a graph that minimizes constraint complexity in which all internal nodes have degree 3 and all interface nodes have degree 2, and which moreover can be put in the form of a "tree-structured trellis realization." The constraint complexity of a general cycle-free graph realization can be less than that of any conventional trellis realization, but not by very much. Such realizations can yield reductions in decoding complexity even when they do not reduce constraint complexity.

Minimum distances, distance distributions, and error exponents on a binary-symmetric channel (BSC) are given for typical codes from Shannon's random code ensemble and for typical codes from a random linear code ensemble. A typical random code of length N and rate R is shown to have minimum distance N/spl delta//sub GV/(2R), where /spl delta//sub GV/(R) is the Gilbert-Varshamov (GV) relative distance at rate R, whereas a typical linear code (TLC) has minimum distance N/spl delta//sub GV/(R). Consequently, a TLC has a better error exponent on a BSC at low rates, namely, the expurgated error exponent.

Tight frames and rank-one quantum measurements are shown to be intimately related. In fact, the family of normalized tight frames for the space in which a quantum-mechanical system lies is precisely the family of rank-one generalized quantum measurements on that space. Using this relationship, frame-theoretical analogs of various quantum-mechanical concepts and results are developed. The analog of a least-squares quantum measurement is a tight frame that is closest in a least-squares sense to a given set of vectors. The least-squares tight frame is found for both the case in which the scaling of the frame is specified (constrained least-squares frame (CLSF)) and the case in which the scaling is chosen to minimize the least-squares error (unconstrained least-squares frame (ULSF)). The well-known canonical frame is shown to be proportional to the ULSF and to coincide with the CLSF with a certain scaling.

We consider the problem of constructing measurements optimized to distinguish between a collection of possibly nonorthogonal quantum states. We consider a collection of pure states and seek a positive operator-valued measure (POVM) consisting of rank-one operators with measurement vectors closest in squared norm to the given states. We compare our results to previous measurements suggested by Peres and Wootters (1991) and Hausladen et al. (1996), where we refer to the latter as the square-root measurement (SRM). We obtain a new characterization of the SRM, and prove that it is optimal in a least-squares sense. In addition, we show that for a geometrically uniform state set the SRM minimizes the probability of a detection error. This generalizes a similar result of Ban et al. (see Int. J. Theor. Phys., vol.36, p.1269-88, 1997).

A generalized state realization of the Wiberg (1996) type is called normal if symbol variables have degree 1 and state variables have degree 2. A natural graphical model of such a realization has leaf edges representing symbols, ordinary edges representing states, and vertices representing local constraints. Such a graph can be decoded by any version of the sum-product algorithm. Any state realization of a code can be put into normal form without essential change in the corresponding graph or in its decoding complexity. Group or linear codes are generated by group or linear state realizations. On a cycle-free graph, there exists a well-defined minimal canonical realization, and the sum-product algorithm is exact. However, the cut-set bound shows that graphs with cycles may have a superior performance-complexity tradeoff, although the sum-product algorithm is then inexact and iterative, and minimal realizations are not well-defined. Efficient cyclic and cycle-free realizations of Reed-Muller (RM) codes are given as examples. The dual of a normal group realization, appropriately defined, generates the dual group code. The dual realization has the same graph topology as the primal realization, replaces symbol and state variables by their character groups, and replaces primal local constraints by their duals. This fundamental result has many applications, including to dual state spaces, dual minimal trellises, duals to Tanner (1981) graphs, dual input/output (I/O) systems, and dual kernel and image representations. Finally a group code may be decoded using the dual graph, with appropriate Fourier transforms of the inputs and outputs; this can simplify decoding of high-rate codes.

In the 50 years since Shannon determined the capacity of ergodic channels, the construction of capacity-approaching coding schemes has been the supreme goal of coding research. Finally today, we know of practical codes and decoding algorithms that can closely approach the channel capacity of some classical memoryless channels. It is a remarkable fact motivating this special issue that all known practical, capacity-approaching coding schemes are now understood to be codes defined on graphs, together with the associated iterative decoding algorithms.

A simple sphere bound gives the best possible tradeoff between the volume per point of an infinite array L and its error probability on an additive white Gaussian noise (AWGN) channel. It is shown that the sphere bound can be approached by a large class of coset codes or multilevel coset codes with multistage decoding, including certain binary lattices. These codes have structure of the kind that has been found to be useful in practice. Capacity curves and design guidance for practical codes are given. Exponential error bounds for coset codes are developed, generalizing Poltyrev's (1994) bounds for lattices. These results are based on the channel coding theorems of information theory, rather than the Minkowski-Hlawka theorem of lattice theory.

Tail-biting trellis representations of block codes are investigated. We develop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16-state 12-section structurally invariant tail-biting trellis for the (24, 12, 8) binary Golay code. This tail-biting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12-section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasi-cyclic representation of this code, which leads to a 64-state tail-biting trellis. Unwrapping this tail-biting trellis produces a periodically time-varying 16-state rate-1/2 "convolutional Golay code" with d=8, which has attractive performance/complexity properties. We furthermore show that the (6, 3, 4) quaternary hexacode has a minimal 8-state group tail-biting trellis, even though it has no such linear trellis over F/sub 4/. Minimal tail-biting trellises are also constructed for the (8, 4, 4) binary Hamming code, the (4, 2, 3) ternary tetracode, the (4, 2, 3) code over F/sub 4/, and the Z/sub 4/-linear (8. 4, 4) octacode.

Shannon's determination of the capacity of the linear Gaussian channel has posed a magnificent challenge to succeeding generations of researchers. This paper surveys how this challenge has been met during the past half century. Orthogonal minimum-bandwidth modulation techniques and channel capacity are discussed. Binary coding techniques for low-signal-to-noise ratio (SNR) channels and nonbinary coding techniques for high-SNR channels are reviewed. Recent developments, which now allow capacity to be approached on any linear Gaussian channel, are surveyed. These new capacity-approaching techniques include turbo coding and decoding, multilevel coding, and combined coding/precoding for intersymbol-interference channels.

A full-rank K/spl times/n matrix G(D) over the rational functions F(D) generates a rate R=k/n convolutional code C. G(D) is minimal if it can be realized with as few memory elements as any encoder for C, and G(D) is canonical if it has a minimal realization in controller canonical form. We show that G(D) is minimal if and only if for all rational input sequences u(D), the span of u(D)G(D) covers the span of u(D). Alternatively, G(D) is minimal if and only if G(D) is globally zero-free, or globally invertible. We show that G(D) is canonical if and only if G(D) is minimal and also globally orthogonal, in the valuation-theoretic sense of Monna (1970).

It is shown that multistage generalized minimum-distance (GMD) decoding of Euclidean-space codes and lattices can provide an excellent tradeoff between performance and complexity. We introduce a reliability metric for Gaussian channels that is easily computed from an inner product, and prove that a multistage GMD decoder using this metric is a bounded-distance decoder up to the true packing radius. The effective error coefficient of multistage GMD decoding is determined. Two simple modifications in the GMD decoding algorithm that drastically reduce this error coefficient are proposed. It is shown that with these modifications GMD decoding achieves the error coefficient of maximum-likelihood decoding for block codes and for generalized construction A lattices. Multistage GMD decoding of the lattices D/sub 4/, E/sub 8/, K/sub 12/, BW/sub 16/, and /spl Lambda//sub 24/ is investigated in detail. For K/sub 12/BW/sub 16/, and /spl Lambda//sub 24/, the GMD decoders have considerably lower complexity than the best known maximum-likelihood or bounded-distance decoding algorithms, and appear to be the most practically attractive decoders available. For high-dimensional codes and lattices (/spl ges/64 dimensions) maximum-likelihood decoding becomes infeasible, while GMD decoding algorithms remain quite practical. As an example, we devise a multistage GMD decoder for a 128-dimensional sphere packing with a nominal coding gain of 8.98 dB that attains an effective error coefficient of 1365760. This decoder requires only about 400 real operations, in addition to algebraic errors-and-erasures decoding of certain BCH and Hamming codes. It therefore appears to be practically feasible to implement algebraic multistage GMD decoders for high-dimensional sphere packings, and thus achieve high effective coding gains.

The minimum mean-squared-error decision-feedback equalizer (MMSE-DFE) has properties that suggest that it is a canonical equalization structure for systems that combine equalization with coded modulation. The structure and performance of the MMSE-DFE are succinctly derived using linear-estimation-theoretic principles in this first part of this two-part paper. The front-end of the MMSE-DFE, called the "mean-square whitened matched filter" (MS-WMF), is preferable in some ways to a matched filter or a whitened matched filter as a canonical receiver front end. In a coded system, the feedback filter of the MMSE-DFE may be implemented in the transmitter using precoding. The MMSE-DFE can perform significantly better than a zero-forcing decision-feedback equalizer, particularly at moderate-to-low SNR's and on severe-ISI channels. The MMSE-DFE is biased. The optimum unbiased MMSE-DFE is the MMSE-DFE with the bias removed. Removing bias improves error probability, but reduces the SNR to SNR/sub MMSE-DFE,U/=SNR/sub MMSE-DFE/-1. It is shown that this SNR relationship is a particular case of a very general result and that SNR/sub MMSE-DFE,U/ gives a more realistic estimate of SNR. The results are extended to partial response equalization and to equalization with correlated inputs in an appendix.>

For pt.I see ibid., vol.43, no.10, p.2582 (1995). The minimum-mean-squared-error decision-feedback equalizer (MMSE-DFE) has properties that suggest that it is a canonical equalization structure in systems that combine equalization with coded modulation. With a given symbol rate 1/T and transmit spectrum, the output signal-to-noise ratio SNR/sub MMSE-DFE,U/ of a MMSE-DFE with an unbiased decision rule is a single parameter that characterizes the channel for coding purposes. Indeed, the transmit spectrum that maximizes SNR/sub MMSE-DFE,U/ is the capacity-achieving (water-pouring) spectrum, and the capacity C(T) (in bits per two dimensions) is given by C(T)=log/sub 2/[1+SNR/sub MMSE-DFE,U/] regardless of the channel characteristics. The performance of a coded system with a MMSE-DFE equalization structure may be accurately estimated using the gain of the coding scheme at a given Pr(E). This performance is shown to be approximately the same as that of a multicarrier system using the same transmit spectrum and similar coding; such systems are known to be able to approach capacity arbitrarily closely. The MMSE-DFE can perform significantly better than a zero-forcing decision-feedback equalizer, particularly at moderate-to-low SNR's and on severe-ISI channels. Simulation results indicate that performance of the MMSE-DFE is surprisingly insensitive to transmit spectral shaping, as long as the transmit spectrum exceeds the capacity-achieving band, but that there is an optimal symbol rate that should (approximately) be used.>

This semi-tutorial paper discusses the connections between the dimension/length profile (DLP) of a linear code, which is essentially the same as its "generalized Hamming weight hierarchy", and the complexity of its minimal trellis diagram. These connections are close and deep. DLP duality is closely related to trellis duality. The DLP of a code gives tight bounds on its state and branch complexity profiles under any coordinate ordering; these bounds can often be met. A maximum distance separable (MDS) code is characterized by a certain extremal DLP, from which the main properties of MDS codes are easily derived. The simplicity and generality of these interrelationships are emphasized.>

The density/length profile (DCP) of a lattice /spl Lambda/ is analogous to the dimension/length profile of a linear code. The DLP is a geometrical invariant of /spl Lambda/ that includes the coding gain of /spl Lambda/. Duality results analogous to those of linear block codes are derived for lattices. Bounds on the DLP may be derived from bounds on Hermite's constants; these hold with equality for many dense lattices. In turn, the DLP lowerbounds the state complexity profile of a minimal trellis diagram for /spl Lambda/ in any coordinate system. It is shown that this bound can be met for the E/sub 8/ lattice by a laminated lattice construction with a novel trellis diagram. Bounds and constructions for other important low-dimensional lattices are given. Two laminated lattice constructions of the Leech lattice yield trellis diagrams with maximum state space sizes 1024 and 972.>

High-rate lattice and trellis quantizers for nonuniform sources are introduced and analyzed. The performance of these quantizers is determined by two separable quantities, the granular gain and the boundary gain, which are determined by the shapes of the granular cells and of the support region, respectively. The granular gain and boundary gain are the duals of shaping and coding gain in data transmission applications. Using this duality, it is shown for Gaussian sources that the ultimate achievable boundary gain with high-rate lattice-bounded lattice codebooks is the same as the ultimate gain that can be obtained from variable-rate entropy coding. It is observed that if lattice codebooks can achieve the ultimate granular gain of 0.255 b per dimension, then lattice-bounded lattice codebooks can approach the rate-distortion limit. The performance of lattice quantizers is compared to that of optimum vector quantizers.>

A group code C over a group G is a set of sequences of group elements that itself forms a group under a component-wise group operation. A group code has a well-defined state space Sigma /sub k/ at each time k. Each code sequence passes through a well-defined state sequence. The set of all state sequences is also a group code, the state code of C. The state code defines an essentially unique minimal realization of C. The trellis diagram of C is defined by the state code of C and by labels associated with each state transition. The set of all label sequences forms a group code, the label code of C, which is isomorphic to the state code of C. If C is complete and strongly controllable, then a minimal encoder in controller canonical (feedbackfree) form may be constructed from certain sets of shortest possible code sequences, called granules. The size of the state space Sigma /sub k/ is equal to the size of the state space of this canonical encoder, which is given by a decomposition of the input groups of C at each time k. If C is time-invariant and nu -controllable, then mod Sigma /sub k/ mod = Pi /sub 1>

On a linear Gaussian channel with intersymbol interference (ISI), trellis precoding is a method that achieves the equalization performance of Tomlinson-Harashima (TH) precoding, the coding gain of any known lattice-type coset code, and a considerable shaping gain. Trellis precoding may be viewed as a generalization of trellis shaping to Gaussian ISI channels, or, alternatively, as a generalization of TH precoding, with coded modulation that achieves shaping gain. With trellis precoding channel capacity can be approached essentially as closely on any strictly bandlimited, high signal-to-noise ratio Gaussian channel as on the ideal channel, using the same coding techniques. For first- and second-order FIR and IIR (finite and infinite impulse response) channels, it is shown that shaping gains close to 1 dB can be obtained with a two-dimensional four-state trellis code. Trellis precoding is quite practical whenever channel information is available at the transmitter.>

The author discusses trellis shaping, a method of selecting a minimum-weight sequence from an equivalence class of possible transmitted sequences by a search through the trellis diagram of a shaping convolutional code C/sub s/. Shaping gains on the order of 1 dB may be obtained with simple four-state shaping codes and with moderate constellation expansion. The shaping gains obtained with more complicated codes approach the ultimate shaping gain of 1.53 dB. With a feedback-free syndrome-former for C/sub s/, transmitted data can be recovered without catastrophic error propagation. Constellation expansion and peak-to-average energy ratio may be effectively limited by peak constraints. With lattice-theoretic constellations, the shaping operation may be characterized as a decoding of an initial sequence in a channel trellis code by a minimum-distance decoder for a shaping trellis code based on the shaping convolutional code, and the set of possible transmitted sequences is then the set of code sequences in the channel trellis code that lie in the Voronoi region of the trellis shaping code.>

Under certain mild conditions, the minimum Hamming distance D of an (N, K, D) group code C over a non-abelian group G is bounded by DN/2. Consequently, there exists no (N, K, N-K+1) group code C over an non-abelian group G if 1>

A signal space code C is defined as geometrically uniform if, for any two code sequences in C, there exists an isometry that maps one sequence into the other while leaving the code C invariant. Geometrical uniformity, a strong kind of symmetry, implies such properties as a) the distance profiles from code sequences in C to all other code sequences are all the same, and b) all Voronoi regions of code sequences in C have the same shape. It is stronger than Ungerboeck Zehavi-Wolf symmetry or Calderbank-Sloane regularity. Nonetheless, most known good classes of signal space codes are shown to be generalized coset codes, and therefore geometrically uniform, including (a) lattice-type trellis codes based on lattice partitions Lambda / Lambda ' such that Z/sup N// Lambda / Lambda '/4Z/sup N/ is a lattice partition chain, and (b) phase-shift-keying (PSK)-type trellis codes based on up to four-way partitions of a 2/sup n/-PSK signal set.>

For pt.I see ibid., vol.7, no.6, p.877-92 (1989). Voronoi constellations, also called Voronoi codes are implementable N-dimensional constellations based on partitions of N-dimensional lattices ( Lambda ) that can achieve good shape gains and that are inherently suited for use with coded modulation. Two methods are given for specifying Voronoi constellations on the basis of arbitrary lattice partitions Lambda / Lambda /sub s/, where Lambda /sub s/, the shaping lattice, is an N-dimensional sublattice of Lambda . One of the methods is conjectured to be optimum, and the other has desirable symmetries and naturally supports opportunistic secondary channels. When Lambda and Lambda /sub s/ are 2-D-symmetric, the constituent 2-D constellation is itself a Voronoi constellation. The shaping constellation expansion ratio and peak-to-average-power ratio are determined in general and for various Lambda /sub s/. Methods for labeling Voronoi constellations are given. Their complexity is shown to be dominated by that of decoding Lambda /sub s/. It is also shown that coding and shaping are separable and dual. Bounds on the shape gain of Voronoi constellations are given that depend on the depth and normalized informativity of Lambda /sub s/. These bounds suggest the use of lattices Lambda with depth 2 and normalized informativity less than 1, which can achieve near-optimal shape gains with reduced constellation expansion and implementation complexity.>

The authors discuss the major attributes desired in signal constellations, such as signal-to-noise ratio (SNR) efficiency, simplicity of mapping bits to points and vice versa, compatibility with coded modulation schemes, and compatibility with quadrature amplitude modulation (QAM). The capability of supporting a so-called opportunistic secondary channel, often used for internal control signaling, is considered. The gain in SNR efficiency of a multidimensional constellation (lattice code) consisting of the points from a lattice Lambda within a region R compared to a cubic constellation is shown to be approximately separable into the coding gain of Lambda and the shape gain of R, for large constellations. Similarly, the expansion of the associated constituent 2-D constellation is shown to be approximately separable into a constellation expansion ratio (CER) coding component CER/sub c/( Lambda ) and a shaping component CER/sub s/(R). The N sphere is the region R with the best shape gain, but N also has large constellation expansion. Bounds for the best possible shape gain versus CER/sub s/(R) or peak-to-average-power ratio (PAR) are given. Generalized cross constellations are discussed. These constellations yield a modest shape gain with very low CER/sub s/(R) or PAR, are easily implemented, are well suited for use with coded QAM modems, and can be readily adapted to support an opportunistic secondary channel.>

An algorithm is given that decodes the Leech lattice with not much more than twice the complexity of soft-decision decoding of the Golay code. The algorithm has the same effective minimum distance as maximum-likelihood decoding and increases the effective error coefficient by less than a factor or two. The algorithm can be recognized as a member of the class of multistage algorithms that are applicable to hierarchical constructions. It is readily generalized to lattices that can be expressed in terms of binary code formulas, and in particular to construction B lattices.>

Known coset codes are adapted for use on partial response channels or to generate signals with spectral nulls. By using coset precoding and running digital sum feedback, any desired tradeoff can be achieved between the power and spectra of the relevant sequences, up to the optimum tradeoff possible. A fundamental theorem specifying this optimum tradeoff is given. A maximum-likelihood-sequence-estimation (MLSE) decoder for the original code may be used for the adapted code, and such a decoder then attains the minimum squared distance of the original code. These methods sometimes generate codes with greater minimum squared distance than that of the original code; this distance can be attained by augmented decoders, although such decoders inherently require long decoding delays and may be subjected to quasi-catastrophic error propagation. The authors conclude that, at least for sequences supporting large numbers of bits per symbol, coset codes can be adapted to achieve effectively the same performance and complexity on partial response channels, or for sequences with spectral nulls, as they do in the ordinary memoryless case.>

Practically all known good constructive coding techniques for bandlimited channels, including lattice codes and various trellis-coded modulation schemes, can be characterized as coset codes. A coset code is defined by a lattice partition Lambda / Lambda ' and by a binary encoder C that selects a sequence of cosets of the lattice Lambda '. The fundamental coding gain of a coset code, as well as other important parameters such as the error coefficient, the decoding complexity, and the constellation expansion factor, are purely geometric parameters determined by C Lambda / Lambda '. The known types of coset codes, as well as a number of new classes that systematize and generalize known codes, are classified and compared in terms of these parameters.>

For pt.I see ibid., vol.34, no.5, p.1123-51 (1988). The family of Barnes-Wall lattices (including D/sub 4/ and E/sub 8/) of lengths N=2/sup n/ and their principal sublattices, which are useful in constructing coset codes, are generated by iteration of a simple construction called the squaring construction. The closely related Reed-Muller codes are generated by the same construction. The principal properties of these codes and lattices are consequences of the general properties of iterated squaring constructions, which also exhibit the interrelationships between codes and lattices of different lengths. An extension called the cubing construction generates good codes and lattices of lengths N=3*2/sup n/, including the Golay code and Leech lattice, with the use of special bases for 8-space. Another related construction generates the Nordstrom-Robinson code and an analogous 16-dimensional nonlattice packing. These constructions are represented by trellis diagrams that display their structure and interrelationships and that lead to efficient maximum-likelihood decoding algorithms. >

This paper attempts to present a comprehensive tutorial survey of the development of efficient modulation techniques for bandlimited channels, such as telephone channels. After a history of advances in commercial high-speed modems and a discussion of theoretical limits, it reviews efforts to optimize two-dimensional signal constellations and presents further elaborations of uncoded modulation. Its principal emphasis, however, is on coded modulation techniques, in which there is an explosion of current interest, both for research and for practical application. Both block-coded and trellis-coded modulation are covered, in a common framework. A few new techniques are presented.

The publication offers a note of thanks and lists its reviewers.

A linear correspondence is developed between the states of a rate-k/nconvolutional encoderGand the states of a corresponding syndrome formerH^T, whereHis an encoder of the code dual to the code generated byG. This correspondence is used to find an expression for the number of all-zero paths of length\tauin the code trellis; the answer depends only on the constraint lengths of the dual code. A partial answer to the resynchronization problem also falls out of this development.

A lower bound on the symbol error probability achieved by any estimator of a digital pulse-amplitude-modulated sequence in the presence of white Gaussian noise and intersymbol interference is presented. The bound reduces to the well-known single-pulse error probability bound when intersymbol interference is small, but is tighter when interference is large. For example, on the singlepole (RC) channel, the effective signal-to-noise ratio for any estimator is shown to decrease by at least 3 dB for every doubling in pulse rate T-1asT \rightarrow 0and, on the double-pole channel, by at least 9 dB, thus disproving a recent conjecture [2] on the performance of nonlinear receivers.

A maximum-likelihood sequence estimator for a digital pulse-amplitude-modulated sequence in the presence of finite intersymbol interference and white Gaussian noise is developed, The structure comprises a sampled linear filter, called a whitened matched filter, and a recursive nonlinear processor, called the Viterbi algorithm. The outputs of the whitened matched filter, sampled once for each input symbol, are shown to form a set of sufficient statistics for estimation of the input sequence, a fact that makes obvious some earlier results on optimum linear processors. The Viterbi algorithm is easier to implement than earlier optimum nonlinear processors and its performance can be straightforwardly and accurately estimated. It is shown that performance (by whatever criterion) is effectively as good as could be attained by any receiver structure and in many cases is as good as if intersymbol interference were absent. Finally, a simplified but effectively optimum algorithm suitable for the most popular partial-response schemes is described.

A convolutional encoder is defined as any constant linear sequential circuit. The associated code is the set of all output sequences resulting from any set of input sequences beginning at any time. Encoders are called equivalent if they generate the same code. The invariant factor theorem is used to determine when a convolutional encoder has a feedback-free inverse, and the minimum delay of any inverse. All encoders are shown to be equivalent to minimal encoders, which are feedback-free encoders with feedback-free delay-free inverses, and which can be realized in the conventional manner with as few memory elements as any equivalent encoder, Minimal encoders are shown to be immune to catastrophic error propagation and, in fact, to lead in a certain sense to the shortest decoded error sequences possible per error event. In two appendices, we introduce dual codes and syndromes, and show that a minimal encoder for a dual code has exactly the complexity of the original encoder; we show that systematic encoders with feedback form a canonical class, and compare this class to the minimal class.

An existing sequential decoding program can be easily modified to enumerate the number of low-weight codewords in a convolutional code, where weight is defined either over a decoding constraint length or "free." We tabulated several good rate one-half constraint-length 49 systematic codes that were obtained quickly with this procedure.

By an extension of Gallager's bounding methods, exponential error bounds applicable to coding schemes involving erasures, variable-size lists, and decision feedback are obtained. The bounds are everywhere the tightest known.

This paper discusses the use of two types of convolutional codes, diffuse threshold-decoded codes and Gallager codes, on channels with memory (burst channels). The operation of these codes is explained and test results are given for a variety of equipments operated over phone line, HF radio, and troposcatter channels. Error propagation in the threshold-decoded codes is discussed and, in the Appendix, we prove that, for one important diffuse code, propagation is finite and small.

We introduce a new distance measure which permits likelihood information to be used in algebraic minimum distance decoding techniques. We give an efficient decoding algorithm, and develop exponential bounds on the probability of not decoding correctly. In one application, this technique yields the same probability of error as maximum likelihood decoding.

The Gorenstein-Zierler decoding algorithm for BCH codes is extended, modified, and analyzed; in particular, we show how to correct erasures as well as errors, exhibit improved procedures for finding error and erasure values, and consider in some detail the implementation of these procedures in a special-purpose computer.