This paper presents and compares two iterative coded modulation techniques for deep-space optical communications using pulse-position modulation (PPM). The first code, denoted by SCPPM, consists of the serial concatenation of an outer convolutional code, an interleaver, a bit accumulator, and PPM. The second code, denoted by LDPC-PPM, consists of the serial concatenation of an LDPC code and PPM. We employ Extrinsic Information Transfer (EXIT) charts for their analysis and design. Under conditions typical of a communications link from Mars to Earth, SCPPM is 1 dB away from capacity, while LDPC-PPM is 1.4 dB away from capacity, at a Bit Error Rate (BER) of approximately 10-5. However, LDPC-PPM lends itself naturally to low latency parallel processing in contrast to SCPPM.

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.

Significant technological advances were made toward utilizing the Hale telescope for receiving the faint laser communication signals transmitted from an optical transceiver on a spacecraft orbiting Mars. The so-called Palomar receive terminal design, which would have supported nominal downlink data rates of 1-30 Mbps, is described. Testing to validate technologies for near-Sun (3deg from edge of solar disc) daytime operations is also discussed. Finally, a laboratory end-to-end link utilizing a 64-ary pulse-position modulated photon-counting receiver and decoder that achieved predicted near-capacity (within 1.4 dB) performance is described.

We present an efficient implementation of a coded modulation for the deep space optical channel. NASA designed this so called serially concatenated pulse position modulation (SCPPM) code to provide an optical link that can operate within one dB signal energy of the Shannon capacity during a nominal mission condition from Mars. Here, we describe some of the challenges in realizing the SCPPM decoder on a field-programmable gate array (FPGA). Through various architectural optimizations, we achieve a 6 Mbps decoder on a single FPGA. Moreover, we demonstrate that it is possible to communicate reliably on an efficient bits-per-photon count in an end-to-end SCPPM coded system.

Space missions are being developed with increasing levels of autonomy, as a means to increase their science return, fault-tolerance, and longevity. In this paper, we present NASA's low-complexity techniques to autonomously identify the modulation order of an M-ary phase-shift-keying signal in the presence of additive white Gaussian noise. This is part of a larger program to develop an autonomous radio that receives a signal without a priori knowledge of its modulation type, modulation index, data rate, and pulse shape. For classification between binary and quaternary phase-shift keying, these techniques represent a lopsided trade-off in which a factor of 100 reduction in complexity results in less than a 0.2 dB loss in performance relative to the maximum likelihood modulation classifier.

We describe novel interleaver and deinterleaver architectures that support bandwidth efficient memory access for decoders of turbo-like codes that are used in conjunction with high order modulations. The presentation focuses on a decoder for serially concatenated pulse-position modulation (SCPPM), which is a forward-error-correction code designed by NASA to support laser communications from Mars at mega-bits-per-second (Mbps) rates. For 64-ary PPM, the new architectures effectively triple the fan-in of the interleaver and fan-out of the deinterleaver, enabling parallelization that doubles the overall throughput. The techniques described here can be readily modified for other PPM orders

We show the capacity of a generalized pulse position modulation (PPM) channel, where the input vectors may be any set that allows a transitive group of coordinate permutations, is achieved by a uniform input distribution. We derive a simple expression for capacity in terms of the Kullback-Leibler distance for the binary case, and find the asymptote in the PPM order. We prove a subadditivity result for the PPM channel and use it to show PPM capacity is monotonic in the order.

We examine several properties of n-pulse pulse position modulation (PPM) [H. Sugiyama et al., 1989] on memoryless channels. We derive the maximum likelihood decision rule and an exact expression for the symbol error rate for nges1, generalizing previous results [R.M. Gagliardi et al., 1976, M. Simon et al., 2003]. A capacity comparison indicates that muItipulse PPM does not produce appreciable gains over conventional PPM except at high average power

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 formula for the error rate of maximum-likelihood detection of M-ary orthogonal signaling on a discrete memoryless channel is manipulated into a form that avoids numerical imprecision when it is used to calculate low error rates.

A fixed-rate shape-gain quantizer for the memoryless Gaussian source is proposed. The shape quantizer is constructed from wrapped spherical codes that map a sphere packing in /spl Ropf//sup k-1/ onto a sphere in /spl Ropf//sup k/, and the gain codebook is a globally optimal scalar quantizer. A wrapped Leech lattice shape quantizer is used to demonstrate a signal-to-quantization-noise ratio within 1 dB of the distortion-rate function for rates above 1 bit per sample, and an improvement over existing techniques of similar complexity. An asymptotic analysis of the tradeoff between gain quantization and shape quantization is also given.

A new technique is presented to separate two cochannel frequency modulation signals. Two candidate solutions for the phases are analytically derived, and a sequence of phase solutions is chosen to match the expected power spectral density of each constituent signal. This is accomplished with a one-step linear predictor and a simple two-state Viterbi algorithm. Simulations on recorded radio frequency data indicate improved separation capability over other techniques such as the joint Viterbi algorithm and cross-coupled phase-locked loop.

This paper presents a method for separating cochannel FM signals. We show that the Viterbi algorithm, traditionally limited to estimation of digital sequences, can jointly track analog FM signals by separately quantizing the derivatives of their instantaneous frequencies. We employ per-survivor processing in the trellis to estimate unknown channel effects. The approach works well when the signal to interference ratio (SIR) is less than or equal to zero, in contrast to conventional interference suppression algorithms that degrade as the SIR approaches zero and fail catastrophically when the SIR<0. Comparisons of mean squared error (MSE) between the estimates and the true signals are given for varying SIR, SNR, Doppler offsets, and frequency deviations. The same approach can also be used for any other continuous phase modulation scheme, such as continuous-phase frequency-shift keying (CPFSK).

The maximum size of binary radar arrays (matrices) with only eight or fewer rows has previously been determined. We determine the maximum size of radar arrays containing 9-16 rows, and for those containing 17 rows we narrow the maximum size down to two values. We also give improved upper and lower asymptotic bounds on the maximum size of radar arrays, which narrow the gap between the existing upper and lower asymptotic bounds by more than 25%.

A new class of spherical codes called wrapped spherical codes is constructed by "wrapping" any sphere packing /spl Lambda/ in Euclidean space onto a finite subset of the unit sphere in one higher dimension. The mapping preserves much of the structure of /spl Lambda/, and unlike previously proposed maps, the density of the wrapped spherical codes approaches the density of /spl Lambda/ as the minimum distance approaches zero. We show that this implies that the asymptotically maximum spherical coding density is achieved by wrapped spherical codes whenever /spl Lambda/ is the densest possible sphere packing.

For pt. I see ibid., vol.43, no.6, p.1774-85, 1997. New spherical codes called laminated spherical codes are constructed in dimensions 2-49 using a technique similar to the construction of laminated lattices. Each spherical code is recursively constructed from existing spherical codes in one lower dimension. Laminated spherical codes outperform the best known spherical codes in the minimum distance sense for many code sizes. The density of a laminated spherical code approaches the density of the laminated lattice in one lower dimension, as the minimum distance approaches zero. In particular, the three-dimensional laminated spherical code is asymptotically optimal, in the sense that its density approaches the Fejes Toth (1959) upper bound as the minimum distance approaches zero. Laminated spherical codes perform asymptotically as well as wrapped spherical codes in those dimensions where laminated lattices are optimal sphere packings.

The switchbox routing problem (SRP) in which terminals have some flexibility in placement on the border is considered. The general problem with position constraints is NP-complete, as is the problem with only order constraints or separation constraints. The problem is solved for the case in which terminals are permutable within prespecified groups of adjacent vertices, called clusters. Whenever possible, the algorithm determines a terminal assignment such that the resulting SRP is solvable; the total time to assign the terminals and to construct a layout is O(N log N), where N is the number of nets. The results extend to multiple layers and to convex grids.>

A layout for the k-ary overlap rectangle routing problem (k-RRP) is a set of paths connecting pairs of terminals on the boundary such that each edge hosts at most k distinct nets. The authors give necessary and sufficient conditions for the existence of such a layout, and present an algorithm that constructs a layout, if one exists, in time O(kN), where N is the number of gridpoints in the rectangle. Extensions to more general problems are also discussed.>