Chernoff bounds on pairwise error probabilities of space-time codes

We derive Chernoff bounds on pairwise error probabilities of coherent and noncoherent space-time signaling schemes. First, general Chernoff bound expressions are derived for a correlated Ricean fading channel and correlated additive Gaussian noise. Then, we specialize the obtained results to the cases of space-time-separable noise, white noise, and uncorrelated fading. We derive approximate Chernoff bounds for high and low signal-to-noise ratios (SNRs) and propose optimal signaling schemes. We also compute the optimal number of transmitter antennas for noncoherent signaling with unitary mutually orthogonal space-time codes.     

Tight error bounds for asynchronous multicarrier CDMA and theirapplication

Upper and lower bounds on the average bit error rate for binary phase-shift keying (BPSK), asynchronous multicarrier (MC)-CDMA communications using coherent detection are derived. The bounds can be made very tight by adjusting a parameter in the computation and this is demonstrated by numerical examples. Based on the derived bounds it is shown by numerical examples that the performance of asynchronous MC-CDMA using Zadoff-Chu sequences is better than that using Walsh codes     

Tight bounds on the bit-error probabilities of 2DPSK and 4DPSK innonselective Rician fading

The bit-error probabilities (BEPs) of matched-filtered differentially detected two differential phase-shift keying (2DPSK) and 4DPSK over the nonselective Rician-fading channel are studied using the upper bound in Kam (1994). The bound coincides with the exact error probability result in the binary case and provides very accurate estimates of the BEP in the quadriphase case, especially for high signal-to-noise ratio (SNR) and small K-factor. The bound provides a simple analytical handle for studying the behavior of the error probability as a function of the Doppler spectrum, the Doppler bandwidth, and the K-factor. A new result is obtained for the irreducible error-rate floor. The results are useful for the design of digital mobile radio communication systems     

Tight bounds on the error probability of coded modulation schemesin Rayleigh fading channels

This paper presents a tight upper bound on the bit error performance of coded modulation schemes in Rayleigh fading channels. Upper and lower bounds on the pairwise error probability are first derived. The upper bound is then expressed in a product form to be used with the transfer function bounding technique. This upper bound has the same simplicity as the union-Chernoff bound while providing closer results to the exact expression. Examples for the case of four-state and eight-state TCM 8PSK schemes are also given to illustrate the tightness and the application of this upper bound     

Upper bounds to error probabilities of coded systems beyond the cutoff rate

A family of upper bounds to error probabilities of coded systems was recently proposed by D. Divsalar (see IEEE Communication Theory Workshop, 1999; JPL TMO Prog. Rep. 42-139, 1999). These bounds are valid for transmission over the additive white Gaussian noise channel, and require only the knowledge of the weight spectrum of the code words. After illustrating these bounds, we extend them to fading channels. Contrary to the union bound, our bounds maintain their effectiveness below the signal-to-noise ratio (SNR) at which the cutoff rate of the channel equals the rate of the code. Some applications are shown. First, we derive upper bounds to the minimum SNR necessary to achieve zero error probability as the code block length increases to infinity. Next, we use our bounds to predict the performance of turbo codes and low-density parity-check codes.     

Tight error bounds for space-time orthogonal block codes under slow Rayleigh flat fading

The performance of space-time orthogonal block (STOB) codes over slow Rayleigh fading channels and maximum-likelihood (ML) decoding is investigated. Two Bonferroni-type bounds (one upper bound and one lower bound) for the symbol error rate (SER) and bit error rate (BER) of the system are obtained. The bounds are expressed in terms of the pairwise error probabilities (PEPs) and the two-dimensional pairwise error probabilities (2-D PEPs) of the transmitted symbols. Furthermore, the bounds can be efficiently evaluated and they hold for arbitrary (nonstandard) signaling schemes and mappings. Numerical results demonstrate that the bounds are very accurate in estimating the performance of STOB codes. In particular, the upper and lower bounds often coincide even at low channel signal-to-noise ratios, large constellation sizes, and large diversity orders.     

Generic error probabilities

This paper presents new forms for an error probability associated, with the phase angle between two vectors perturbed by Gaussian noise. An interesting consequence of the underlying generic form is a new expression for the symbol error rate in MDPSK that is very similar to its counterpart for MPSK. The generic error probability is further shown to contain as special cases MPSK, MDPSK, CPFSK, and digital FM; and to give a new expression for the Marcum Q-function. The generic error probability also simplifies the error probability expressions in other situations such as nonorthogonal signaling, maximum likelihood differential detection of DPSK with block-by-block detection, and Gray coding of MDPSK     

Tight bounds on the redundancy of Huffman codes

A method for deriving optimal upper bounds on the redundancy of binary Huffman codes in terms of the probability p₁ of the most likely source letter is presented. This method will be used to compute bounds for all p₁⩾1/127, which were previously known only for a few special cases. Furthermore, the known optimal lower bound for binary Huffman codes is generalized to arbitrary code alphabets and some upper bounds for D-ary Huffman codes, 2⩽D<∞, are given, which are the tightest possible for all p₁⩾1/2     

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.     

On error bounds and turbo-codes

Turbo-codes have been hailed as the ultimate step toward achieving the capacity limit Shannon established some 50 years ago. We look at the performance of turbo-codes with respect to various information theoretic error bounds. This comparison suggests that, if (block, or) frame error rates are considered, careful interleaver design is necessary to ensure an error performance within a fraction of a decibel of the theoretical limit for large block sizes, while random interleavers perform well for block sizes smaller than about 2 K. If the bit error performance is considered, interleaver design seems to have only a minor effect, and the codes perform close to the limit for all block sizes considered     

New upper bounds on error exponents

We derive new upper bounds on the error exponents for the maximum-likelihood decoding and error detecting in the binary symmetric channels. This is an improvement on the best earlier known bounds by Shannon-Gallager-Berlekamp (1967) and McEliece-Omura (1977). For the probability of undetected error the new bounds are better than the bounds by Levenshtein (1978, 1989) and the bound by Abdel-Ghaffar (see ibid., vol.43, p.1489-502, 1997). Moreover, we further extend the range of rates where the undetected error exponent is known to be exact. The new bounds are based on an analysis of possible distance distributions of the codes along with some inequalities relating the distance distributions to the error probabilities     

ERROR-DETECTING CODES AND UNDETECTED ERROR PROBABILITIES

The definition of good codes for error-detection is given. It is proved that a (n, k) linear block code in GF(q) are the good code for error-detection, if and only if its dual code is also. A series of new results about the good codes for error-detection are derived. New lower bounds for undetected error probabilities are obtained, which are relative to n and k only, and not the weight structure of the codes.     

Tight upper bounds on the redundancy of Huffman codes

Bounds on the redundancy of Huffman codes in terms of the probability p₁ of the most likely source letter are provided. In particular, upper bounds are presented that are sharper than the bounds given recently by R.G. Gallager (ibid., vol.IT-24, no.6, p.668-74, Nov.1978) and by R.M. Capocelli et al. (ibid., vol. IT-32, no.6, p.854-857, Nov. 1986) for an interval 2/(2^l+1+1)<p₁<1/(2^l-1), l⩾2. It is shown that the new bounds are the tightest possible for these intervals     

On multiple interference error bounds

This letter presents upper and lower bounds for the error rate for (effectively) PAM signalling in the presence of thermal noise, cochannel interference, and intersymbol interference. To accomplish this, two known bounds and one new lower bound are used. For a class of examples from the literature, these simple bounds were found to provide an error-rate estimate accurate to 1 db in system SNR. Computational experiments indicate that this level of accuracy can be achieved when the system's eye is open by at least a factor of two.     

Exponential-type error probabilities for multiterminal hypothesistesting

Multiterminal hypothesis testing is considered, subject to the exponential-type constraint α_n⩽exp(-nr) on the error probability of the first kind. The problem is to determine the minimum β*_n of the error probability of the second kind under the given constraint at limited rates R₁ and R₂ for observing the respective pairs of variables. Good lower bounds on the power exponent for β*_n are presented by invoking basic properties of r-divergent sequences. In particular, the one-bit and the zero-rate compression cases are considered. The power exponent for the former and a lower bound for the latter are established     

Bounds on the undetected error probabilities of linear codes forboth error correction and detection

The author investigates the (n, k, d⩾2t+1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t=1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n+1) [2^n-k-n]^-1 when used on a binary symmetric channel with transition probability less than 2/n     

Calculation of error probabilities for distance-invariant nonlinear error control codes

Expressions are given for the distance distribution of some nonlinear codes which enable error probabilities to be calculated using methods commonly associated with linear error control codes.<>     

Lower bounds on the mean square estimation error

A general class of lower bounds on the mean square error (mse) in random parameter estimation is formulated. These bounds are generated using functions of the parameter and the data that are orthogonal to the data. A particular choice in the class yields a new lower bound which is superior to both the Cramer-Rao and Bobrovsky-Zakai lower bounds.     

Tight bounds for LDPC and LDGM codes under MAP decoding

A new method for analyzing low-density parity-check (LDPC) codes and low-density generator-matrix (LDGM) codes under bit maximum a posteriori probability (MAP) decoding is introduced. The method is based on a rigorous approach to spin glasses developed by Francesco Guerra. It allows one to construct lower bounds on the entropy of the transmitted message conditional to the received one. Based on heuristic statistical mechanics calculations, we conjecture such bounds to be tight. The result holds for standard irregular ensembles when used over binary-input output-symmetric (BIOS) channels. The method is first developed for Tanner-graph ensembles with Poisson left-degree distribution. It is then generalized to "multi-Poisson" graphs, and, by a completion procedure, to arbitrary degree distribution     

On computing undetected error probabilities on the Gilbert channel

Two methods for computing the probability of undetected error on the Gilbert (1960) channel are examined. First, using a method proposed by Kittel (1978), we study some standard cyclic redundancy codes and compare the results with those on the binary symmetric channel. Then we consider a general method of approximate code evaluation, proposed by Elliott, which involves P(m, n), the probability of m errors in a block of length n bits. A nonrecursive technique for computing P(m, n) on the Gilbert channel is described