The Brascamp-Lieb inequality in functional analysis can be viewed as a measure of the “uncorrelatedness” of a joint probability distribution. We define the smooth Brascamp-Lieb (BL) divergence as the infimum of the best constant in the Brascamp-Lieb inequality under a perturbation of the joint probability distribution. An information spectrum upper bound on the smooth BL divergence is proved, using properties of the subgradient of a certain convex functional. In particular, in the i.i.d. setting, such an infimum converges to the best constant in a certain mutual information inequality. We then derive new single-shot converse bounds for the omniscient helper common randomness generation problem and the Gray-Wyner source coding problem in terms of the smooth BL divergence, where the proof relies on the functional formulation of the Brascamp-Lieb inequality. Exact second-order rates are thus obtained in the stationary memoryless and nonvanishing error setting. These offer rare instances of strong converses/second-order converses for continuous sources when the rate region involves auxiliary random variables.

A fundamental tool in network information theory is the covering lemma, which lower bounds the probability that there exists a pair of random variables; among a given number of independently generated candidates, falling within a given set. We use a weighted sum trick and Talagrand’s concentration inequality to prove new mutual covering bounds. We identify two interesting applications: 1) when the probability of the set under the given joint distribution is bounded away from 0 and 1, the covering probability converges to 1doublyexponentially fast in the blocklength, which implies that the covering lemma does not induce penalties on the error exponents in the applications to coding theorems; and 2) using Hall’s marriage lemma, we show that the maximum difference between the probability of the set under the joint distribution and the covering probability equals half the minimum total variation distance between the joint distribution and any distribution that can be simulated by selecting a pair from the candidates. Thus we use the mutual covering bound to derive the exact error exponent in the joint distribution simulation problem. In both applications, the determination of the exact exponential (or double exponential) behavior relies crucially on the sharp concentration inequality used in the proof of the mutual covering lemma.

We introduce a definition of perfect and quasi-perfect codes for discrete symmetric channels based on the packing and covering properties of generalized spheres whose shape is tilted using an auxiliary probability measure. This notion generalizes previous definitions of perfect and quasi-perfect codes and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to coincide with the estimate provided by the meta-converse lower bound. We illustrate how the proposed definition naturally extends to cover almost-lossless source-channel coding and lossy compression.

We study the problem of sequential prediction with coded side information under logarithmic loss (log-loss). We show an operational equivalence between this setup and lossy compression with log-loss distortion. Using this insight, together with recent work on lossy compression with log-loss, we connect prediction strategies with distributions in a certain subset of the probability simplex. This allows us to derive a Shtarkov-like bound for regret and to evaluate the regret for several illustrative classes of experts. In the present work, we mainly focus on the “batch” side information setting with sequential prediction.

In the rejection sampling problem, a sequence of samples distributed according to Q are observed sequentially by a sampler which stops and makes the selection at a certain point so that the selected sample is distributed according to P. Harsha-Jain-McAllester-Radhakrishnan showed that the expected length of a variable-length compression of the index of the selected sample is approximately D(P||Q). We prove Renyi generalizations of their result under some regularity conditions on the information spectrum. It turns out that causality matters except for Renyi divergence of order 1. For α ∈ (0,1), the minimum α -moment of the selected index is approximately exp (αD1/(1-α)(P||Q)) · In contrast, in the variant where the sequence is observed noncausally, the minimum α -moment ((α ≥ 0) is approximately exp(αD1+α(P||Q)). The proof is based on a simple optimization duality between sampling and covering.

This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan's bounds, they are expressed in terms of the Arimoto- Rényi conditional entropy. Although Arikan's bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are provided, characterizing the exact locus of their attainable values.

Bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are presented as well. Lower bounds on the cumulant generating function of the codeword lengths are given, by means of the smooth Rényi entropy, for source codes that allow decoding errors.

Universal lossy source coding under the logarithmic loss (log-loss) criterion is studied. Bounds on the rate-redundancy of variable-length universal codes with respect to a family of distributions are derived. These bounds correspond to previously derived bounds on distortion-redundancy of fixed-length coding. The asymptotic behavior of the resulting optimization problem is studied for a family of i.i.d. sources with a finite alphabet size. As is the case with distortion-redundancy, rate-redundancy of memoryless sources is lower bounded by [k/2] logn, wherenis the blocklength andkis the number of degrees of freedom in the parameter space. The impact of the distortion constraint is on the constant term: higher allowed distortion effectively reduces the volume of the parameter uncertainty set. In view of previously established connections between lossy variable-length coding under log-loss and compression with list decoding, the bounds derived in this work also apply to variable-length coding with list decoding.

We introduce a definition of perfect and quasi-perfect codes for symmetric channels parametrized by an auxiliary output distribution. This new definition generalizes previous definitions and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to attain the meta-converse lower bound.

Bounding the generalization error of learning algorithms has a long history, which yet falls short in explaining various generalization successes including those of deep learning. Two important difficulties are (i) exploiting the dependencies between the hypotheses, (ii) exploiting the dependence between the algorithm’s input and output. Progress on the first point was made with the chaining method, originating from the work of Kolmogorov, and used in the VC-dimension bound. More recently, progress on the second point was made with the mutual information method by Russo and Zou ’15. Yet, these two methods are currently disjoint. In this paper, we introduce a technique to combine chaining and mutual information methods, to obtain a generalization bound that is both algorithm-dependent and that exploits the dependencies between the hypotheses. We provide an example in which our bound significantly outperforms both the chaining and the mutual information bounds. As a corollary, we tighten Dudley’s inequality when the learning algorithm chooses its output from a small subset of hypotheses with high probability.

This paper gives upper and lower bounds on the minimum error probability of Bayesian M-ary hypothesis testing in terms of the Arimoto-Rényi conditional entropy of an arbitrary order α. The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy (α = 1) is demonstrated. In particular, in the case where M is finite, we show how to generalize Fano's inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano's inequality, allowing M to be infinite, a lower bound on the Arimoto-Rényi conditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto-Rényi conditional entropy for both positive and negative α. Furthermore, we give upper bounds on the minimum error probability as functions of the Rényi divergence. In the setup of discrete memoryless channels, we analyze the exponentially vanishing decay of the Arimoto-Rényi conditional entropy of the transmitted codeword given the channel output when averaged over a random-coding ensemble.

This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan's bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan's bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors.

This paper considers the problem of lossy source coding with a specific distortion measure: logarithmic loss. The focus of this paper is on the single-shot approach, which exposes crisply the connection between lossless source coding with list decoding and lossy source coding with log-loss. Fixed-length and variable-length bounds are presented. Fixed-length bounds include the single-shot fundamental limit for average as well as excess distortion. Variable-length bounds include the single-shot fundamental limit for average as well as excess length. Two multi-terminal problems are addressed: coding with side information (Wyner-Ziv) and multiple descriptions coding. In both the cases, the application of the Shannon-McMillan theorem to the single-shot bounds yields the rate-distortion function and the rate distortion-region for stationary ergodic sources.

The redundancy for universal lossless compression of discrete memoryless sources in Campbell's setting is characterized as a minimax Rényi divergence, which is shown to be equal to the maximal α -mutual information via a generalized redundancy-capacity theorem. Special attention is placed on the analysis of the asymptotics of minimax Rényi divergence, which is determined up to a term vanishing in blocklength.

This paper investigates the fundamental limits for compressing data on graphs, exploiting dependencies due to community structures in the graph. The source model, referred to as the data block model (DBM), is a mixture of discrete memoryless sources determined by the community structure of a stochastic block model (SBM). The main result gives the optimal expected length of a lossless compressor when the community signal is strong enough, a condition on the edge probabilities and the data distributions, which can take place below the exact recovery threshold of the SBM. This is derived in part by obtaining the threshold for exact recovery in SBMs with strong side information, a result of independent interest, which extends the CH-divergence threshold. Finally we discuss compressing data with almost exact recovery algorithms.

This paper presents a fixed-length-parsing universal compression algorithm for settings where compressor and decompressor share the same side information. We prove the optimality of the algorithm for any stationary processes. Furthermore, strategies to modify the algorithm are suggested in order to lower the data compression rate.

This paper proposes a general method for establishing non-asymptotic converses in information theory via reverse hypercontractivity of Markov semigroups. In contrast to the blowing-up approach for strong converses, the proposed approach is applicable to non-discrete settings, and yields the optimal order of the second-order term in the rate expansion (square root of the blocklength) in the regime of non-vanishing error probability.

This paper gives upper and lower bounds on the minimum error probability of Bayesian M-ary hypothesis testing in terms of the Arimoto-Rényi conditional entropy of an arbitrary order α. The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy (α = 1) is demonstrated. In particular, in the case where M is finite, we show how to generalize Fano's inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano's inequality, allowing M to be infinite, a lower bound on the Arimoto-Rényi conditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto-Rényi conditional entropy.

Universal lossy source coding with the logarithmic loss distortion criterion is studied. Bounds on the non-asymptotic fundamental limit of fixed-length universal coding with respect to a family of distributions are derived. These bounds generalize the well-known minimax bounds for universal lossless source coding. The asymptotic behavior of the resulting optimization problem is studied for a family of i.i.d. sources with a finite alphabet size, and is characterized up to a constant. The redundancy of memoryless sources behaves like k/2 log n, where n is the blocklength and k is the number of degrees of freedom in the parameter space. The impact of the coding rate is on the constant term: higher compression rate effectively reduces the volume of the parameter uncertainty set.

The redundancy for universal lossless compression in Campbell's setting is characterized as a minimax Rényi divergence, which is shown to be equal to the maximal α-mutual information via a generalized redundancy-capacity theorem. Special attention is placed on the analysis of the asymptotics of minimax Rényi divergence, which is determined up to a term vanishing in blocklength.

New one-shot bounds for multivariate covering are derived via a weighted sum technique and a one-sided concentration inequality which is stronger than the McDiarmid inequality. The new bounds are more compact and sharper than known bounds in the literature. In particular, the covering error can be shown to decay doubly exponentially in the blocklength. Implications for the error exponent in broadcast channels are discussed.

This paper quantifies the fundamental limits of variable-length transmission of a general (possibly analog) source over a memoryless channel with noiseless feedback, under a distortion constraint. We consider excess distortion, average distortion, and guaranteed distortion (d-semifaithful codes). In contrast to the asymptotic fundamental limit, a general conclusion is that allowing variable-length codes and feedback leads to a sizable improvement in the fundamental delaydistortion tradeoff. In addition, we investigate the minimum energy required to reproduce k source samples with a given fidelity after transmission over a memoryless Gaussian channel, and we show that the required minimum energy is reduced with feedback and an average (rather than maximal) power constraint.

The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper, we study Eγ-resolvability, in which total variation is replaced by the more general Eγdistance. A general one-shot achievability bound for the precision of such an approximation is developed. Let QX|Ube a random transformation, n be an integer, and E ∈ (0, +∞). We show that in the asymptotic setting where γ = exp(nE), a (nonnegative) randomness rate above inf QU:D(QXIIπX)≤E{D(QXIIπX) + I(QU, QX|U) - E} is sufficient to approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX, and is also necessary in the case of finite U and X . In particular, a randomness rate of inf QUI(QU, QX|U) - E is always sufficient. We also study the convergence of the approximation error under the high-probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating Eγand other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive: 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d. setting; 2) a one-shot version of the mutual covering lemma; and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.

A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depends on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the key bits per interaction bit (KBIB) is expressed with a new “symmetric strong data processing constant”, which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate.

The fundamental tradeoff of channel coding per unit cost in the fixed-error probability regime is investigated for discrete memoryless channels in the presence of a free input symbol. The speed of convergence to the capacity per unit cost in the absence of feedback is characterized in terms of a characteristic of the channel and cost function, which is referred to as ε-dispersion per unit cost. Further, a sufficient condition for feedback to improve this convergence speed is provided.

Estimation of the entropy rate of a stochastic process with unknown statistics, from a single sample path is a classical problem in information theory. While universal estimators for general families of processes exist, the estimates have not been accompanied by guarantees for fixed-length sample paths. We provide finite sample bounds on the convergence of a plug-in type estimator for the entropy rate of a Markov chain in terms of its alphabet size and its mixing properties. We also discuss Rényi entropy rate estimation for reversible Markov chains.

We study the infimum of the best constant in a functional inequality, the Brascamp-Lieb-like inequality, over auxiliary measures within a neighborhood of a product distribution. In the finite alphabet and the Gaussian cases, such an infimum converges to the best constant in a mutual information inequality. Implications for strong converse properties of two common randomness (CR) generation problems are discussed. In particular, we prove the strong converse property of the rate region for the omniscient helper CR generation problem in the discrete and the Gaussian cases. The latter case is a rare instance of a strong converse for a continuous source when the rate region involves auxiliary random variables.

We generalize a result by Carlen and Cordero-Erausquin on the equivalence between the Brascamp-Lieb inequality and the subadditivity of relative entropy by allowing for random transformations (a broadcast channel). This leads to a unified perspective on several functional inequalities that have been gaining popularity in the context of proving impossibility results. We demonstrate that the information theoretic dual of the Brascamp-Lieb inequality is a convenient setting for proving properties such as data processing, tensorization, convexity and Gaussian optimality. Consequences of the latter include an extension of the Brascamp-Lieb inequality allowing for Gaussian random transformations, the determination of the multivariate Wyner common information for Gaussian sources, and a multivariate version of Nelson's hypercontractivity theorem. Finally we present an information theoretic characterization of a reverse Brascamp-Lieb inequality involving a random transformation (a multiple access channel).

The basic two-terminal key generation model is considered, where the communication between the terminals is limited. We introduce a preorder relation on the set of joint distributions called XY-absolute continuity, and we reduce the multi-letter characterization of the key-communication tradeoff to the evaluation of the XY-concave envelope of a functional. For small communication rates, the key bits per interaction bit is expressed with a “symmetrical strong data processing constant”. Using hypercontractivity and Rényi divergence, we also prove a computationally friendly strong converse bound for the common randomness bits per interaction bit in terms of the supremum of the maximal correlation coefficient over a set of distributions, which is tight for binary symmetric sources. Regarding the other extreme case, a new characterization of the minimum interaction for achieving the maximum key rate (MIMK) is given, and is used to resolve a conjecture by Tyagi [1] about the MIMK for binary sources.

This paper studies the problem of lossy source coding with a specific distortion measure: logarithmic loss. The focus of this paper is on the single-shot approach which exposes the connection between lossy source coding with log-loss and lossless source coding. Point-to-point bounds, including the single-shot fundamental limit for average as well as excess distortion, are presented. Two multi-terminal problems are addressed: coding with side information (Wyner-Ziv), and multiple descriptions coding. In both cases, the application of the Shannon-McMillan Theorem to the single-shot bounds immediately yields the rate-distortion function and the rate distortion-region for stationary and ergodic sources.

This paper shows new general nonasymptotic achievability and converse bounds and performs their dispersion analysis for the lossy compression problem in which the compressor observes the source through a noisy channel. While this problem is asymptotically equivalent to a noiseless lossy source coding problem with a modified distortion function, nonasymptotically there is a noticeable gap in how fast their minimum achievable coding rates approach the common rate-distortion function, as evidenced both by the refined asymptotic analysis (dispersion) and the numerical results. The size of the gap between the dispersions of the noisy problem and the asymptotically equivalent noiseless problem depends on the stochastic variability of the channel through which the compressor observes the source.

We show that for product sources, rate splitting is optimal for secret key agreement using limited one-way communication between two terminals. This yields an alternative proof of the tensorization property of a strong data processing inequality originally studied by Erkip and Cover and amended recently by Anantharam et al. We derive a water-filling solution of the communication-rate-key-rate tradeoff for a wide class of discrete memoryless vector Gaussian sources which subsumes the case without an eavesdropper. Moreover, we derive an explicit formula for the maximum secret key per bit of communication for all discrete memoryless vector Gaussian sources using a tensorization property and a variation on the enhanced channel technique of Weingarten et al. Finally, a one-shot information spectrum achievability bound for key generation is proved from which we characterize the communication-rate-key-rate tradeoff for stationary Gaussian processes.

This paper develops systematic approaches to obtain f -divergence inequalities, dealing with pairs of probability measures defined on arbitrary alphabets. Functional domination is one such approach, where special emphasis is placed on finding the best possible constant upper bounding a ratio of f -divergences. Another approach used for the derivation of bounds among f -divergences relies on moment inequalities and the logarithmic-convexity property, which results in tight bounds on the relative entropy and Bhattacharyya distance in terms of χ2divergences. A rich variety of bounds are shown to hold under boundedness assumptions on the relative information. Special attention is devoted to the total variation distance and its relation to the relative information and relative entropy, including “reverse Pinsker inequalities,” as well as on the Eγdivergence, which generalizes the total variation distance. Pinsker's inequality is extended for this type of f -divergence, a result which leads to an inequality linking the relative entropy and relative information spectrum. Integral expressions of the Rényi divergence in terms of the relative information spectrum are derived, leading to bounds on the Rényi divergence in terms of either the variational distance or relative entropy.

Block coding over memoryless channels with causal and noiseless feedback is investigated in the moderate deviations regime. By means of a converse, we show that feedback does not improve the sub-exponential decay rate of the optimal error probability for a certain class of discrete memoryless channels, which includes symmetric ones, as well as the additive white Gaussian noise channel subject to an almost-sure power constraint.

Entropy is well known to be Schur concave on finite alphabets. Recently, the authors have strengthened the result by showing that for any pair of probability distributions P and Q with Q majorized by P, the entropy of Q is larger than the entropy of P by the amount of relative entropy D(P||Q). This result applies to P and Q defined on countable alphabets. This paper shows the counterpart of this result for the Rényi entropy and the Tsallis entropy. Lower bounds on the difference in the Rényi (or Tsallis) entropy are given in terms of a new divergence which is related to the Rényi (or Tsallis) divergence. This paper also considers a notion of generalized mutual information, namely α-mutual information, which is defined through the Rényi divergence. The convexity/concavity for different ranges of α is shown. A sufficient condition for the Schur concavity is discussed and upper bounds on α-mutual information are given in terms of the Rényi entropy.

This paper quantifies the fundamental limits of variable-length transmission of a general (possibly analog) source over a memoryless channel with noiseless feedback, under a distortion constraint. We consider excess distortion, average distortion and guaranteed distortion (d-semifaithful codes). In contrast to the asymptotic fundamental limit, a general conclusion is that allowing variable-length codes and feedback leads to a sizable improvement in the fundamental delay-distortion tradeoff.

A new model of multi-party secret key agreement is proposed, in which one terminal called the communicator can transmit public messages to other terminals before all terminals agree on a secret key. A single-letter characterization of the achievable region is derived in the stationary memoryless case. The new model generalizes some other (old and new) models of key agreement. In particular, key generation with an omniscient helper is the special case where the communicator knows all sources, for which we derive a zero-rate one-shot converse for the secret key per bit of communication.

We study the amount of randomness needed for an input process to approximate a given output distribution of a channel in the Eγ distance. A general one-shot achievability bound for the precision of such an approximation is developed. In the i.i.d. setting where γ = exp(nE), a (nonnegative) randomness rate above infQU:D(QX||πX)≤E{D(QX||πX) + I(QU, QX|U) - E} is necessary and sufficient to asymptotically approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX. The new resolvability result is then used to derive a oneshot upper bound on the error probability in the rate distortion problem; and a lower bound on the size of the eavesdropper list to include the actual message in the wiretap channel problem. Both bounds are asymptotically tight in i.i.d. settings.

By developing one-shot mutual covering lemmas, we derive a one-shot achievability bound for broadcast with a common message which recovers Marton's inner bound (with three auxiliary random variables) in the i.i.d. case. The encoder employed is deterministic. Relationship between the mutual covering lemma and a new type of channel resolvability problem is discussed.

We investigate the minimum transmitted energy required to reproduce k source samples with a given fidelity after transmission over a memoryless Gaussian channel. In particular, we analyze the reduction in transmitted energy that accrues thanks to the availability of noiseless feedback. Allowing a nonvanishing excess distortion probability ∈ boosts the asymptotic fundamental limit by a factor of 1-∈, with or without feedback. If feedback is available, achieving guaranteed distortion with finite average energy is possible.

In information theory, the packing and covering lemmas are conventionally used in conjunction with the typical sequence approach in order to prove the asymptotic achievability results for discrete memoryless systems. In contrast, the single-shot approach in information theory provides non-asymptotic achievability and converse results, which are useful to gauge the backoff from the asymptotic fundamental limits due to fixed blocklength, and which do not rely on discrete/memoryless assumptions. This paper reviews the non-asymptotic covering lemmas we have obtained recently and their application in single-user and multiuser information theory.

This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability ε, for lossless compression. We give nonasymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit, which is quite accurate for all but small blocklengths: (1 - ε)kH(S) - ((kV(S)/2π))1/2exp[-((Q-1(ε))2/2)], where Q-1(·) is the functional inverse of the standard Gaussian complementary cumulative distribution function, and V(S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1 - ε, but this asymptotic limit is approached from below, i.e, larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties.

This paper shows the strong converse and the dispersion of memoryless channels with cost constraints and performs a refined analysis of the third-order term in the asymptotic expansion of the maximum achievable channel coding rate, showing that it is equal to (1/2)((log n)/n) in most cases of interest. The analysis is based on a nonasymptotic converse bound expressed in terms of the distribution of a random variable termed the b-tilted information density, which plays a role similar to that of the d-tilted information in lossy source coding. We also analyze the fundamental limits of lossy joint-source-channel coding over channels with cost constraints.

The degrees of freedom (DoFs) of the K -user Gaussian interference channel determine the asymptotic growth of the maximal sum rate as a function of the signal-to-noise ratio. Subject to a very general sufficient condition on the cross-channel gains, we give a formula for the DoFs of the scalar interference channel as a function of the deterministic channel matrix, which involves maximization of a sum of information dimensions over K scalar input distributions. Known special cases are recovered, and even generalized in certain cases with unified proofs.

This paper analyzes the distribution of the codeword lengths of the optimal lossless compression code without prefix constraints both in the non-asymptotic regime and in the asymptotic regime. The technique we use is based on upper and lower bounding the cumulant generating function of the optimum codeword lengths. In the context of prefix codes, the normalized version of this quantity was proposed by Campbell in 1965 as a generalized average length. We then use the one-shot bounds to analyze the large deviations (reliability function) and small deviations (normal approximation) of the asymptotic fundamental limit in the case of memoryless sources. In contrast to other approaches based on the method of types or the Berry-Esséen inequality, we are able to deal with sources with infinite alphabets.

This paper gives non-asymptotic converse bounds on the cumulant generating function of the encoded lengths in variable-rate lossy compression and in variable-to-fixed channel coding. The results are given in terms of the Rényi mutual information and the d-tilted Rényi entropy. We also illustrate the application of the non-asymptotic bounds to obtain strong converses.

This paper studies the fundamental limits of the minimum average length of variable-length compression when a nonzero error probability ε is tolerated. We give non-asymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit which is quite accurate for all but small blocklengths: equation where Q-1(·) is the functional inverse of the Q-function and V (S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1-ε, but also this asymptotic limit is approached from below, i.e. a larger source dispersion and shorter blocklengths are beneficial. Further, we show that variable-length lossy compression under excess distortion constraint also exhibits similar properties.

We show that for product sources, rate splitting is optimal for secret key agreement using limited one-way communication at two terminals. This yields an alternative proof of the tensorization property of a strong data processing inequality originally studied by Erkip and Cover and amended recently by Anantharam et al. We derive a `water-filling' solution of the communication rate-key rate tradeoff for two arbitrarily correlated vector Gaussian sources, for the case with an eavesdropper, and for stationary Gaussian processes.

This paper provides an extensive study of the behavior of the best achievable rate (and other related fundamental limits) in variable-length strictly lossless compression. In the non-asymptotic regime, the fundamental limits of fixed-to-variable lossless compression with and without prefix constraints are shown to be tightly coupled. Several precise, quantitative bounds are derived, connecting the distribution of the optimal code lengths to the source information spectrum, and an exact analysis of the best achievable rate for arbitrary sources is given. Fine asymptotic results are proved for arbitrary (not necessarily prefix) compressors on general mixing sources. Nonasymptotic, explicit Gaussian approximation bounds are established for the best achievable rate on Markov sources. The source dispersion and the source varentropy rate are defined and characterized. Together with the entropy rate, the varentropy rate serves to tightly approximate the fundamental nonasymptotic limits of fixed-to-variable compression for all but very small block lengths.

This paper studies several properties of channel codes that approach the fundamental limits of a given (discrete or Gaussian) memoryless channel with a nonvanishing probability of error. The output distribution induced by an ϵ-capacity-achieving code is shown to be close in a strong sense to the capacity achieving output distribution. Relying on the concentration of measure (isoperimetry) property enjoyed by the latter, it is shown that regular (Lipschitz) functions of channel outputs can be precisely estimated and turn out to be essentially nonrandom and independent of the actual code. It is also shown that the output distribution of a good code and the capacity achieving one cannot be distinguished with exponential reliability. The random process produced at the output of the channel is shown to satisfy the asymptotic equipartition property.

This work1deals with the fundamental limits of strictly-lossless variable-length compression of known sources without prefix constraints. The source dispersion characterizes the time-horizon over which it is necessary to code in order to approach the entropy rate within a pre-specified tolerance. We show that for a large class of sources, the dispersion of the source is equal to the varentropy rate, defined as the asymptotic per-symbol variance of the information random variables. We focus on ergodic Markov chains, whose optimal encodings are shown to be asymptotically normal and to satisfy an appropriate laws of the iterated logarithm.

This paper shows the strong converse and the dispersion of memoryless channels with cost constraints. The analysis is based on a new non-asymptotic converse bound expressed in terms of the distribution of a random variable termed the b-tilted information density, which plays a role similar to that of the information density in channel coding without cost constraints. We also analyze the fundamental limits of lossy joint-source-channel coding over channels with cost constraints.

This paper shows new general nonasymptotic achievability and converse bounds and performs their dispersion analysis for the lossy compression problem in which the compressor observes the source through a noisy channel. While this problem is asymptotically equivalent to a noiseless lossy source coding problem with a modified distortion function, nonasymptotically there is a difference in how fast their minimum achievable coding rates approach the rate-distortion function, providing yet another example where at finite blocklengths one must put aside traditional asymptotic thinking.

This paper finds new tight finite-blocklength bounds for the best achievable lossy joint source-channel code rate, and demonstrates that joint source-channel code design brings considerable performance advantage over a separate one in the nonasymptotic regime. A joint source-channel code maps a block ofksource symbols onto a length-nchannel codeword, and the fidelity of reproduction at the receiver end is measured by the probability ε that the distortion exceeds a given thresholdd. For memoryless sources and channels, it is demonstrated that the parameters of the best joint source-channel code must satisfynC-kR(d) ≈ √(nV+k V(d))Q-1(ε), whereCandVare the channel capacity and channel dispersion, respectively;R(d) andV(d) are the source rate-distortion and rate-dispersion functions; andQis the standard Gaussian complementary cumulative distribution function. Symbol-by-symbol (uncoded) transmission is known to achieve the Shannon limit when the source and channel satisfy a certain probabilistic matching condition. In this paper, we show that even when this condition is not satisfied, symbol-by-symbol transmission is, in some cases, the best known strategy in the nonasymptotic regime.

Consider a Bernoulli-Gaussian complexn-vector whose components areVi=XiBi, withXi~C N(0,Px) and binaryBimutually independent and iid acrossi. This randomq-sparse vector is multiplied by a square random matrixU, and a randomly chosen subset, of average sizen p,p∈ [0,1], of the resulting vector components is then observed in additive Gaussian noise. We extend the scope of conventional noisy compressive sampling models whereUis typically a matrix with iid components, to allowUsatisfying a certain freeness condition. This class of matrices encompasses Haar matrices and other unitarily invariant matrices. We use the replica method and the decoupling principle of Guo and Verdú, as well as a number of information-theoretic bounds, to study the input-output mutual information and the support recovery error rate in the limit ofn→ ∞. We also extend the scope of the large deviation approach of Rangan and characterize the performance of a class of estimators encompassing thresholded linear MMSE andl1relaxation.

This paper shows new tight finite-blocklength bounds for the best achievable lossy joint source-channel code rate, and demonstrates that joint source-channel code design brings considerable performance advantage over a separate one in the non-asymptotic regime. A joint source-channel code maps a block of k source symbols onto a length - n channel codeword, and the fidelity of reproduction at the receiver end is measured by the probability ϵ that the distortion exceeds a given threshold d. For memoryless sources and channels, it is demonstrated that the parameters of the best joint source-channel code must satisfy nC - kR(d) ≈ √(nV + kV(d)) Q-1(ϵ), where C and V are the channel capacity and dispersion, respectively; R(d) and V(d) are the source rate-distortion and rate-dispersion functions; and Q is the standard Gaussian complementary cdf.

Compressed sensing deals with efficient recovery of analog signals from linear encodings. This paper presents a statistical study of compressed sensing by modeling the input signal as an i.i.d. random process. Three classes of encoders are considered, namely, optimal nonlinear, optimal linear and random linear encoders. Focusing on optimal decoders, we investigate the fundamental tradeoff between measurement rate and reconstruction fidelity gauged by the noise sensitivity. The optimal phase-transition threshold is determined as a functional of the input distribution and compared to suboptimal thresholds achieved by popular reconstruction algorithms. In particular, we show that Gaussian sensing matrices incur no penalty on the phase-transition threshold with respect to optimal nonlinear encoding. Our results also provide a rigorous justification of previous results based on replica heuristics in the weak-noise regime.

We revisit the dilemma of whether one should or should not code when operating under delay constraints. In those curious cases when the source and the channel are probabilistically matched so that symbol-by-symbol coding is optimal in terms of the average distortion achieved, we show that it also achieves the dispersion of joint source-channel coding. Moreover, even in the absence of such probabilistic matching between the source and the channel, symbol-by-symbol transmission, though asymptotically suboptimal, might outperform not only separate source-channel coding but also the best known random-coding joint source-channel coding achievability bound in the finite blocklength regime.

The information-theoretic notion of energy efficiency is studied in the context of various joint source-channel coding problems. The minimum transmission energyE(D) required to communicate a source over a noisy channel so that it can be reconstructed within a target distortionDis analyzed. Unlike the traditional joint source-channel coding formalisms, no restrictions are imposed on the number of channel uses per source sample. For single-source memoryless point-to-point channels,E(D) is shown to be equal to the product of the minimum energy per bitEbminof the channel and the rate-distortion functionR(D) of the source, regardless of whether channel output feedback is available at the transmitter. The primary focus is on Gaussian sources and channels affected by additive white Gaussian noise under quadratic distortion criteria, with or without perfect channel output feedback. In particular, for two correlated Gaussian sources communicated over a Gaussian multiple-access channel, inner and outer bounds on the energy-distortion region are obtained, which coincide in special cases. For symmetric channels, the difference between the upper and lower bounds on energy is shown to be at most a constant even when the lower bound goes to infinity asD→ 0. It is also shown that simple uncoded transmission schemes perform better than the separation-based schemes in many different regimes, both with and without feedback.

This paper studies the minimum achievable source coding rate as a function of blocklengthnand probability ϵ that the distortion exceeds a given leveld. Tight general achievability and converse bounds are derived that hold at arbitrary fixed blocklength. For stationary memoryless sources with separable distortion, the minimum rate achievable is shown to be closely approximated byR(d) + √V(d)/(n)Q-1(ϵ), whereR(d) is the rate-distortion function,V(d) is the rate dispersion, a characteristic of the source which measures its stochastic variability, andQ-1(·) is the inverse of the standard Gaussian complementary cumulative distribution function.

In addition to exploring its various regularity properties, we show that the minimum mean-square error (MMSE) is a concave functional of the input-output joint distribution. In the case of additive Gaussian noise, the MMSE is shown to be weakly continuous in the input distribution and Lipschitz continuous with respect to the quadratic Wasserstein distance for peak-limited inputs. Regularity properties of mutual information are also obtained. Several applications to information theory and the central limit theorem are discussed.

Compressed sensing deals with efficient recovery of analog signals from linear encodings. This paper presents a statistical study of compressed sensing by modeling the input signal as an i.i.d. process with known distribution. Three classes of encoders are considered, namely optimal nonlinear, optimal linear, and random linear encoders. Focusing on optimal decoders, we investigate the fundamental tradeoff between measurement rate and reconstruction fidelity gauged by error probability and noise sensitivity in the absence and presence of measurement noise, respectively. The optimal phase-transition threshold is determined as a functional of the input distribution and compared to suboptimal thresholds achieved by popular reconstruction algorithms. In particular, we show that Gaussian sensing matrices incur no penalty on the phase-transition threshold with respect to optimal nonlinear encoding. Our results also provide a rigorous justification of previous results based on replica heuristics in the weak-noise regime.

This paper studies the minimum achievable source coding rate as a function of blocklength n and tolerable distortion level d. Tight general achievability and converse bounds are derived that hold at arbitrary fixed blocklength. For stationary memoryless sources with separable distortion, the minimum rate achievable is shown to be q closely approximated by R(d) + √v(d)/nQ-1(ϵ), where R(d) is the rate-distortion function, V (d) is the rate dispersion, a characteristic of the source which measures its stochastic variability, Q-1(·) is the inverse of the standard Gaussian complementary cdf, and ϵ is the probability that the distortion exceeds d. The new bounds and the second-order approximation of the minimum achievable rate are evaluated for the discrete memoryless source with symbol error rate distortion. In this case, the second-order approximation reduces to R(d) + 1/2 log n/n if the source is non-redundant.

The backoff from capacity due to finite blocklength can be assessed accurately from the channel dispersion. This paper analyzes the dispersion of a single-user, scalar, coherent fading channel with additive Gaussian noise. We obtain a convenient two-term expression for the channel dispersion which shows that, unlike the capacity, it depends crucially on the dynamics of the fading process.

Consider a Bernoulli-Gaussian complex n-vector whose components are XiBi, with Bi~Bernoulli-q and Xi~ CN(0; σ2), iid across i and mutually independent. This random q-sparse vector is multiplied by a random matrix U, and a randomly chosen subset of the components of average size np, p ∈ [0; 1], of the resulting vector is then observed in additive Gaussian noise. We extend the scope of conventional noisy compressive sampling models where U is typically the identity or a matrix with iid components, to allow U that satisfies a certain freeness condition, which encompasses Haar matrices and other unitarily invariant matrices. We use the replica method and the decoupling principle of Guo and Verdú, as well as a number of information theoretic bounds, to study the input-output mutual information and the support recovery error rate as n → ∞.

We give a general formula for the degrees of freedom of the K-user real additive-noise interference channel involving maximization of information dimension. Previous results are recovered, and even generalized in certain cases with simplified proofs. Connections to fractal geometry are drawn.

For an i.i.d. Gaussian source with variance σ2, we show that it is necessary to spend ½ ln σ2/d + 1/√(2n) Q-1(ε) + O (ln n/n) nats per sample in order to reproduce n source samples within mean-square error d with probability at least 1 - ε, where Q-1(·) is the inverse of the standard Gaussian complementary cdf. The first-order term is the rate-distortion function of the Gaussian source, while the second-order term measures its stochastic variability. We derive new achievability and converse bounds that are valid at any blocklength and show that the second-order approximation is tightly wedged between them, thus providing a concise and accurate approximation of the minimum achievable source coding rate at a given fixed blocklength (unless the blocklength is very small).

Consider the minimum mean-square error (MMSE) of estimating an arbitrary random variable from its observation contaminated by Gaussian noise. The MMSE can be regarded as a function of the signal-to-noise ratio (SNR) as well as a functional of the input distribution (of the random variable to be estimated). It is shown that the MMSE is concave in the input distribution at any given SNR. For a given input distribution, the MMSE is found to be infinitely differentiable at all positive SNR, and in fact a real analytic function in SNR under mild conditions. The key to these regularity results is that the posterior distribution conditioned on the observation through Gaussian channels always decays at least as quickly as some Gaussian density. Furthermore, simple expressions for the first three derivatives of the MMSE with respect to the SNR are obtained. It is also shown that, as functions of the SNR, the curves for the MMSE of a Gaussian input and that of a non-Gaussian input cross at most once over all SNRs. These properties lead to simple proofs of the facts that Gaussian inputs achieve both the secrecy capacity of scalar Gaussian wiretap channels and the capacity of scalar Gaussian broadcast channels, as well as a simple proof of the entropy power inequality in the special case where one of the variables is Gaussian.

We explore the duality between lossy compression and channel coding in the operational sense: whether a capacity-achieving encoder-decoder sequence achieves the rate-distortion function of the dual problem when the channel decoder [encoder] is the source compressor [decompressor, resp.], and vice versa. We show that, if used as a lossy compressor, the maximum-likelihood channel decoder of a randomly chosen capacity-achieving codebook achieves the rate-distortion function almost surely. However, operational duality does not hold for every capacity achieving encoder-decoder sequence, or rate-distortion achieving compressor-decompressor sequence. We show that there exist optimal channel coding [lossy compression] schemes, which fail when used for the dual lossy compression [channel coding resp.] problem.

In this paper, we consider scaling laws for maximal energy efficiency of communicating a message to all the nodes in a wireless network, as the number of nodes in the network becomes large. Two cases of large wireless networks are studied-dense random networks and constant density (extended) random networks. In addition, we also study finite size regular networks in order to understand how regularity in node placement affects energy consumption. We first establish an information-theoretic lower bound on the minimum energy per bit for multicasting in arbitrary wireless networks when the channel state information is not available at the transmitters. Upper bounds are obtained by constructing a simple flooding scheme that requires no information at the receivers about the channel states or the locations and identities of the nodes. The gap between the upper and lower bounds is only a constant factor for dense random networks and regular networks, and differs by a poly-logarithmic factor for extended random networks. Furthermore, we show that the proposed upper and lower bounds for random networks hold almost surely in the node locations as the number of nodes approaches infinity.

In this paper, we study the minimum energy per bit required for communicating a message to all the destination nodes in a wireless network. The physical layer is modeled as an additive white Gaussian noise (AWGN) channel affected by circularly symmetric fading. The fading coefficients are known at neither transmitters nor receivers. We provide an information-theoretic lower bound on the energy requirement of general multicasting in arbitrary networks as the solution of a linear program, when no restrictions are placed on the bandwidth or the delay. We study the performance of decode-and-forward operating in the noncoherent wideband scenario, and compare it with the lower bound, for a variety of network classes where all nonsource nodes are destinations. For three-terminal networks with one source and two cooperative destination nodes, the energy expenditure of decode-and-forward is shown to be at most twice the lower bound and optimal in many cases. We also show that for arbitrary networks withknodes, the energy requirement of decode-and-forward is at mostk-1 times that of the lower bound regardless of the magnitude of channel gains. In networks that can be represented as directed acyclic graphs (DAGs), we establish the minimum energy per bit, also achieved by decode-and-forward. In addition, we also study regular networks where the energy consumption of decode-and-forward is shown to be almost order optimal in many situations of interest.

Channel dispersion plays a fundamental role in assessing the backoff from capacity due to finite blocklength. This paper analyzes the channel dispersion for a simple channel with memory: the Gilbert-Elliott communication model in which the crossover probability of a binary symmetric channel evolves as a binary symmetric Markov chain, with and without side information at the receiver about the channel state. With side information, dispersion is equal to the average of the dispersions of the individual binary symmetric channels plus a term that depends on the Markov chain dynamics, which do not affect the channel capacity. Without side information, dispersion is equal to the spectral density at zero of a certain stationary process, whose mean is the capacity. In addition, the finite blocklength behavior is analyzed in the non-ergodic case, in which the chain remains in the initial state forever.

The minimum achievable energy per bit over memoryless Gaussian channels has been previously addressed in the limit when the number of information bits goes to infinity, in which case it is known that the availability of noiseless feedback does not lower the minimum energy per bit, which is -1.59 dB below the noise level. This paper analyzes the behavior of the minimum energy per bit for memoryless Gaussian channels as a function ofk, the number of information bits. It is demonstrated that in this nonasymptotic regime, noiseless feedback leads to significantly better energy efficiency. In particular, without feedback achieving energy per bit of -1.57 dB requires coding over at leastk=106information bits, while we construct a feedback scheme that transmits a single information bit with energy -1.59 dB and zero error. We also show that unlesskis very small, approaching the minimal energy per bit does not require using the feedback link except to signal that transmission should stop.

Without feedback, the backoff from capacity due to non-asymptotic blocklength can be quite substantial for blocklengths and error probabilities of interest in many practical applications. In this paper, novel achievability bounds are used to demonstrate that in the non-asymptotic regime, the maximal achievable rate improves dramatically thanks to variable-length coding and feedback. For example, for the binary symmetric channel with capacity 1/2 the blocklength required to achieve 90% of the capacity is smaller than 200, compared to at least 3100 for the best fixed-blocklength code (even with noiseless feedback). Virtually all the advantages of noiseless feedback are shown to be achievable, even if the feedback link is used only to send a single signal informing the encoder to terminate the transmission (stop-feedback). It is demonstrated that the non-asymptotic behavior of the fundamental limit depends crucially on the particular model chosen for the “end-of-packet” control signal. Fixed-blocklength codes and related questions concerning communicating with a guaranteed delay are discussed, in which situation feedback is demonstrated to be almost useless even non-asymptotically.

The minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as nH + O(1), where the term O(1) lies between 0 and 1. However, this well-known performance is obtained under the implicit constraint that the code assigned to the whole n-block is a prefix code. Dropping the prefix constraint, which is rarely necessary at the block level, we show that the minimum expected length for a finite-alphabet memoryless source with known distribution grows as nH-1/2 log n + O(1) unless the source is equiprobable. We also refine this result up to o(1) for those memoryless sources whose log probabilities do not reside on a lattice.

Assuming additive Gaussian noise, a general sufficient condition on the input distribution is established to guarantee that the ratio of mutual information to signal-to-noise ratio (SNR) goes to one half nat as SNR vanishes. The result allows SNR-dependent input distribution and side information.

If N is standard Gaussian, the minimum mean square error (MMSE) of estimating a random variable X based on √(snr)X+Nvanishes at least as fast as 1/snrassnr→ ∞. We define the MMSE dimension of X as the limit assnr→ ∞ of the product of snr and the MMSE. MMSE dimension is also shown to be the asymptotic ratio of nonlinear MMSE to linear MMSE. For discrete, absolutely continuous or mixed distribution we show that MMSE dimension equals Rényi's information dimension. However, for a class of self-similar singular X (e.g., Cantor dis tribution), we show that the product of snr and MMSE oscillates around information dimension periodically in snr (dB). We also show that these results extend considerably beyond Gaussian noise under various technical conditions.

The energy-distortion function (E(D)) for a network is defined as the minimum total energy required to achieve a target distortion D at the receiver without putting any restrictions on the number of channel uses per source sample. E(D) is studied for a sensor network in which multiple sensors transmit their noisy observations of a Gaussian source to the destination over a Gaussian multiple access channel with perfect channel output feedback. While the optimality of separate source and channel coding is proved for the case of a single sensor, this optimality is shown to fail when there are multiple sensors in the network. A network with two sensors is studied in detail. First a lower bound on E(D) is given. Then, two achievability schemes are proposed: a separation based digital scheme and a Schalkwijk-Kailath (SK) type uncoded scheme. The gap between the lower bound and the upper bound based on separation is shown to be a constant even as the total energy requirement goes to infinity in the low distortion regime. On the other hand, as the distortion requirement is relaxed, the SK based scheme is shown to outperform separation in certain cases, proving that the optimality of source-channel separation does not hold in the multi-sensor setting.

We study the minimum energy per bit required for communicating a message to all the destination nodes in a wireless network. The physical layer is modeled as an additive white Gaussian noise channel affected by circularly symmetric fading. The fading coefficients are known at neither transmitters nor receivers. We provide an information-theoretic lower bound on the energy requirement of multicasting in arbitrary wireless networks as the solution of a linear program. We study the broadcast performance of decode-and-forward operating in the non-coherent wideband scenario, and compare it with the lower bounds. For arbitrary networks with k nodes, the energy requirement of decode-and-forward is within a factor of (k-1) of the lower bound regardless of the magnitude of channel gains. We also show that decode-and-forward achieves the minimum energy per bit in networks that can be represented as directed acyclic graphs, thus establishing the exact minimum energy per bit for this class of networks. We also study regular networks where the area is divided into cells, each cell containing at least k and at most k¿ nodes placed arbitrarily within the cell. A path loss model (with path loss exponent ¿ > 2) dictates the channel gains between the nodes. It is shown that the ratio between the upper bound using decode-and-forward based flooding, and the lower bound is at most a constant times (k¿¿+2/k).

We explore the duality between the Gelfand-Pinsker problem of channel coding with side information at the transmitter and the Wyner-Ziv problem of lossy compression with side information at the decompressor in the operational sense: whether a capacity-achieving encoder-decoder sequence achieves the rate distortion function of the dual problem when the channel decoder (resp. encoder) is the source compressor (resp. decompressor). We show that there exist capacity-achieving channel coding schemes that also achieve the rate-distortion function for the dual problem. However, this duality does not hold for every capacity-achieving channel coding scheme. In particular, we show that the original capacity-achieving encoder-decoder scheme of Gelfand-Pinsker operates far from the Wyner-Ziv rate-distortion function.

The question of minimum achievable energy per bit over memoryless channels has been previously addressed in the limit of number of information bits going to infinity, in which case it is known that availability of noiseless feedback does not lower the minimum energy per bit. This paper analyzes the behavior of the minimum energy per bit for memoryless Gaussian channels as a function of the number of information bits. It is demonstrated that in this non-asymptotic regime, noiseless feedback leads to significantly better energy efficiency. A feedback coding scheme with zero probability of block error and finite energy per bit is constructed. For both achievability and converse, the feedback coding problem is reduced to a sequential hypothesis testing problem for Brownian motion.

Without feedback, the backoff from capacity due to non-asymptotic block length can be quite substantial for block lengths and error probabilities of interest in many practical applications. In this paper, novel achievability bounds are used to demonstrate that in the non-asymptotic regime, the maximal achievable rate improves dramatically thanks to variable-length coding with feedback. For example, for the binary symmetric channel with capacity 1/2 the blocklength required to achieve 90% of the capacity is smaller than 200, compared to at least 3100 for the best fixed-blocklength, non-feedback code. Virtually all the advantages of noiseless feedback are shown to be achievable with decision-feedback only. It is demonstrated that the non-asymptotic behavior of the fundamental limit depends crucially on the particular model chosen for the “end-of-packet” control signal.

We show that the minimum mean-square error (MMSE) of estimating the input based on the channel output is a concave functional of the input-output joint distribution, and its various regularity properties are explored. In particular, the MMSE in Gaussian channels is shown to be weakly continuous in the input distribution and Lipschitz continuous with respect to the quadratic Wasserstein distance for peak-limited inputs. Regularity properties of mutual information are also obtained and some connections with rate-distortion theory are also drawn.

If N is standard Gaussian, the minimum mean-square error (MMSE) of estimating X based on √(snr)X + N vanishes at least as fast as 1/snr as snr → ∞. We define the MMSE dimension of X as the limit as snr → ∞ of the product of snr and the MMSE. For discrete, absolutely continuous or mixed X we show that the MMSE dimension equals Rényi's information dimension. However, for singular X, we show that the product of snr and MMSE oscillates around information dimension periodically in snr (dB). We also show that discrete side information does not reduce MMSE dimension. These results extend considerably beyond Gaussian N under various technical conditions.

Fano's inequality relates the error probability of guessing a finitely-valued random variableXgiven another random variableYand the conditional entropy ofXgivenY. It is not necessarily tight when the marginal distribution ofXis fixed. This paper gives a tight upper bound on the conditional entropy ofXgivenYin terms of the error probability and the marginal distribution ofX. A new lower bound on the conditional entropy for countably infinite alphabets is also found. The relationship between the reliability criteria of vanishing error probability and vanishing conditional entropy is also discussed. A strengthened form of the Schur-concavity of entropy which holds for finite or countably infinite random variables is given.

We consider the Wyner-Ziv (WZ) problem of lossy compression where the decompressor observes a noisy version of the source, whose statistics are unknown. A new family of WZ coding algorithms is proposed and their universal optimality is proven. Compression consists of sliding-window processing followed by Lempel-Ziv (LZ) compression, while the decompressor is based on a modification of the discrete universal denoiser (DUDE) algorithm to take advantage of side information. The new algorithms not only universally attain the fundamental limits, but also suggest a paradigm for practical WZ coding. The effectiveness of our approach is illustrated with experiments on binary images, and English text using a low complexity algorithm motivated by our class of universally optimal WZ codes.

In this paper, we investigate the linear precoding and power allocation policies that maximize the mutual information for general multiple-input-multiple-output (MIMO) Gaussian channels with arbitrary input distributions, by capitalizing on the relationship between mutual information and minimum mean-square error (MMSE). The optimal linear precoder satisfies a fixed-point equation as a function of the channel and the input constellation. For non-Gaussian inputs, a nondiagonal precoding matrix in general increases the information transmission rate, even for parallel noninteracting channels. Whenever precoding is precluded, the optimal power allocation policy also satisfies a fixed-point equation; we put forth a generalization of the mercury/waterfilling algorithm, previously proposed for parallel noninterfering channels, in which the mercury level accounts not only for the non-Gaussian input distributions, but also for the interference among inputs.

This paper investigates the maximal channel coding rate achievable at a given blocklength and error probability. For general classes of channels new achievability and converse bounds are given, which are tighter than existing bounds for wide ranges of parameters of interest, and lead to tight approximations of the maximal achievable rate for blocklengthsnas short as 100. It is also shown analytically that the maximal rate achievable with error probability¿isclosely approximated by C - ¿(V/n) Q-1(¿) where C is the capacity, V is a characteristic of the channel referred to as channel dispersion , and Q is the complementary Gaussian cumulative distribution function.

This paper finds the capacity of single-user discrete-time channels subject to both frequency-selective and time-selective fading, where the channel output is observed in additive Gaussian noise. A coherent model is assumed where the fading coefficients are known at the receiver. Capacity depends on the first-order distributions of the fading processes in frequency and in time, which are assumed to be independent of each other, and a simple formula is given when one of the processes is independent identically distributed (i.i.d.) and the other one is sufficiently mixing. When the frequency-selective fading coefficients are known also to the transmitter, we show that the optimum normalized power spectral density is the waterfilling power allocation for a reduced signal-to-noise ratio (SNR), where the gap to the actual SNR depends on the fading distributions. Asymptotic expressions for high/low SNR and easily computable bounds on capacity are also provided.

A random variable with distribution P is observed in Gaussian noise and is estimated by a mismatched minimum mean-square estimator that assumes that the distribution is Q, instead of P . This paper shows that the integral over all signal-to-noise ratios (SNRs) of the excess mean-square estimation error incurred by the mismatched estimator is twice the relative entropy D(P ||Q) (in nats). This representation of relative entropy can be generalized to nonreal-valued random variables, and can be particularized to give new general representations of mutual information in terms of conditional means. Inspired by the new representation, we also propose a definition of free relative entropy which fills a gap in, and is consistent with, the literature on free probability.

This paper introduces the notions of variable-to-fixed and fixed-to-variable channel capacity, without feedback. For channels that satisfy the strong converse, these notions coincide with the conventional Shannon capacity. For channels that do not behave ergodically, the conventional fixed-rate Shannon capacity only depends on least-favorable channel conditions, while the variable-rate capacity notions are able to capture the whole range of channel states and their likelihood, even in the absence of any side information about channel state at the transmitter. Particular emphasis is placed on memoryless channels that are governed by finitely valued states. We show that (single-user) variable-to-fixed channel capacity is intimately connected to the capacity region of broadcast channels with degraded message sets, and we give an expression for the fixed-to-variable capacity.

In Shannon theory, lossless source coding deals with the optimal compression of discrete sources. Compressed sensing is a lossless coding strategy for analog sources by means of multiplication by real-valued matrices. In this paper we study almost lossless analog compression for analog memoryless sources in an information-theoretic framework, in which the compressor or decompressor is constrained by various regularity conditions, in particular linearity of the compressor and Lipschitz continuity of the decompressor. The fundamental limit is shown to the information dimension proposed by Rényi in 1959.

We consider scaling laws for maximal energy efficiency of communicating a message to all the nodes in a random wireless network, as the number of nodes in the network becomes large. Two cases of large wireless networks are studied — dense random networks and constant density (extended) random networks. We first establish an information-theoretic lower bound on the minimum energy per bit for multicasting that holds for arbitrary wireless networks when the channel state information is not available at the transmitters. These lower bounds are then evaluated for two cases of random networks. Upper bounds are also obtained by constructing a simple flooding scheme that requires no information at the receivers about the channel states or the locations and identities of the nodes. The gap between the upper and lower bounds is only a constant factor for dense random networks and differs by a poly-logarithmic factor for extended random networks. Furthermore, the proposed upper and lower bounds hold almost surely in the node locations as the number of nodes approaches infinity.

The minimum block-length required to achieve a given rate and error probability can be easily and tightly approximated from two key channel parameters: the capacity and the channel dispersion. The channel dispersion gauges the variability of the channel relative to a deterministic bit pipe with the same capacity. This paper finds the dispersion of the additive white Gaussian noise (AWGN) channel, the parallel AWGN channel, and the Gaussian channel with non-white noise and intersymbol interference.

Channel dispersion plays a fundamental role in assessing the backoff from capacity due to finite blocklength. This paper analyzes the channel dispersion for a simple channel with memory: the Gilbert-Elliott communication model in which the crossover probability of a binary symmetric channel evolves as a binary symmetric Markov chain, with and without side information at the receiver about the channel state. With side information, although capacity is invariant to the chain dynamics, dispersion is shown to be the sum of two terms: due to the Markov chain dynamics and due to the the randomness in the error generation, respectively.

Conventional wisdom states that the minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as nH+O(1). However, this performance is obtained under the constraint that the code assigned to the whole n-block is a prefix code. Dropping this unnecessary constraint we show that the minimum expected length grows as nH - 1/2 log n + O(1) unless the source is equiprobable.

A random variable with distribution P is observed in Gaussian noise and is estimated by a minimum mean-square estimator that assumes that the distribution is Q. This paper shows that the integral over all signal-to-noise ratios of the excess mean-square estimation error incurred by the mismatched estimator is twice the relative entropy D(P‖Q). This representation of relative entropy can be generalized to non real-valued random variables, and can be particularized to give a new general representation of mutual information in terms of conditional means. Inspired by the new representation, we also propose a definition of free relative entropy which fills a gap in, and is consistent with, the literature on free probability.

In Shannon theory, lossless source coding deals with the optimal compression of discrete sources. Compressed sensing is a lossless coding strategy for analog sources by means of multiplication by real-valued matrices. In this paper we study almost lossless analog compression for analog memoryless sources in an information-theoretic framework, in which the compressor is not constrained to linear transformations but it satisfies various regularity conditions such as Lipschitz continuity. The fundamental limit is shown to be the information dimension proposed by Renyi in 1959.

We propose a scheme for lossy compression of discrete memoryless sources: The compressor is the decoder of a nonlinear channel code, constructed from a sparse graph. We prove asymptotic optimality of the scheme for any separable (letter-by-letter) bounded distortion criterion. We also present a suboptimal compression algorithm, which exhibits near-optimal performance for moderate block lengths.

Like the conventional two-user interference channel, the cognitive interference channel consists of two transmitters whose signals interfere at two receivers. It is assumed that there is a common message (message 1) known to both transmitters, and an additional independent message (message 2) known only to the cognitive transmitter (transmitter 2). The cognitive receiver (receiver 2) needs to decode messages 1 and 2, while the non cognitive receiver (receiver 1) should decode only message 1. Furthermore, message 2 is assumed to be a confidential message which needs to be kept as secret as possible from receiver 1, which is viewed as an eavesdropper with regard to message 2. The level of secrecy is measured by the equivocation rate. In this paper, a single-letter expression for the capacity-equivocation region of the discrete memoryless cognitive interference channel is obtained. The capacity-equivocation region for the Gaussian cognitive interference channel is also obtained explicitly. Moreover, particularizing the capacity-equivocation region to the case without a secrecy constraint, the capacity region for the two-user cognitive interference channel is obtained, by providing a converse theorem.

A new universal estimator of divergence is presented for multidimensional continuous densities based on$k$-nearest-neighbor ($k$-NN) distances. Assuming independent and identically distributed (i.i.d.) samples, the new estimator is proved to be asymptotically unbiased and mean-square consistent. In experiments with high-dimensional data, the$k$-NN approach generally exhibits faster convergence than previous algorithms. It is also shown that the speed of convergence of the$k$-NN method can be further improved by an adaptive choice of$k$.

Erasure entropy rate differs from Shannon's entropy rate in that the conditioning occurs with respect to both the past and the future, as opposed to only the past (or the future). In this paper, consistent universal algorithms for estimating erasure entropy rate are proposed based on the basic and extended context-tree weighting (CTW) algorithms. Simulation results for those algorithms applied to Markov sources, tree sources, and English texts are compared to those obtained by fixed-order plug-in estimators with different orders.

We determine the linear precoding policy that maximizes the mutual information for general multiple-input multiple-output (MIMO) Gaussian channels with arbitrary input distributions, by capitalizing on the relationship between mutual information and minimum mean squared error (MMSE). The optimal linear precoder can be computed by means of a fixed- point equation as a function of the channel and the input constellation. We show that diagonalizing the channel matrix does not maximize the information transmission rate for nonGaussian inputs. A full precoding matrix may significantly increase the information transmission rate, even for parallel non-interacting channels. We illustrate the application of our results to typical Gigabit DSL systems.

Robustness of optimization models for networking problems has been an under-explored area. Yet most existing algorithms for solving robust optimization problems are centralized, thus not suitable for many communication networking problems that demand distributed solutions. This paper represents the first step towards building a framework for designing distributed robust optimization algorithms. We first discuss several models for describing parameter uncertainty sets that can lead to decomposable problem structures. These models include general polyhedron, D-norm, and ellipsoid. We then apply these models to solve robust power control in wireless networks and robust rate control in wireline networks. In both applications, we propose distributed algorithms that converge to the optimal robust solution. Various tradeoffs among performance, robustness, and distributiveness are illustrated both analytically and through simulations.

This work studies the properties of the minimum mean-square error (MMSE) of estimating an arbitrary random variable contaminated by Gaussian noise based on the observation. The MMSE can be regarded as a function of the signal-to-noise ratio (SNR), as well as a functional or transform of the input distribution. This paper shows that the MMSE is analytic in SNR for every random variable. Simple expressions for the derivatives of the MMSE as a function of the SNR are obtained. Since the input-output mutual information can be written as the integral of the MMSE as a function of SNR, the results also lead to higher derivatives of the mutual information. The MMSE and mutual informationpsilas convexity in the SNR and concavity in the input distribution are established. It is shown that there can be only one SNR for which the MMSE of a Gaussian random variable and that of a non-Gaussian random variable coincide. Application of the properties of the MMSE to the scalar Gaussian broadcast channel problem is presented.

We present two results related to the computational complexity of lossy compression. The first result shows that for a memoryless source Ps with rate-distortion function R(D), the rate-distortion pair (R(D) + gamma, D + isin) can be achieved with constant decoding time per symbol and encoding time per symbol proportional to C1(gamma)isin-C2(gamma). The second results establishes that for any given R, there exists a universal lossy compression scheme with O(ng(n)) encoding complexity and O(n) decoding complexity, that achieves the point (R,D(R)) asymptotically for any ergodic source with distortion-rate function D(.), where g(n) is an arbitrary non-decreasing unbounded function. A computationally feasible implementation of the first scheme outperforms many of the best previously proposed schemes for binary sources with blocklengths of the order of 1000.

Fano's inequality relates the error probability and conditional entropy of a finitely-valued random variable X given another random variable Y. It is not necessarily tight when the marginal distribution of X is fixed. In this paper, we consider both finite and countably infinite alphabets. A tight upper bound on the conditional entropy of X given Y is given in terms of the error probability and the marginal distribution of X. A new lower bound on the conditional entropy for countably infinite alphabet is also found. The equivalence of the reliability criteria of vanishing error probability and vanishing conditional entropy is established in wide generality.

Three essentially different approaches to the constructive part of the channel coding theorem have been proposed by Shannon, Feinstein and Gallager, respectively, leading to upper bounds on the minimal error probability achievable with a given rate and blocklength. Here, new upper bounds are given on both average and maximal error probability, which are tighter than existing bounds for many ranges of blocklength and channel parameters of interest. Along with converse bounds, the new achievability bounds allow to approximate tightly the maximum rate achievable for a given blocklength and error probability for blocklengths as short as n = 200 for both the BSC and the BEC.

Cognitive state-dependent interference channels are analyzed. We focus on the two-user case with two message sources. One of the transmitters, referred to as the cognitive informed user, knows both messages and also the states of the channel in a non-causal manner. The other transmitter knows only one of the messages and does not know the channel states. Each of the two decoders is supposed to decode only its intended message. Inner and outer bounds on the capacity region of this channel are provided for the general finite input alphabet case. The asymmetric state-dependent Gaussian weak interference channel with non-causal state information is then considered, and a closed form formula for the capacity region is established in the regime of weak interference.

This paper finds the capacity of a linear time-invariant system with a given transfer function, observed in additive Gaussian noise through a memoryless fading channel. A coherent model is assumed where the fading coefficients are known at the receiver (but not the transmitter). We show that the optimum normalized power spectral density is the waterfilling solution for reduced signal-to-noise ratio, where the gap to the actual signal-to-noise ratio depends on both the fading distribution and the channel transfer function.

We investigate the input covariance that maximizes the mutual information of deterministic multiple-input multipleo-utput (MIMO) Gaussian channels with arbitrary (not necessarily Gaussian) input distributions, by capitalizing on the relationship between the gradient of the mutual information and the minimum mean-squared error (MMSE) matrix. We show that the optimal input covariance satisfies a simple fixed-point equation involving key system quantities, including the MMSE matrix. We also specialize the form of the optimal input covariance to the asymptotic regimes of low and high snr. We demonstrate that in the low-snr regime the optimal covariance fully correlates the inputs to better combat noise. In contrast, in the high-snr regime the optimal covariance is diagonal with diagonal elements obeying the generalized mercury/waterfilling power allocation policy. Numerical results illustrate that covariance optimization may lead to significant gains with respect to conventional strategies based on channel diagonalization followed by mercury/waterfilling or waterfilling power allocation, particularly in the regimes of medium and high snr.

This paper formulates power allocation policies that maximize the region of mutual informations achievable in multiuser downlink OFDM channels. Arbitrary partitioning of the available tones among users and arbitrary modulation formats, possibly different for every user, are considered. Two distinct policies are derived, respectively for slow fading channels tracked instantaneously by the transmitter and for fast fading channels known only statistically thereby. With instantaneous channel tracking, the solution adopts the form of a multiuser mercury/waterfilling procedure that generalizes the single-user mercury/waterfilling introduced in [1], [2]. With only statistical channel information, in contrast, the mercury/waterfllling interpretation is lost. For both policies, a number of limiting regimes are explored and illustrative examples are provided.

Following the discovery of a fundamental connection between information measures and estimation measures in Gaussian channels, this paper explores the counterpart of those results in Poisson channels. In the continuous-time setting, the received signal is a doubly stochastic Poisson point process whose rate is equal to the input signal plus a dark current. It is found that, regardless of the statistics of the input, the derivative of the input-output mutual information with respect to the intensity of the additive dark current can be expressed as the expected difference between the logarithm of the input and the logarithm of its noncausal conditional mean estimate. The same holds for the derivative with respect to input scaling, but with the logarithmic function replaced by x log x. Similar relationships hold for discrete-time versions of the channel where the outputs are Poisson random variables conditioned on the input symbols.

In many applications, an uncompressed source stream is systematically encoded by a channel code (which ignores the source redundancy) for transmission over a discrete memoryless channel. The decoder knows the channel and the code but does not know the source statistics. This paper proposes several universal channel decoders that take advantage of the source redundancy without requiring prior knowledge of its statistics.

A popular way to measure the degree of dependence between two random objects is by their mutual information, defined as the divergence between the joint and product-of-marginal distributions. We investigate an alternative measure of dependence: the lautum information defined as the divergence between the product-of-marginal and joint distributions, i.e., swapping the arguments in the definition of mutual information. Some operational characterizations and properties are provided for this alternative measure of information.

We generalize the Gel'fand–Pinsker model to encompass the setup of a memoryless multiple-access channel (MAC). According to this setup, only one of the encoders knows the state of the channel (noncausally), which is also unknown to the receiver. Two independent messages are transmitted: a common message and a message transmitted by the informed encoder. We find explicit characterizations of the capacity region with both noncausal and causal state information. Further, we study the noise-free binary case, and we also apply the general formula to the Gaussian case with noncausal channel state information, under an individual power constraint as well as a sum power constraint. In this case, the capacity region is achievable by a generalized writing-on-dirty-paper scheme.

We consider sources and channels with memory observed through erasure channels. In particular, we examine the impact of sporadic erasures on the fundamental limits of lossless data compression, lossy data compression, channel coding, and denoising. We define the erasure entropy of a collection of random variables as the sum of entropies of the individual variables conditioned on all the rest. The erasure entropy measures the information content carried by each symbol knowing its context. The erasure entropy rate is shown to be the minimal amount of bits per erasure required to recover the lost information in the limit of small erasure probability. When we allow recovery of the erased symbols within a prescribed degree of distortion, the fundamental tradeoff is described by the erasure rate-distortion function which we characterize. We show that in the regime of sporadic erasures, knowledge at the encoder of the erasure locations does not lower the rate required to achieve a given distortion. When no additional encoded information is available, the erased information is reconstructed solely on the basis of its context by a denoiser. Connections between erasure entropy and discrete denoising are developed. The decrease of the capacity of channels with memory due to sporadic memoryless erasures is also characterized in wide generality.

A sourceXgoes through an erasure channel whose output isZ. The goal is to compress losslesslyXwhen the compressor knowsXandZand the decompressor knowsZ. We propose a universal algorithm based on context-tree weighting (CTW), parameterized by a memory-length parameter. We show that if the erasure channel is stationary and memoryless, andXis stationary and ergodic, then the proposed algorithm achieves a compression rate ofH(X0|X-l-1,Zl) bits per erasure.

We consider the Wyner-Ziv (WZ) problem of rate- distortion coding with decoder side information, for the case where the source statistics are unknown or non-existent. A new family of WZ coding algorithms is proposed and its universal optimality is proven. Encoding is based on a sliding window operation followed by LZ compression, while decoding is based on a natural extension of the Discrete Universal DEnoiser (DUDE) algorithm to the case where side information is present. The effectiveness of our approach is illustrated with experiments on binary images using a low complexity algorithm motivated by our class of universally optimal WZ codes.

We generalize the Gel'fand-Pinsker model to encompass the setup of a memoryless multiple-access channel. According to this setup, only one of the encoders knows the state of the channel (non-causally), which is also unknown to the receiver. Two independent messages are transmitted: a common message and a message transmitted by the informed encoder. We find explicit characterizations of the capacity region with both non-causal and causal state information. Further, we apply the general formula to the Gaussian case with non-causal channel state information, under an individual power constraint as well as a sum power constraint. In this case, the capacity region is achievable by a generalized writing-on-dirty-paper scheme.

This paper finds the capacity of linear time-invariant systems observed in additive Gaussian noise through a memoryless erasure channel. This problem requires obtaining the asymptotic spectral distribution of a submatrix of a nonnegative definite Toeplitz matrix obtained by retaining each column/row independently and with identical probability. We show that the optimum normalized power spectral density is the water filling solution for reduced signal-to-noise ratio, where the gap to the actual signal-to-noise ratio depends on both the erasure probability and the channel transfer function. We find asymptotic expressions for the capacity in the sporadic erasure and sporadic non-erasure regimes as well as the low and high signal-to-noise regimes.

A relationship between information theory and estimation theory was recently shown for the Gaussian channel, relating the derivative of mutual information with the minimum mean-square error. This paper generalizes the link between information theory and estimation theory to arbitrary channels, giving representations of the derivative of mutual information as a function of the conditional marginal input distributions given the outputs. We illustrate the use of this representation in the efficient numerical computation of the mutual information achieved by inputs such as specific codes or natural language

Fountain codes are currently employed for reliable and efficient transmission of information via erasure channels with unknown erasure rates. This correspondence introduces the notion of fountain capacity for arbitrary channels. In contrast to the conventional definition of rate, in the fountain setup the definition of rate penalizes the reception of symbols by the receiver rather than their transmission. Fountain capacity measures the maximum rate compatible with reliable reception regardless of the erasure pattern. We show that fountain capacity and Shannon capacity are equal for stationary memoryless channels. In contrast, Shannon capacity may exceed fountain capacity if the channel has memory or is not stationary.

This paper formulates the power allocation policy that maximizes the region of ergodic mutual informations achievable in multiuser downlink OFDM channels known only statistically by the base station. Arbitrary partitioning of the available tones among users and arbitrary modulation formats, possibly different for every user, are considered. The derivation relies on the nexus between the mutual information of Gaussian channels and the minimum mean-square error incurred in the nonlinear estimation of the transmit constellation points given their noisy receive observations.

This paper characterizes the marginal probability density function of an unordered eigenvalue of finite-dimensional random matrices of particular interest in MIMO (multiple-input multiple-output) wireless communications. Specifically, a technique is presented for deriving the eigenvalue statistics in one-side correlated Rayleigh-faded channels and in Ricean-faded channels, with or without cochannel interferers. The exact expressions found turn out to be extremely useful in calculating information-theoretic quantities. As an application, we calculate the ergodic mutual information for all the abovementioned channel fading conditions, obtaining a closed form formula for the Rayleigh case and, in turn, a series expression for the Ricean faded one.

The differential entropy of a random variable (or vector) can be expressed as the integral over signal-to-noise ratio (SNR) of the minimum mean-square error (MMSE) of estimating the variable (or vector) when observed in additive Gaussian noise. This representation sidesteps Fisher's information to provide simple and insightful proofs for Shannon's entropy power inequality (EPI) and two of its variations: Costa's strengthened EPI in the case in which one of the variables is Gaussian, and a generalized EPI for linear transformations of a random vector due to Zamir and Feder.

Fountain codes have been successfully employed for reliable and efficient transmission of information via erasure channels with unknown erasure rates. This paper introduces the notion of fountain capacity for arbitrary channels, and shows that it is equal to the conventional Shannon capacity for stationary memoryless channels. In contrast, when the channel is not stationary or has memory, Shannon capacity and fountain capacity need not be equal

Using an information-spectrum approach, a limiting expression for the capacity region of a general network without relays combined of M transmitters observing K input messages, and L receivers, is found. This general setup accounts for the broadcast channel with common messages, the general interference channel, and the multiple access channel as special cases. It is demonstrated how the limiting expression can be used to yield a single-letter tight outer bound for the case of a two-user stationary memoryless degraded broadcast channel

We define the erasure entropy of a collection of random variables as the sum of entropies of the individual variables conditioned on all the rest. The erasure entropy rate of a source is defined as the limit of the normalized erasure entropy. The erasure entropy measures the information content carried by each symbol knowing its context. In the setup of a source observed through an erasure channel, we offer an operational characterization of erasure entropy rate as the minimal amount of bits per erasure required to recover the erased information in the limit of small erasure probability. When we allow recovery of the erased symbols within a prescribed degree of distortion, the fundamental tradeoff is described by the erasure rate-distortion function which we characterize. When no additional encoded information is available, the erased information is reconstructed solely on the basis of its context by a denoiser. Connections between erasure entropy and discrete denoising are also explored

A method for divergence estimation between multidimensional distributions based on nearest neighbor distances is proposed. Given i.i.d. samples, both the bias and the variance of this estimator are proven to vanish as sample sizes go to infinity. In experiments on high-dimensional data, the nearest neighbor approach generally exhibits faster convergence compared to previous algorithms based on partitioning

Erasure entropy rate (introduced recently by Verdu and Weissman) differs from Shannon's entropy rate in that the conditioning occurs with respect to both the past and the future, as opposed to only the past (or the future). In this paper, universal algorithms for estimating erasure entropy rate are proposed based on the basic and extended context-tree weighting (CTW) algorithms. Consistency results are shown for those CTW based algorithms. Simulation results for those algorithms applied to Markov sources, tree sources and English texts are compared to those obtained by fixed-order plug-in estimators with different orders. An estimate of the erasure entropy of English texts based on the proposed algorithms is about 0.22 bits per letter, which can be compared to an estimate of about 1.3 bits per letter for the entropy rate of English texts by a similar CTW based algorithm

A popular way to measure the degree of dependence between two random variables is with mutual information, defined as the divergence between the joint and product-of- marginal distributions. We introduce an alternative measure of dependence we refer to as lautum information: the divergence between the product-of-marginal and joint distributions. Some operational characterizations and properties are provided for this alternative measure of information.

This paper studies universal estimation of divergence from the realizations of two unknown finite-alphabet sources. Two algorithms that borrow techniques from data compression are presented. The first divergence estimator applies the Burrows–Wheeler block sorting transform to the concatenation of the two realizations; consistency of this estimator is shown for all finite-memory sources. The second divergence estimator is based on the Context Tree Weighting method; consistency is shown for all sources whose memory length does not exceed a known bound. Experimental results show that both algorithms perform similarly and outperform string-matching and plug-in methods.

This paper proposes a new algorithm based on the Context-Tree Weighting (CTW) method for universal compression of a finite-alphabet sequence x1nwith side information y1navailable to both the encoder and decoder. We prove that with probability one the compression ratio converges to the conditional entropy rate for jointly stationary ergodic sources. Experimental results with Markov chains and English texts show the effectiveness of the algorithm

The mutual information of independent parallel Gaussian-noise channels is maximized, under an average power constraint, by independent Gaussian inputs whose power is allocated according to the waterfilling policy. In practice, discrete signaling constellations with limited peak-to-average ratios (m-PSK, m-QAM, etc.) are used in lieu of the ideal Gaussian signals. This paper gives the power allocation policy that maximizes the mutual information over parallel channels with arbitrary input distributions. Such policy admits a graphical interpretation, referred to as mercury/waterfilling, which generalizes the waterfilling solution and allows retaining some of its intuition. The relationship between mutual information of Gaussian channels and nonlinear minimum mean-square error (MMSE) proves key to solving the power allocation problem.

This paper considers a general linear vector Gaussian channel with arbitrary signaling and pursues two closely related goals: i) closed-form expressions for the gradient of the mutual information with respect to arbitrary parameters of the system, and ii) fundamental connections between information theory and estimation theory. Generalizing the fundamental relationship recently unveiled by Guo, Shamai, and Verdu/spl acute/, we show that the gradient of the mutual information with respect to the channel matrix is equal to the product of the channel matrix and the error covariance matrix of the best estimate of the input given the output. Gradients and derivatives with respect to other parameters are then found via the differentiation chain rule.

A conceptually simple proof for the capacity formula of an exponential server timing channel is provided. The proof links the timing channel to the point-process channel with instantaneous noiseless feedback. This point-process approach enables a study of timing channels that arise in multiserver queues, queues in tandem, and other simple configurations. Although the capacities of such channels remain to be found, the paper provides some analytical bounds and highlights a method to find achievable rates via simulations.

Artstein, Ball, Barthe, and Naor have recently shown that the non-Gaussianness (divergence with respect to a Gaussian random variable with identical first and second moments) of the sum of independent and identically distributed (i.i.d.) random variables is monotonically nonincreasing. We give a simplified proof using the relationship between non-Gaussianness and minimum mean-square error (MMSE) in Gaussian channels. As Artstein , we also deal with the more general setting of nonidentically distributed random variables

This correspondence gives a simple proof of Shannon's entropy-power inequality (EPI) using the relationship between mutual information and minimum mean-square error (MMSE) in Gaussian channels.

We develop adaptive schemes for bidirectional modeling of unknown discrete stationary sources. These algorithms can be applied to statistical inference problems such as noncausal universal discrete denoising that exploit bidirectional dependencies. Efficient algorithms for constructing those models are developed and we compare their performance to that of the DUDE algorithm for universal discrete denoising

We characterize the capacity-achieving input covariance for multi-antenna channels known instantaneously at the receiver and in distribution at the transmitter. Our characterization, valid for arbitrary numbers of antennas, encompasses both the eigenvectors and the eigenvalues. The eigenvectors are found for zero-mean channels with arbitrary fading profiles and a wide range of correlation and keyhole structures. For the eigenvalues, in turn, we present necessary and sufficient conditions as well as an iterative algorithm that exhibits remarkable properties: universal applicability, robustness and rapid convergence. In addition, we identify channel structures for which an isotropic input achieves capacity.

This paper characterizes the asymptotic distribution of the input-output mutual information of multiantenna channels. Using recent results on random matrix theory, we prove asymptotic normality of the unnormalized mutual information for arbitrary signal-to-noise ratios and fading distributions, allowing for correlation between the antennas at either transmitter or receiver.

In the high-SNR regime, the multi-antenna mutual information behaves as an affine function of SNR|/sub dB/, described by the multiplexing gain, which quantifies the multiplicative increase as function of the number of antennas, and the power offset (zero-order term in dB). The conventional high-SNR analysis that considers only the multiplexing gain is unable to assess the impact of channel features such as the Rician factor since, irrespective thereof, the multiplexing gain equals the minimum of the number of transmit and receive antennas. The impact of the Rician factor at high SNR can be conveniently quantified through the corresponding power offset, which this paper evaluates in closed-form.

This paper proposes a new algorithm based on the context-tree weighting method for universal compression of a finite-alphabet sequence x/sub 1//sup n/ with side information y/sub 1//sup n/ available to both the encoder and decoder. We prove that with probability one the compression ratio converges to the conditional entropy rate for jointly stationary ergodic sources. Experimental results with Markov chains and English texts show the effectiveness of the algorithm.

This paper proposes a practical scheme to transmit reliable information through a noisy symmetric DMC using limited noiseless feedback. The ratio of feedback rate to feedforward rate is a design parameter that can be selected from zero to 1 - C, where C is the capacity of the channel. The proposed scheme uses a concatenation of low-density parity-check codes, belief propagation, and a noisy version of the closed-loop iterative doping algorithm, previously proposed by the authors for data compression using linear codes. Our scheme takes advantage of the availability of a modicum of feedback to achieve very small block error rates

It has recently been shown that the derivative of the input-output mutual information of Gaussian noise channels with respect to the signal-to-noise ratio is equal to the minimum mean-square error. This paper considers general additive noise channels where the noise may not be Gaussian distributed. It is found that, for every fixed input distribution, the derivative of the mutual information with respect to the signal strength is equal to the correlation of two conditional mean estimates associated with the input and the noise respectively. Special versions of the result are given in the respective cases of additive exponentially distributed noise, Cauchy noise, Laplace noise, and Rayleigh noise. The previous result on Gaussian noise channels is also recovered as a special case

For parallel independent Gaussian-noise channels with an aggregate power constraint, independent Gaussian inputs whose powers are allocated according to the waterfilling policy maximize the sum mutual information. In practice, however, discrete signalling constellations such as m-PSK or m-QAM are used in lieu of the ideal Gaussian signals. This paper gives the power allocation policy, referred to as mercury/waterfilling, that maximizes the sum mutual information over parallel channels with arbitrary input constellations

This paper considers a general linear vector Gaussian channel with arbitrary signaling and pursues two closely related goals: i) closed-form expressions for the gradient of the mutual information with respect to arbitrary parameters of the system, and ii) fundamental connections between information theory and estimation theory. Generalizing the fundamental relationship recently unveiled by Guo, Shamai, and Verdu, we show that the gradient of the mutual information with respect to the channel matrix is equal to the product of the channel matrix and the error covariance matrix of the estimate of the input given the output

We consider the broadcast-relay channel: a broadcast channel where receivers are permitted to assist in the distribution of data to other receivers by relaying. We extend the previous results and demonstrate that effective transmission strategies can be derived by combining well-known techniques for broadcast and relay channels. Additionally, we derive new outer bounds to capacity regions

We present a universal estimator of the divergence D(PparQ) for two arbitrary continuous distributions P and Q satisfying certain regularity conditions. This algorithm, which observes i.i.d. samples from both P and Q, is based on the estimation of the Radon-Nikodym derivative dP/dQ via a data-dependent partition of the observation space. Strong convergence of this estimator is proved with an empirically equivalent segmentation of the space. This basic estimator is further improved by adaptive partitioning schemes and by bias correction. In the simulations, we compare our estimators with the plug-in estimator and estimators based on other partitioning approaches. Experimental results show that our methods achieve the best convergence performance in most of the tested cases

In this presentation, the author gives an overview of the state of the art in universal estimation of: entropy; divergence; mutual information with emphasis on recent algorithms we have proposed with H. Cai, S. Kulkarni and Q. Wang. These algorithms converge to the desired quantities without any knowledge of the statistical properties of the observed data, under several conditions such as stationary-ergodicity in the case of discrete processes, and memorylessness in the case of analog data. A sampling of the literature in this topic is given below.

This paper deals with arbitrarily distributed finite-power input signals observed through an additive Gaussian noise channel. It shows a new formula that connects the input-output mutual information and the minimum mean-square error (MMSE) achievable by optimal estimation of the input given the output. That is, the derivative of the mutual information (nats) with respect to the signal-to-noise ratio (SNR) is equal to half the MMSE, regardless of the input statistics. This relationship holds for both scalar and vector signals, as well as for discrete-time and continuous-time noncausal MMSE estimation. This fundamental information-theoretic result has an unexpected consequence in continuous-time nonlinear estimation: For any input signal with finite power, the causal filtering MMSE achieved at SNR is equal to the average value of the noncausal smoothing MMSE achieved with a channel whose SNR is chosen uniformly distributed between 0 and SNR.

This paper studies randomly spread code-division multiple access (CDMA) and multiuser detection in the large-system limit using the replica method developed in statistical physics. Arbitrary input distributions and flat fading are considered. A generic multiuser detector in the form of the posterior mean estimator is applied before single-user decoding. The generic detector can be particularized to the matched filter, decorrelator, linear minimum mean-square error (MMSE) detector, the jointly or the individually optimal detector, and others. It is found that the detection output for each user, although in general asymptotically non-Gaussian conditioned on the transmitted symbol, converges as the number of users go to infinity to a deterministic function of a "hidden" Gaussian statistic independent of the interferers. Thus, the multiuser channel can be decoupled: Each user experiences an equivalent single-user Gaussian channel, whose signal-to-noise ratio (SNR) suffers a degradation due to the multiple-access interference (MAI). The uncoded error performance (e.g., symbol error rate) and the mutual information can then be fully characterized using the degradation factor, also known as the multiuser efficiency, which can be obtained by solving a pair of coupled fixed-point equations identified in this paper. Based on a general linear vector channel model, the results are also applicable to multiple-input multiple-output (MIMO) channels such as in multiantenna systems.

The analysis of the multiple-antenna capacity in the high-SNR regime has hitherto focused on the high-SNR slope (or maximum multiplexing gain), which quantifies the multiplicative increase as a function of the number of antennas. This traditional characterization is unable to assess the impact of prominent channel features since, for a majority of channels, the slope equals the minimum of the number of transmit and receive antennas. Furthermore, a characterization based solely on the slope captures only the scaling but it has no notion of the power required for a certain capacity. This paper advocates a more refined characterization whereby, as a function of SNR|/sub dB/, the high-SNR capacity is expanded as an affine function where the impact of channel features such as antenna correlation, unfaded components, etc., resides in the zero-order term or power offset. The power offset, for which we find insightful closed-form expressions, is shown to play a chief role for SNR levels of practical interest.

We analyze the spectral efficiency (sum-rate per subcarrier) of randomly spread synchronous multicarrier code-division multiple access (MC-CDMA) subject to frequency-selective fading in the asymptotic regime of number of users and bandwidth going to infinity with a constant ratio. Both uplink and downlink are considered, either conditioned on the subcarrier fading coefficients (for nonergodic channels) or unconditioned thereon (for ergodic channels). The following receivers are analyzed: a) jointly optimum receiver, b) linear minimum mean-square error (MMSE) receiver, c) decorrelator, and d) single-user matched filter.

This paper applies random matrix theory to obtain analytical characterizations of the capacity of correlated multiantenna channels. The analysis is not restricted to the popular separable correlation model, but rather it embraces a more general representation that subsumes most of the channel models that have been treated in the literature. For arbitrary signal-to-noise ratios (SNR), the characterization is conducted in the regime of large numbers of antennas. For the low- and high-SNR regions, in turn, we uncover compact capacity expansions that are valid for arbitrary numbers of antennas and that shed insight on how antenna correlation impacts the tradeoffs among power, bandwidth, and rate.

We present a universal estimator of the divergence D(P/spl par/Q) for two arbitrary continuous distributions P and Q satisfying certain regularity conditions. This algorithm, which observes independent and identically distributed (i.i.d.) samples from both P and Q, is based on the estimation of the Radon-Nikodym derivative dP/dQ via a data-dependent partition of the observation space. Strong convergence of this estimator is proved with an empirically equivalent segmentation of the space. This basic estimator is further improved by adaptive partitioning schemes and by bias correction. The application of the algorithms to data with memory is also investigated. In the simulations, we compare our estimators with the direct plug-in estimator and estimators based on other partitioning approaches. Experimental results show that our methods achieve the best convergence performance in most of the tested cases.

A discrete denoising algorithm estimates the input sequence to a discrete memoryless channel (DMC) based on the observation of the entire output sequence. For the case in which the DMC is known and the quality of the reconstruction is evaluated with a given single-letter fidelity criterion, we propose a discrete denoising algorithm that does not assume knowledge of statistical properties of the input sequence. Yet, the algorithm is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution, which is only assumed to be stationary. Moreover, the algorithm is universal also in a semi-stochastic setting, in which the input is an individual sequence, and the randomness is due solely to the channel noise. The proposed denoising algorithm is practical, requiring a linear number of register-level operations and sublinear working storage size relative to the input data length.

Transmission of information over a discrete-time memoryless Rician fading channel is considered, where neither the receiver nor the transmitter knows the fading coefficients. First, the structure of the capacity-achieving input signals is investigated when the input is constrained to have limited peakedness by imposing either a fourth moment or a peak constraint. When the input is subject to second and fourth moment limitations, it is shown that the capacity-achieving input amplitude distribution is discrete with a finite number of mass points in the low-power regime. A similar discrete structure for the optimal amplitude is proven over the entire signal-to-noise ratio (SNR) range when there is only a peak-power constraint. The Rician fading with the phase-noise channel model, where there is phase uncertainty in the specular component, is analyzed. For this model, it is shown that, with only an average power constraint, the capacity-achieving input amplitude is discrete with a finite number of levels. For the classical average-power-limited Rician fading channel, it is proven that the optimal input amplitude distribution has bounded support.

Transmission of information over a discrete-time memoryless Rician fading channel is considered, where neither the receiver nor the transmitter knows the fading coefficients. The spectral-efficiency/bit-energy tradeoff in the low-power regime is examined when the input has limited peakedness. It is shown that if a fourth-moment input constraint is imposed, or the input peak-to-average power ratio is limited, then in contrast to the behavior observed in average-power-limited channels, the minimum bit energy is not always achieved at zero spectral efficiency. The low-power performance is also characterized when there is a fixed peak limit that does not vary with the average power. A new signaling scheme that overlays phase-shift keying on ON-OFF keying (OOK) is proposed and shown to be optimally efficient in the low-power regime.

Transmission of information over wideband fading channels using M-ary orthogonal on/off FSK (OOFSK) signaling, in which M-ary FSK signaling is overlaid on on/off keying, is considered. It is assumed that the receiver uses energy detection for the reception of OOFSK signals. Capacity expressions are obtained when the receiver has perfect and imperfect fading side information. Power efficiency is investigated when the transmitter is subject to a peak-to-average power ratio (PAR) limitation or a peak power limitation. It is shown that under PAR limitation, it is extremely power inefficient to operate in the very low SNR regime. On the other hand, if there is only a peak power limitation, it is demonstrated that power efficiency improves as one operates with smaller SNR and vanishing duty factor.

Consider arbitrarily distributed input signals observed in additive Gaussian noise. A new fundamental relationship is found between the input-output mutual information and the minimum mean-square error (MMSE) of an estimate of the input given the output: The derivative of the mutual information (nats) with respect to the signal-to-noise ratio (SNR) is equal to half the MMSE. This identity holds for both scalar and vector signals, as well as for discrete- and continuous-time noncausal MMSE estimation (smoothing). A consequence of the result is a new relationship in continuous-time nonlinear filtering: Regardless of the input statistics, the causal MMSE achieved at snr is equal to the expected value of the noncausal MMSE achieved with a channel whose SNR is chosen uniformly distributed between 0 and snr

In this paper, the capacity and spectral efficiency of peak power limited Rician block-fading channels when neither the receiver nor the transmitter knows the fading coefficients is studied. The capacity-achieving input amplitude distribution of the average power limited memoryless unknown Rayleigh fading channel is discrete with a finite number of mass points is proved. The spectral-efficiency and the bit energy tradeoff in the low power regime is studied.

In this paper, the high-SNR multiantenna capacity with coherent receivers on the multiplexing gain, i.e., the multiplicative increase as function of the number of antennas is analyzed. For most channels of interest, such multiplexing gain equals the minimum of the number of transmit and receive antennas. This traditional characterization, however, is unable to quantify the impact of many relevant channel features. As a function of SNR, the capacity is very well approximated, from moderate SNR on, as an affine function. The impact of the various channel features is captured in the power offset (in dB) or zero-order term in the affine expansion.

This paper describes the channel decoding of systematically encoded unknown redundant sources. The redundancy of the data is known at the decoder and the channel decoder incorporates the statistics of the data to enhance the performance. The practical decoders are designed which takes the advantage of the source redundancy of systematically encoded for transmission over a discrete memoryless channel (DMC). The performance is achieved by operating discrete universal denoiser (DUDE) and the experiments involving Reed-Solomon codes show that DUDE-enhanced decoding is very effective at high rates.

In this paper, we analyze the effect of scaling laws in random heterogeneous networks. This paper describes a square grid with shortcuts and a scaling law with wired shortcuts

This paper proposes a universal variable-length lossless compression algorithm based on fountain codes. The compressor concatenates the Burrows-Wheeler block sorting transform (BWT) with a fountain encoder, together with the closed-loop iterative doping algorithm. The decompressor uses a belief propagation algorithm in conjunction with the iterative doping algorithm and the inverse BWT. Linear-time compression/decompression complexity and competitive performance with respect to state-of-the-art compression algorithms are achieved.

Following the recent discovery of new connections between information and estimation in Gaussian channels, this paper reports parallel results in the Poisson regime. Both scalar and continuous-time Poisson channels are considered. It is found that, regardless of the statistics of the input, the derivative of the input-output mutual information with respect to the dark current can be expressed in the expected difference between the logarithm of the input and the logarithm of its conditional mean estimate (noncausal in case of continuous-time). The same is true for the derivative with respect to input scaling, but with the logarithmic function replaced by x log x.

We characterize the power allocation that maximizes the rate per unit bandwidth supported with arbitrary reliability over single-user multiantenna channels known instantaneously by the receiver and in distribution by the transmitter. The characterization is valid for arbitrary channels and numbers of antennas. Although, in general, it leads to a fixed-point solution, at low and high signal-to-noise it provides explicit allocations. For arbitrary signal-to-noise ratios, we present an iterative algorithm that exhibits remarkable properties: robustness, rapid convergence and universal applicability. Further, when applied to the proper set of signalling eigenvectors, the algorithm converges to the power allocation that attains capacity.

In this correspondence, we present a new universal entropy estimator for stationary ergodic sources, prove almost sure convergence, and establish an upper bound on the convergence rate for finite-alphabet finite memory sources. The algorithm is motivated by data compression using the Burrows-Wheeler block sorting transform (BWT). By exploiting the property that the BWT output sequence is close to a piecewise stationary memoryless source, we can segment the output sequence and estimate probabilities in each segment. Experimental results show that our algorithm outperforms Lempel-Ziv (LZ) string-matching-based algorithms.

We investigate the spectral efficiency achievable by random synchronous code-division multiple access (CDMA) with quaternary phase-shift keying (QPSK) modulation and binary error-control codes, in the large system limit where the number of users, the spreading factor, and the code block length go to infinity. For given codes, we maximize spectral efficiency assuming a minimum mean-square error (MMSE) successive stripping decoder for the cases of equal rate and equal power users. In both cases, the maximization of spectral efficiency can be formulated as a linear program and admits a simple closed-form solution that can be readily interpreted in terms of power and rate control. We provide examples of the proposed optimization methods based on off-the-shelf low-density parity-check (LDPC) codes and we investigate by simulation the performance of practical systems with finite code block length.

We consider multiaccess, broadcast, and interference channels with additive Gaussian noise. Although the set of rate pairs achievable by time-division multiple access (TDMA) is not equal to the capacity region, the TDMA achievable region converges to the capacity region as the power decreases. Furthermore, TDMA achieves the optimum minimum energy per bit. Despite those features, this paper shows that the growth of TDMA-achievable rates with the energy per bit is suboptimal in the low-power regime except in special cases: multiaccess channels where the users' energy per bit are identical and broadcast channels where the receivers have identical signal-to-noise ratios. For the additive Gaussian noise interference channel, we identify a small region of interference parameters outside of which TDMA is also shown to be suboptimal. The effect of fading (known to the receiver) on the suboptimality of TDMA is also explored.

We consider a nonergodic multiple-access Gaussian block-fading channel where a fixed number of independent and identically distributed (i.i.d.) fading coefficients affect each codeword. Variable-rate coding with input power constraint enforced on a per-codeword basis is examined. A centralized power and rate allocation policy is determined as a function of the previous and present fading coefficients. The power control policy that optimizes the expected rates is obtained through dynamic programming and the average capacity region and the average capacity region per unit energy are characterized. Moreover, we study the slope of spectral efficiency curve versus E/sub b//N/sub 0/ (dB), and we quantify the penalty incurred by time-division multiple access (TDMA) over superposition coding in the low-power regime.

Reduced-rank minimum mean-squared error (MMSE) multiuser detectors using asymptotic weights have been shown to reduce receiver complexity while maintaining good performance in long-sequence code-division multiple-access (CDMA) systems. In this paper, we consider the design of reduced-rank MMSE receivers in a general framework which includes fading, single and multiantenna receivers, as well as direct-sequence CDMA (DS-CDMA) and multicarrier CDMA (both uplink and downlink). In all these cases, random matrix results are used to obtain explicit expressions for the asymptotic eigenvalue moments of the interference autocorrelation matrix and for the asymptotic weights used in the reduced-rank receiver.

A formula for the second-order expansion of the input-output mutual information of multidimensional channels as the signal-to-noise ratio (SNR) goes to zero is obtained. While the additive noise is assumed to be Gaussian, we deal with very general classes of input and channel distributions. As special cases, these channel models include fading channels, channels with random parameters, and channels with almost Gaussian noise. When the channel is unknown at the receiver, the second term in the asymptotic expansion depends not only on the covariance matrix of the input signal but also on the fourth mixed moments of its components. The study of the second-order asymptotics of mutual information finds application in the analysis of the bandwidth-power tradeoff achieved by various signaling strategies in the wideband regime.

We determine the capacity region of a degraded Gaussian relay channel with multiple relay stages. This is done by building an inductive argument based on the single-relay capacity theorem of Cover and El Gamal. For an arbitrary distribution of noise powers, we derive the optimal power distribution strategy among the transmitter and the relays and the best possible improvement in signal-to-noise ratio (SNR) that can be achieved from using a given number of relays. The time-division multiplexing operation of the relay channel in the wideband regime is analyzed and it is shown that time division does not achieve minimum energy per bit.

We optimize the random-like ensemble of irregular repeat-accumulate (IRA) codes for binary-input symmetric channels in the large block-length limit. Our optimization technique is based on approximating the evolution of the densities (DE) of the messages exchanged by the belief-propagation (BP) message-passing decoder by a one-dimensional dynamical system. In this way, the code ensemble optimization can be solved by linear programming. We propose four such DE approximation methods, and compare the performance of the obtained code ensembles over the binary-symmetric channel (BSC) and the binary-antipodal input additive white Gaussian noise channel (BIAWGNC). Our results clearly identify the best among the proposed methods and show that the IRA codes obtained by these methods are competitive with respect to the best known irregular low-density parity-check (LDPC) codes. In view of this and the very simple encoding structure of IRA codes, they emerge as attractive design choices.

Reduced-rank MMSE receivers using asymptotic weights reduce receiver complexity while maintaining good performance in long-sequence DS-CDMA systems. In this paper, we analyze such receivers in multipath fading channels and extend their design to multicarrier CDMA (both uplink and downlink). An explicit expression is obtained for the asymptotic eigenvalue moments of the interference autocorrelation matrix and for the asymptotic weights derived there from and used in the reduced-rank receiver. The full-rank MMSE receiver is also considered for multicarrier CDMA and a fixed point of equation of the asymptotic maximum output SINR is derived, which particularizes to the Tse-Hanly fixed point equation for the special case of DS-CDMA. An explicit expression of the MMSE spectral efficiency is proposed for multicarrier CDMA.

This paper describes a discrete universal denoiser for two dimensional data and also presents an experimental results of its application to noisy binary images. A discrete universal denoiser (DUDE) is introduced for recovering a signal with finite-valued components corrupted by finite-valued, uncorrelated noise. The DUDE is asymptotically optimal and universal, in the sense of asymptotically achieving, without access to any information on the statistics of the clean signal, the same performance as the best denoiser that does have access to such information. It is also practical, and can be implemented in low complexity.

A new fixed-length asymptotically optimal scheme for lossless compression of stationary ergodic tree sources with memory is proposed. Our scheme is based on the concatenation of the Burrows-Wheeler block sorting transform with the syndrome former of a linear error correcting code. Low-density parity-check (LDPC) codes together with belief propagation decoding lead to linear compression and decompression times, and to natural universal implementation of the algorithm.

We present some new results on large-system CDMA obtained through the replica method developed in statistical physics. We find the spectral efficiency of randomly spread CDMA subject to Gaussian noise and flat fading in the large-system limit under arbitrary input distributions. Both joint decoding and single-user decoding are considered. In the latter case, a conditional mean estimator is first applied to separate the users and it is found that the resulting single-user channel for every user is equivalent to a Gaussian channel. The multiuser efficiency of that Gaussian channel is the same for all users and satisfies a fixed-point equilibrium equation. The additive decomposition by Shamai-Verdu of optimum capacity in terms of single-user capacity is shown to hold for arbitrary input distributions.

We present an analytical characterization of multi-antenna capacity in the limit of a large number of antennas. In contrast to previous studies, the entries of the channel matrix are not restricted to be identically distributed, thus incorporating diversity mechanisms that are otherwise excluded, such as those based on the use of antennas with distinct polarizations and radiation patterns. In addition to the capacity, first-order expressions in the low- and high-power regimes are also evaluated both asymptotically and non-asymptotically.

This paper provides analytical characterizations of the impact on the multiple-antenna capacity of several important features that fall outside the standard multiple-antenna model, namely: (i) antenna correlation, (ii) Ricean factors, (iii) polarization diversity, and (iv) out-of-cell interference; all in the regime of low signal-to-noise ratio. The interplay of rate, bandwidth, and power is analyzed in the region of energy per bit close to its minimum value. The analysis yields practical design lessons for arbitrary number of antennas in the transmit and receive arrays.

In emerging mobile systems users must operate very often in the low-power regime. Specifically, almost 40 % of geographical locations experience signal-to-noise ratios (SNR) below 0 dB. Despite its relevance, the multi-antenna low-power regime had not been analyzed in depth until the paper by S. Verdu (see IEEE Trans. on Inform. Theory, p.1319-43, June 2002), where the figure of merit is not the SNR, but rather the normalized energy per information bit, E/sub b//N/sub 0/. This paper expands these findings using a channel model that realistically describes the conditions found in typical wireless systems. The focus is on channels that are known to the receiver, but unknown to the transmitter.

We propose a discrete denoising algorithm, that, based on the observation of the output of a known discrete memoryless channel (DMC), estimates the input sequence to minimize a given fidelity criterion. The algorithm is universal in the sense that it requires no knowledge of the input sequence or its statistical properties. Yet, asymptotically it performs as well as the optimum denoiser that knows the input sequence distribution. The proposed denoising algorithm is practical, and can be implemented in O(n log n) time and O(n/sup 2/3/ log n) storage complexity. Extensions to the case of delay-constrained denoising, and to the case of channel uncertainty, are briefly discussed.

The Burrows Wheeler transform (1994) is a reversible sequence transformation used in a variety of practical lossless source-coding algorithms. In each, the BWT is followed by a lossless source code that attempts to exploit the natural ordering of the BWT coefficients. BWT-based compression schemes are widely touted as low-complexity algorithms giving lossless coding rates better than those of the Ziv-Lempel codes (commonly known as LZ'77 and LZ'78) and almost as good as those achieved by prediction by partial matching (PPM) algorithms. To date, the coding performance claims have been made primarily on the basis of experimental results. This work gives a theoretical evaluation of BWT-based coding. The main results of this theoretical evaluation include: (1) statistical characterizations of the BWT output on both finite strings and sequences of length n /spl rarr/ /spl infin/, (2) a variety of very simple new techniques for BWT-based lossless source coding, and (3) proofs of the universality and bounds on the rates of convergence of both new and existing BWT-based codes for finite-memory and stationary ergodic sources. The end result is a theoretical justification and validation of the experimentally derived conclusions: BWT-based lossless source codes achieve universal lossless coding performance that converges to the optimal coding performance more quickly than the rate of convergence observed in Ziv-Lempel style codes and, for some BWT-based codes, within a constant factor of the optimal rate of convergence for finite-memory sources.

This paper proves large-system asymptotic normality of the output of a family of linear multiuser receivers that can be arbitrarily well approximated by polynomial receivers. This family of receivers encompasses the single-user matched filter, the decorrelator, the minimum mean square error (MMSE) receiver, the parallel interference cancelers, and many other linear receivers of interest. Both with and without the assumption of perfect power control, we show that the output decision statistic for each user converges to a Gaussian random variable in distribution as the number of users and the spreading factor both tend to infinity with their ratio fixed. Analysis reveals that the distribution conditioned on almost all spreading sequences converges to the same distribution, which is also the unconditional distribution. This normality principle allows the system performance, e.g., the multiuser efficiency, to be completely determined by the output signal-to-interference ratio (SIR) for large linear systems.

The tradeoff of spectral efficiency (b/s/Hz) versus energy-per-information bit is the key measure of channel capacity in the wideband power-limited regime. This paper finds the fundamental bandwidth-power tradeoff of a general class of channels in the wideband regime characterized by low, but nonzero, spectral efficiency and energy per bit close to the minimum value required for reliable communication. A new criterion for optimality of signaling in the wideband regime is proposed, which, in contrast to the traditional criterion, is meaningful for finite-bandwidth communication.

A simple multi-cell Rayleigh fading uplink communication model is suggested and analyzed for optimally coded randomly spread DS-CDMA with multiuser detection. The model adheres to Wyner's (1994) infinite linear cell-array setting, according to which only adjacent-cell interference is present, and characterized by a single parameter 0/spl les//spl alpha//spl les/1. The discussion is confined to asymptotic analysis where both the number of users per cell and the processing gain go to infinity, while their ratio goes to some finite constant. The spectral efficiency of various multiuser detection strategies is evaluated assuming single cell-site processing, and equal transmit powers for all users in all cells. Comparative results demonstrate how performance is affected by the introduction of inter-cell interference (with and without fading), and what is the penalty associated with the randomly spread coded DS-CDMA strategy.

Linear multiuser detectors for vector channels with crosstalk are approximated by weighted matrix polynomials. The weight optimization problem is overcome using convergence results from random matrix theory. The results are also extended to receivers with subsequent successive decoding. In the case of subsequent successive decoding, a novel low-complexity implementation is found for the first-order approximation that is based on matched filter banks only and does not require matrix algebra. Spectral efficiency is obtained analytically and found to be fairly close to the optimum. The paper is focussed on multiuser detection for CDMA, but the results can be easily extended to communication via antenna arrays.

In this paper, we design and analyze a new class of linear multiuser detectors, which can be applied when the users employ BPSK modulation and the fading coefficients of the active users are known at the receiver (such as base-station demodulation). The tools of asymptotic distribution of the spectrum of large random matrices are used to show that relative to the classical minimum mean-square-error (MMSE) receiver, the output signal-to-noise ratio (SNR) improves by halving the number of effective interferers and adding 3 dB to the input SNR. We also propose sensible approximations to the proposed linear receivers so as to facilitate their use in CDMA systems that employ long codes.

A simple multicell uplink communication model is suggested and analyzed for optimally coded randomly spread direct sequence code-division multiple access (DS-CDMA). The model adheres to Wyner's (1994) infinite linear cell-array model, according to which only adjacent-cell interference is present, and characterized by a single parameter 0/spl les//spl alpha//spl les/1. The discussion is confined to asymptotic analysis where both the number of users and the processing gain go to infinity, while their ratio goes to some finite constant. Single cell-site processing is assumed and four multiuser detection strategies are considered: the matched-filter detector, "optimum" detection with adjacent-cell interference treated as Gaussian noise, the linear minimum mean square error (MMSE) detector and a detector that performs MMSE-based successive interference cancellation for intracell users with linear MMSE processing of adjacent-cell interference. Spectral efficiency is evaluated under three power allocation policies: equal received powers (for all users), equal rates, and a maximal spectral efficiency policy. Comparative results demonstrate how performance is affected by the introduction of intercell interference, and what is the penalty associated with the randomly spread coded DS-CDMA strategy. Finally, the effect of intercell time-sharing protocols as suggested by Shamai and Wyner (1997) is also examined, and a significant system performance enhancement is observed.

The capacity of the randomly spread synchronous code-division multiple-access (CDMA) channel subject to frequency-flat fading is studied in the wide-band limit of large number of users. We find the spectral efficiency as a function of the number of users per chip, the distribution of the flat fading, and the signal-to-noise ratio (SNR), for the optimum receiver as well as linear receivers (single-user matched filter, decorrelator, and minimum mean-square error (MMSE)). The potential improvements due to both decentralized transmitter power control and multi-antenna receivers are also analyzed.

A universal variable-to-fixed length algorithm for binary memoryless sources which converges to the entropy of the source at the optimal rate is known. We study the problem of universal variable-to-fixed length coding for the class of Markov sources with finite alphabets. We give an upper bound on the performance of the code for large dictionary sizes and show that the code is optimal in the sense that no codes exist that have better asymptotic performance. The optimal redundancy is shown to be H log log M/log M where H is the entropy rate of the source and M is the code size. This result is analogous to Rissanen's (1984) result for fixed-to-variable length codes. We investigate the performance of a variable-to-fixed coding method which does not need to store the dictionaries, either at the coder or the decoder. We also consider the performance of both these source codes on individual sequences. For individual sequences we bound the performance in terms of the best code length achievable by a class of coders. All the codes that we consider are prefix-free and complete.

To transmit information by timing arrivals to a single-server queue, we consider using the exponential server channel's maximum likelihood decoder. For any server with service times that are stationary and ergodic with mean 1//spl mu/ seconds, we show that the rate e/sup -1//spl mu/ nats per second (capacity of the exponential server timing channel) is achievable using this decoder. We show that a similar result holds for the timing channel with feedback. We also show that if the server jams communication by adding an arbitrary amount of time to the nominal service time, then the rate e/sup -1//spl mu//sub 1//spl mu//sub 2//(/spl mu//sub 1/+/spl mu//sub 2/) nats per second is achievable with random codes, where the nominal service times are stationary and ergodic with mean 1//spl mu//sub 1/ seconds, and the arithmetic mean of the delays added by the server does not exceed 1//spl mu//sub 2/ seconds. This is a model of an arbitrarily varying channel where the current delay and the current input can affect future outputs. We also show the counterpart of these results for single-server discrete-time queues.

We show the existence of a good tree code with a sequential decoder for the exponential server timing channel. The expected number of computations before moving one step ahead is upper-bounded by a finite number. The rate of information transfer for this code is /spl mu//(2e) nats per second i.e., one half of the capacity. The cutoff rate for the exponential server queue is therefore at least /spl mu//(2u) nats per second.

This correspondence analyzes the high signal-to-noise ratio (SNR) performance of optimum multiuser detectors for synchronous direct-sequence spread spectrum with random spreading in an additive white Gaussian noise channel. Under very general conditions on the received powers, we show that the optimum asymptotic efficiency of a K-user system with spreading gain N converges to 1 almost surely as K/spl rarr//spl infin/, and K/N is kept equal to an arbitrary nonzero constant. Therefore, the asymptotic behavior of the minimum bit error rate is equivalent to that of a single-user system.

We investigate the performance of the Lempel-Ziv (1978) incremental parsing scheme on nonstationary sources. We show that it achieves the best rate achievable by a finite-state block coder for the nonstationary source. We also show a similar result for a lossy coding scheme given by Yang and Kieffer (see ibid., vol.42, p.239-45, 1996) which uses a Lempel-Ziv scheme to perform lossy coding.

We consider the problem of determining when a given source can be used to approximate the output due to any input to a given channel. We provide achievability and converse results for a general source and channel. For the special case of a full-rank discrete memoryless channel we give a stronger converse result than we can give for a general channel.

The performance and computational complexity of five multi-access receivers are compared. A methodology is then presented for making area and power estimates of these algorithms for both software programmable DSP and dedicated direct mapped architectures. With this methodology and by using experimental data from previous designs, the feasibility of implementation of the multi-access receivers can be determined.

The CDMA channel with randomly and independently chosen spreading sequences accurately models the situation where pseudonoise sequences span many symbol periods. Furthermore, its analysis provides a comparison baseline for CDMA channels with deterministic signature waveforms spanning one symbol period. We analyze the spectral efficiency (total capacity per chip) as a function of the number of users, spreading gain, and signal-to-noise ratio, and we quantify the loss in efficiency relative to an optimally chosen set of signature sequences and relative to multiaccess with no spreading. White Gaussian background noise and equal-power synchronous users are assumed. The following receivers are analyzed: (a) optimal joint processing, (b) single-user matched filtering, (c) decorrelation, and (d) MMSE linear processing.

We consider uncertainty classes of noise distributions defined by a bound on the divergence with respect to a nominal noise distribution. The noise that maximizes the minimum error probability for binary-input channels is found. The effect of the reduction in uncertainty brought about by knowledge of the signal-to-noise ratio is also studied. The particular class of Gaussian nominal distributions provides an analysis tool for near-Gaussian channels. The asymptotic behavior of the least favorable noise distribution and the resulting error probability are studied in a variety of scenarios, namely: asymptotically small divergence with and without power constraint; asymptotically large divergence with and without power constraint; and asymptotically large signal-to-noise ratio.

The fundamental limits of "systematic" communication are analyzed. In systematic transmission, the decoder has access to a noisy version of the uncoded raw data (analog or digital). The coded version of the data is used to reduce the average reproduced distortion D below that provided by the uncoded systematic link and/or increase the rate of information transmission. Unlike the case of arbitrarily reliable error correction (D/spl rarr/0) for symmetric sources/channels, where systematic codes are known to do as well as nonsystematic codes, we demonstrate that the systematic structure may degrade the performance for nonvanishing D. We characterize the achievable average distortion and we find necessary and sufficient conditions under which systematic communication does not incur loss of optimality. The Wyner-Ziv (1976) rate distortion theorem plays a fundamental role in our setting. The general result is applied to several scenarios. For a Gaussian bandlimited source and a Gaussian channel, the invariance of the bandwidth-signal-to-noise ratio (SNR, in decibels) product is established, and the optimality of systematic transmission is demonstrated. Bernoulli sources transmitted over binary-symmetric channels and over certain Gaussian channels are also analyzed. It is shown that if nonnegligible bit-error rate is tolerated, systematic encoding is strictly suboptimal.

A brief chronicle is given of the historical development of the central problems in the theory of fundamental limits of data compression and reliable communication.

A random number generator generates fair coin flips by processing deterministically an arbitrary source of nonideal randomness. An optimal random number generator generates asymptotically fair coin flips from a stationary ergodic source at a rate of bits per source symbol equal to the entropy rate of the source. Since optimal noiseless data compression codes produce incompressible outputs, it is natural to investigate their capabilities as optimal random number generators. We show under general conditions that optimal variable-length source codes asymptotically achieve optimal variable-length random bit generation in a rather strong sense. In particular, we show in what sense the Lempel-Ziv (1978) algorithm can be considered an optimal universal random bit generator from arbitrary stationary ergodic random sources with unknown distributions.

Additive-noise channels with binary inputs and zero-threshold detection are considered. We study worst case noise under the criterion of maximum error probability with constraints on both power and divergence with respect to a given symmetric nominal noise distribution. Particular attention is focused on the cases of a) Gaussian nominal distributions and b) asymptotic increase in worst case error probability when the divergence tolerance tends to zero.

The performance analysis of the minimum-mean-square-error (MMSE) linear multiuser detector is considered in an environment of nonorthogonal signaling and additive white Gaussian noise. In particular, the behavior of the multiple-access interference (MAI) at the output of the MMSE detector is examined under various asymptotic conditions, including: large signal-to-noise ratio; large near-far ratios; and large numbers of users. These results suggest that the MAI-plus-noise contending with the demodulation of a desired user is approximately Gaussian in many cases of interest. For the particular case of two users, it is shown that the maximum divergence between the output MAI-plus-noise and a Gaussian distribution having the same mean and variance is quite small in most cases of interest. It is further proved in this two-user case that the probability of error of the MMSE detector is better than that of the decorrelating linear detector for all values of normalized crosscorrelations not greater than 1/2 /spl radic/(2+/spl radic/3)/spl cong/0.9659.

Let the kth-order empirical distribution of a code be defined as the proportion of k-strings anywhere in the codebook equal to every given k-string. We show that for any fixed k, the kth-order empirical distribution of any good code (i.e., a code approaching capacity with vanishing probability of error) converges in the sense of divergence to the set of input distributions that maximize the input/output mutual information of k channel uses. This statement is proved for discrete memoryless channels as well as a large class of channels with memory. If k grows logarithmically (or faster) with blocklength, the result no longer holds for certain good codes, whereas for other good codes, the result can be shown for k growing as fast as a certain fraction of blocklength.

The (noiseless) fixed-length source coding theorem states that, except for outcomes in a set of vanishing probability, a source can be encoded at its entropy but not more efficiently. It is well known that the asymptotic equipartition property (AEP) is a sufficient condition for a source to be encodable at its entropy. This paper shows that the AEP is necessary for the source coding theorem to hold for nonzero-entropy finite-alphabet sources. Furthermore, we show that a nonzero-entropy finite-alphabet source satisfies the direct coding theorem if and only if it satisfies the strong converse. In addition, we introduce the more general setting of nonserial information sources which need not put out strings of symbols. In this context, which encompasses the conventional serial setting, the AEP is equivalent to the validity of the strong coding theorem. Fundamental limits for data compression of nonserial information sources are shown based on the flat-top property-a new sufficient condition for the AEP.

The Shannon capacity of the single-server queue is analyzed. We show that the capacity is lowest, equal to e/sup -1/ nats per average service time, when the service time distribution is exponential. Further, this capacity cannot be increased by feedback. For general service time distributions, upper bounds for the Shannon capacity are determined. The capacities of the telephone signaling channel and of queues with information-bearing packets are also analyzed.

We study the randomness necessary for the simulation of a random process with given distributions, on terms of the finite-precision resolvability of the process. Finite-precision resolvability is defined as the minimal random-bit rate required by the simulator as a function of the accuracy with which the distributions are replicated. The accuracy is quantified by means of various measures: variational distance, divergence, Orstein (1973), Prohorov (1956) and related measures of distance between the distributions of random process. In the case of Ornstein, Prohorov and other distances of the Kantorovich-Vasershtein type, we show that the finite-precision resolvability is equal to the rate-distortion function with a fidelity criterion derived from the accuracy measure. This connection leads to new results on nonstationary rate-distortion theory. In the case of variational distance, the resolvability of stationary ergodic processes is shown to equal entropy rate regardless of the allowed accuracy. In the case of normalized divergence, explicit expressions for finite-precision resolvability are obtained in many cases of interest; and connections with data compression with minimum probability of block error are shown.

The decorrelating detector and the linear minimum mean-square error (MMSE) detector are known to be effective strategies to counter the presence of multiuser interference in code-division multiple-access channels; in particular, those multiuser detectors provide optimum near-far resistance. When training data sequences are available, the MMSE multiuser detector can be implemented adaptively without knowledge of signature waveforms or received amplitudes. This paper introduces an adaptive multiuser detector which converges (for any initialization) to the MMSE detector without requiring training sequences. This blind multiuser detector requires no more knowledge than does the conventional single-user receiver: the desired user's signature waveform and its timing. The proposed blind multiuser detector is made robust with respect to imprecise knowledge of the received signature waveform of the user of interest.>

In some channels subject to crosstalk or other types of additive interference, the noise is the sum of a dominant Gaussian noise and a relatively weak non Gaussian contaminating noise. Although the capacity of such channels cannot be evaluated in general, the authors analyze the decrease in capacity, or sensitivity of the channel capacity to the weak contaminating noise. The main result is that for a very large class of contaminating noise processes, explicit expressions for the sensitivity of a discrete-time channel capacity do exist. Moreover, in those cases the sensitivity depends on the contaminating process distribution only through its autocorrelation function and so it coincides with the sensitivity with respect to a Gaussian contaminating noise with the same autocorrelation function.

Consider two random variables X and Y, where X is finitely (or countably-infinitely) valued, and where Y is arbitrary. Let /spl epsiv/ denote the minimum probability of error incurred in estimating X from Y. It is shown that /spl epsiv//spl ges//sub 0/spl les//spl alpha//spl les/1//sup sup/(1-/spl alpha/)P(/spl pi/(X|Y)/spl les//spl alpha/) where /spl pi/(X|Y) denotes the posterior probability of X given Y. This bound finds information-theoretic applications in the proof of converse channel coding theorems. It generalizes and strengthens previous lower bounds due to Shannon, and to Verdu and Han (1994).

The single-user separation theorem of joint source-channel coding has been proved previously for wide classes of sources and channels. We find an information-stable source/channel pair which does not satisfy the separation theorem. New necessary and sufficient conditions for the transmissibility of a source through a channel are found, and we characterize the class of channels for which the separation theorem holds regardless of the source statistics.>

Suppose we are given a random source and want to use it as a random number generator; at what rate can we generate fair bits from it? We address this question in an information-theoretic setting by allowing for some arbitrarily small but nonzero deviation from "ideal" random bits. We prove our results with three different measures of approximation between the ideal and the obtained probability distributions: the variational distance, the d-bar distance, and the normalized divergence. Two different contexts are studied: fixed-length and variable-length random number generation. The fixed-length results of this paper provide an operational characterization of the inf-entropy rate of a source, defined in Han and Verdu (see ibid., vol.39, no.3, p.752-772, 1993) and the variable-length results characterize the liminf of the entropy rate, thereby establishing a pleasing duality with the fundamental limits of source coding. A feature of our results is that we do not restrict ourselves to ergodic or to stationary sources.>

The Fano inequality gives a lower bound on the mutual information between two random variables that take values on an M-element set, provided at least one of the random variables is equiprobable. The authors show several simple lower bounds on mutual information which do not assume such a restriction. In particular, this ran be accomplished by replacing log M with the infinite-order Renyi entropy in the Fano inequality. Applications to hypothesis testing are exhibited along with bounds on mutual information in terms of the a priori and a posteriori error probabilities.>

Studies the minimum random bit rate required to simulate a random system (channel), where the simulator operates with a given external input. As measures of simulation accuracy the authors use both the variational distance and the d~ distance between joint input-output distributions. They find the asymptotic number of random bits per input sample required for accurate simulation, as a function of the distribution of the input process. These results hold for arbitrary channels and input processes, including nonstationary and nonergodic processes and do not hinge on a specific simulation scheme. A by-product of the analysis is a general formula for the minimal achievable source coding rate with side information.>

A formula for the capacity of arbitrary single-user channels without feedback (not necessarily information stable, stationary, etc.) is proved. Capacity is shown to equal the supremum, over all input processes, of the input-output inf-information rate defined as the liminf in probability of the normalized information density. The key to this result is a new converse approach based on a simple new lower bound on the error probability of m-ary hypothesis tests among equiprobable hypotheses. A necessary and sufficient condition for the validity of the strong converse is given, as well as general expressions for /spl epsiv/-capacity.>

The capacity region of a two-user Gaussian multiaccess channel with intersymbol interference (ISI) in which the inputs pass through respective linear systems and are superimposed before being corrupted by an additive Gaussian noise process is discussed. A geometrical method for obtaining the optimal input power spectral densities and the capacity region is presented. This method can be viewed as a nontrivial generalization of the single-user water-filling argument. It is shown that, as in the traditional memoryless multiaccess channel, frequency-division multiaccess (FDMA) with optimally selected frequency bands for each user achieves the total capacity of the multiuser Gaussian multiaccess channel with ISI. However, the capacity region of the two-user channel with memory is, in general, not a pentagon unless the channel transfer functions for both users are identical.>

The restriction to Gaussian inputs in the limiting expression for the capacity regions of memoryless Gaussian interference and multiple-access channels is shown to fall short of achieving capacity even if the inputs are allowed to be dependent and nonstationary. In addition, the equality between the limiting and the single-letter characterizations of memoryless multiple-access channel capacity is established directly, without recourse to independent coding theorems.>

Given a channel and an input process with output statistics that approximate the original output statistics with arbitrary accuracy, the randomness of the input processes is studied. The notion of resolvability of a channel, defined as the number of random bits required per channel use in order to generate an input that achieves arbitrarily accurate approximation of the output statistics for any given input process, is introduced. A general formula for resolvability that holds regardless of the channel memory structure is obtained. It is shown that for most channels, resolvability is equal to the Shannon capacity. By-products of the analysis are a general formula for the minimum achievable source coding rate of any finite-alphabet source and a strong converse of the identification coding theorem, which holds for any channel that satisfies the strong converse of the channel coding theorem.>

Blind equalization up to a constant gain of linear time-invariant channels is studied. Dropping the requirement of gain identification allows equalizer anchoring. This results in the elimination of a degree of freedom that causes ill-convergence of conventional blind equalizers, and affords the possibility of using simple update rules based on the stochastic approximation of output energy. Unlike conventional blind equalizers, truncations of the nonrecursive infinite-dimensional realizations of those equalizers inherit the convergence properties of their infinitely parametrized counterparts. A globally convergent blind recursive equalizer for channels without all-pass sections is obtained based on the exact equalization of the minimum-phase part of the channel and the identification of its nonminimum-phase zeros.>

The identification coding theorems of R. Ahlswede and G. Dueck (1981) have shown that for any nonzero probabilities of missed and false identification, it is possible to transmit exp(exp(nR)) messages with n uses of a noisy channel, where R is as close as desired to the Shannon capacity of the channel. That capability is achieved by the identification codes explicitly constructed with a three-layer concatenated constant-weight code used in conjunction with a channel transmission code of rate R.>

The degradation due to complete asynchronism (at the codeword and symbol levels) in the total capacity, maximum rate-sum, of white Gaussian multiple-access channels is investigated. It is shown that asynchronism reduces the total capacity of a K-user channel by at most a factor of K. Moreover, this bound is achieved, in asymptotically high signal-to-noise ratios, by the TDMA signaling strategy. When the signaling strategies are optimally designed to maximize the asynchronous total capacity under bandwidth constraints, the authors find that in a two-user channel: (1) for a certain set of signal-to-noise ratios there is no degradation due to asynchronism, (2) for any bandwidth and signal-to-noise ratios the asynchronous total capacity is at least 88% of the synchronous total capacity, and (3) asynchronism has a vanishing small effect on total capacity for both low and high signal-to-noise ratios.>

The identification capacity is the maximal iterated logarithm of the number of messages divided by the blocklength that can be reliably transmitted when the receiver is only interested in deciding whether a specific message was transmitted or not. The identification coding theorem of R. Ahlswede and G. Dueck (1989) for single-user discrete memoryless channels states that the identification capacity is equal to the Shannon capacity. A novel method to prove the converse to the identification coding theorem is shown to achieve the strong version of the result. Identification plus transmission (IT) coding, a variant of the original problem of identification via channels, is proposed in the context of a common problem in point-to-multipoint communication, where a central station wishes to transmit information reliably to one of N terminals, whose identity is not predetermined. The authors show that as long as log log N is smaller than the number of bits to be transmitted, IT codes allow information transmission at channel capacity.>

Additive noise channels with binary-valued inputs and real-valued outputs are considered. The maximum error probability and the minimum channel capacity achieved by any power-constrained noise distribution are obtained. A general framework which applies to a variety of performance measures shows that the least-favorable noise distribution is, in general, a mixture of two lattice probability mass functions. The framework holds for m-ary input constellations on finite-dimensional lattices.>

A model noncoherent, optical, asynchronous, CDMA system is described. The error rate for a single-user matched-filter receiver that is valid for arbitrary photomultipliers and signature sequence sets, adheres to the semiclassical model of light, and does not depend on approximations for large user groups, strong received optical fields, or chip synchronism is analyzed. The exact minimum probability of error and optimal threshold are compared to those obtained with user-synchronism and multiple-access interference (MAI) distribution approximations. For the special case of unity-gain photodetectors and prime sequences, it is shown that the approximation of chip synchronism yields a weak upper bound on the exact error rate. It is demonstrated that the approximations of perfect optical-to-electrical conversion and Gaussian-distributed MAI yield a poor approximation to the minimum error rate and an underestimate of the optimal threshold. Arbitrarily tight bounds are developed on the error rate for unequal energies per bit. In the case when the signal energies coincide, these bounding expressions are considerably easier to compute than the exact error rate.>

Continuous-time additive white Gaussian noise channels with strictly time-limited and root-mean-square (RMS)-bandlimited inputs are studied. The capacity of the single-user and two-user RMS-bandlimited channels are found in easy-to-compute parametric forms and are compared to the classical formulas for the capacity of strictly bandlimited channels. In addition, channels are considered where the inputs are further constrained to be pulse-amplitude-modulated waveforms. The capacity of the single-user RMS-bandlimited PAM channel is shown to coincide with Shannon's capacity formula for the strictly bandlimited channel. This shows that the laxer bandwidth constraints precisely offsets the PAM structural constraint and illustrates a tradeoff between the time-domain and frequency-domain constraints. In the synchronous two-user channel, the pair of pulses that achieves the boundary of the capacity region is derived, and it is shown that the shapes of the optimal pulses depend not only on the bandwidth but also on the respective signal-to-noise ratios.>

Consideration is given to an asynchronous code-division multiple-access environment in which receiver has knowledge of the signature waveforms of all the users. Under the assumption of white Gaussian background noise, the authors compare detectors by their worst case bit error rate in a near-far environment with low background noise, where the received energies of the users are unknown to the receiver and are not necessarily similar. Conventional single-user detection in a multiuser channel is not near-far resistant, and the substantially higher performance of the optimum multiuser detector requires exponential complexity in the number of users. The authors explore suboptimal demodulation schemes which exhibit a low order of complexity while not exhibiting the impairment of the conventional single-user detector. It is shown that there exists a linear detector whose bit-error-rate is independent of the energy of the interfering users. It is also shown that the near-far resistance of optimum multiuser detection can be achieved by a linear detector. The optimum linear detector for worst-case energies is found, along with existence conditions, which are always satisfied in the models of practical interest.>

Memoryless communication channels with arbitrary alphabets where each input symbol is assigned a cost are considered. The maximum number of bits that can be transmitted reliably through the channel per unit cost is studied. It is shown that, if the input alphabet contains a zero-cost symbol, then the capacity per unit cost admits a simple expression as the maximum normalized divergence between two conditional output distributions. The direct part of this coding theorem admits a constructive proof via Stein's lemma on the asymptotic error probability of binary hypothesis tests. Single-user, multiple-access, and interference channels are studied.>

An optical, direct-detection differential phase-shift keying (DPSK) receiver whose error probability is quantum-limited as the transmitting laser linewidth vanishes is analyzed. The receiver design is based on a binary equiprobable hypothesis test with doubly stochastic point process observations, the conditional random rates of which depend on the transmitting laser phase noise, which is modeled as a Brownian motion. The receiver structure consists of a simple delay-and-sum optical preprocessor followed by a photoelectric converter and an integrate-and-dump circuit. Upper and lower bounds on the receiver bit error rate are derived by developing bounds on the conditional rates of the point process, and it is shown that the error probability bounds converge to the true value as the transmitting laser linewidth decreases. Bounds on the power penalty are computed for parameters corresponding to existing semiconductor injection lasers, and are seen to be less than the limiting power penalty for the balanced DPSK receiver.>

Under the assumptions of symbol-synchronous transmissions and white Gaussian noise, the authors analyze the detection mechanism at the receiver, comparing different detectors by their bit error rates in the low-background-noise region and by their worst-case behavior in a near-far environment where the received energies of the users are not necessarily similar. Optimum multiuser detection achieves important performance gains over conventional single-user detection at the expense of computational complexity that grows exponentially with the number of users. It is shown that in the synchronous case the performance achieved by linear multiuser detectors is similar to that of optimum multiuser detection. Attention is focused on detectors whose linear memoryless transformation is a generalized inverse of the matrix of signature waveform crosscorrelations, and on the optimum linear detector. It is shown that the generalized inverse detectors exhibit the same degree of near-far resistance as the optimum multiuser detectors. The optimum linear detector is obtained.< >

The capacity region of frame-synchronous and frame-asynchronous, discrete, two-user multiple-access channels with finite memory is obtained. Frame synchronism refers to the ability of the transmitters to send their code words in unison. The absence of frame synchronism in memoryless multiple-access channels is known to result in the removal of the convex hull operation from the expression of the capacity region. It is shown that when the channel has memory, frame asynchronism rules out nonstationary inputs to achieve any point in the capacity region, thereby allowing only coding strategies that involve cooperation in the frequency domain but not in the time domain. This restriction drastically reduces the capacity region of some multiple-access channels with memory, and in particular the total capacity of the channel, which is invariant to frame asynchronism for memoryless channels.>

An equivalent discrete-time Gaussian channel parametrized by the signal cross-correlations is derived to obtain an equivalent channel model with discrete-time outputs. The main feature introduced by the lack of symbol synchronism is that the channel has memory. This is due to the overlap of each symbol transmitted by a user with two consecutive symbols transmitted by the other user. It is shown that if the transmitters are assigned the same waveform, symbol asynchronism has no effect on the two-user capacity region of the white Gaussian channel which is equal to the Cover-Syner pentagon, whereas if the assigned waveforms are different (e.g., code division multiple access), the symbol-asynchronous capacity region is no longer a pentagon. An alternative representation of the capacity region which results in a particularly compact characterization of the fundamental limits of the multiple-access channel in the region of signal-to-noise ratios is also considered.>

Optimum decentralized demodulation for asynchronous Gaussian multiaccess channels is considered. It is assumed that the receiver is the destination of the information transmitted by only one active user, and single-user detectors that take into account the existence of the other active users in the channel are obtained. The problem considered is one of signal detection in additive colored nonGaussian noise, and attention is focused on one-shot structures where detection of each symbol is based only on the received process during its corresponding interval. Particular emphasis is placed on asymptotically optimum detectors for weak interferers, for CDMA (code-division multiple-access) signature waveforms with long spreading codes, and for low background Gaussian noise level.>

Maximum likelihood sequence detection of digital signaling subject to intersymbol interference and additive white Gaussian noise is considered. A new approach to the error probability analysis results in an upper bound which is tighter than the Forney bound. In addition, in the case of infinite-length intersymbol interference a locally convergent bound is shown to hold under fairly general assumptions on the signal autocorrelation.

Mosely and Humblet have obtained an efficient Contention Resolution Algorithm for transmission scheduling in a multi-user collision channel with ternary feedback (idle, success, collision). In this letter, a recursion for the expected value of the algorithm cycle delay is shown to reduce the computation of the efficiency and optimum partition functions to a simple optimization problem.

The degradation in bit error rate due to the presence of multiple-access interference in a white Gaussian channel can be measured by the multiuser asymptotic efficiency, defined as the ratio between the SNR required to achieve the same uncoded bit error rate in the absence of interfering users and the actual SNR. In this paper, the asymptotic efficiency of the optimum multiuser demodulator (a bank of matched filters followed by a Viterbi algorithm) is investigated and compared to that of the conventional single-user matched filter receiver. The computation of the optimum asymptotic efficiency of any given user is equivalent to the minimization of the Euclidean distance between any pair of multiuser signals which differ in at least one of the symbols of that user. It is shown that the optimum multiuser efficiency of asynchronous systems is nonzero with probability 1, and therefore the optimum demodulator does not become multiple-access limited in contrast to the single-user receiver. A class of signal constellations with moderate cross-correlation requirements is shown to achieve unit optimum multiuser efficiencies and, hence, to be equivalent to orthogonal signal sets from the viewpoint of performance of the optimum multiuser detector.

Consider a Gaussian multiple-access channel shared byKusers who transmit asynchronously independent data streams by modulating a set of assigned signal waveforms. The uncoded probability of error achievable by optimum multiuser detectors is investigated. It is shown that theK-user maximum-likelihood sequence detector consists of a bank of single-user matched filters followed by a Viterbi algorithm whose complexity per binary decision isO(2^{K}). The upper bound analysis of this detector follows an approach based on the decomposition of error sequences. The issues of convergence and tightness of the bounds are examined, and it is shown that the minimum multiuser error probability is equivalent in the Iow-noise region to that of a single-user system with reduced power. These results show that the proposed multiuser detectors afford important performance gains over conventional single-user systems, in which the signal constellation carries the entire burden of complexity required to achieve a given performance level.

It is shown that the asymptotic probability of error of a binary equiprobable hypothesis test for observed Poisson point processes with rates\lambda_{i}(t)=b_{i}(t)+(\rho_{i}(t)+z)^{2}, i=0,1, z \rightarrow \infty, is equal to the error probability of optimum deterministic-signal detection in additive white Gaussian noise when the signals coincide with the square roots of the point-process rates. The implication of this result in the error rate analysis of optical digital communication systems is discussed.

The derivation and analysis of optimum multiuser detectors for additive-rate and additive-light Poisson multiple-access channels are studied. The observed point process models the output of an ideal photodetector illuminated by several synchronous or asynchronous users who modulate coherent light of the same frequency. Dynamic programming-based decision rules for the asynchronous multiple-access channel exhibit the same computational complexity as their synchronous counterparts and are shown to be optimum under the criteria of minimum error probability and maximum likelihood sequence detection. Upper and lower bounds on the minimum uncoded bit error rate achievable with arbitrary signal constellations are obtained in terms of the error probability of binary hypothesis testing problems. A particular case of these results, namely, the single-user finite-length intersymbol interference problem, solves the error rate analysis of optimum direct-detection systems for dispersive optical fibers.

The minimax approach to the design of systems that are robust with respect to modeling uncertainties is studied using a game theoretic formulation in which the performance functional and the sets of modeling uncertainties and admissible design policies are arbitrary. The existence and characterization of minimax robust solutions that form saddle points are discussed through various methods that take into account several common features of the games encountered in applications. In particular, it is shown that if the performance functional and the uncertainty set are convex then a certain type of regularity condition on the functional is sufficient to ensure that the optimal strategy for a least favorable element of the uncertainty set is minimax robust. The efficacy of the methods proposed for a general game is tested in the problems of matched filtering, Wiener filtering, quadratic detection, and output energy filtering, in which uncertainties in their respective signal and noise models are assumed to exist. These problems are analyzed in a common Hilbert space framework and they serve to point out the advantages and limitations of the proposed techniques.

The problem of designing finite-length discrete-time matched filters is considered for situations in which exact knowledge of the input signal and/or noise characteristics is not available. Such situations arise in many applications due to channel distortion, incoherencies, nonlinear effects, and other modeling uncertainties. In such cases it is often of interest to design a minimax robust matched filter, i.e., a nonadaptive filter with an optimum level of worst-case performance for the expected uncertainty class. This problem is investigated here for three types of uncertainty models for the input signal, namely, the mean-absolute, mean-square, and maximum-absolute distortion classes, and for a wide generality of norm-deviation models for the noise covariance matrix. Some numerical examples illustrate the robustness properties of the proposed designs.

The optimum signal selection problem under a power constraint for minimax robust discrete-time finite-length matched filtering is studied. The classical solution, which is to choose the signal as a minimum-eigenvalue eigenvector of the noise covariance matrix, is generalized to cases in which the transmitted signal is subject to channel distortion modeled by mean-square, maximum-absolute, and mean-absolute distortion uncertainty classes.

A previously published derivation of an optimal quadratic receiver with respect to a generalized signal-to-noise ratio is corrected, and a different performance measure is proposed for which a general analytical solution exists.