Coherent states achieve the Holevo capacity of a pure-loss channel when paired with an optimal measurement, but a physical realization of this measurement is unknown, and likely to be of high complexity. In this paper, we focus on the photon-counting measurement and study the photon and dimensional efficiencies attainable with modulations over classical- and nonclassical-state alphabets. We first review state-of-the-art coherent on-off-keying (OOK) and pulse-position modulation (PPM) with a photon-counting measurement, illustrating its asymptotic inefficiency relative to the Holevo limit. Then we analyze two architectures that improve upon the dimensional versus photon efficiency tradeoff achievable with conventional OOK or PPM. We show that at high photon efficiency these architectures achieve an efficiency tradeoff that differs from the best possible tradeoff by only a constant factor. The first architecture is a coherent-state transmitter that relies on feedback from the receiver to control the transmitted energy. The second architecture uses a single-photon number-state source.

This paper discusses construction of protograph-based low-density parity-check (LDPC) codes. Emphasis is placed on protograph ensembles whose typical minimum distance grows linearly with block size. Asymptotic performance analysis for both weight enumeration and iterative decoding threshold determination is provided and applied to a series of code constructions. Construction techniques that yield both low thresholds and linear minimum distance growth are introduced by way of example throughout. The paper also examines implementation strategies for high throughput decoding derived from first principles of belief propagation on bipartite graphs.

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.

A construction method for protograph-based LDPC codes that simultaneously achieve low iterative decoding threshold and linear minimum distance is proposed. We start with a high-rate protograph LDPC code with variable node degrees of at least 3. Lower rate codes are obtained by splitting check nodes and connecting them by degree-2 nodes. This guarantees the linear minimum distance property for the lower-rate codes. Excluding checks connected to degree-1 nodes, we show that the number of degree-2 nodes should be at most one less than the number of checks for the protograph LDPC code to have linear minimum distance. Iterative decoding thresholds are obtained by using the reciprocal channel approximation. Thresholds are lowered by using either precoding or at least one very high-degree node in the base protograph. A family of high- to low-rate codes with minimum distance linearly increasing in block size and with capacity-approaching performance thresholds is presented. FPGA simulation results for a few example codes show that the proposed codes perform as predicted

A general class of nonlinear compound pulse position modulation (CPPM) codes is introduced to incorporate nonlinear low-rate PPM constraints directly into a Tanner-like code graph on which iterative decoding can be performed. The iterative decoding algorithm is specified for these codes, including the extrinsic message computations at the nonlinear constraint nodes. For a particular subclass of CPPM codes a simple but strange encoding algorithm is defined that encodes a variable number of source bits for each code block. The encoding algorithm is applied to calculate the average information rate of a particular type of parallel concatenated CPPM code ensemble called turbo PPM

We propose several LDPC code constructions that simultaneously achieve good threshold and error floor performance. Minimum distance is shown to grow linearly with block size (similar to regular codes of variable degree at least 3) by considering ensemble average weight enumerators. Our constructions are based on projected graph, or protograph, structures that support high-speed decoder implementations. As with irregular ensembles, our constructions are sensitive to the proportion of degree-2 variable nodes. A code with too few such nodes tends to have an iterative decoding threshold that is far from the capacity threshold. A code with too many such nodes tends to not exhibit a minimum distance that grows linearly in block length. In this paper we also show that preceding can be used to lower the threshold of regular LDPC codes. The decoding thresholds of the proposed codes, which have linearly increasing minimum distance in block size, outperform that of regular LDPC codes. Furthermore, a family of low to high rate codes, with thresholds that adhere closely to their respective channel capacity thresholds, is presented. Simulation results for a few example codes show that the proposed codes have low error floors as well as good threshold SNR performance.

We have demonstrated that the performance (as measured by its variance) of a popular SNR estimator can be improved by increasing the number of observables per symbol (accomplished by partitioning the symbol interval into a larger (than two) even number of subdivisions) but still processing them in successive pairs. We have shown that the amount of improvement is a function of the true SNR being estimated and continues to increase monotonically with increasing SNR. Despite its ad hoc nature, the modified estimator tracks the Cramer-Rao bound on the variance of SNR estimators with known or unknown data over the entire range of SNR values, a property not previously achievable with the traditional version of this estimator.

Inspired by recently proposed accumulate-repeat-accumulate (ARA) codes, in this paper we propose a construction method for LDPC codes using simple loop-free encoding modules. Such codes can be viewed as serial/parallel concatenations of simple modules such as accumulators, repetition codes, differentiators, and punctured single parity check codes. Examples are accumulate-repeat-accumulate (ARA) codes, accumulate-repeat-accumulate-accumulate (ARAA) codes and accumulate-repeat-check-accumulate codes, and other variations. These codes constitute a subclass of LDPC codes with very fast encoder structure. They also have a projected graph or protograph representation that allows for high-speed decoder implementation. Based on density evolution, we show through some examples that low iterative decoding thresholds close to the channel capacity limits can be achieved with low maximum variable node degrees, as the block size goes to infinity. The decoding threshold in many examples outperforms that of the best known unstructured irregular LDPC codes constrained to have the same maximum node degree. Furthermore, by puncturing the accumulator modules, any desired higher rate codes can be obtained with thresholds that stay close to their respective channel capacity thresholds uniformly.

In this paper, we present two encoding methods for block-circulant LDPC codes. The first is an iterative encoding method based on the erasure decoding algorithm, and the computations required are well organized due to the block-circulant structure of the parity check matrix. The second method uses block-circulant generator matrices, and the encoders are very similar to those for recursive convolutional codes. Some encoders of the second type have been implemented in a small field programmable gate array (FPGA) and operate at 100 Msymbols/second

This paper provides a construction method for low-rate low density parity check codes. Inspired by recently proposed accumulate-repeat-accumulate (ARA) codes, and hybrid concatenated codes, in this paper we extend the construction to low rates. Such codes can be viewed as hybrid concatenations of simple modules such as accumulators, repetition codes, differentiators, and punctured single parity check codes. These codes constitute a subclass of LDPC codes with very fast encoder structure. They also have a projected graph or protograph representation that allows for high-speed decoder implementation. Based on density evolution, we show through some examples that low iterative decoding thresholds close to the channel capacity limits can be achieved, as the block size goes to infinity. Iterative decoding simulation results for short blocks are provided for a few examples that show near-capacity performance and very low error floor

We construct a protograph-based rate-compatible family of low-density parity-check (LDPC) codes that cover a very wide range of rates from 1/2 to 16/17, perform within about 0.5 dB of their capacity limits for all rates, and can be decoded conveniently and efficiently with a common hardware implementation. In contrast to alternative methods that create codes of different rates by puncturing, shortening, or expurgation, our method uses a combination of expurgation and lengthening (equivalent to an unusual extension) to produce lower-rate codes. Advantages compared to the alternative methods include roughly uniform utilization of common family decoder hardware for different rates, implementation with uniformly low maximum check node degrees despite high maximum rate, and a large fixed portion of the protograph that can be labeled with a fixed set of edge permutations for all rates. We apply this method to create a rate-compatible code family anchored by a particular code of (nominal) rate 7/8 and length n = 8176 designed by Kou, Lin and Fossorier [1] whose edge permutations are determined by Euclidean geometries (EG). All members of our family retain all of the EG-designed edges and circulant permutations of this anchor code, and this helps to avoid weak spots in the code graph that usually arise when edge permutations are assigned by greedy algorithms. There are also varying numbers of auxiliary and ancillary checks, variables, and edges, allowing realization of different rates, with fixed (nominal) dimension k = 8176 for all rates. Simulations show that all members of this family achieve steeply falling error rate curves without detectable error floors, at least to codeword error rates of about 10-6

It is shown that a non-square (NS) 2/sup 2n+1/-ary quadrature amplitude modulation (QAM) can be decomposed into a single parity-check (SPC) block encoder and a memoryless modulator in such a way that the inherent block encoder has a recursive nature. When concatenated with a forward-error-correcting (FEC) code, iterative demodulation, demapping, and decoding of the FEC code and the inherent SPC code of NS-2/sup 2n+1/-QAM is then possible. Simulation results show that coded NS-8QAM performs nearly 2 dB better than standard 8QAM and star-8QAM, and nearly 1 dB better than 8-ary phase-shift keying when the FEC code is a rate-1/2, 16-state convolutional code, while coded NS-32QAM performs 0.75 dB better than standard 32QAM.

A method by which a popular signal-to-noise ratio (SNR) estimator can be reconfigured to yield improved performance is proposed. The reconfiguration consists of partitioning the symbol interval into a larger (but even) number of subdivisions than the two that have been traditionally suggested for this estimator but still processing the observables in successive pairs. The optimum number of subdivisions is shown to depend on the SNR range in which the true SNR lies; however, we also show that these SNR regions can be significantly widened with very little loss in performance. Most important is the fact that with this reconfiguration, the SNR estimator tracks the Cramer-Rao bound on the variance of the estimator over the entire range of SNR values.

A robust SNR estimator is proposed and its performance analyzed for a variety of cases dealing with its operation in receivers where little or no information is known regarding other system parameters such as carrier phase and frequency, order of the modulation, and data symbol knowledge.

Low-density mirror-concatenated (LDMC) codes are defined and shown to be equivalent to low-density parity-check (LDPC) codes. As a generalization of irregular repeat-and-accumulate (IRA) codes, LDMC codes offer a slightly different, but potentially useful, perspective on LDPC codes as concatenated codes.

We present a scalable decoding architecture for a certain class of structured LDPC codes. The codes are designed using a small (n, r) protograph that is replicated Z times to produce a decoding graph for a (Z/spl times/n, Z/spl times/r) code. Using this architecture, we have implemented a decoder for a (4096, 2048) LDPC code on a Xilinx Virtex-II 2000 FPGA, and achieved decoding speeds of 31 Mbps with 10 fixed iterations. The implemented message-passing algorithm uses an optimized 3-bit nonuniform quantizer that allows near floating point performance in the waterfall region, with drastically smaller hardware implementation requirements.

A method is presented for constructing LDPC codes with excellent performance, simple hardware implementation, low encoder complexity, and which can be concisely documented. The simple code structure is achieved by using a base graph, expanded with circulants. The base graph is chosen by computer search using simulated annealing, driven by density evolution's decoding threshold as determined by the reciprocal channel approximation. To build a full parity check matrix, each edge of the base graph is replaced by a circulant permutation, chosen to maximize loop length by using a Viterbi-like algorithm.

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.

The A* algorithm is applied to maximum-likelihood soft-decision decoding of binary linear block codes. This paper gives a tutorial on the A* algorithm, compares the decoding complexity with that of exhaustive search and Viterbi decoding algorithms, and presents performance curves obtained for several codes.

In this partially tutorial paper, we examine minimal trellis representations of linear block codes and analyze several measures of trellis complexity: maximum state and edge dimensions, total span length, and total vertices, edges and mergers. We obtain bounds on these complexities as extensions of well-known dimension/length profile (DLP) bounds. Codes meeting these bounds minimize all the complexity measures simultaneously; conversely, a code attaining the bound for total span length, vertices, or edges, must likewise attain it for all the others. We define a notion of "uniform" optimality that embraces different domains of optimization, such as different permutations of a code or different codes with the same parameters, and we give examples of uniformly optimal codes and permutations. We also give some conditions that identify certain cases when no code or permutation can meet the bounds. In addition to DLP-based bounds, we derive new inequalities relating one complexity measure to another, which can be used in conjunction with known bounds on one measure to imply bounds on the others. As an application, we infer new bounds on maximum state and edge complexity and on total vertices and edges from bounds on span lengths.

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.

A real-time digital signal combining system for use with array feeds is proposed. The combining system attempts to compensate for signal-to-noise ratio (SNR) loss resulting from antenna deformations induced by gravitational and atmospheric effects. The combining weights are obtained directly from the observed residual carrier samples in each channel using a 'sliding-window' implementation of a maximum-likelihood (ML) parameter estimator. It is shown that with averaging times of about 0.1 s, combining loss for a seven-element array can be limited to about 0.1 dB in a realistic operational environment. This result suggests that the real-time combining system proposed is capable of recovering virtually all of the signal power captured by the array feed, even in the presence of severe wind gusts and similar disturbances.>