Improved upper bounds on sizes of codes

Let A(n,d) denote the maximum possible number of codewords in a binary code of length n and minimum Hamming distance d. For large values of n, the best known upper bound, for fixed d, is the Johnson bound. We give a new upper bound which is at least as good as the Johnson bound for all values of n and d, and for each d there are infinitely many values of n for which the new bound is better than the Johnson bound. For small values of n and d, the best known method to obtain upper bounds on A(n,d) is linear programming. We give new inequalities for the linear programming and show that with these new inequalities some of the known bounds on A(n,d) for n⩽28 are improved     

Lower bounds on the error probability of block codes based on improvements on de Caen's inequality

New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.     

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.     

Generalized Union Bound for Space–Time Codes

Gallager's second bounding technique, also known as the generalized union bound, is employed to derive a new upper bound on the error probability of space-time codes (STCs) with maximum-likelihood (ML) decoding on quasi-static Rayleigh fading channels. The new bound is distinguished by two characteristics: unlike the classical union bound, the new bound is rapidly convergent and is only a few decibels away from simulation results; and compared with Gallager's first bound, it has better computational efficiency and numerical stability. Hence, the new bound is a useful tool for performance analysis and computer search of good STCs. Moreover, the correlation between fading coefficients is easily accommodated by the new bound. The application of the new bound to convolutional coding on block-fading channels is also demonstrated, and an improved version is derived for the bit-error probability of maximum a posteriori probability decoding     

A lower bound on filtering error with application to phase demodulation

A new lower bound on nonlinear filtering mean square error (MSE) based on rate distortion theory is derived for message and observation models described by state space equations. Unlike previous contributions, the present bound is general in applicability: it can be used in beth the continuous and discrete time cases; it is applicable during the transient (e.g., acquisition) as well as steady state phases; vector-valued processes of arbitrary dimension can be treated; stationary as well as nonstationary processes can be considered; and essentially no restrictions are placed on the nonlinearities. Two easily implemented approaches to the evaluation of the new lower bound are given: one is analytical in nature while the other uses Monte Carlo simulation techniques. The theory is extended to filtering with distortion measures other then MSE. The MSE lower bound is applied to a phase demodulation problem and compared to other lower bounds which are based on rate distortion theory and the Cramacute{e}r-Rao inequality. Results for this problem show the new lower bound to be tighter than the others in the nonlinear, high noise-to-signal ratio region of receiver operation.     

An Improved Sphere-Packing Bound for Finite-Length Codes Over Symmetric Memoryless Channels

This paper derives an improved sphere-packing (ISP) bound for finite-length error-correcting codes whose transmission takes place over symmetric memoryless channels, and the codes are decoded with an arbitrary list decoder. We first review classical results, i.e., the 1959 sphere-packing (SP59) bound of Shannon for the Gaussian channel, and the 1967 sphere-packing (SP67) bound of Shannon et al. for discrete memoryless channels. An improvement on the SP67 bound, as suggested by Valembois and Fossorier, is also discussed. These concepts are used for the derivation of a new lower bound on the error probability of list decoding (referred to as the ISP bound) which is uniformly tighter than the SP67 bound and its improved version. The ISP bound is applicable to symmetric memoryless channels, and some of its applications are presented. Its tightness under maximum-likelihood (ML) decoding is studied by comparing the ISP bound to previously reported upper and lower bounds on the ML decoding error probability, and also to computer simulations of iteratively decoded turbo-like codes. This paper also presents a technique which performs the entire calculation of the SP59 bound in the logarithmic domain, thus facilitating the exact calculation of this bound for moderate to large block lengths without the need for the asymptotic approximations provided by Shannon.     

On the dimension of subfield subcodes

A new lower bound for the dimension of a subfield subcode is given. This bound improves the well-known lower bound of P. Delsarte (1975) and coincides in many cases with the true dimension of the code. Alternant codes and geometric Goppa codes are discussed as special cases     

A Generalized Upper Bound and a Multilevel Construction for Distance-Preserving Mappings

A new general upper bound is derived on the sum of the Hamming distances between sequences when mapping from one set of sequences to another. It is shown that a similar upper bound for mappings from binary sequences to permutation sequences is a special case of this upper bound and this is used to evaluate known mappings. Also, new distance-preserving mappings (DPMs) from binary sequences to permutation sequences are presented, based on a multilevel construction. In addition to explicit distance-conserving mappings, distance-increasing, and distance-reducing mappings are also presented. Several of the new DPMs attain the upper bound     

Universal bound on the performance of lattice codes

We present a lower bound on the probability of symbol error for maximum-likelihood decoding of lattices and lattice codes on a Gaussian channel. The bound is tight for error probabilities and signal-to-noise ratios of practical interest, as opposed to most existing bounds that become tight asymptotically for high signal-to-noise ratios. The bound is also universal; it provides a limit on the highest possible coding gain that may be achieved, at specific symbol error probabilities, using any lattice or lattice code in n dimensions. In particular, it is shown that the effective coding gains of the densest known lattices are much lower than their nominal coding gains. The asymptotic (as n→∞) behavior of the new bound is shown to coincide with the Shannon (1948) limit for Gaussian channels     

Reliability Bounds for Coherent Communications with Maximum Likelihood Phase Estimation

This concise paper describes a new technique for upper bounding the performance of coherent binary phase-shift keyed (PSK) systems which derive a phase reference using one-shot maximum likelihood phase estimates. By performance, we mean any positive monotonically increasing function of phase error, such as error probability or power loss. A tight upper bound to the phase error cumulative distribution is shown to consist of the concave support to a previously derived Chernov bound. Performance measures appropriate for binary PSK systems are listed and evaluated with the new bound.     

A New Bound for the Minimum Distance of a Cyclic Code From Its Defining Set

A new lower bound for the distance of cyclic codes is proposed. This bound depends on the defining set of the code, like several other bounds. The proposed bound improves upon the Bose-Chaudhuri-Hocquehghen (BCH) bound and, for some codes, improves upon the Hartmann-Tzeng bound and the Roos bound as well     

A new upper bound on the ML decoding error probability of linear binary block codes in AWGN interference

Performance evaluation of maximum-likelihood (ML) soft-decision-decoded binary block codes is usually carried out using bounding techniques. Many tight upper bounds on the error probability of binary codes are based on the so-called Gallager's first bounding technique (GFBT). The tangential sphere bound (TSB) of Poltyrev which has been believed for many years to offer the tightest bound developed for binary block codes is an example. Within the framework of the TSB and GFBT, we apply a new method referred to as the "added-hyper-plane" (AHP) technique, to the decomposition of the error probability. This results in a bound developed upon the application of two stages of the GFBT with two different Gallager regions culminating in a tightened upper bound beyond the TSB. The proposed bound is simple and only requires the spectrum of the binary code.     

Some notes on Varn coding

A duality between Varn (1971) coding and Tunstall (1968) coding is demonstrated and new bounds on the expected transmission cost per source symbol for Varn codes are established. For binary channels, the superiority of the new upper bound over Krause's (1962) upper bound is proven     

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.     

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     

A new interpretation on the MMSE as a robust MEE criterion

The minimum mean-square error (MMSE) and minimum error entropy (MEE) are two important criteria in the estimation related problems. The MMSE can be viewed as a robust MEE criterion in the minimax sense, as its minimization is equivalent to minimizing an upper bound (the maximum value) of the error entropy. This note gives a new and more meaningful interpretation on the robustness of MMSE for problems in which there exists uncertainty in the probability model. It is shown that the MMSE estimator imposes an upper bound on error entropy for the true model. The upper bound consists of two terms. The first term quantifies the “MMSE performance” under nominal conditions, and the second term measures the “distance” between the true and nominal models. This robustness property is parallel to that of the risk-sensitive estimation. Illustration examples are included to confirm the robustness of MMSE.     

An Upper Bound on the Error Probability for Differential Phase-Shift Keying in the Presence of Additive Gaussian White Noise and Peak-Limited Interference

A new upper bound on the error probability for differential phase-shift keyed transmission in the presence of additive Gaussian white noise (AGWN) and peak-limited interference is estimated using numerical techniques. An error probability expression is evaluated for various interference angles and the maximum value found is chosen as the upper bound. A simple approximation is presented and found to be close to the upper bound. This upper bound is shown to be a realistic bound, hence it could be useful for practical design purposes.     

Double circulant quadratic residue codes

We give a lower bound for the minimum distance of double circulant binary quadratic residue codes for primes p/spl equiv//spl plusmn/3(mod8). This bound improves on the square root bound obtained by Calderbank and Beenker, using a completely different technique. The key to our estimates is to apply a result by Helleseth, to which we give a new and shorter proof. Combining this result with the Weil bound leads to the improvement of the Calderbank and Beenker bound. For large primes p, their bound is of order /spl radic/(2p) while our new improved bound is of order 2/spl radic/p. The results can be extended to any prime power q and the modifications of the proofs are briefly indicated.     

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     

A PAC-Bayesian margin bound for linear classifiers

We present a bound on the generalization error of linear classifiers in terms of a refined margin quantity on the training sample. The result is obtained in a probably approximately correct (PAC)-Bayesian framework and is based on geometrical arguments in the space of linear classifiers. The new bound constitutes an exponential improvement of the so far tightest margin bound, which was developed in the luckiness framework, and scales logarithmically in the inverse margin. Even in the case of less training examples than input dimensions sufficiently large margins lead to nontrivial bound values and-for maximum margins-to a vanishing complexity term. In contrast to previous results, however, the new bound does depend on the dimensionality of feature space. The analysis shows that the classical margin is too coarse a measure for the essential quantity that controls the generalization error: the fraction of hypothesis space consistent with the training sample. The practical relevance of the result lies in the fact that the well-known support vector machine is optimal with respect to the new bound only if the feature vectors in the training sample are all of the same length. As a consequence, we recommend to use support vector machines (SVMs) on normalized feature vectors only. Numerical simulations support this recommendation and demonstrate that the new error bound can be used for the purpose of model selection.