On the design of algebraic space-time codes for MIMO block-fading channels

The availability of multiple transmit antennas allows for two-dimensional channel codes that exploit the spatial transmit diversity. These codes were referred to as space-time codes by Tarokh et al. (see ibid., vol.44, p.744-765, Mar. 1998) Most prior works on space-time code design have considered quasi-static fading channels. We extend our earlier work on algebraic space-time coding to block-fading channels. First, we present baseband design criteria for space-time codes in multi-input multi-output (MIMO) block-fading channels that encompass as special cases the quasi-static and fast fading design rules. The diversity advantage baseband criterion is then translated into binary rank criteria for phase shift keying (PSK) modulated codes. Based on these binary criteria, we construct algebraic space-time codes that exploit the spatial and temporal diversity available in MIMO block-fading channels. We also introduce the notion of universal space-time codes as a generalization of the smart-greedy design rule. As a part of this work, we establish another result that is important in its own right: we generalize the full diversity space-time code constructions for quasi-static channels to allow for higher rate codes at the expense of minimal reductions in the diversity advantage. Finally, we present simulation results that demonstrate the excellent performance of the proposed codes.     

Coding for Parallel Channels: Gallager Bounds and Applications to Turbo-Like Codes

The transmission of coded communication systems is widely modeled to take place over a set of parallel channels. This model is used for transmission over block-fading channels, rate-compatible puncturing of turbo-like codes, multicarrier signaling, multilevel coding, etc. New upper bounds on the maximum-likelihood (ML) decoding error probability are derived in the parallel-channel setting. We focus on the generalization of the Gallager-type bounds and discuss the connections between some versions of these bounds. The tightness of these bounds for parallel channels is exemplified for structured ensembles of turbo codes, repeat-accumulate (RA) codes, and some of their recent variations (e.g., punctured accumulate-repeat-accumulate codes). The bounds on the decoding error probability of an ML decoder are compared to computer simulations of iterative decoding. The new bounds show a remarkable improvement over the union bound and some other previously reported bounds for independent parallel channels. This improvement is exemplified for relatively short block lengths, and it is pronounced when the block length is increased. In the asymptotic case, where we let the block length tend to infinity, inner bounds on the attainable channel regions of modern coding techniques under ML decoding are obtained, based solely on the asymptotic growth rates of the average distance spectra of these code ensembles.     

Noncoherent space-time coding: An algebraic perspective

The design of space-time signals for noncoherent block-fading channels where the channel state information is not known a priori at the transmitter and the receiver is considered. In particular, a new algebraic formulation for the diversity advantage design criterion is developed. The new criterion encompasses, as a special case, the well-known diversity advantage for unitary space-time signals and, more importantly, applies to arbitrary signaling schemes and arbitrary channel distributions. This criterion is used to establish the optimal diversity-versus-rate tradeoff for training based schemes in block-fading channels. Our results are then specialized to the class of affine space-time signals which allows for a low complexity decoder. Within this class, space-time constellations based on the threaded algebraic space-time (TAST) architecture are considered. These constellations achieve the optimal diversity-versus-rate tradeoff over noncoherent block-fading channels and outperform previously proposed codes in the considered scenarios as demonstrated by the numerical results. Using the analytical and numerical results developed in this paper, nonunitary space-time codes are argued to offer certain advantages in block-fading channels where the appropriate use of coherent space-time codes is shown to offer a very efficient solution to the noncoherent space-time communication paradigm.     

Reliable channel regions for good binary codes transmitted over parallel channels

We study the average error probability performance of binary linear code ensembles when each codeword is divided into J subcodewords with each being transmitted over one of J parallel channels. This model is widely accepted for a number of important practical channels and signaling schemes including block-fading channels, incremental redundancy retransmission schemes, and multicarrier communication techniques for frequency-selective channels. Our focus is on ensembles of good codes whose performance in a single channel model is characterized by a threshold behavior, e.g., turbo and low-density parity-check (LDPC) codes. For a given good code ensemble, we investigate reliable channel regions which ensure reliable communications over parallel channels under maximum-likelihood (ML) decoding. To construct reliable regions, we study a modifed 1961 Gallager bound for parallel channels. By allowing codeword bits to be randomly assigned to each component channel, the average parallel-channel Gallager bound is simplified to be a function of code weight enumerators and channel assignment rates. Special cases of this bound, average union-Bhattacharyya (UB), Shulman-Feder (SF), simplified-sphere (SS), and modified Shulman-Feder (MSF) parallel-channel bounds, allow for describing reliable channel regions using simple functions of channel and code spectrum parameters. Parameters describing the channel are the average parallel-channel Bhattacharyya noise parameter, the average channel mutual information, and parallel Gaussian channel signal-to-noise ratios (SNRs). Code parameters include the union-Bhattacharyya noise threshold and the weight spectrum distance to the random binary code ensemble. Reliable channel regions of repeat-accumulate (RA) codes for parallel binary erasure channels (BECs) and of turbo codes for parallel additive white Gaussian noise (AWGN) channels are numerically computed and compared with simulation results based on iterative decoding. In addition, an examp     

Coded modulation in the block-fading channel: coding theorems and code construction

We consider coded modulation schemes for the block-fading channel. In the setting where a codeword spans a finite number N of fading degrees of freedom, we show that coded modulations of rate R bit per complex dimension, over a finite signal set /spl chi//spl sube//spl Copf/ of size 2/sup M/, achieve the optimal rate-diversity tradeoff given by the Singleton bound /spl delta/(N,M,R)=1+/spl lfloor/N(1-R/M)/spl rfloor/, for R/spl isin/(0,M/spl rfloor/. Furthermore, we show also that the popular bit-interleaved coded modulation achieves the same optimal rate-diversity tradeoff. We present a novel coded modulation construction based on blockwise concatenation that systematically yields Singleton-bound achieving turbo-like codes defined over an arbitrary signal set /spl chi//spl sub//spl Copf/. The proposed blockwise concatenation significantly outperforms conventional serial and parallel turbo codes in the block-fading channel. We analyze the ensemble average performance under maximum-likelihood (ML) decoding of the proposed codes by means of upper bounds and tight approximations. We show that, differently from the additive white Gaussian noise (AWGN) and fully interleaved fading cases, belief-propagation iterative decoding performs very close to ML on the block-fading channel for any signal-to-noise ratio (SNR) and even for relatively short block lengths. We also show that, at constant decoding complexity per information bit, the proposed codes perform close to the information outage probability for any block length, while standard block codes (e.g., obtained by trellis termination of convolutional codes) have a gap from outage that increases with the block length: this is a different and more subtle manifestation of the so-called "interleaving gain" of turbo codes.     

On performance limits of space-time codes: a sphere-packing bound approach

A sphere-packing bound (SPB) on average word-error probability (WEP) is derived to determine the performance limits of space-time codes on Rayleigh block-fading channels under delay and maximum energy constraints. Two other explicit bounds, a looser bound and a tight approximate bound, are also derived to provide more intuition on how the system parameters affect the performance limits. Moreover, it is shown that as the block length grows to infinity, the SPB converges to the outage probability, and the asymptotic behavior of performance limits is determined by the outage probability.     

On coding for block fading channels

This work considers the achievable performance for coded systems adapted to a multipath block-fading channel model. This is a particularly useful model for analyzing mobile-radio systems which employ techniques such as slow frequency-hopping under stringent time-delay or bandwidth constraints for slowly time-varying channels. In such systems, coded information is transmitted over a small number of fading channels in order to achieve diversity. Bounds on the achievable performance due to coding are derived using information-theoretic techniques. It is shown that high diversity can be achieved using relatively simple codes as long as very high spectral efficiency is not required. Examples of simple block codes and carefully chosen trellis codes are given which yield, in some cases, performances approaching the information-theoretic bounds     

High-Rate Full-Diversity Space–Time–Frequency Codes for Broadband MIMO Block-Fading Channels

A systematic design of high-rate full-diversity space-time-frequency (STF) codes is proposed for multiple-input multiple-output frequency-selective block-fading channels. It is shown that the proposed STF codes can achieve rate M_t and full-diversity M_tM_rM_bL, i.e., the product of the number of transmit antennas M_t, receive antennas M_r, fading blocks M_b, and channel taps L. The proposed STF codes are constructed from a layered algebraic design, where each layer of algebraic coded symbols are parsed into different transmit antennas, orthogonal frequency-division multiplexing tones, and fading blocks without rate loss. Simulation results show that the proposed STF codes achieve higher diversity gain in block-fading channels than some typical space-frequency codes     

Performance analysis of convolutionally coded systems over quasi-static fading channels

This paper presents an improved upper bound on the performance of convolutionally coded systems over quasi-static fading channels (QSFC). The bound uses a combination of a classical union bound when the fading channel is in a high signal-to-noise ratio (SNR) state together with a new upper bound for the low SNR state. This new bounding approach is applied to both BPSK convolutional and turbo codes, as well as serially concatenated BPSK convolutional/turbo and space-time block codes. The new analytical technique produces bounds which are usually about 1 dB tighter than existing bounds. Finally, based on the proposed bound, we introduce an improved design criterion for convolutionally coded systems in slow flat fading channels. Simulation results are included to confirm the improved ability of the proposed criterion to search for convolutional codes with good performance over a QSFC.     

Variations on the Gallager bounds, connections, and applications

There has been renewed interest in deriving tight bounds on the error performance of specific codes and ensembles, based on their distance spectrum. We discuss many reported upper bounds on the maximum-likelihood (ML) decoding error probability and demonstrate the underlying connections that exist between them. In addressing the Gallager bounds and their variations, we focus on the Duman and Salehi (see IEEE Trans. Commun., vol.46, p.717-723, 1998)variation, which originates from the standard Gallager bound. A large class of efficient bounds (or their Chernoff versions) is demonstrated to be a special case of the generalized second version of the Duman and Salehi bounds. Implications and applications of these observations are pointed out, including the fully interleaved fading channel, resorting to either matched or mismatched decoding. The proposed approach can be generalized to geometrically uniform nonbinary codes, finite-state channels, bit interleaved coded modulation systems, and it can be also used for the derivation of upper bounds on the conditional decoding error probability.     

Upper Bounds on the Rate of LDPC Codes for a Class of Finite-State Markov Channels

In this correspondence, we consider the class of finite-state Markov channels (FSMCs) in which the channel behaves as a binary symmetric channel (BSC) in each state. Upper bounds on the rate of LDPC codes for reliable communication over this class of FSMCs are found. A simple upper bound for all noninverting FSMCs is first derived. Subsequently, tighter bounds are derived for the special case of Gilbert-Elliott (GE) channels. Tighter bounds are also derived over the class of FSMCs considered. The latter bounds hold almost-surely for any sequence of randomly constructed LDPC codes of given degree distributions. Since the bounds are derived for optimal maximum-likelihood decoding, they also hold for belief propagation decoding. Using the derivations of the bounds on the rate, some lower bounds on the density of parity check matrices for given performance over FSMCs are derived     

Finite-Dimensional Bounds on Zm and Binary LDPC Codes With Belief Propagation Decoders

This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zopf_m and binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For Zopf _m LDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for Zopf_m LDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with nonequiprobably distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional noniterative bound, the latter of which is the best known bound that is tight for binary-symmetric channels (BSCs), and is a strict improvement over the existing bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for nonsymmetric channels, which coincides with the existing bound for symmetric channels     

Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.     

Krawtchouk多项式与纯的加性量子纠错码的上界

该文利用Krawtchouk多项式函数给出了纯的加性量子纠错码的两个不同的上界,并进一步证明了量子Singleton界和渐近量子Hamming界只是这两个上界的特例。     

Performance of Space–Time Codes: Gallager Bounds and Weight Enumeration

Since the standard union bound for space-time codes may diverge in quasi-static fading channels, the limit-before-average (LBA) technique has been exploited to derive tight performance bounds. However, it suffers from the computational burden arising from a multidimensional integral. In this paper, efficient bounding techniques for space-time codes are developed in the framework of Gallager bounds. Two closed-form upper bounds, the ellipsoidal bound and the spherical bound, are proposed that come close to simulation results within a few tenths of a decibel. In addition, two novel methods of weight enumeration operating on a further reduced state diagram are presented, which, in conjunction with the bounding techniques, give a thorough treatment of performance bounds for space-time codes.     

Performance bounds for coded free-space optical communications through atmospheric turbulence channels

Error-control codes can help to mitigate atmospheric turbulence-induced signal fading in free-space optical communication links using intensity modulation/direct detection (IM/DD). Error performance bound analysis can yield simple analytical upper bounds or approximations to the bit-error probability. We first derive an upper bound on the pairwise codeword-error probability for transmission through channels with correlated turbulence-induced fading, which involves complicated multidimensional integration. To simplify the computations, we derive an approximate upper bound under the assumption of weak turbulence. The accuracy of this approximation under weak turbulence is verified by numerical simulation. Its invalidity when applied to strong turbulence is also shown. This simple approximate upper bound to the pairwise codeword-error probability is then applied to derive an upper bound to the bit-error probability for block codes, convolutional codes, and turbo codes for free-space optical communication through weak atmospheric turbulence channels. We also discuss the choice of interleaver length in block codes and turbo codes based on numerical evaluation of our performance bounds.     

Performance bounds for space-time trellis codes

We derive the union bound for space-time trellis codes over quasi-static fading channels. We first observe that the standard approach for evaluating the union bound yields very loose, in fact divergent, bounds over the quasi-static fading channel. We then develop a method for obtaining a tight bound on the error probability. We derive the union bound by performing expurgation of the standard union bound. In addition, we limit the conditional union bound before averaging over the fading process. We demonstrate that this approach provides a tight bound on the error probability of space-time codes. The bounds can be used for the case when the fading coefficients among different transmit/receive antenna pairs are correlated as well. We present several examples of the bounds to illustrate their usefulness.     

Outer bounds on the capacity of interference channels (Corresp.)

New outer bounds are demonstrated for the capacity regions of discrete memoryless interference channels and Gaussian interference channels. The bound for discrete channels coincides with the capacity region in special cases. The bound for Gaussian channels improves previous knowledge when the interference is of medium strength.     

Performance bounds for optimum multiuser DS-CDMA systems

In this letter we estimate the bit error probability (BEP) of optimum multiuser detection for synchronous and asynchronous code division multiple access (CDMA) systems on Gaussian and fading channels. We first compute an upper bound and a lower bound on the bit error probability for a given spreading code, then average the bounds over a few thousand sets of spreading codes. These bounds are obtained from a partial distance spectrum. On Gaussian channels, the upper bound converges to the lower bound at moderate to large signal-to-noise ratios. However, on fading channels the upper bound does not converge, hence we present our results for the lower bound only. The numerical results show that: 1) the BEP of a 31-user CDMA system with binary random spreading codes of length 31 is only two to four times higher than the BEP of the single user system; 2) the number of users that can be accommodated in an asynchronous CDMA system is larger than the processing gain; and 3) optimum multiuser detection outperforms linear detection (e.g., the decorrelating detector) by about 2.8 to 5.7 dB     

Upper bounds on the size of quantum codes

This paper is concerned with bounds for quantum error-correcting codes. Using the quantum MacWilliams (1972, 1977) identities, we generalize the linear programming approach from classical coding theory to the quantum case. Using this approach, we obtain Singleton-type, Hamming-type, and the first linear-programming-type bounds for quantum codes. Using the special structure of linear quantum codes, we derive an upper bound that is better than both Hamming and the first linear programming bounds on some subinterval of rates