A Study on Universal Codes With Finite Block Lengths

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.     

General random coding bounds: AWGN channels to MIMO fading channels

Random coding bounds are obtained for multiple-input multiple-output (MIMO) fading channels. To derive the result in a compact and easy-to-evaluate form, a series of combinatorial codeword enumeration problems are solved for input-constrained MIMO fading channels. The bounds obtained in this paper are shown useful as performance prediction measures for MIMO systems which employ turbo-like block codes as the outer code to derive the space-time inner code. The error exponents for MIMO channels are also derived from the bounds, and then compared with the classical Gallager error exponents as well as the channel capacities. The random coding bounds associated with the maximum likelihood receiver exhibit good match with the extensive system simulation results obtained with a turbo-iterative receiver.     

Bounds on the error performance of coding for nonindependentRician-fading channels

New upper bounds on the error performance of coded systems for Rician channels are presented. The fading channels need not be fully interleaved to obtain meaningful performance results. These bounds hold for coherent, differentially coherent and noncoherent demodulation of binary signals. They provide a useful analytical approach to the evaluation of the error performance of convolutional or block coding and they may be generalized to M-ary signals and trellis modulation. The approach allows for complex bounds using the fine structure of the code, for simpler bounds similar to those on memoryless channels and finally for a random coding bound using the cutoff rate of the channel. The analysis thus permits a step by step evaluation of coded error performances for Rician-fading channels     

Tight exponential upper bounds on the ML decoding error probability of block codes over fully interleaved fading channels

We derive tight exponential upper bounds on the decoding error probability of block codes which are operating over fully interleaved Rician fading channels, coherently detected and maximum-likelihood decoded. It is assumed that the fading samples are statistically independent and that perfect estimates of these samples are provided to the decoder. These upper bounds on the bit and block error probabilities are based on certain variations of the Gallager bounds. These bounds do not require integration in their final version and they are reasonably tight in a certain portion of the rate region exceeding the cutoff rate of the channel. By inserting interconnections between these bounds, we show that they are generalized versions of some reported bounds for the binary-input additive white Gaussian noise channel.     

Composition bounds for channel block codes

The performance of Channel block codes for a general channel is studied by examining the relationship between the rate of a code, the joint composition of pairs of codewords, and the probability of decoding error. At fixed rate, lower bounds and upper bounds, both on minimum Bhattacharyya distance between codewords and on minimum equivocation distance between codewords, are derived. These bounds resemble, respectively, the Gilbert and the Elias bounds on the minimum Hamming distance between codewords. For a certain large class of channels, a lower bound on probability of decoding error for low-rate channel codes is derived as a consequence of the upper bound on Bhattacharyya distance. This bound is always asymptotically tight at zero rate. Further, for some channels, it is asymptotically tighter than the straight line bound at low rates. Also studied is the relationship between the bounds on codeword composition for arbitrary alphabets and the expurgated bound for arbitrary channels having zero error capacity equal to zero. In particular, it is shown that the expurgated reliability-rate function for blocks of letters is achieved by a product distribution whenever it is achieved by a block probability distribution with strictly positive components.     

On improved bounds on the decoding error probability of block codesover interleaved fading channels, with applications to turbo-like codes

We derive here improved upper bounds on the decoding error probability of block codes which are transmitted over fully interleaved Rician fading channels, coherently detected and maximum-likelihood (ML) decoded. We assume that the fading coefficients during each symbol are statistically independent (due to a perfect channel interleaver), and that perfect estimates of these fading coefficients are provided to the receiver. The improved upper bounds on the block and bit error probabilities are derived for fully interleaved fading channels with various orders of space diversity, and are found by generalizing some previously introduced upper bounds for the binary-input additive white Gaussian nose (AWGN) channel. The advantage of these bounds over the ubiquitous union bound is demonstrated for some ensembles of turbo codes and low-density parity-check (LDPC) codes, and it is especially pronounced in a portion of the rate region exceeding the cutoff rate. Our generalization of the Duman and Salehi bound (Duman and Salehi 1998, Duman 1998) which is based on certain variations of Gallager's (1965) bounding technique, is demonstrated to be the tightest reported upper bound. We therefore apply it to calculate numerically upper bounds on the thresholds of some ensembles of turbo-like codes, referring to the optimal ML decoding. For certain ensembles of uniformly interleaved turbo codes, the upper bounds derived here also indicate good match with computer simulation results of efficient iterative decoding algorithms     

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.     

On general Gilbert bounds

We define a distance measure for block codes used over memoryless channels and show that it is related to upper and lower bounds on the low-rate error probability in the same way as Hamming distance is for binary block codes used over the binary symmetric channel. We then prove general Gilbert bounds for block codes using this distance measure. Some new relationships between coding theory and rate-distortion theory are presented.     

Performance analysis on LDPC-Coded systems over quasi-static (MIMO) fading channels

In this paper, we derive closed form upper bounds on the error probability of low-density parity-check (LDPC) coded modulation schemes operating on quasi-static fading channels. The bounds are obtained from the so-called Fano- Gallager?s tight bounding techniques, and can be readily calculated when the distance spectrum of the code is available. In deriving the bounds for multiple-input multiple-output (MIMO) systems, we assume the LDPC code is concatenated with the orthogonal space-time block code as an inner code. We obtain an equivalent single-input single-output (SISO) channel model for this concatenated coded-modulation system. The upper bounds derived here indicate good matches with simulation results of a complete transceiver system over Rayleigh and Rician MIMO fading channels in which the iterative detection and decoding algorithm is employed at the receiver.     

A New Union Bound on the Error Probability of Binary Coded OFDM Systems in Wireless Environments

Orthogonal Frequency Division Multiplexing (OFDM) systems are commonly used to mitigate frequency-selective multipath fading and provide high-speed data transmission. In this paper, we derive new union bounds on the error probability of a coded OFDM system in wireless environments. In particular, we consider convolutionally coded OFDM systems employing single and multiple transmit antennas over correlated block fading (CBF) channels with perfect channel state information (CSI). Results show that the new union bound is tight to simulation results. In addition, the bound accurately captures the effect of the correlation between sub-carriers channels. It is shown that as the channel becomes more frequency-selective, the performance get better due to the increased frequency diversity. Moreover, the bound also captures the effect of multi-antenna as space diversity. The proposed bounds can be applied for coded OFDM systems employing different coding schemes over different channel models.     

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.     

Performance of truncated type-II hybrid ARQ schemes with noisyfeedback over block fading channels

This paper considers truncated type-II hybrid automatic repeat-request (ARQ) schemes with noisy feedback over block fading channels. With these ARQ techniques, the number of retransmissions is limited, and, similar to forward error correction (FEC), error-free delivery of data packets cannot be guaranteed. Bounds on the average number of transmissions, the average coding rate as well as the reliability of the schemes are derived using random coding techniques, and the performance is compared with FEC. The random coding bounds reveal the achievable performance with block codes and maximum-likelihood soft-decision decoding. Union upper bounds and simulation results show that over block fading channels, these bounds can be closely approached with simple terminated convolutional codes and soft-decision Viterbi decoding. Truncated type-II hybrid ARQ and the corresponding FEC schemes have the same probability of packet erasure; however, the truncated ARQ schemes offer a trade-off between the average coding rate and the probability of undetected error. Truncated ARQ schemes have significantly higher average coding rates than FEC at high and medium signal-to-noise ratio even with noisy feedback. Truncated ARQ can be viewed as adaptive FEC that adapts to the instantaneous channel conditions     

An upper bound on turbo codes performance over quasi-static fading channels

This letter proposes an upper bound on the performance of turbo-codes over quasi-static fading channels. First an upper bound is derived for the case of a single-input single-output channel. The result is then extended to the case of a serial concatenation of a turbo-code and a space-time block code. Unlike a simple extension of the union bound, the derived upper bounds are shown to converge for all signal-to-noise ratios. Additionally the closed form upper bounds obtained confirm analytically that, unlike over additive white Gaussian noise channels, turbo-code performance does not improve by increasing frame length over quasi-static fading channels.     

Improved Lower Bounds for the Capacity of i.i.d. Deletion and Duplication Channels

This paper considers the capacity of binary deletion channels, where bits are deleted independently with probability d. It improves significantly upon the best previous framework used to obtain provable lower bounds on this capacity by utilizing a stronger definition of a typical output from the channel. The new results give the best known provable bounds on the capacity for all values of d. Moreover, the techniques presented here extend to yield lower bounds for channels with certain types of random insertions, namely, duplications, or combinations of duplications and deletions. To demonstrate these techniques in this context, two binary channels are analyzed: a channel where each transmitted bit is copied with probability nu and a channel where each transmitted bit is copied a geometrically distributed number of times.     

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.     

DC-free coset codes

A class of block coset codes with disparity and run-length constraints are studied. They are particularly well suited for high-speed optical fiber links and similar channels, where DC-free pulse formats, channel error control, and low-complexity encoder-decoder implementations are required. The codes are derived by partitioning linear block codes. The encoder and decoder structures are the same as those of linear block codes with only slight modifications. A special class of DC-free coset block codes are derived from BCH codes with specified bounds on minimum distance, disparity, and run length. The codes have low disparity levels (a small running digital sum) and good error-correcting capabilities     

Achievable Performance of Orthogonal STBC Over Spatially Correlated Rician Channels

The effect of spatial correlation on the performance of orthogonal space-time block codes (OSTBCs) over multiple-input-multiple-output (MIMO) Rician fading channels is studied. Asymptotic error-rate formulas for OSTBC with high average signal-to-noise ratios (ASNRs) over arbitrarily correlated Rician MIMO channels are derived in terms of the diversity and coding gains. Our results show that, in correlated fading, the phase vector phi of the channel line-of-sight (LOS) components affects the effective Rice K-factor at the OSTBC receiver output and, hence, may result in a coding gain that is significantly higher than that for independent Rician MIMO channels. Furthermore, when the channel covariance matrix is rank deficient and under some additional mild conditions, the error and outage probabilities of OSTBC achieve those in a nonfading additive-white-Gaussian-noise channel. For both cases of full-rank and rank-deficient channel covariance matrices, analytical expressions of optimal and worst case phase vectors phi, and exact upper and lower bounds of OSTBC performance are derived. These results provide new insights into the achievable performance of OSTBC over correlated Rician MIMO channels and, if incorporated into future multiple antenna systems design, will bring about significant performance enhancement     

Near-optimal limited-search detection on ISI/CDMA channels anddecoding of long convolutional codes

We derive an upper bound on the bit-error probability (BEP) in limited-search detection over a finite interference channel. A unified channel model is presented; this includes finite-length intersymbol interference channels and multiuser CDMA channels as two special cases. We show that the BEP of the M-algorithm (MA) is bounded from above by the sum of three terms: an upper bound on the error probability of the Viterbi (1967) algorithm (VA) detection given by Forney Jr. (1972), and upper bounds on the error probabilities of two types of erroneous decision caused by the correct path loss event. We prove that error propagation (in terms of the mean recovery step number) is finite for all finite interference channels. The convergence and asymptotic behavior of the upper bounds are studied. The results show that, if a channel satisfies certain mild conditions, all series in the bounds are convergent. One of the key results is that, for any finite interference channel satisfying certain mild conditions. the asymptotic BEP of the MA is bounded by the same upper and lower bounds (which have the same asymptotical behavior) as those for the VA if the correct path loss probability is smaller than that of the VA. Furthermore, we extend the above results to near optimally decode long convolutional codes in a short packet format (about 200-300 bits). We present a nonsorting combined M/T algorithm and showed that the M/T algorithm with M>2( ^dfree/ⁿ) and T>(d_freeE_b)/n can near-optimally decode the code. We also propose a hierarchical decoding algorithm (HDA) to further cut down the average decoding complexity. Numerical results show that the bounds are reasonably tight. The HDA can achieve a performance within about 0.8 dB of the sphere-packing lower bound for a packet error rate of 10^-4 and a packet length below 200 bits, which is the best reported decoding performance so far for block sizes from 100 to 200 bits     

A new universal random coding bound for the multiple-access channel

The minimum average error probability achievable by block codes on the two-user multiple-access channel is investigated. A new exponential upper bound is found which can be achieved universally for all discrete memoryless multiple-access channels with given input and output alphabets. It is shown that the exponent of this bound is greater than or equal to those of previously known bounds. Moreover, examples are given where the new exponent is strictly larger     

Bounds on ε-rate for linear, time-invariant,multiinput/multioutput channels

Upper and lower bounds on the ε-rate of a linear, time-invariant multiple input multiple output channel are derived by using the same volume argument previously used by W.L. Root (1968) for single input single output channels. Because these bounds are not very tight, an approximation to the ε-rate is presented which lies between the upper and lower bounds, and can be used to compare ε-rates for different channels. The extension considered uses a result due to Lerer (1978) on the eigenvalue distribution of a convolution operator with a matrix kernel (impulse response). The present results are used to assess the increase in data rate attainable by designing input signals which exploit the multidimensional nature of the channel, relative to treating each constituent channel in isolation. Numerical results based upon a simple model for two coupled twisted-pair wires are presented