On the redundancy of optimal binary prefix-condition codes for finite and infinite sources (Corresp.)

A new lower bound, which is the tightest possible, is obtained for the redundancy of optimal bimuy prefix-condition (OBPC) codes for a memoryless source for which the probability of the most likely source letter is known. It is shown that this bound, and upper bounds obtained by Gallager and Johnsen, hold for infinite as well as finite source alphabets. Also presented are bounds on the redundancy of OBPC codes for sources satisfying the condition that each of the first several probabilities in the list of source probabilities is sufficiently large relative to the sum of the remaining probabilities.     

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.     

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.     

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     

Bounds on Error in Signal Parameter Estimation

In this correspondence, the problem of lower bounds on mean-square error in parameter estimation is considered. Lower bounds on mean-square error can be used, for instance, to bound the performances, namely the attainable output signal-to-noise ratio, of pulse modulation transmission systems, such as pulse-position modulation (PPM) or pulse-frequency modulation (PFM). The tightest lower bounds to mean-square error previously known are the Ziv-Zakai bounds; the analysis carried out in this paper, which is based on an inequality first obtained by Kotel'nikov, leads to lower bounds tighter than previously known bounds.     

A unification of Cramér-Rao type bounds (Corresp.)

This correspondence examines multiparameter generalizations of the Cramér-Rao (C-R) bound and related bounds from a new viewpoint. We derive a general class of bounds and show that Rao's generalization is the tightest (bes0 of the class. A bound reported by Zacks is another member of the class. This derivation of the C-R bound emphasizes its optimum nature. The relationship of the general class to Barankin bounds is also discussed.     

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     

Bounds on the redundancy of Huffman codes (Corresp.)

New upper bounds on the redundancy of Huffman codes are provided. A bound that for2/9 leq P_{1} leq 0.4is sharper than the bound of Gallager, when the probability of the most likely source letterP_{1}is the only known probability is presented. The improved bound is the tightest possible for1/3 leq P_{1} leq 0.4. Upper bounds are presented on the redundancy of Huffman codes when the extreme probabilitiesP_{1}andP_{N}are known.     

On the redundancy of binary Huffman codes (Corresp.)

Some properties of Huffman codes are presented. It is shown that knowing the probabilityP_{1}of the most likely source letter, there exist new lower and upper bounds on the redundancy of the Huffman code which are tighter forP_{1} geq 0.4than those given by Shannon's first theorem or by the more recent results of Gallager. It is also shown that the new bounds are the tightest possible forP_{1} geq 0.4when it is supposed that PI is the only known probability.     

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     

On the Fingerprinting Capacity Under the Marking Assumption

We address the maximum attainable rate of fingerprinting codes under the marking assumption, studying lower and upper bounds on the value of the rate for various sizes of the attacker coalition. Lower bounds are obtained by considering typical coalitions, which represents a new idea in the area of fingerprinting and enables us to improve the previously known lower bounds for coalitions of size two and three. For upper bounds, the fingerprinting problem is modeled as a communications problem. It is shown that the maximum code rate is bounded above by the capacity of a certain class of channels, which are similar to the multiple-access channel (MAC). Converse coding theorems proved in the paper provide new upper bounds on fingerprinting capacity. It is proved that capacity for fingerprinting against coalitions of size two and three over the binary alphabet satisfies and , respectively. For coalitions of an arbitrary fixed size , we derive an upper bound on fingerprinting capacity in the binary case. Finally, for general alphabets, we establish upper bounds on the fingerprinting capacity involving only single-letter mutual information quantities.     

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.     

Improved Upper Bounds on the Reliability Function of the Gaussian Channel

A new lower bound on the distance distribution of spherical codes is derived. This yields two new upper bounds on the reliability function of the Gaussian channel. These bounds outperform previously known bounds, and imply a new range of rates for which the exact value of the reliability function is known.     

On the symmetric information rate of two-dimensional finite-state ISI channels

We derive a pair of bounds (upper and lower) on the symmetric information rate of a two-dimensional finite-state intersymbol interference (ISI) channel model. For channels with small impulse response support, they can be estimated via a modified forward recursion of the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm. The convergence of the bounds is also analyzed. To relax the constraint on the size of the impulse response, a new upper bound is proposed which allows the tradeoff of the computational complexity and the tightness of the bound. These bounds are further extended to d-dimensional (d>2) ISI channels.     

Information rates of non-Gaussian processes

The rate distortion functionR(D)of an information source was introduced by Shannon to specify the channel capacity required in transmitting information from the source with an average distortion not exceedingD. Exact rates have been calculated for Gaussian sources under a mean-square error criterion. For non-Gaussian continuous sources, Shannon has given upper and lower bounds onR(D). In specific cases, the difference between these two bounds may not be sufficiently small to provide a useful estimate ofR(D). The present paper is concerned with improving estimates of information rates of non-Gaussian sources under a mean-square error criterion. The sources considered are ergodic, and their statistical properties are characterized by a bounded and continuousn-dimensional probability density function. The paper gives a set of necessary and sufficient conditions forR(D)to equal Shannon's lower bound. For sources satisfying these conditions, exact rate calculations are possible. For sources that do not satisfy the required conditions, an improved upper bound is obtained that never exceeds Shannon's upper bound. Under rather general conditions, the new upper bound approaches Shannon's lower bound for small values of distortion, so that the true value ofR(D)can be estimated very accurately for smallD.     

Reliability function of a discrete memoryless channel at rates above capacity (Corresp.)

Asymptotically coincident upper and lower bounds on the exponent of the largest possible probability of the correct decoding of block codes are given for all rates above capacity. The lower bound sharpens Omura's bound. The upper bound is proved by a new and simple combinatorial argument.     

Improved bounds on the word error probability of RA(2) codes with linear-programming-based decoding

This paper deals with the linear-programming-based decoding algorithm of Feldman and Karger for repeat-accumulate "turbo-like" codes. We present a new structural characterization that captures the event that decoding fails. Based on this structural characterization, we develop polynomial algorithms that, given an RA(2) code, compute upper and lower bounds on the word error probability P/sub w/ for the binary-symmetric and the additive white Gaussian noise (AWGN) channels. Our experiments with an implementation of these algorithms for bounding P/sub w/ demonstrate in many interesting cases an improvement in the upper bound on the word error probability by a factor of over 1000 compared to the bounds by Feldman et al.. The experiments also indicate that the improvement in upper bound increases as the codeword length increases and the channel noise decreases. The computed lower bounds on the word error probability in our experiments are roughly ten times smaller than the upper bound.     

Asymptotic analysis for transmission capacity of wireless Ad-hoc networks

This article puts forward a new solution to the bound of the outage probability and transmission capacity of Ad-hoc networks. For the proofs of the upper and lower bounds are too complex, a much easier way is introduced to get the same results, and by using Taylor series, the asymptotic bound is derived. By comparing with the simulation results, we found that the asymptotic bound is sufficient accurate when the network parameters are selected properly, and is tighter than the upper and lower bounds.     

Estimation variance bounds of importance sampling simulations indigital communication systems

In practical applications of importance sampling (IS) simulation, two basic problems are encountered, that of determining the estimation variance and that of evaluating the proper IS parameters needed in the simulations. The authors derive new upper and lower bounds on the estimation variance which are applicable to IS techniques. The upper bound is simple to evaluate and may be minimized by the proper selection of the IS parameter. Thus, lower and upper bounds on the improvement ratio of various IS techniques relative to the direct Monte Carlo simulation are also available. These bounds are shown to be useful and computationally simple to obtain. Based on the proposed technique, one can readily find practical suboptimum IS parameters. Numerical results indicate that these bounding techniques are useful for IS simulations of linear and nonlinear communication systems with intersymbol interference in which bit error rate and IS estimation variances cannot be obtained readily using prior techniques     

On symbol error probability bounds for ISI-like channels

Some issues with Forney's upper and lower bounds (1972) for the symbol error probability in systems with memory (e.g., intersymbol interference channels) have been pointed out in the literature. We expound on these issues. For the upper bound, we show that, although the most commonly cited proofs are not logically consistent, the bound is true for more general conditions. The reasoning leading to the lower bound is shown to be flawed and, in general,to lead to invalid lower bounds. We suggest a lower bound based on Mazo's bound (1975) as an alternative