We develop a remarkably tight upper bound on the performance of a parameterized family of bounded angle maximum-likelihood (BA-ML) incomplete decoders. The new bound for this class of incomplete decoders is calculated from the codepsilas weight enumerator, and is an extension of Poltyrev-type bounds developed for complete ML decoders. This bound can also be applied to bound the average performance of random code ensembles in terms of an ensemble average weight enumerator. We also formulate conditions defining a parameterized family of optimal incomplete decoders, defined to minimize both the total codeword error probability and the undetected error probability for any fixed capability of the decoder to detect errors. We illustrate the gap between optimal and BA-ML incomplete decoding via simulation of a small code.

The development of error-correcting codes has been closely coupled with deep-space exploration since the early days of both. Since the discovery of turbo codes in 1993, the research community has invested a great deal of work on modern iteratively decoded codes, and naturally NASA's Jet Propulsion Laboratory (JPL) has been very much involved. This paper describes the research, design, implementation, and standardization work that has taken place at JPL for both turbo and low-density parity-check (LDPC) codes. Turbo code development proceeded from theoretical analyses of polynomial selection, weight distributions imposed by interleaver designs, decoder error floors, and iterative decoding thresholds. A family of turbo codes was standardized and implemented and is currently in use by several spacecraft. JPL's LDPC codes are built from protographs and circulants, selected by analyses of decoding thresholds and methods to avoid loops in the code graph. LDPC encoders and decoders have been implemented in hardware for planned spacecraft, and standardization is under way.

The well-known uniform error property for signal constellations and codes is extended to encompass information bits. We introduce a class of binary labelings for signal constellations, called bit geometrically uniform (BGU) labelings, for which the uniform bit error property holds, i.e., the bit error probability does not depend on the transmitted signal. Strong connections between the symmetries of constellations and binary Hamming spaces are involved. For block-coded modulation (BCM) and trellis-coded modulation (TCM) Euclidean-space codes, BGU encoders are introduced and studied. The properties of BGU encoders prove quite useful for the analysis and design of codes aimed at minimizing the bit, rather than symbol, error probability. Applications to the analysis and the design of serially concatenated trellis codes are presented, together with a case study which realizes a spectral efficiency of 2 b/s/Hz.

We track the density of extrinsic information in iterative turbo decoders by actual density evolution, and also approximate it by symmetric Gaussian density functions. The approximate model is verified by experimental measurements. We view the evolution of these density functions through an iterative decoder as a nonlinear dynamical system with feedback. Iterative decoding of turbo codes and of serially concatenated codes is analyzed by examining whether a signal-to-noise ratio (SNR) for the extrinsic information keeps growing with iterations. We define a "noise figure" for the iterative decoder, such that the turbo decoder will converge to the correct codeword if the noise figure is bounded by a number below zero dB. By decomposing the code's noise figure into individual curves of output SNR versus input SNR corresponding to the individual constituent codes, we gain many new insights into the performance of the iterative decoder for different constituents. Many mysteries of turbo codes are explained based on this analysis. For example, we show why certain codes converge better with iterative decoding than more powerful codes which are only suitable for maximum likelihood decoding. The roles of systematic bits and of recursive convolutional codes as constituents of turbo codes are crystallized. The analysis is generalized to serial concatenations of mixtures of complementary outer and inner constituent codes. Design examples are given to optimize mixture codes to achieve low iterative decoding thresholds on the signal-to-noise ratio of the channel.

Summary form only given. We present an integrated system for the intelligent progressive transmission of data for deep space communications. This work is motivated by the realization that much more information can be collected by imaging and remote sensing equipment than can be transmitted through downlink channels. The goal of this work was to extend the idea of progressive transmission by incorporating semantic value to the "importance" attributes of encoded data. In particular, we define a simple measure of science return based on information theoretic considerations as well as on the estimated scientific value of the transmitted data. The task of determining the relative scientific importance of segments of data is carried out by an onboard science processing module, designed according to guidelines provided by the remote user (the science community). This module pre-processes the image and provides input to the progressive encoder in the form of a suitable "classification map". By combining the semantic characterization produced by the science processing module with the content-blind data organization criteria of the traditional progressive encoder, we obtain a new measure of the importance of each segment of data. Algorithms that best utilize the available resources can thus be designed and their performances in terms of science return assessed.

We develop new, low complexity turbo codes suitable for bandwidth and power limited systems, for very low bit and word error rate requirements. Motivated by the structure of previously discovered low complexity codes such as repeat-accumulate (RA) codes with low density parity check matrix, we extend the structure to high-level modulation such as 8PSK, and 16QAM. The structure consists of a simple 4-state convolutional or short block code as an outer code, and a rate-1, 2 or 4-state inner code. Two design criteria are proposed: the maximum likelihood design criterion, for short to moderate block sizes, and an iterative decoding design criterion for very long block sizes.

A double serially concatenated code with two interleavers consists of the cascade of an outer encoder, an interleaver permuting the outer codeword bits, a middle encoder, another interleaver permuting the middle codeword bits, and an inner encoder whose input words are the permuted middle codewords. The construction can be generalized to h cascaded encoders separated by h-1 interleavers, where h>3. We obtain upper bounds to the average maximum likelihood bit-error probability of double serially concatenated block and convolutional coding schemes. Then, we derive design guidelines for the outer, middle, and inner codes that maximize the interleaver gain and the asymptotic slope of the error probability curves. Finally, we propose a low-complexity iterative decoding algorithm. Comparisons with parallel concatenated convolutional codes, known as "turbo codes", and with the proposed serially concatenated convolutional codes are also presented, showing that in some cases, the new schemes offer better performance.

A serially concatenated code with interleaver consists of the cascade of an outer encoder, an interleaver permuting the outer codewords bits, and an inner encoder whose input words are the permuted outer codewords. The construction can be generalized to h cascaded encoders separated by h-1 interleavers. We obtain upper bounds to the average maximum-likelihood bit error probability of serially concatenated block and convolutional coding schemes. Then, we derive design guidelines for the outer and inner encoders that maximize the interleaver gain and the asymptotic slope of the error probability curves. Finally, we propose a new, low-complexity iterative decoding algorithm. Throughout the paper, extensive comparisons with parallel concatenated convolutional codes known as "turbo codes" are performed, showing that the new scheme can offer superior performance.

A serially concatenated code with interleaver consists of the cascade of an outer encoder, an interleaver permuting the outer codeword bits, and an inner encoder whose input words are the permuted outer codewords. In this paper we derive design guidelines for the outer and inner codes that maximize the interleaver gain and the asymptotic slope of the error probability curves.

The deBruijn graph B n is the state diagram for an n -stage binary shift register. It has 2 n vertices and 2 n + 1 edges. In this papers, it is shown that B n can be built by appropriately “wiring together“ (i.e., connecting together with extra edges) many isomorphic copies of a fixed graph, which is called a building block for B n . The efficiency of such a building block is refined as the fraction of the edges of B n which are present in the copies of the building block. It is then shown, among other things, that for any α < 1, there exists a graph G which is a building block for B n of efficiency > α for all sufficiently large n . These results are illustrated by describing how a special hierarchical family of building blocks has been used to construct a very large Viterbi decoder (whose floorplan is the graph B 13 ) which will be used on NASA's Galileo mission.

Several modulation and coding advances supported by NASA are summarized. To support long-constraint-length convolutional code, a VLSI maximum-likelihood decoder, utilizing parallel processing techniques, which is being developed to decode convolutional codes of constraint length 15 and a code rate as low as 1/6 is discussed. A VLSI high-speed 8-b Reed-Solomon decoder which is being developed for advanced tracking and data relay satellite (ATDRS) applications is discussed. A 300-Mb/s modem with continuous phase modulation (CPM) and codings which is being developed for ATDRS is discussed. Trellis-coded modulation (TCM) techniques are discussed for satellite-based mobile communication applications.>

A class of codes called finite-state (FS) codes is defined and investigated. The codes, which generalize both block and convolutional codes, are defined by their encoders, which are finite-state machines with parallel inputs and outputs. A family of upper bounds on the free distance of a given FS code is derived. A general construction for FS codes is given, and it is shown that in many cases the FS codes constructed in this way have a free distance that is the largest possible. Catastrophic error propagation (CEP) for FS codes is also discussed. It is found that to avoid CEP one must solve the graph-theoretic problem of finding a uniquely decodable edge labeling of the state diagram.>