We focus on applications of low-rate Gallager (1963) (low-density parity-check) codes in code-division multiple-access schemes. The codes that we present here achieve good performance with relatively short frame-lengths in additive white Gaussian noise channels and, perhaps more importantly, in fading channels. These codes can be decoded with low complexity by using iterative decoding procedures. We present a construction that yields good short frame-length Gallager codes. Bounds on the frame-error probability for a maximum-likelihood decoder are obtained.

We focus our attention on Gallager codes with parameters compatible with the IS-95 cellular radio standard. We discuss low complexity software and hardware implementations of an iterative decoder for {N,-,3} Gallager codes. We estimate that by using Gallager codes, a factor of five improvement in the code-division multiple-access system capacity relative to an uncoded system can be achieved, equivalent to a factor of two improvement relative to state-of-the art orthogonal convolutional codes. Simulation results demonstrate the good performance of short-frame Gallager codes in the additive white Gaussian noise and certain fading channels.

It is known that spread-spectrum (SS) communications in general, and code-division multiple access (CDMA) in particular, gain certain advantages in performance, if powerful low-rate error-correcting codes are used for error-protection in such systems. We propose an innovative coding scheme for SS systems based on Gallager (low-density parity-check) codes that can be iteratively decoded with relatively low complexity. Consequently, this scheme is readily implementable in both base station and subscriber side receivers. We focus our attention on Gallager codes with parameters compatible with the IS-95 cellular radio standard. We discuss soft- and hardware implementations of iterative decoding for Gallager codes. We estimate that by using Gallager codes, a factor of five improvement in CDMA cell capacity relative to the uncoded system can be achieved, equivalent to a factor of two improvement relative to the state-of-the art orthogonal convolutional codes.

A sequential decoder for linear block codes that performs maximum-likelihood soft-decision decoding is described. The decoder uses a metric computed from a lower bound on the cost of the unexplored portion of the code tree. It is shown that for certain block codes the average computational complexity of this metric is superior to that of the Fano metric. A new function, the cumulative column distance function, is introduced for linear block codes. This function is an important factor that determines the average computational effort of a sequential decoder for a linear block code with an arbitrary maximum-likelihood metric. Simulation results show that a sequential decoder for linear block codes with a fast growing cumulative column distance function achieves a low computational complexity, a result analogous to that for convolutional codes.

The problem of minimizing the vertex count at a given time index in the trellis for a general (nonlinear) code is shown to be NP-complete. Examples are provided that show that (1) the minimal trellis for a nonlinear code may not be observable, i.e. some codewords may be represented by more than one path through the trellis and (2) minimizing the vertex count at one time index may be incompatible with minimizing the vertex count at another time index. A trellis produce is defined and used to construct trellises for sum codes. Minimal trellises for linear codes are obtained by forming the product of elementary trellises corresponding to the one-dimensional subcodes generated by atomic codewords. The structure of the resulting trellis is determined solely by the spans of the atomic codewords. A correspondence between minimal linear block code trellises and configurations of nonattacking rooks on a triangular chess board is established and used to show that the number of distinct minimal linear block code trellises is a Stirling number of the second kind. Various bounds on trellis size are reinterpreted in this context.