Search

This paper describes and analyzes low-density parity-check code families that support variety of different rates while maintaining the same fundamental decoder architecture. Such families facilitate the decoding hardware design and implementation for applications that require communication at different rates, for example to adapt to changing channel conditions. Combining rows of the lowest-rate parity-check matrix produces the parity-check matrices for higher rates. An important advantage of this approach is that all effective code rates have the same blocklength. This approach is compatible with well known techniques that allow low-complexity encoding and parallel decoding of these LDPC codes. This technique also allows the design of programmable analog LDPC decoders. The proposed design method maintains good graphical properties and hence low error floors for all rates. Index Terms--Channel coding, low-density parity-check (LDPC) codes, multiple-rate codes.

This paper presents serially concatenated trellis coded modulations (SCTCMs) that perform consistently close to the available mutual information for periodic erasure channel (PEC), periodic fading channel (PFC) and the 2 x 2 compound matrix channel. We use both the maximum-likelihood decoding criteria and iterative decoding criteria to design universal SCTCMs for the PEC and the PFC. For the space-time channel, by de-multiplexing the symbols across the antennas, the proposed universal SCTCMs for the period-2 PFC deliver consistent performance over the eigenvalue skew of the matrix channel. Within the family of channels having the same eigenvalue skew, a time-varying linear transformation (TVLT) is used to mitigate the performance variation over different eigenvectors. The proposed space-time SCTCMs of 1.0, 2.0 and 3.0 bits per transmission require excess mutual information in the ranges 0.11-0.15, 0.23-0.26 and 0.35-0.53 bits per antenna, respectively. Because of their consistent performance over all channels, the proposed codes will have good frame-error-rate (FER) performance over any quasi-static fading distribution. In particular, the codes provide competitive FER performance in quasi-static Rayleigh fading. Index Terms--Turbo code, robust channel coding, universal codes, compound multiple-input multiple-output(MIMO) channel, spacetime systems.

Based on random codes and typical set decoding, an alternative proof of Root and Varaiya's compound channel coding theorem for linear Gaussian channels is presented. The performance limit of codes with finite block length under a compound channel is studied through error bounds and simulation. Although the theorem promises uniform convergence of the probability of error as the block length approaches infinity, with short block lengths the performance can differ considerably for individual channels. Simulation results show that universal performance can be a practical goal as the block lengths become large. Index Terms--Compound channel, random coding bound, sphere-packing bound (SPB), universal code.

Root and Varaiya proved the existence of a code that can communicate reliably over any linear Gaussian channel for which the channel mutual information level exceeds the transmitted rate. This paper provides several examples of scalar (single-input single-output) fading channels and shows that on these channels the performance of low-density parity-check (LDPC) codes lies in close proximity to the performance limits identified by Root and Varaiya. Specifically, we consider periodic fading channels and partial-band jamming (PBJ) channels. A special case of periodic fading is the variation of signal-to-noise ratio across orthogonal frequency division modulation subchannels. The robustness of LDPC codes to periodic fading and PBJ across parameterizations of these different channels is demonstrated through the consistency of the required mutual information to provide a specified bit error rate. For the periodic fading case, the Gaussian approximation to density evolution has been adapted such that asymptotic threshold measures can be compared to simulated code performance in various periodic fading scenarios. Index Terms--Low-density parity-check (LDPC) codes, orthogonal frequency-division modulation (OFDM), partial-band jamming (PBJ), robust channel coding, universal codes.

In broadcast scenarios or in the absence of accurate channel probability distribution information, code design for consistent channel-by-channel performance, rather than average performance over a channel distribution, may be desirable. Root and Varaiya's compound channel theorem for linear Gaussian channels promises the existence of universal codes that operate reliably whenever the channel mutual information (MI) is above the transmitted rate. This paper presents two-dimensional trellis codes that provide such universal performance over the compound linear vector Gaussian channel when demultiplexed over two, three, and four transmit antennas. The presented trellis codes, found by exhaustive search, guarantee consistent performance on every matrix channel that supports the information transmission rate with an MI gap that is similar to the capacity gap of a well-designed additive white Gaussian noise (AWGN)-specific code on the AWGN channel. As a result of their channel-by-channel consistency, the universal trellis codes presented here also deliver comparable, or, in some cases, superior, frame-error rate and bit-error rate performance under quasi-static Rayleigh fading, as compared with trellis codes of similar complexity that are designed specifically for the quasi-static Rayleigh-fading scenario. Index Terms--Compound multiple-input multiple-output (MIMO) channel, multiple antennas, space--time systems, trellis codes, universal codes.

We study the maximum flow possible between a single-source and multiple terminals in a weighted random graph (modeling a wired network) and a weighted random geometric graph (modeling an ad-hoc wireless network) using network coding. For the weighted random graph model, we show that the network coding capacity concentrates around the expected number of nearest neighbors of the source and the terminals. Specifically, for a network with a single source, l terminals, and n relay nodes such that the link capacities between any two nodes is independent and identically distributed (i.i.d.) ~ X, the maximum flow between the source and the terminals is approximately [.sub.n]E[X] with high probability. For the weighted random geometric graph model where two nodes are connected if they are within a certain distance of each other we show that with high probability the network coding capacity is greater than or equal to the expected number of nearest neighbors of the node with the least coverage area. Index Terms--Minimum cut, multicast, network coding, random geometric graphs, random graphs.

This paper presents a symmetry-based technique for trellis-code state-diagram reduction that has more general applicability than the quasi-regularity technique of Rouanne et al. and Zehavi et al. for trellis codes using standard constellations and labelings. For a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] -state trellis code, the new technique reduces the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] state diagram to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] -state diagram where 0 [less than or equal to] [v.sub.q] [less than or equal to] [v.sub.x]. The particular value of [v.sub.q] depends on the constellation labeling and the convolutional encoder. For standard rate-k/(k + 1) set-partitioned trellis codes, [v.sub.q] : 0, and the overall number of states is the same with the new technique as with quasi-regularity. For codes that are not quasi-regular (and thus not amenable to the quasi-regularity technique), the new technique often provides some improvement (when [v.sub.q] < [v.sub.x]). For 8-phase-shift-keying trellis codes, the new technique always yields [v.sub.q] : 0. Index Terms--Distance spectrum, enumerating functions, error probability, generating functions, transfer functions, trellis-coded modulation (TCM), trellis codes, union bounds.

This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girt conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that at orders of magnitude below those of random codes with very small degradation in capacity-approaching capability. Index Terms--Error floor, extrinsic message degree (EMD graph cycles, irregular low-density parity-check (LDPC) code, iterative decoding, message passing, stopping sets, unstructured graph construction.

Bergmans and Cover identified the capacity region of the Gaussian degraded broadcast channel, where different receivers observe the transmitted signal with different signal-to-noise ratios. This letter presents a superposition turbo-coding scheme that performs within 1 dB of the capacity region boundary of the degraded broadcast channel at a bit-error rate of [10.sup.-5]. Index Terms--Degraded broadcast channel, superposition, time division, trellis-coded modulation, turbo coding, unequal error protection.

For trellis codes, generating function techniques provide the distance spectrum and a union bound on bit-error rate. The computation of the generating function of a trellis code may be separated into two stages. The first stage reduces the number of states as much as possible using low-complexity approaches. The second stage produces the generating function from the reduced-state diagram through some form of matrix inversion, which has a relatively high complexity. In this paper, we improve on the amount of state reduction possible during the low-complexity first stage. We also show that for a trellis code that is a linear convolutional code followed by a signal mapper, the number of states may always be reduced from [N.sup.2] to (([N.sup.2] - N)/2) + 1 using low-complexity techniques. Finally, we analytically compare the complexity of various matrix inversion techniques and verify through simulation that the two-stage approach we propose has the lowest complexity. In an example, the new technique produced the union bound in about half the time required by the best algorithm already in the literature. Index Terms--Distance spectrum, error probability, generating functions, transfer functions, trellis-code modulation, trellis codes, union bounds.

A trellis coding technique for the layered space-time architecture of D-BLAST is described and discussed.

This correspondence gives practical examples of space-time trellis codes performing as predicted by Root and Varaiya's compound channel theorem. Specifically, 32-state and 64-state 2 x 2 space-time trellis codes are presented that provide a bit-error rate (BER) of [10.sup.-5] on all 2 x 2 matrix channels with an excess mutual information (MI) within 8% of the excess MI required by standard trellis codes of the same complexity operating only in additive white Gaussian noise (AWGN). Not surprisingly, the universal space-time trellis-coded modulations (ST-TCMs) provide average bit- and frame-error rates in quasi-static Rayleigh fading (QRF) that are comparable to those achieved by ST-TCMs designed specifically for QRF as well as standard TCMs followed by the Alamouti space-time block code. However, all of these other schemes require more excess MI in the worst case, and some have a significantly wider variation in the required excess MI. The correspondence also compares the universal and quasi-static Rayleigh fading design approaches analytically and bounds the worst case distance of a trellis code on a 2 x 2 channel using the distances of the code on singular and unitary channels. This bound is extended to the more general [n.sub.T] x [n.sub.R] scenario. Index Terms--Compound channel, outage, quasi-static Rayleigh fading, space-time trellis codes.

We consider the problem of binary hypothesis testing using binary decisions from independent and identically distributed (i.i.d). sensors. Identical likelihood-ratio quantizers with threshold [lambda] are used at the sensors to obtain sensor decisions. Under this condition, the optimal fusion rule is known to be a [kappa]-out-of-n rule with threshold [kappa]. For the Bayesian detection problem, we show that given [kappa], the probability of error is a quasi-convex function of [kappa] and has a single minimum that is achieved by the unique optimal [[lambda].sub.opt]. Except for the trivial situation where one hypothesis is always decided, we obtain a sufficient and necessary condition on [[lambda].sub.opt], and show that [[lambda.sub.opt] can be efficiently obtained via the SECANT algorithm. The overall optimal solution is obtained by optimizing every pair of ([kappa], [lambda]). For the Neyman-Pearson detection problem, we show that the use of the Lagrange multiplier method is justified for a given fixed [kappa] since the objective function is a quasi-convex function of [lambda]. We further show that the receiver operating characteristic (ROC) for a fixed [kappa] is concave downward. Index Terms--Decision-making, multisensor systems, quantization, signal detection.

A receiver structure is described, for tracking and equalizing a multi-input multi-output (MIMO) frequency-selective fading channel. A Kalman filter is used to track the channel, which relies on a low-order autoregressive model to fit the true statistics of the channel variation.

This paper presents bandwidth-efficient speech transmission systems using rate-compatible channel coders and variable bitrate embedded source coders. Rate-compatible punctured convolutional codes (RCPC) are often used to provide unequal error protection (UEP) via progressive bit puncturing. RCPC codes are well suited for constellations for which Euclidean and Hamming distances are equivalent (BPSK and 4-PSK). This paper introduces rate-compatible punctured trellis codes (RCPT) where rate compatibility and UEP are provided via progressive puncturing of symbols in a trellis. RCPT codes constitute a special class of codes designed to maximize residual Euclidean distances (RED) after symbol puncturing. They can be designed for any constellation, allowing for higher throughput than when restricted to using 4-PSK. We apply RCPC and RCPT to two embedded source coders: a perceptual subband coder and the ITU embedded ADPCM G.727 standard. Different operating modes with distinct source/channel bit allocation and UEP are defined. Each mode is optimal for a certain range of AWGN channel SNRs. Performance results using an 8-PSK constellation clearly illustrate the wide range of channel conditions at which the adaptive scheme using RCPT can operate. For an 8-PSK constellation, RCPT codes are compared to RCPC with bit interleaved coded modulation codes (RCPC-BICM). We also compare performance to RCPC codes used with a 4-PSK constellation. Index Terms--Adaptive multirate (AMR), bit interleaved coded modulation (BICM), embedded coding, punctured codes, rate-compatible channel coding, perceptual coding, rate-compatible punctured convolutional codes (RCPC), rate-compatible punctured trellis codes (RCPT), trellis codes, unequal error protection.