Search

We introduce a new one-dimensional (1-D) analysis of low-density parity-check (LDPC) codes on additive white Gaussian noise channels which is significantly more accurate than similar 1-D methods. Our method assumes a Gaussian distribution in message-passing decoding only for messages from variable nodes to check nodes. Compared to existing work, which makes a Gaussian assumption both for messages from check nodes and from variable nodes, our method offers a significantly more accurate estimate of convergence behavior and threshold of convergence. Similar to previous work, the problem of designing irregular LDPC codes reduces to a linear programming problem. However, our method allows irregular code design in a wider range of rates without any limit on the maximum variable-node degree. We use our method to design irregular LDPC codes with rates greater than 1/4 that perform within a few hundredths of a decibel from the Shannon limit. The designed codes perform almost as well as codes designed by density evolution. Index Terms--Degree distribution, density evolution, extrinsic information transfer (EXIT) charts, Gaussian assumption, irregular low-density parity-check (LDPC) codes.

We apply irregular low-density parity-check (LDPC) codes to the design of multilevel coded quadrature amplitude modulation (QAM) schemes for application in discrete multitone systems in frequency-selective channels. A combined Gray/Ungerboeck scheme is used to label each QAM constellation. The Gray-labeled hits are protected using an irregular LDPC code with iterative soft-decision decoding, while other bits are protected using a high-rate Reed-Solomon code with hard-decision decoding (or are left uncoded). The rate of the LDPC code is selected by analyzing the capacity of the channel seen by the Gray-labeled bits and is made adaptive by selective concatenation with an inner repetition code. Using a practical bit-loading algorithm, we apply this coding scheme to an ensemble of frequency-selective channels with Gaussian noise. Over a large number of channel realizations, this coding scheme provides an average effective coding gain of more than 7.5 dB at a bit-error rate of [10.sup.-7] and a block length of approximately [10.sup.5] b. This represents a gap of approximately 2.3 dB from the Shannon limit of the additive white Gaussian noise channel, which could be closed to within 0.8-1.2 dB using constellation shaping. Index Terms--Discrete multitone systems, low-density parity-check (LDPC) codes, multilevel-coded modulation, frequency-selective channels.

We determine upper and lower bounds on the channel capacity of power- and bandwidth-constrained optical intensity channels corrupted by white Gaussian noise. These bounds are shown to converge asymptotically at high optical signal-to-noise ratios (SNRs). Unlike previous investigations on low-intensity Poisson photon counting channels, such as some fiber optic links, this channel model is realistic for indoor free space optical channels corrupted by intense ambient light. An upper bound on the capacity is found through a sphere-packing argument while a lower bound is computed through the maxentropic source distribution. The role of bandwidth is expressed by way of the effective dimension of the set of signals and, together with an average optical power constraint, is used to determine bounds on the spectral efficiency of time-disjoint optical intensity signaling schemes. The bounds show that, at high optical SNRs, pulse sets based on raised-quadrature amplitude modulation (QAM) and prolate spheroidal wave functions have larger achievable maximum spectral efficiencies than traditional rectangular pulse basis sets. This result can be considered as an extension of previous work on photon counting channels which closely model low optical intensity channels with rectangular pulse shapes. Index Terms--Channel capacity, direct detection, free space, infrared communication, optical communications, optical intensity modulation, wireless.

Traditional approaches to constructing constellations for electrical channels cannot be applied directly to the optical intensity channel. This work presents a structured signal space model for optical intensity channels where the nonnegativity and average amplitude constraints are represented geometrically. Lattice codes satisfying channel constraints are defined and coding and shaping gain relative to a baseline are computed. An effective signal space dimension is defined to represent the precise impact of coding and shaping on bandwidth. Average optical power minimizing shaping regions are derived in some special cases. Example lattice codes are constructed and their performance on an idealized point-to-point wireless optical link is computed. Bandwidth-efficient schemes are shown to have promise for high data-rate applications, but require greater average optical power. Index Terms--Free-space optical communications, lattice codes, optical intensity modulation, signal space, wireless infrared channel.

Unequal error protection (UEP) is essential when different portions of the source data do not contribute evenly to the overall quality of the decoded information. Conventional techniques achieve UEP by independent coding of the bit streams or by adopting conventional unequal error-protection codes. In this paper, we propose a practical alternative to the QPSK-based transmission systems with explicit UEP, such as GSM or IS-54 wireless transmission standards. In this scheme, the task of providing unequal protection is divided between the channel encoder and a nonuniform signal set, which discriminates in favor of the more important bits. The new approach allows for a simpler convolutional encoder and, hence, a less complex decoding procedure. Specifically, a reduction by more than half in the number of encoder states can easily be achieved using our scheme. Countering the degradation of the less important bits, we propose to adopt a high-rate punctured convolutional code to minimize the incurred transmission rate penalty. We also discuss a pilot sequence transmission scheme which realizes a coherent reception. Decentralizing the bit protection culminates in an extra degree of freedom which, in turn, introduces more flexibility into the system design. Index Terms - Asymmetric modulation, GSM and IS-54 wireless transmission standards, pilot-sequence channel compensation, punctured convolutional codes, unequal error protection.

An important problem in the theory and application of block-code trellises is to find a coordinate permutation of a given code to minimize the trellis complexity. In this correspondence we show that the problem of finding a coordinate permutation that minimizes the number of vertices at a given depth in the minimal trellis for a binary linear block code is NP-complete. Index Terms - Permutation trellis complexity, NP-completeness.

We prove a conjecture of McEliece, establishing that for each fixed order of positions of a linear code C, the minimal trellis minimizes the quantity [absolute value of E] - [absolute value of V] + 1, where [absolute value of E] and [absolute value of V] stand for the number of edges and vertices in the trellis, respectively. As a consequence, it follows that the minimal trellis uniquely minimizes the total number of operations required for Viterbi decoding of a given code. Moreover, we show that these results extend to the general class of rectangular codes (namely, the class of codes that admit a biproper trellis presentation), which includes all group codes and many other useful nonlinear codes. Index Terms - Trellis complexity, linear block codes, rectangular codes, Viterbi decoding.

We show that the family of maximal fixed-cost (MFC) codes, with codeword costs defined in a right-cancellative semigroup, are rectangular, and hence admit biproper trellis presentations. Among all possible trellis presentations for a rectangular code, biproper trellises minimize a wide variety of complexity measures, including the Viterbi decoding complexity. Examples of MFC codes include such "nonlinear" codes as permutation codes and shells of constant norm in the integer lattice, as well as linear codes over a finite field. The intersection of two rectangular codes is another rectangular code; therefore, "nonlinear" codes such as lattice shells or words of constant weight in a linear code have biproper trellis presentations. We show that every rectangular code can be interpreted as an MFC code. Applications of these results include error detection, trellis-based indexing, and soft-decision decoding. Index Terms - Maximal fixed-cost codes, rectangular codes, biproper trellises, minimal trellises, lattice codes, constant-weight subcodes.

A multistage signal estimation scheme is proposed for phase-and-amplitude modulated soliton communication systems. The estimator provides a significant mean-squared-error reduction in soliton amplitude estimation, which, in conjunction with detection of encoded phase information, results in spectral-efficiency improvements. A low-complexity version of the multistage estimation scheme is also proposed, whose performance is studied via numerical simulations under the distributed Raman amplification strategy. The achievable information rate is increased by about 1 bit/symbol for pulse bandwidth of 30 GHz, 40 GHz, and 50 GHz. [ABSTRACT FROM AUTHOR]

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 product 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. Index Terms - Nonlinear codes, linear codes, trellises, atomic codewords, trellis enumeration.

Multidimensional constellation shaping with a family of regions called truncated polydiscs is studied. This family achieves maximum shaping gain for a given two-dimensional peak-to-average energy ratio or a given two-dimensional constellation expansion ratio. An efficient algorithm for mapping data words to constellation points is described that requires O(N log N) arithmetic operations and O([N.sup.2]) lookup table space. Truncated polydisc shaping can easily be incorporated into standard coded modulation schemes.

Variable-rate data transmission schemes in which constellation points are selected according to a nonuniform probability distribution are studied. When the criterion is one of minimizing the average transmitted energy for a given average bit rate, the best possible distribution with which to select constellation points is a Maxwell-Boltzmann distribution. In principle, when constellation points are selected according to a Maxwell-Boltzmann distribution, the ultimate shaping gain (Pi-e/6 or 1.53 dB) can be achieved in any dimension. Nonuniform signaling schemes can be designed by mapping simple variable-length prefix codes onto the constellation. Using the Huffman procedure, prefix codes can be designed that approach the optimal performance. These schemes provide a fixed-rate primary channel and a variable-rate secondary channel, and are easily incorporated into standard lattice-type coded modulation schemes.

We consider the design of near-capacity-achieving error-correcting codes for a discrete multitone (DMT) system in the presence of both additive white Gaussian noise and impulse noise. Impulse noise is one of the main channel impairments for digital subscriber lines (DSL). One way to combat impulse noise is to detect the presence of the impulses and to declare an erasure when an impulse occurs. In this paper, we propose a coding system based on low-density parity-check (LDPC) codes and bit-interleaved coded modulation that is capable of taking advantage of the knowledge of erasures. We show that by carefully choosing the degree distribution of an irregular LDPC code, both the additive noise and the erasures can be handled by a single code, thus eliminating the need for an outer code. Such a system can perform close to the capacity of the channel and for the same redundancy is significantly more immune to the impulse noise than existing methods based on an outer Reed-Solomon (RS) code. The proposed method has a lower implementation complexity than the concatenated coding approach.