Universal compression can learn the source and adapt to it either in a batch mode (forward adaptation), or in a sequential mode (backward adaptation). We recast the sequential mode as a multi-armed bandit problem, a fundamental model in reinforcement-learning, and study the trade-off between exploration and exploitation in the lossy compression case. We show that a previously proposed “natural type selection” scheme can be cast as a reconstruction-directed MAB algorithm, for sequential lossy compression, and explain its limitations in terms of robustness and short-block performance. We then derive and analyze robust cost-directed MAB algorithms, which work at any block length.

Analog codes add redundancy by expanding the dimension using real/complex-valued operations. Frame theory provides a mathematical basis for constructing such codes, with diverse applications in non-orthogonal code-division multiple access (NOMA-CDMA), distributed computation, multiple description source coding, space-time coding (STC), and more. The channel model corresponding to these applications is a combination of noise and erasures. Recent analyses showed a useful connection between spectral random-matrix theory and large equiangular tight frames (ETFs) under random uniform erasures. In this work we generalize this model to a channel where the erasures come in blocks. This particularly fits NOMA-CDMA with multiple transmit antennas for each user and STC with known spatial grouping. We present a method to adjust ETF codes to suit block erasures, and find minimum intra-block-correlation frames which outperform ETFs in this setting.

Iterative constrained optimization often requires convexity conditions about the argument set in order to converge to the global optimum. One such instant is the parametric version of the Blahut algorithm for rate-distortion function computation. However, there are many interesting cases for which the parametric set is not convex, e.g a discrete reproduction alphabet at unknown (parametric) locations for a continuous source. In this paper we show examples of non-convex families for which the parametric Blahut algorithm does not converge to the global optimum, and suggest a combined parametric Blahut and random annealing (A) method to overcome this problem.

It is common to assess the "memory strength" of a stationary process by looking at how fast the normalized log– determinant of its covariance submatrices (i.e., entropy rate) decreases. In this work, we propose an alternative characterization in terms of the normalized trace–inverse of the covariance submatrices. We show that this sequence is monotonically non-decreasing and is constant if and only if the process is white. Furthermore, while the entropy rate is associated with one-sided prediction errors (present from past), the new measure is associated with two-sided prediction errors (present from past and future). Minimizing this measure is then used as an alternative to Burg’s maximum-entropy principle for spectral estimation.

It is common to assess the “memory strength” of a stationary process by looking at how fast the normalized log–determinant of its covariance submatrices (i.e., entropy rate) decreases. In this work, we propose an alternative characterization in terms of the normalized trace–inverse of the covariance submatrices. We show that this sequence is monotonically non-decreasing and is constant if and only if the process is white. Furthermore, while the entropy rate is associated with one-sided prediction errors (present from past), the new measure is associated with two-sided prediction errors (present from past and future). Minimizing this measure is then used as an alternative to Burg’s maximum-entropy principle for spectral estimation. We also propose a counterpart for non-stationary processes, by looking at the average trace–inverse of subsets.

It is well known that independent (separate) encoding of$K$correlated sources may incur some rate loss compared to joint encoding, even if the decoding is done jointly. This loss is particularly evident in the multiple descriptions problem, where it is the same source that is encoded in each description. We observe that under mild conditions about the source and distortion measure, the sum-rate of$K$separately encoded individually good descriptions tends to the rate-distortion function of the joint decoder in the limit of vanishing small coding rates of the descriptions. Moreover, we then propose to successively encode the source into$K$independent descriptions in each round in order to achieve a final distortion$D$after$M$rounds. We provide two examples – a Gaussian source with mean-squared error and an exponential source with one-sided error – for which the excess rate vanishes in the limit as the number of rounds$M$goes to infinity, for any fixed$D$and$K$. This result has an interesting interpretation for a multi-round variant of the multiple descriptions problem, where after each round the encoder gets a (block) feedback regarding which of the descriptions arrived: In the limit as the number of rounds$M$goes to infinity (i.e., many incremental rounds), the total rate of received descriptions approaches the rate-distortion function. We provide theoretical and experimental evidence showing that this phenomenon is in fact more general than in the two examples above.

This paper proposes an effective and asymptotically optimal framework for stochastic, adaptive codebook regeneration for sequential (“on the fly”) lossy coding of continuous alphabet sources. Earlier work has shown that the rate-distortion bound can be asymptotically achieved for discrete alphabet sources, by a “natural type selection” (NTS) algorithm. At each iteration$n$, a maximum-likelihood framework is used to estimate the reproduction distribution most likely to generate the empirical types of a sequence of$K$length-$l$codewords that respectively “d-match” (i.e., are within distortion$d$from) a sequence of$K$length-$\ell$source words. The reproduction distribution estimated at iteration$n$is used to regenerate the codebook for iteration$n+1$. The sequence of reproduction distributions was shown to converge, asymptotically in$K, n$, and$\ell$, to the optimal distribution that achieves the rate-distortion bound for discrete alphabet sources. This work generalizes the NTS framework to handle sources over more general (e.g., continuous) alphabet spaces, which often preclude a natural interpretation of the concept of “type”. We show, for continuous alphabet sources and fixed block length$\ell$, that as$K\rightarrow \infty$and$n \rightarrow \infty$, the sequence of estimated reproduction distributions converges, in the weak convergence sense, to a distribution that achieves the rate-distortion bound, albeit for an auxiliary distortion measure introduced as subterfuge to effectively impose a maximum distortion constraint over$K$blocks. Leveraging this result, we establish that the sequence of reproduction distributions converges, asymptotically in$\ell$, to the optimal codebook reproduction distribution$Q^{\ast}$that achieves the rate-distortion bound, with respect to the original distortion measure.

Motivated by multiple-description source coding with feedback, it was recently proposed to encode the one-sided exponential source$X$via$K$parallel channels,$Y_{1}, \ldots, Y_{K}$, such that the error signals$X-Y_{i}, i=1, \ldots, K$, are one-sided exponential and mutually independent given$X$. Moreover, it was shown that the optimal estimator$\hat{Y}$of the source$X$with respect to the one-sided error criterion, is simply given by the maximum of the outputs, i.e.,$\hat{Y}=\max\{Y_{1},\ldots, Y_{K}\}$. In this paper, we show that the distribution of the resulting estimation error$X-\hat{Y}$, is equivalent to that of the optimum noise in the backward test-channel of the one-sided exponential source, i.e., it is one-sided exponentially distributed and statistically independent of the joint output$Y_{1}, \ldots, Y_{K}$.

Diversity "multiple description" (MD) source coding promises graceful degradation in the presence of a priori unknown number of erased packets in the channel. A simple coding scheme for the case of two packets consists of oversampling the source by a factor of two and delta-sigma quantization. This approach was applied successfully to JPEG-based image coding over a lossy packet network, where the interpolation and splitting into two descriptions are done in the discrete cosine transform (DCT) domain. Moreover, unlike the classical source-channel separation approach - which is designed for a predetermined number of erasures (say, K out of N ), hence its distortion does not improve when the channel behaves better than expected - an MD coding scheme aims to achieve a better reconstruction quality when more or all the N descriptions are received at the decoder side. The extension to a larger number of descriptions, however, suffers from noise amplification whenever the received descriptions form a non-uniform sampling pattern. In this work, we examine inter- and intra-block interpolation methods, and show how noise amplification can be reduced by redesigning the interpolation filter at the encoder. Specifically, for a given total coding rate, we demonstrate that an "irregular" interpolation filter is robust to the pattern of received packets over all ( K out of N ) patterns, with some degradation relative to low-pass (LP) interpolation in the case where all N packets arrived. We provide experimental results comparing LP and irregular interpolation filters, and examine the effect of noise shaping on the trade-off between the central distortion (receiving all packets) and side distortion (receiving K packets).

In this paper, we consider the rate-distortion problem where a source X is encoded into k parallel descriptions Y1, . . ., Yk, such that the error signals X - Yi, i = 1, . . ., k, are mutually independent given X. We show that if X is one-sided exponentially distributed, the optimal decoder (estimator) under the one-sided absolute error criterion, is simply given by the maximum of the outputs Y1, . . ., Yk. We provide a closed-form expression for the rate and distortion for any k number of parallel descriptions and for any coding rate. We furthermore show that as the coding rate per description becomes asymptotically small, encoding into k parallel descriptions and using the maximum output as the source estimate, is rate-distortion optimal.

Construction C* was recently introduced as a generalization of the multilevel Construction C (or Forney's code-formula), such that the coded levels may be dependent. Both constructions do not produce a lattice in general, hence the central idea of this paper is to present a 3-level lattice Construction C* scheme that admits an efficient nearest-neighborhood decoding. In order to achieve this objective, we choose coupled codes for levels 1 and 3, and set the second level code C2as an independent linear binary self-dual code, which is known to have a rich mathematical structure among families of linear codes. Our main result states a necessary and sufficient condition for this construction to generate a lattice. We then present examples of efficient lattices and also non-lattice constellations with good packing properties.

For a discrete memoryless channel with finite input and output alphabets, we prove convergence of an iterative computation of the optimal correct-decoding exponent as a function of communication rate, for a fixed rate and for a fixed slope.

This paper proposes a generalized stochastic mechanism for codebook generation in lossy coding settings for sources with memory. Earlier work has shown that the rate-distortion bound can be asymptotically achieved for discrete memoryless sources by a “natural type selection” (NTS) algorithm. In iteration n, the distribution that is most likely to produce the types of a sequence of K codewords of finite length I that “dmatch” a respective sequence of K source words of length I, (i.e., which satisfy the distortion constraint), is used to regenerate the codebook for iteration n+1. The resulting sequence of codebook generating distributions converges to the optimal distribution Q* that achieves the rate-distortion bound for the memoryless source, asymptotically in I, K, and n. This work generalizes the NTS algorithm to account for sources with memory. The algorithm encodes mI-length source words consisting of I vectors (or super-symbols) of length m. We show that for finite m and I, the sequence of codebook reproduction distributions Q0,m,l, Q1,m,l,... (each computed after observing a sequence of K d-match events) converges to the optimal achievable distribution Q*m,l(within a set of achievable distributions determined by m and I), asymptotically in K and n. It is further shown that Q*m,lconverges to the optimal reproduction distribution Q* that achieves the rate-distortion bound for sources with memory, asymptotically in m and I.

Diversity "multiple description" (MD) source coding promises graceful degradation in the presence of an unknown number of erasures in the channel. A simple scheme for the case of two descriptions consists of oversampling the source by a factor of two and delta-sigma quantization. This approach was applied successfully to JPEG-based image coding over a lossy packet network, where the interpolation and splitting into two descriptions is done in the discrete cosine transform (DCT) domain. The extension to a larger number of descriptions, however, suffers from noise amplification whenever the received descriptions form a nonuniform sampling pattern. In this work, we examine inter and intra-block interpolation methods and show how noise amplification can be reduced by optimizing the interpolation filter. Specifically, for a given total coding rate, we demonstrate that an irregular interpolation filter minimizes the average distortion over all (K out of N) patterns of received packets, ("side receivers"). We provide experimental results comparing low-pass (LP) and irregular interpolation filters for the side receivers and the all-N central receiver. We further examine the effect of noise shaping on the trade-off between the central and side distortions.

The matrix version of the entropy-power inequality for real or complex coefficients and variables is proved using a transportation argument that easily settles the equality case. An application to blind source extraction is given.

Lattice and special nonlattice multilevel constellations constructed from binary codes, such as Constructions A, C, and D, have relevant applications in Mathematics (sphere packing) and in Communication (multi-stage decoding and efficient vector quantization). In this work, we explore some properties of Construction C, in particular its geometric uniformity. We then propose a new multilevel construction, inspired by bit interleaved coded modulation (BICM), that we call Construction$C^\star $. We investigate the geometric uniformity, latticeness, and minimum distance properties of Construction$C^\star $, and discuss its superior packing efficiency when compared to Construction C.

The Welch (lower) Bound on the mean square cross correlation between n unit-norm vectors f1, ..., fnin the m dimensional space (Rmor Cm), for n ≥ m, is a useful tool in the analysis and design of spread spectrum communications, compressed sensing and analog coding. Letting F = [f1|...|fn] denote the m-by-n frame matrix, the Welch bound can be viewed as a lower bound on the second moment of F, namely on the trace of the squared Gram matrix (F' F)2. We consider an erasure setting, in which a reduced frame, composed of a random subset of Bernoulli selected vectors, is of interest. We present the erasure Welch bound and generalize it to the d-th order moment of the reduced frame, for d = 2, 3, 4. We provide simple, explicit formulae for the generalized bound, which interestingly is equal to the d-th moment of Wachter's classical MANOVA distribution plus a vanishing term (as n goes to infinity with m/n held constant). The bound holds with equality if (and for d = 4 only if) F is an Equiangular Tight Frame (ETF). Hence, our results offer a novel perspective on the superiority of ETFs over other frames, and provide explicit characterization for their subset moments.

We propose an on-line algorithm for adapting the input of an unknown or slowly varying channel, while keeping reliable communication at some fixed rate R during the adaptation process. The purpose of the algorithm is to push the generating distribution of an i.i.d. random code toward the input that achieves the channel capacity C. The algorithm uses one bit feedback per each transmission block, that acknowledges whether the decoded codeword crossed some pre-determined threshold T > R, with respect to some “fitness” metric. In the rare event of threshold crossing, the encoder and decoder update the input distribution according to the type of the current codeword, while the decoder updates the fitness metric. We show that for a large block length, this algorithm simulates computation of the channel correct-decoding exponent, and it leads to the capacity-achieving input if we set T = C.

Ozarow's test channel for the quadratic Gaussian (QG) multiple description (MD) problem consists of two correlated AWGN channels. It is known that simply replacing the AWGN channels by quantizers with equivalent statistical properties as the channels, will generally not lead to a rate-distortion optimal realization of the MD rate-distortion function. We have previously proposed a symmetric two-channel model for the QG MD problem for the case, where the two noise terms have equal variances. We show in this paper, that by replacing the AWGN channels of this model by quantizers that are statistical equivalent to the channels, will under high-resolution assumption be rate-distortion optimal. We furthermore extend this symmetric two-channel model to the asymmetric case, and provide a simple suboptimal implementation of the channel based on scalar quantizers. Simulations are provided to show the performance of the proposed implementation.

We propose a source/channel duality in the exponential regime, where success/failure in source coding parallels error/correctness in channel coding, and a distortion constraint becomes a log-likelihood ratio (LLR) threshold. We establish this duality by first deriving exact exponents for lossy coding of a memoryless source P, at distortion D, for a general i.i.d. codebook distribution Q, for both encoding success (RR(P, Q, D)). We then turn to maximum likelihood (ML) decoding over a memoryless channel P with an i.i.d. input Q, and show that if we substitute P = QP, Q = Q, and D = 0 under the LLR distortion measure, then the exact exponents for decoding-error (RI(Q, P)) follow as special cases of the exponents for source encoding success/failure, respectively. Moreover, by letting the threshold D take general values, the exact random-coding exponents for erasure (D > 0) and list decoding (D1.

Construction C (also known as Forney's multi-level code formula) forms a Euclidean code for the additive white Gaussian noise (AWGN) channel from L binary code components. If the component codes are linear, then the minimum distance is the same for all the points, although the kissing number may vary. In fact, while in the single level (L = 1) case it reduces to lattice Construction A, a multi-level Construction C is in general not a lattice. We show that the two-level (L = 2) case is special: a two-level Construction C satisfies Forney's definition for a geometrically uniform constellation. Specifically, every point sees the same configuration of neighbors, up to a reflection of the coordinates in which the lower level code is equal to 1. In contrast, for three levels and up (L ≥ 3), we construct examples where the distance spectrum varies between the points, hence the constellation is not geometrically uniform.

Analog coding decouples the tasks of protecting against erasures and noise. For erasure correction, it creates an “analog redundancy” by means of band-limited discrete Fourier transform (DFT) interpolation, or more generally, by an over-complete expansion based on a frame. We examine the analog coding paradigm for the dual setup of a source with “erasure” side-information (SI) at the encoder. The excess rate of analog coding above the rate-distortion function (RDF) is associated with the energy of the inverse of submatrices of the frame, where each submatrix corresponds to a possible erasure pattern. We give a partial theoretical as well as numerical evidence that a variety of structured frames, in particular DFT frames with difference-set spectrum and more general equiangular tight frames (ETFs), with a common MANOVA limiting spectrum, minimize the excess rate over all possible frames. However, they do not achieve the RDF even in the limit as the dimension goes to infinity.

In 1973, Gallager proved that the random-coding bound is exponentially tight for the random code ensemble at all rates, even below expurgation. This result explained that the random-coding exponent does not achieve the expurgation exponent due to the properties of the random ensemble, irrespective of the utilized bounding technique. It has been conjectured that this same behavior holds true for a random ensemble of linear codes. This conjecture is proved in this paper. In addition, it is shown that this property extends to Poltyrev's random-coding exponent for a random ensemble of lattices.

It is well known that Shannon's rate-distortion function (RDF) in the colored quadratic Gaussian (QG) case can be parametrized via a single Lagrangian variable (the water level in the reverse water filling solution). In this paper, we show that the symmetric colored QG multiple description (MD) RDF in the case of two descriptions can be parametrized in the spectral domain via two Lagrangian variables, which control the tradeoff between the side distortion, the central distortion, and the coding rate. This spectral-domain analysis is complemented by a time-domain scheme-design approach: we show that the symmetric colored QG MD RDF can be achieved by combining ideas of delta-sigma modulation and differential pulse-code modulation. In particular, two source prediction loops, one for each description, are embedded within a common noise-shaping loop, whose parameters are explicitly found from the spectral-domain characterization.

The Arimoto algorithm computes the Gallager function maxQE0(ρ, Q) for a given channel P (y | x) and parameter ρ, by means of alternating maximization. Along the way, it generates a sequence of input distributions Q1(x), Q2(x), ..., that converges to the maximizing input Q*(x). We propose a stochastic interpretation for the Arimoto algorithm. We show that for a random (i.i.d.) codebook with a distribution Qk(x), the next distribution Qk+1(x) in the Arimoto algorithm is equal to the type (Q') of the feasible transmitted codeword that maximizes the conditional Gallager exponent (conditioned on a specific transmitted codeword type Q'). This interpretation is a first step toward finding a stochastic mechanism for on-line channel input adaptation.

Shannon's capacity and rate-distortion function, combined with the separation principle, provide tight bounds for the minimum possible distortion in joint source-channel coding. These bounds, however, are usually achievable only in the limit of a large block length. In their 1973 paper, Ziv and Zakai introduced a family of alternative capacity and rate-distortion functions, based on functionals satisfying the data-processing inequality, which potentially give tighter bounds for systems with a small block length. There is a considerable freedom as to how to choose those functionals, and the ways of finding the best possible functionals yielding the best bounds for a given source-channel combination are not specified. We examine recently conjectured high SNR asymptotic expressions for the Ziv-Zakai bounds, based on the Rényi-divergence functional. We derive nonasymptotic bounds on the Ziv-Zakai-Rényi rate-distortion function and capacity for a broad class of sources and additive noise channels, which hold for arbitrary SNR and prove the conjectured asymptotic expressions in the limit of a small distortion/high SNR. The results lead to new bounds on the best achievable distortion in finite dimensional joint source-channel coding. Examples are presented where the new bounds achieve significant improvement upon Shannon's original bounds.

Lattice decoding of a lattice-shaped codebook is a simple alternative for ML decoding, and it is equivalent to ML decoding after modulo-lattice reduction of the channel output. For good (high-dimensional) lattices, this modulo operation is information lossless in the presence of AWGN. At a finite shaping dimension, however, the lattice decoder is inferior to direct ML decoding from the channel output. The “modulo loss” is particularly large at low SNR, and it gets up to 4dB for scalar shaping. We consider the effect of a known interference (i.e., a dirty-paper channel) on the gap between the two decoders. We show that in the limit of a strong interference, the modulo output becomes a sufficient statistic for decoding the input. Thus, in the strong-interference regime, ML decoding suffers the same “modulo loss” as lattice decoding.

Lattice codes find applications in various digital communications settings, including shaping for power-constrained channels, coding with side information (dirty-paper channel, Wyner-Ziv source), and Gaussian networks. In this paper we deal neither with the construction of a good lattice, nor with algorithms for lattice coding and decoding, but with other elements of a lattice coding system. We shall consider (1) the two roles of the fundamental cell of the shaping lattice; (2) efficient mappings from information bits to a lattice point; (3) the loss due to a finite alphabet in construction-A lattices; (4) randomization with a simple dither; and (5) how to incorporate a multi-dimensional lattice into a sequential (feedback) scheme. While these are not new issues and observations, they seem to be somewhat overlooked or hidden inside the rich literature about lattice codes.

The Gaussian parallel relay network, introduced by Schein and Gallager, consists of a concatenation of a Gaussian additive broadcast channel from a single encoder to a layer of relays followed by a Gaussian multiple-access channel from the relays to the final destination (decoder), where all noises are independent. This setup exhibits an inherent conflict between digital and analog relaying; while analog relaying [known as amplify-and-forward (A&F)] suffers from noise accumulation, digital relaying (known as decode-and-forward) looses the potential coherence gain in combining the relay noises at the decoder. For a large number of relays, the coherence gain is large, and thus analog relaying has better performance; however, it is limited to white channels of equal bandwidth. In this paper, we present a generalization of the analog approach to the case of bandwidth mismatch. Our strategy, coined rematch and forward (R&F), is based upon applying joint source-channel coding techniques that belong to a certain class of maximally analog schemes. Using such techniques, R&F converts the bandwidth of the broadcast section to that of the multiple-access section, creating an equivalent matched-bandwidth network over which A&F is applied. It is shown that this strategy exploits the full bandwidth of the individual channels, without sacrificing the coherence gain offered by A&F. Specifically, for given individual-link capacities, R&F remains within a constant gap from the network capacity for any number of relays and any bandwidth ratio between the sections. Finally, the approach is extended to the case of colored channels.

The penalty incurred by imposing a finite delay constraint in lossless source coding of a memoryless source is investigated. It is well known that for the so-called block-to-variable and variable-to-variable codes, the redundancy decays at best polynomially with the delay, where in this case the delay is identified with the source block length or maximal source phrase length, respectively. In stark contrast, it is shown that for sequential codes (e.g., a delay-limited arithmetic code) the redundancy can be made to decay exponentially with the delay constraint. The corresponding redundancy-delay exponent is shown to be at least as good as the Rényi entropy of order 2 of the source, but (for almost all sources) not better than a quantity depending on the minimal source symbol probability and the alphabet size.

The Nyquist theorem (for perfect reconstruction of a band-limited signal from its noiseless samples) depends, essentially, only on the average sampling rate. In contrast, reconstruction from imperfect samples strongly depends also on the sampling pattern. Specifically, when the samples are corrupted with independent noise, the reconstruction distortion is generally higher for nonuniform sampling than for uniform sampling at the same average rate - a phenomenon known as “noise amplification”. We show that this degradation in performance can be avoided if the noise spectrum can be controlled; for any periodic nonuniform sampling pattern, there exists a quantization noise-shaping scheme that mitigates the noise amplification. Moreover, a scheme that combines noise shaping, Wiener filtering and entropy-coded dithered quantization (ECDQ) achieves the rate-distortion function of a (white or colored) Gaussian source, up to the granular loss of the lattice quantizer. This loss tends to zero, for a sequence of good latices, as the lattice dimension tends to infinity.

Random binning is an efficient, yet complex, coding technique for the symmetric L-description source coding problem. We propose an alternative approach, that uses the quantized samples of a bandlimited source as “descriptions”. By the Nyquist condition, the source can be reconstructed if enough samples are received. We examine a coding scheme that combines sampling and noise-shaped quantization for a scenario in which only K <;L descriptions or all L descriptions are received. Some of the received K-sets of descriptions correspond to uniform sampling while others to non-uniform sampling. This scheme achieves the optimum rate-distortion performance for uniform-sampling K-sets, but suffers noise amplification for nonuniform-sampling K-sets. We then show that by increasing the sampling rate and adding a random-binning stage, the optimal operation point is achieved for any K-set.

In the setting of a Gaussian channel without power constraints, proposed by Poltyrev in 1994, the codewords are points in ann-dimensional Euclidean space (an infinite constellation) and the tradeoff between their density and the error probability is considered. The normalized log density (NLD) plays the role of the communication rate, and capacity as well as error exponent bounds for this setting are known. This paper considers the infinite constellation setting in the finite block-length (dimension) regime. A simplified expression for Poltyrev's achievability bound is found and it is shown to be closely related to the sphere converse bound and to a recently proposed achievability bound based on point processes. The bounds are then analyzed asymptotically for growingn: for fixed NLD, the bounds turn out to be extremely tight compared to previous error exponent analysis. For fixed error probability ε, it is shown that the gap of the highest achievable NLD to the optimal NLD (Poltyrev's capacity) is approximately √{[1/(2n)]}Q-1(ε) , whereQis the standard complementary Gaussian cumulative distribution function, thus extending the channel dispersion analysis to infinite constellations. Connections to the error exponent of the power-constrained Gaussian channel and to the volume-to-noise ratio as a figure of merit are discussed. Finally, the new tight bounds are compared to state-of-the-art coding schemes.

We revisit the setting of a Gaussian channel without power constraints, proposed by Poltyrev, where the codewords are points in Euclidean space and their density is considered instead of the communication rate. We refine the expurgation technique (proposed by Poltyrev for the derivation of the error exponent) to the finite dimensions case and obtain a finite-dimensional achievability bound. While the expurgation exponent improves upon the random coding exponent only for certain rates (below a rate known as δex), we show that for finite dimensions the expurgation technique is useful for a broader range of rates. In addition, we present precise asymptotical analysis of the expurgation bound and find the sub-exponential terms, which turn out to be non-negligible.

In the setting of a Gaussian channel without power constraints, proposed by Poltyrev, the codewords are points in an n-dimensional Euclidean space (an infinite constellation) and their optimal density is considered. Poltyrev's “capacity” is the highest achievable normalized log density (NLD) with vanishing error probability. This capacity as well as error exponents for this setting are known. In this work we consider the optimal NLD for a fixed, nonzero error probability, as a function of the codeword length (dimension) n. We show that as n grows, the gap to capacity is inversely proportional (up to the first order) to the square-root of n where the proportion constant is given by the inverse Q-function of the allowed error probability, times the square root of 1/2. In an analogy to similar result in channel coding, the dispersion of infinite constellations is 1/2 nat2per channel use. We show that this optimal convergence rate can be achieved using lattices, therefore the result holds for the maximal error probability as well. Connections to the error exponent of the power constrained Gaussian channel and to the volume-to-noise ratio as a figure of merit are discussed.

The additive rate-distortion function (ARDF) was developed in order to universally bound the rate loss in the Wyner-Ziv problem, and has since then been instrumental in e.g., bounding the rate loss in successive refinements, universal quantization, and other multi-terminal source coding settings. The ARDF is defined as the minimum mutual information over an additive test channel followed by estimation. In the limit of high resolution, the ADRF coincides with the true RDF for many sources and fidelity criterions. In the other extreme, i.e., the limit of low resolutions, the behavior of the ARDF has not previously been rigorously addressed. In this work, we consider the special case of quadratic distortion and where the noise in the test channel is Gaussian distributed. We first establish a link to the I-MMSE relation of Guo et al. and use this to show that for any source the slope of the ARDF near zero rate, converges to the slope of the Gaussian RDF near zero rate. We then consider the multiplicative rate loss of the ARDF, and show that for bursty sources it may be unbounded, contrary to the additive rate loss, which is upper bounded by 1/2 bit for all sources. We finally show that unconditional incremental refinement, i.e., where each refinement is encoded independently of the other refinements, is ARDF optimal in the limit of low resolution, independently of the source distribution. Our results also reveal under which conditions linear estimation is ARDF optimal in the low rate regime.

Shannon's capacity and rate-distortion function, combined with the separation principle, provide tight bounds for the minimum possible distortion in joint source-channel coding. These bounds, however, are usually achievable only in the limit of large block length. In their 1973 paper, Ziv and Zakai provide a family of alternative capacity and rate-distortion functions, based on functionals satisfying the data-processing inequality, which potentially give tighter bounds for systems with a small block length, e.g., for scalar modulation. We examine a recently proposed approximation for the Ziv-Zakai bounds based on the Rényi-divergence functional. For the specific case of a uniform source, we derive explicit bounds on the Ziv-Zakai-Rényi rate- distortion function, which prove this approximation in the limit of small distortion. Our results can be extended, using the same technique, to more general sources.

Analog (uncoded) transmission provides a simple and robust scheme for communicating a Gaussian source over a Gaussian channel under the mean-squared-error (MSE) distortion measure. Unfortunately, its performance is usually inferior to the all-digital, separation-based source-channel coding solution, which requires exact knowledge of the channel at the encoder. The loss comes from the fact that except for very special cases, e.g., white source and channel of matching bandwidth (BW), it is impossible to achieve perfect matching of source to channel and channel to source by linear means. We show that by combining prediction and modulo-lattice operations, it is possible to match any colored Gaussian source to any colored Gaussian noise channel (of possibly different BW), hence achieve Shannon's optimum attainable performance R(D)=C. Furthermore, when the source and channel BWs are equal (but otherwise their spectra are arbitrary), this scheme is asymptotically robust in the sense that for high signal-to-noise ratio (SNR) a single encoder (independent of the noise variance) achieves the optimum performance. The derivation is based upon a recent modulo-lattice modulation scheme for transmitting a Wyner-Ziv source over a dirty-paper channel.

In Costa's dirty-paper channel, Gaussian random binning is able to eliminate the effect of interference which is known at the transmitter, and thus achieve capacity. We examine a generalization of the dirty-paper problem to a multiple access channel (MAC) setup, where structured (lattice-based) binning seems to be necessary to achieve capacity. In the dirty-MAC, two additive interference signals are present, one known to each transmitter but none to the receiver. The achievable rates using Costa's Gaussian binning vanish if both interference signals are strong. In contrast, it is shown that lattice-strategies (“lattice precoding”) can achieve positive rates, independent of the interference power. Furthermore, in some cases-which depend on the noise variance and power constraints-high-dimensional lattice strategies are in fact optimal. In particular, they are optimal in the limit of high SNR-where the capacity region of the dirty MAC with strong interference approaches that of a clean MAC whose power is governed by the minimum of the users' powers rather than their sum. The rate gap at high SNR between lattice-strategies and optimum (rather than Gaussian) random binning is conjectured to be1/2log2(πe/6) ≈ 0.254 bit. Thus, the doubly dirty MAC is another instance of a network setting, like the Körner-Marton problem, where (linear) structured coding is potentially better than random binning.

Multiple description (MD) source coding is a method to overcome unexpected information loss in a diversity system such as the Internet, or a wireless network. While classic MD coding handles the situation where the rate in some channels drops to zero temporarily, thus causing unexpected packet-loss, it fails to accommodate more subtle changes in link rate such as rate reduction. In such a case, a classic scheme canpsilat use the link capacity left for information transfer, causing even minor rate reduction to be considered as link failure. In order to accommodate such a frequent situation, we propose a more modular design for transmitting over a diversity system, which can handle unexpected reduction in link's rate, by downgrading the original description into a more coarse description, so it would fit to the new linkpsilas rate. The method is analyzed theoretically, and performance results are presented.

We study cost constrained side-information channels, where the cost function depends on a state which is known only to the encoder. In the additive noise case, we bound the capacity loss due to not knowing the cost state at the decoder and show that it is small under various assumptions, and goes to zero in the limit of weak noise. This model plays an important role in the (non-degraded) broadcast channel. In the semi-additive noise case, we bound the gap between the best known single letter achievable region and the true capacity region, using tools developed for the first problem. In the limit of weak noise, we show that the bounds coincide, thus we get the complete characterization of the capacity region.

The combination of source coding with decoder side information (the Wyner-Ziv problem) and channel coding with encoder side information (the Gel'fand-Pinsker problem) can be optimally solved using the separation principle. In this work, we show an alternative scheme for the quadratic-Gaussian case, which merges source and channel coding. This scheme achieves the optimal performance by applying a modulo-lattice modulation to the analog source. Thus, it saves the complexity of quantization and channel decoding, and remains with the task of ldquoshapingrdquo only. Furthermore, for high signal-to-noise ratio (SNR), the scheme approaches the optimal performance using an SNR-independent encoder, thus it proves for this special case the feasibility of universal joint source-channel coding.

We address the connection between the multiple-description (MD) problem and Delta–Sigma quantization. The inherent redundancy due to oversampling in Delta–Sigma quantization, and the simple linear-additive noise model resulting from dithered lattice quantization, allow us to construct a symmetric and time-invariant MD coding scheme. We show that the use of a noise-shaping filter makes it possible to trade off central distortion for side distortion. Asymptotically, as the dimension of the lattice vector quantizer and order of the noise-shaping filter approach infinity, the entropy rate of the dithered Delta–Sigma quantization scheme approaches the symmetric two-channel MD rate–distortion function for a memoryless Gaussian source and mean square error (MSE) fidelity criterion, at any side-to-central distortion ratio and any resolution. In the optimal scheme, the infinite-order noise-shaping filter must be minimum phase and have a piecewise flat power spectrum with a single jump discontinuity. An important advantage of the proposed design is that it is symmetric in rate and distortion by construction, so the coding rates of the descriptions are identical and there is therefore no need for source splitting.

For general memoryless systems, the existing information-theoretic solutions have a ldquosingle-letterrdquo form. This reflects the fact that optimum performance can be approached by a random code (or a random binning scheme), generated using independent and identically distributed copies of some scalar distribution. Is that the form of the solution of any (information-theoretic) problem? In fact, some counter examples are known. The most famous one is the ldquotwo help onerdquo problem: Korner and Marton showed that if we want to decode the modulo-two sum of two correlated binary sources from their independent encodings, then linear coding is better than random coding. In this paper we provide another counter example, the ldquodoubly-dirtyrdquo multiple-access channel (MAC). Like the Korner-Marton problem, this is a multiterminal scenario where side information is distributed among several terminals; each transmitter knows part of the channel interference while the receiver only observes the channel output. We give an explicit solution for the capacity region of the binary doubly-dirty MAC, demonstrate how this region can be approached using a linear coding scheme, and prove that the ldquobest known single-letter regionrdquo is strictly contained in it. We also state a conjecture regarding the capacity loss of single-letter characterization in the Gaussian case.

It was recently shown that the symmetric multiple-description (MD) quadratic rate-distortion function for memoryless Gaussian sources and two descriptions can be achieved by dithered Delta-Sigma quantization combined with memoryless entropy coding. In this paper,we generalize this result to stationary (colored) Gaussian sources by combining noise shaping and source prediction. We first propose a new representation for the test channel that realizes the MD rate-distortion function of a Gaussian source, both in the white and in the colored source case. We then show that this test channel canbe materialized by embedding two source prediction loops, one for each description, within a common noise shaping loop. While the noise shaping loop controls the tradeoff between the side and the central distortions, the role of prediction (like in differential pulse code modulation) is to extract the source innovations from the reconstruction at each of the side decoders, and thus reduce the coding rate. Finally, we show that this scheme achieves the MD rate-distortion function at all resolutions and all side-to-central distortion ratios, in the limit of high dimensional quantization.

In a previous paper we derived an upper bound on the redundancy of an arithmetic-type encoder for a memoryless source, designed to meet a finite end- to-end strict delay constraint. It was shown that the redundancy decays exponentially with the delay constraint and that the redundancy-delay exponent is lower bounded by log(1/alpha) where alpha is the probability of the most likely source symbol. In this work, we prove a corresponding upper bound for the redundancy-delay exponent, C - log 1/beta where beta is the probability of the least likely source symbol. This bound is valid for almost all memoryless sources and for all arithmetic-type (possibly time-varying, memory dependent) lossless delay-constrained encoders. We also shed some light on the difference between our exponential bounds and the polynomial O(d-5'3) upper bound on the redundancy with an average delay constraint d, derived in an elegant paper by Bugeaud, Drmota and Szpankowski for another class of variable-to-variable encoders, and show that the difference is due to the precision needed to memorize the encoder's state.

We develop mechanisms for reducing the effect of interference between un-synchronized users by means of controlling the degree of impulsiveness of their interference signals. Our analysis assumes spread-spectrum multiple-access in the form of ternary (0,+1,-1) CDMA signaling. The interference statistics of this signaling and in particular its degree of impulsiveness, can be parameterized while keeping the desired de-spread signal fixed. We find the pairs of random spreading patterns of interferer and user which minimize the bit error rate (BER) at the user, as a function of the signal/interference-to-noise ratio matrix. At low SINRs high degree of impulsiveness (single active chip per spreading sequence) minimizes the BER, while at high SINRs low degree of impulsiveness is better. We then extend our analysis to coded systems with channel state information at the receiver, and show that the same spreading pairs maximize the exponential effective SNR mapping (EESM) criterion at the decoder. Finally, we propose distributed protocols which try to approach the optimal operation points (i.e., pairs of spreading patterns) in the lack of central coordination.

In this work we consider joint source-channel coding (JSCC) schemes that are limited to work in blocks of finite length. We focus on the high resolution and high signal to noise ratio (SNR) regime, and derive new lower bounds for the distortion of JSCC schemes over rth-moment constrained additive noise channels. These new bounds are based on the method of Ziv and Zakai [11], combined with the Renyi information measure, as was recently proposed by Leibowitz and Zamir [5]. Numerical results are presented for the case of Gaussian source and channel, and it is shown that the new bounds improve upon Shannon's original bound in several cases, including bandwidth expansion and reduction.

The Gaussian parallel relay network problem consists of transmitting a message from a single source node to a single destination node, through a layer of parallel relay nodes. The source is connected to the relays by a Gaussian broadcast channel, while the relays are connected to the destination by a Gaussian multiple access channel. When the channels are all white with the same bandwidth, and the relays cannot decode the message, the best known strategy is "amplify and forward", which achieves the coherence gain of multiple relays. We propose a strategy which achieves this gain even when the noises are colored or the channels have different bandwidths. To that end we use analog modulo-lattice modulation of the codewords in the BC, and then forward the estimated codeword by each of the relays to the MAC. This modulation allows the relays to re-match the signal to the optimal spectrum of the MAC, thus demonstrating how a channel problem can gain from a joint source/channel approach. We show that this strategy is asymptotically optimal in some limiting cases, and that it outperforms the known alternatives in most other cases, where the optimum is unknown. We also demonstrate how to improve the achievable rate in the original white problem, for some signal to noise ratio values.

We follow a method introduced by Ziv and Zakai for finding ‘informational’ lower bounds on delay constrained joint source-channel coding. Their method uses the data processing theorem for generalized measures of information. We introduce the use of Rényi’s information of order α in their framework, and use high-resolution approximations to find its rate distortion function for a source that possesses a smooth distribution with rth-power distortion. This allows us to present two new lower bounds, one on the distortion in fixed rate vector quantization, and the other on the transmission through low-dimensional modulo-lattice additive noise channels.

For general memoryless systems, the typical information theoretic solution, when exists, has a ldquosingle-letterrdquo form. This reflects the fact that optimum performance can be approached by a random code (or a random binning scheme), generated using independent and identically distributed copies of some single-letter distribution. Is that the form of the solution of any (information theoretic) problem? In fact, some counter examples are known, perhaps the most famous being the Korner-Marton ldquotwo help onerdquo problem, where the modulo-two sum of two binary sources is to be decoded from their independent encodings. In this paper we provide another counter example, the ldquodoubly-dirtyrdquo multiple access channel (MAC). Like the Korner-Marton problem, this example is associated with a multiterminal scenario where side information is distributed among several terminals; each transmitter knows part of the channel interference but the receiver is not aware of any part of it. We give an explicit solution for the capacity region of a binary version of the doubly-dirty MAC, demonstrate how this capacity region can be approached using a linear coding scheme, and prove that the ldquobest known single-letter regionrdquo is strictly contained in it. We also state a conjecture regarding a similar rate loss of single letter characterization in the Gaussian case.

Costa's celebrated ldquowriting on dirty paperrdquo (WDP) shows that the power-constrained channelY=X+S+Z, with GaussianZ, has the same capacity as the standard AWGN channelY=X+Z, provided that the ldquointerferencerdquoS(no matter how strong it is) is known at the transmitter. While this ability for perfect interference cancelation is very appealing, it relies heavily on the Gaussianity of the (unknown) noiseZ. We construct an example of ldquobadrdquo noise for writing on dirty paper, namely, ldquodifference set noiserdquo. If the interferenceSis strong, then difference-set noise limits the WDP capacity to at most 2 bits. At the same time, like in the AWGN case, the zero-interference capacity grows without bound with the input constraint. Thus almost 100% of the available capacity is lost in WDP in the presence of difference-set noise. This high capacity loss is due to the ldquoentropy amplification propertyrdquo (EAP) of noise with an aperiodic probability distribution. Using the EAP and the duality between WDP and Wyner-Ziv source coding, we also give an example of dramatic rate-loss in quantizing encrypted source.

The impact of side information about the distortion measure in problems of quantization is analyzed. It is shown that such "distortion side information" is not only useful in general, but that in many cases knowing it at only the encoder is as good as knowing it at both encoder and decoder, and knowing it at only the decoder is useless. Moreover, it is shown that the strategy of exploiting distortion side information at the encoder by describing it for the decoder is inefficient. Thus, distortion side information is a natural complement to side information about the source signal, as studied by Wyner and Ziv, which if available only at the decoder is often as good as knowing it at both encoder and decoder. When both types of side information are present, conditions are established under which encoder-only distortion side information and decoder-only signal side information are sufficient in the high-resolution limit, and the rate penalty for deviating from this configuration is characterized.

The ldquowater-fillingrdquo solution for the quadratic rate-distortion function of a stationary Gaussian source is given in terms of its power spectrum. This formula naturally lends itself to a frequency domain ldquotest-channelrdquo realization. We provide an alternative time-domain realization for the rate-distortion function, based on linear prediction. The predictive test channel has some interesting implications, including the optimality at all distortion levels of pre/post filtered vector-quantized differential pulse-code modulation (DPCM), and a duality relationship with decision-feedback equalization (DFE) for intersymbol interference (ISI) channels.

In this paper we address the connection between the multiple-description (MD) problem and delta-sigma quantization. Specifically, we exploit the inherent redundancy due to oversampling in delta-sigma quantization, and the simple linear-additive noise model resulting from dithered lattice quantization, in order to construct a symmetric MD coding scheme. We show that the use of feedback by means of a noise shaping filter makes it possible to trade off central distortion for side distortion. Asymptotically as the dimension of the lattice vector quantizer and order of the noise shaping filter approach infinity, we show that the symmetric two-channel MD rate-distortion function for the memoryless Gaussian source and MSE fidelity criterion can be achieved at any resolution. This realization provides a new interesting interpretation for the information theoretic solution. The proposed design is symmetric in rate by construction and there is therefore no need for source splitting

We address the problem of a finite delay constraint in an arithmetic coding system. Due to the nature of the arithmetic coding process, source sequences causing arbitrarily large encoding or decoding delays exist. Therefore, to meet a finite delay constraint, it is necessary to intervene with the normal flow of the coding process, e.g., to insert fictitious symbols. This results in an inevitable coding rate redundancy. In this paper, we derive an upper bound on the achievable redundancy for a memoryless source. We show that this redundancy decays exponentially as a function of the delay constraint, and thus it is clearly superior to block to variable methods in that aspect. The redundancy-delay exponent is shown to be lower bounded by log(1/alpha), where alpha is the probability of the most likely source symbol. Our results are easily applied to practical problems such as the compression of English text

We consider transmission of a colored Gaussian source through a power constrained colored Gaussian broadcast channel subject to a mean-squared error distortion measure. It is well known that separation of source and channel coding cannot achieve the point R(D)=C simultaneously for more than one receiver. We characterize the distortion region achieved by the recently proposed joint source/channel "analog matching" coding scheme. In the special case of equal bandwidth (but arbitrary source and channel spectra) and in the limit of high signal to noise ratio (SNR), we prove that full robustness is asymptotically possible, i.e., the encoder becomes SNR-independent and each decoder approaches the ideal performance R(D)=C. This result extends the well known optimality of analog transmission in the white source / white channel case. Our results are based upon an encoder which employs modulo-lattice arithmetics, i.e. the transmitted signal is the residue of an analog signal with respect to a lattice.

We consider a generalization of the Gaussian dirty- paper problem to a multiple access setup. There are two additive interferences, one known to each transmitter but none to the receiver. The rates achievable using random binning schemes (i.e. schemes based on Costa's auxiliary random variables) vanish in the limit when the interferences are strong. In contrast, we show that lattice strategies ("lattice preceding") can achieve positive rates independent of the interferences. Furthermore, we derive an outer bound for the capacity region for arbitrary interferences, which is strictly smaller than the clean MAC capacity region. We then show that lattice strategies meet this outer bound for some combinations of noise variance and power constraints. In particular, lattice strategies are optimal in the limit of high SNR. Thus, the dirty MAC is another instance of a network setup, like the Korner-Marton modulo-two sum problem, where linear coding is better than random binning. We also derive lattice transmission schemes and conditions for optimality for the asymmetric case, where there is only one interference which is known to one of the users, and in particular for the helper problem, where the user which knows the interference does not have a message it wishes to transmit.

We investigate the capacity loss for using uncorrelated Gaussian input over a multiple-input multiple-output (MIMO) linear additive-noise channel. We upper-bound the capacity loss by a universal constant C* which is independent of the channel matrix and the noise distribution. For a single-user MIMO channel with ntinputs and nroutputs C* = min [ 1/2, nr/ntlog2(1+nt/nr) ] bit per input dimension (or 2C* bit per transmit antenna per second per hertz), under both total and per-input power constraints. If we restrict attention to (colored) Gaussian noise, then the capacity loss is upper-bounded by a smaller constant CG= nr/2nrlog2(nt/nr) for nrges nt/e, and CG= 0.265 otherwise, and this bound is tight for certain cases of channel matrix and noise covariance. We also derive similar bounds for the sum-capacity loss in multiuser MIMO channels. This includes in particular uncorrelated Gaussian transmission in a MIMO multiple-access channel (MAC), and "flat" Gaussian dirty-paper coding (DPC) in a MIMO broadcast channel. In the context of wireless communication, our results imply that the benefit of beamforming and spatial water-filling over simple isotropic transmission is limited. Moreover, the excess capacity of a point-to-point MIMO channel over the same MIMO channel in a multiuser configuration is bounded by a universal constant.

Ternary code division multiple access (CDMA) with a variable number of non-zero chips per symbol allows to control the transmission impulsiveness, ranging from non-impulsive signaling (with all chips being non-zero) to a fully impulsive signal (with only one chip per symbol being non-zero). The former corresponds to conventional CDMA while the latter to impulse-radio (IR). Recent work showed that the fully impulsive signal maximizes the average signal to interference ratio (ASIR) in asynchronous multiple user environment. We extend this result to information measures, and show that by adapting the impulsiveness figure (i.e., the number of non zero chips) to the channel conditions, the system can create a favorable interference environment for the other users. In particular, fully impulsive signaling maximizes the Shannon capacity of each user (treating interference from other users as noise). On the other hand, at transmission rates strictly below capacity, less impulsive signaling is better in terms of decoding error probability

Uncoded transmission provides a simple, delay-less and robust scheme for communicating a Gaussian source over a filter channel under the mean squared error (MSE) distortion measure. Unfortunately, its performance is usually inferior to the all-digital solution, consisting of a rate-distortion code for the source followed by a capacity achieving code for the channel. The performance loss of uncoded transmission comes from the fact that except for very special cases, it is impossible to achieve simultaneous matching of source to channel and channel to source by linear means. We show that by combining prediction and modulo-lattice arithmetic, we can match any stationary Gaussian source to any inter-symbol interference, colored-noise Gaussian channel, hence we achieve Shannon's optimum attainable performance R(D) = C. This scheme is based upon a novel analog modulo-lattice solution to the joint source-channel coding problem for a Gaussian Wyner-Ziv source and a dirty-paper channel

We address the problem of delay in an arithmetic coding system. Due to the nature of the arithmetic coding process, source sequences causing arbitrarily large encoding or decoding delays exist. This phenomena raises the question of just how large is the expected input to output delay in these systems, i.e., once a source sequence has been encoded, what is the expected number of source letters that should be further encoded to allow full decoding of that sequence. In this paper, we derive several new upper bounds on the expected delay for a memoryless source, which improve upon a known bound due to Gallager. The bounds provided are uniform in the sense of being independent of the sequence's history. In addition, we give a sufficient condition for a source to admit a bounded expected delay, which holds for a stationary ergodic Markov source of any order

The "water-filling" solution for the quadratic rate-distortion function of a stationary Gaussian source is given in terms of its power spectrum. This formula naturally lends itself to a frequency domain "test-channel" realization. We provide an alternative time-domain realization for the rate-distortion function, based on linear prediction. This solution has some interesting implications, including the optimality at all distortion levels of pre/post filtered vector-quantized differential pulse code modulation (DPCM), and a duality relationship with decision-feedback equalization (DFE) for inter-symbol interference (ISI) channels

We introduce a universal quantization scheme based on random coding, and we analyze its performance. This scheme consists of a source-independent random codebook (typically mismatched to the source distribution), followed by optimal entropy coding that is matched to the quantized codeword distribution. A single-letter formula is derived for the rate achieved by this scheme at a given distortion, in the limit of large codebook dimension. The rate reduction due to entropy coding is quantified, and it is shown that it can be arbitrarily large. In the special case of "almost uniform" codebooks (e.g., an independent and identically distributed (i.i.d.) Gaussian codebook with large variance) and difference distortion measures, a novel connection is drawn between the compression achieved by the present scheme and the performance of "universal" entropy-coded dithered lattice quantizers. This connection generalizes the "half-a-bit" bound on the redundancy of dithered lattice quantizers. Moreover, it demonstrates a strong notion of universality where a single "almost uniform" codebook is near optimal for any source and any difference distortion measure. The proofs are based on the fact that the limiting empirical distribution of the first matching codeword in a random codebook can be precisely identified. This is done using elaborate large deviations techniques, that allow the derivation of a new "almost sure" version of the conditional limit theorem.

In a causal source coding system, the reconstruction of the present source sample is restricted to be a function of the present and past source samples, while the code stream itself may be noncausal and have variable rate. Neuhoff and Gilbert showed that for memoryless sources, optimum performance among all causal source codes is achieved by time-sharing at most two memoryless codes (quantizers) followed by entropy coding. In this work, we extend Neuhoff and Gilbert's result in the limit of small distortion (high resolution) to two new settings. First, we show that at high resolution, an optimal causal code for a stationary source with finite differential entropy rate consists of a uniform quantizer followed by a (sequence) entropy coder. This implies that the price of causality at high resolution is approximately 0.254 bit, i.e., the space-filling loss of the uniform quantizer. Then, we consider individual sequences and introduce a deterministic analogue of differential entropy, which we call "Lempel-Ziv differential entropy." We show that for any bounded individual sequence with finite Lempel-Ziv differential entropy, optimum high-resolution performance among all finite-memory variable-rate causal codes is achieved by dithered scalar uniform quantization followed by Lempel-Ziv coding. As a by-product, we also prove an individual-sequence version of the Shannon lower bound.

We consider the problem of broadcasting a single Gaussian source to two listeners over a Gaussian broadcast channel, with rho channel uses per source sample, where rho>1. A distortion pair (D1,D2) is said to be achievable if one can simultaneously achieve a mean-squared error (MSE) D1at receiver 1 and D2at receiver 2. The main result of this correspondence is an outer bound for the set of all achievable distortion pairs. That is, we find necessary conditions under which (D1,D2) is achievable. We then apply this result to the problem of point-to-point transmission over a Gaussian channel with unknown signal-to-noise ratio (SNR) and rho>1. We show that if a system must be optimal at a certain SNRmin, then, asymptotically, the system distortion cannot decay faster than O(1/SNR). As for achievability, we show that a previously reported scheme, due to Mittal and Phamdo (2002), is optimal at high SNR. We introduce two new schemes for broadcasting with bandwidth expansion, combining digital and analog transmissions. We finally show how a system with a partial feedback, returning from the bad receiver to the transmitter and to the good receiver, achieves a distortion pair that lies on the outer bound derived here

We investigate the sum-capacity loss for using uncorrelated Gaussian inputs over multiple-input multiple-output (MIMO) power-constrained linear additive-noise channels in multi-user configurations. We show that the sum-capacity loss is bounded by a universal constant which depends only on the total number of input and output dimensions of the channel, but is independent of the channel matrix, the noise distribution and the number of users. Specifically, for a multiple-access channel with a total number of nttransmit antennas and base-station with nrreceive antennas, the sum-capacity loss is at most C* = min{1/2, nr/2ntlog2(1 + nt/nr)} bit per input dimension (or 1 bit per transmit antenna per second per Hertz). If we restrict attention to Gaussian noises, then the capacity loss is upper bounded by CG* = min{0.265, 0.265nr/ntlog2(nt/nr)}, and this bound is tight for certain channel matrices and noise spectra. We show also that the same bounds hold for the sum-capacity loss of uncorrelated Gaussian input over linear MIMO broadcast channels, input distribution being interpreted either in terms of the equivalent point-to-point channel with Sato condition, or as the output distribution of a "dirty-paper" transmitter. One implication of these results is the limited value of coherence and water-filling in spatial transmission. Another implication is the limited capacity loss in multi-user configurations relative to the fully cooperative (point-to-point) channel

We define an ensemble of lattices, and show that for asymptotically high dimension most of its members are simultaneously good as sphere packings, sphere coverings, additive white Gaussian noise (AWGN) channel codes and mean-squared error (MSE) quantization codes. These lattices are generated by applying Construction A to a random linear code over a prime field of growing size, i.e., by "lifting" the code to /spl Ropf//sup n/.

We consider the generalized dirty-paper channel Y=X+S+N,E{X/sup 2/}/spl les/P/sub X/, where N is not necessarily Gaussian, and the interference S is known causally or noncausally to the transmitter. We derive worst case capacity formulas and strategies for "strong" or arbitrarily varying interference. In the causal side information (SI) case, we develop a capacity formula based on minimum noise entropy strategies. We then show that strategies associated with entropy-constrained quantizers provide lower and upper bounds on the capacity. At high signal-to-noise ratio (SNR) conditions, i.e., if N is weak relative to the power constraint P/sub X/, these bounds coincide, the optimum strategies take the form of scalar lattice quantizers, and the capacity loss due to not having S at the receiver is shown to be exactly the "shaping gain" 1/2log(2/spl pi/e/12)/spl ap/ 0.254 bit. We extend the schemes to obtain achievable rates at any SNR and to noncausal SI, by incorporating minimum mean-squared error (MMSE) scaling, and by using k-dimensional lattices. For Gaussian N, the capacity loss of this scheme is upper-bounded by 1/2log2/spl pi/eG(/spl Lambda/), where G(/spl Lambda/) is the normalized second moment of the lattice. With a proper choice of lattice, the loss goes to zero as the dimension k goes to infinity, in agreement with the results of Costa. These results provide an information-theoretic framework for the study of common communication problems such as precoding for intersymbol interference (ISI) channels and broadcast channels.

We consider lossy source coding when side information affecting the distortion measure may be available at the encoder, decoder, both, or neither. For example, such distortion side information can model reliabilities for noisy measurements, sensor calibration information, or perceptual effects like masking and sensitivity to context. When the distortion side information is statistically independent of the source, we show that in many cases (e.g., for additive or multiplicative distortion side information) there is no penalty for knowing the side information only at the encoder, and there is no advantage to knowing it at the decoder. Furthermore, for quadratic distortion measures scaled by the distortion side information, we evaluate the penalty for lack of encoder knowledge and show that it can be arbitrarily large. In this scenario, we also sketch transform based quantizers constructions which efficiently exploit encoder side information in the high-resolution limit.

A subset of an Abelian group has unique differences if for all nonzeros. when viewed as additive noise, sets with unique differences amplify the output entropy as much as possible for a large class of input distributions, which is known as entropy amplification property. Aperiodic (noise) distributions arise as extreme cases in the investigation of the rate loss in side information problems such as channel coding with additive interference known at the encoder and lossy source coding with side information at the decoder. The decoder outputs a reconstruction, which is required to satisfy a distortion constraint. Reconstructing the clean source with some distortion is equivalent to reconstructing the encrypted source with the same distortion. Using the EAP, the rate loss can be arbitrarily large and arbitrarily close to 100%.

In causal source coding, the reconstruction is restricted to be a function of the present and past source samples, while the variable-length code stream may be noncausal. Neuhoff and Gilbert [1982] showed that for memoryless sources, optimum performance among all causal lossy source codes is achieved by time-sharing at most two memoryless codes (scalar quantizers) followed by entropy coding. We extend this result to causal coding of individual sequences in the limit of small distortion. The optimum performance of finite-memory variable-rate causal codes in this setting is characterized by a deterministic analogue of differential entropy, which we call "Lempel-Ziv differential entropy." As a by-product, we also provide an individual-sequence version of the Shannon lower bound to the rate-distortion function.

We introduce the idea of distortion side information, which does not directly depend on the source but instead affects the distortion measure. Such side information is not only useful at the encoder, but under many conditions of interest, knowing it at the encoder alone is sufficient and knowing it at the decoder alone is useless.

We address an open question, regarding whether a lattice code with lattice decoding (as opposed to maximum-likelihood (ML) decoding) can achieve the additive white Gaussian noise (AWGN) channel capacity. We first demonstrate how minimum mean-square error (MMSE) scaling along with dithering (lattice randomization) techniques can transform the power-constrained AWGN channel into a modulo-lattice additive noise channel, whose effective noise is reduced by a factor of /spl radic/(1+SNR/SNR). For the resulting channel, a uniform input maximizes mutual information, which in the limit of large lattice dimension becomes 1/2 log (1+SNR), i.e., the full capacity of the original power constrained AWGN channel. We then show that capacity may also be achieved using nested lattice codes, the coarse lattice serving for shaping via the modulo-lattice transformation, the fine lattice for channel coding. We show that such pairs exist for any desired nesting ratio, i.e., for any signal-to-noise ratio (SNR). Furthermore, for the modulo-lattice additive noise channel lattice decoding is optimal. Finally, we show that the error exponent of the proposed scheme is lower bounded by the Poltyrev exponent.

We consider the problem of choosing a robust input for communicating over an input constrained additive-noise channel where the noise distribution is arbitrary. We show that the mutual information rate achievable using a white Gaussian input never incurs a loss of more than half a bit per sample with respect to the power constrained capacity. For comparison, for the family of colored Gaussian noise channels a white Gaussian input loses at most log(e)/2e/spl ap/0.265 bit per sample with respect to the optimum water-pouring solution. For general input constraints, we derive a formula for choosing the best input in the min-max capacity loss (bound) sense. The bound on the capacity loss is tight for pulse position modulation (PPM) in the presence of a bursty jammer.

Using random coding techniques, we show that, in high dimensions, there exist lattices which are simultaneously good as sphere packings, sphere coverings, AWGN channel and MSE quantization codes. These lattices are produced by a construction, similar to construction A (Conway, J.H. and Sloane, N.J.A., 1988), and a randomly chosen set of generating vectors.

We present a new adaptive mechanism for empirical "on-line" design of a vector quantizer codebook. The proposed scheme is based on the principle of "natural type selection" (NTS) (Zamir and Rose, 2001). The NTS principle implies that backward adaptation, i.e., adaptation directed by the past reconstruction rather than by the uncoded source sequence converges to an optimum rate-distortion codebook. We incorporate the NTS iteration step into a parametric encoder. We demonstrate that the codebook converges to an optimum rate-distortion solution within the associated parametric class. This new scheme does not suffer from the severe complexity at high dimensions of nonparametric solutions like the generalized Lloyd algorithm (GLA). Moreover, unlike existing parametric adaptive schemes (e.g., code-excited linear prediction (CELP)), this scheme is optimal even for low coding rates.

We consider the problem of choosing robust codebooks for rate-distortion relative to difference distortion measures, and for capacity-cost relative to additive noise channels. We define an information theoretic formula for the min-max redundancy associated with robust random source codes, and similarly for the loss of robust random channel codes. We then show that this min-max performance can be approached by structured, dithered lattice codebooks. Applications to coding with side information are discussed.

Multiple description (MD) source coding is aimed at achieving graceful degradation in reconstruction with respect to losing portions of the code, with the cost of some redundancy. We examine MD schemes which use entropy-coded dithered lattice quantizers (ECDQ). We propose two techniques, one based on successive refinement (SR), and the other a dithered and periodic version of the MID scalar quantizer (MDSQ) with distributed cells proposed by Vaishampayan (1993, 1994). Similarly to the single description case, both techniques are universal in nature, and are equivalent to additive noise channels. This allows one to derive analytical expressions for the rate-distortion performance for general sources, and to compare them to the optimal rate regions at both high and low resolutions. Among other results, we establish that while the dithered MDSQ scheme loses only the space filling loss of the scalar lattice at any resolution, the SR-based scheme loses an additional 0.5 bit at any lattice dimension. Possible improvements, such as "refinement time sharing" and "dependent dithering", are discussed.

Suppose that we want to send a description of a single source to two listeners through a Gaussian broadcast channel, where the channel is used once per source sample. The problem of joint source-channel coding is to design a communication system to minimize the distortion D/sub 1/ at receiver 1 and at the same time minimize the distortion D/sub 2/ at receiver 2. If the source is Gaussian, the optimal solution is well known, and it is achieved by an uncoded "analog" scheme. We consider a Gaussian mixture source. We derive inner and outer bounds for the distortion region of all (D/sub 1/, D/sub 2/) pairs that are simultaneously achievable. The outer bound is based on the entropy power inequality, while the inner bound is attained by a digital-over-analog encoding scheme, which we present. We also show that if the modes of the Gaussian mixture are highly separated, our bounds are tight, and hence, our scheme attains the entire distortion region. This optimal region exceeds the region attained by separating source and channel coding, although it does not contain the "ideal" point (D/sub 1/, D/sub 2/)=(R/sup -1/(C/sub 1/), R/sup -1/(C/sub 2/)).

Entropy coding is a well-known technique to reduce the rate of a quantizer. It plays a particularly important role in universal quantization, where the quantizer codebook is not matched to the source statistics. We investigate the gain due to entropy coding by considering the entropy of the index of the first codeword, in a mismatched random codebook, that D-matches the source word. We show that the index entropy is strictly lower than the "uncoded" rate of the code, provided that the entropy is conditioned on the codebook. The number of bits saved by conditional entropy coding is equal to the divergence between the "favorite type" (the limiting empirical distribution of the first D-matching codeword) and the codebook-generating distribution. Specific examples are provided.

Network information theory promises high gains over simple point-to-point communication techniques, at the cost of higher complexity. However, lack of structured coding schemes limited the practical application of these concepts so far. One of the basic elements of a network code is the binning scheme. Wyner (1974, 1978) and other researchers proposed various forms of coset codes for efficient binning, yet these schemes were applicable only for lossless source (or noiseless channel) network coding. To extend the algebraic binning approach to lossy source (or noisy channel) network coding, previous work proposed the idea of nested codes, or more specifically, nested parity-check codes for the binary case and nested lattices in the continuous case. These ideas connect network information theory with the rich areas of linear codes and lattice codes, and have strong potential for practical applications. We review these developments and explore their tight relation to concepts such as combined shaping and precoding, coding for memories with defects, and digital watermarking. We also propose a few novel applications adhering to a unified approach.

Multiple description (MD) coding allows one to recover compressed video from packet loss, e.g., due to transmission over the Internet. The goal is that each packet will provide a self contained coarse description of a picture block, while the combination of all packets should provide the basis for a finer reconstruction of the block. However, direct application of MD quantization after motion compensation is problematic, because in each description the prediction is based on a different quantized version of the reference frame. Previous work on MD video coding suggested to solve this problem by incorporating an additional coarse quantizer into the prediction loop. This solution may reduce the prediction gain when the correlation between frames is high and the quantization resolution is low. We propose to keep the prediction loop un-quantized, while tracking the offset between the predictions in the joint decoder. We further improve the performance by re-designing the index assignment of the MD quantizer to be robust with respect to variable offsets.

We investigate the consequences of lossy compression, i.e., description with distortion, on the model selection of the minimum description length (MDL) criterion. Our basic observation is that for a finite data sequence and sufficiently large distortion, a two-stage universal lossy encoder tends to under-estimate the model order of the source. We demonstrate this property by examining the behavior of a two-stage universal lossy encoder, based on pre/post-filtered entropy-coded dithered quantization, over some parametric classes of stationary Gaussian sources.

Single-tone and multitone are two modulation methods which can combine multiple digital users over a single channel, and decode them independently, corresponding to time-division and frequency-division multiple access, respectively. When the channel noise is impulsive, its distribution at the receiver decision point, and therefore its effect on the users, depends strongly on the type of modulation. We quantify this effect using information theoretic measures: capacity and error-exponent, where the latter is represented by its cut-off rate parameter. For low to moderate impulse power, the cut-off rate associated with multitone is greater than the cut-off rate associated with single-tone-in contrast to the relation between the corresponding Shannon capacities. This leads to anomalous behavior of the error-versus-information-rate performance. We show that this behavior relates to the tendency toward Gaussianity of the noise after multitone demodulation. We also provide specific evaluation of this phenomena for advanced data transmission over the cable TV (hybrid fiber coax) channel.

Consider the optimum strategy for using channel state ("side") information in transmission over a modulo-additive noise channel, with state-dependent noise, where the receiver does not have access to the side information (SI). Previous work showed that capacity-wise, the optimum transmitter shifts each code letter by a "prediction" of the noise sample based on the SI. We show that this structure achieves also the random-coding error exponent, and, therefore, is optimum at some range of rates below capacity. Specifically, the optimum transmitter predictor minimizes the Renyi entropy of the prediction error; the Renyi order depends on the rate, and goes to one (corresponding to Shannon entropy) for rates close to capacity. In contrast, it is shown that this "prediction strategy" may not be optimal at low transmission rates.

A common belief in quantization theory says that the quantization noise process resulting from uniform scalar quantization of a correlated discrete-time process tends to be white in the limit of small distortion ("high resolution"). A rule of thumb for this property to hold is that the source samples have a "smooth" joint distribution. We give a precise statement of this property, and generalize it to nonuniform quantization and to vector quantization. We show that the quantization errors resulting from independent quantizations of dependent real random variables become asymptotically uncorrelated (although not necessarily statistically independent) if the joint Fisher information (FI) under translation of the two variables is finite and the quantization cells shrink uniformly as the distortion tends to zero.

Consider approximate (lossy) matching of a source string /spl sim/P, with a random codebook generated from reproduction distribution Q, at a specified distortion d. Previous work determined the minimum coding rate R/sub 1/=R(P, Q, d) for this setting. We observe that for a large word length and with high probability, the matching codeword is typical with a distribution Q/sub 1/ which is different from Q. If a new random codebook is generated /spl sim/Q/sub 1/, then the source string will favor codewords which are typical with a new distribution Q/sub 2/, resulting in a minimum coding rate R/sub 2/=R(P, Q/sub 1/, d), and so on. We show that the sequences of distributions Q/sub 1/, Q/sub 2/,... and rates R/sub 1/, R/sub 2/,..., generated by this procedure, converge to an optimum reproduction distribution Q*, and the rate-distortion function R(P, d), respectively. We also derive a fixed rate-distortion slope version of this natural type selection process. In the latter case, an iteration of the process stochastically simulates an iteration of the Blahut-Arimoto (1972) algorithm for rate-distortion function computation (without recourse to prior knowledge of the underlying source distribution). To strengthen these limit statements, we also characterize the steady-state error of these procedures when iterating at a finite string length. Implications of the main results provide fresh insights into the workings of lossy variants of the Lempel-Ziv algorithm for adaptive compression.

Multiple description source coding is aimed at achieving graceful degradation in reconstruction with respect to losing portions of the code, with the cost of some redundancy. In this research we examine source coding schemes for two descriptions and three decoders based on entropy coded dithered ("universal") quantizers (ECDQ). We propose two techniques. The first is a two stage encoder, where the first stage produces two coarse descriptions, and the second stage produces a refinement code to be used only by the joint decoder. The second technique is a dithered and periodic version of a scalar quantizer with distributed cells for multiple descriptions proposed by Vaishampayan (1994). Both techniques are shown to be equivalent to additive noise channels. Analytical expressions for their performance are derived and compared to the optimal rate regions at both high and low resolutions. The first technique is conceptually simple and easily tuned to various parameters, but is inherently sub-optimal. The second technique is less versatile but shows promising results that resemble those of the ECDQ for single description encoding.

The computation of channel capacity with side information at the transmitter side (but not at the receiver side) requires, in general, extension of the input alphabet to a space of "strategies", and is often hard. We consider the special case of a discrete memoryless module-additive noise channel Y=X+Z/sub s/, where the encoder observes causally the random state S/spl isin/S that governs the distribution of the noise Z/sub s/. We show that the capacity of this channel is given by C=log|/spl chi/|-min/sub t:S/spl rarr//spl chi//H(Z/sub S/-t(S)). This capacity is realized by a state-independent code, followed by a shift by the "noise prediction" t/sub min/(S) that minimizes the entropy of Z/sub s/-t(S). If the set of conditional noise distributions {p(z|s),s/spl isin/S} is such that the optimum predictor t/sub min/(/spl middot/) is independent of the state weights, then C is also the capacity for a noncausal encoder, that observes the entire state sequence in advance. Furthermore, for this case we also derive a simple formula for the capacity when the state process has memory.

High-resolution bounds in lossy coding of a real memoryless source are considered when side information is present. Let X be a "smooth" source and let Y be the side information. First we treat the case when both the encoder and the decoder have access to Y and we establish an asymptotically tight (high-resolution) formula for the conditional rate-distortion function R/sub X|Y/(D) for a class of locally quadratic distortion measures which may be functions of the side information. We then consider the case when only the decoder has access to the side information (i.e., the "Wyner-Ziv problem"). For side-information-dependent distortion measures, we give an explicit formula which tightly approximates the Wyner-Ziv rate-distortion function R/sup WZ/(D) for small D under some assumptions on the joint distribution of X and Y. These results demonstrate that for side-information-dependent distortion measures the rate loss R/sup WZ/(D)-R/sub X|Y/(D) can be bounded away from zero in the limit of small D. This contrasts the case of distortion measures which do not depend on the side information where the rate loss vanishes as D/spl rarr/0.

We present a continuous dual of multiterminal source encoding with one distortion criterion (the "Berger-Yeung (1989) problem"). A continuous source X is encoded with "high resolution" (D/sub x//spl rarr/0), with the aid of a "helper," i.e., a correlated discrete or continuous source Y, that is encoded separately subject to some arbitrary distortion criterion D/sub y/. We find the asymptotic form of the set of achievable coding rates R(D/sub x/, D/sub y/) of the X- and Y-encoders as D/sub x//spl rarr/0. Two extreme cases of our result provide high-resolution interpretations to the classical work of Wyner (1975, 1978), Ahlswede (1975), Korner (1975), and Ziv (1976) on source coding with side information.

The problem of asymptotic (i,e., low-distortion) behavior of the rate-distortion function of a random vector is investigated for a class of non-difference distortion measures. The main result is an asymptotically tight expression which parallels the Shannon lower bound for difference distortion measures. For example, for an input-weighted squared error distortion measure d(x,y)=/spl par/W(x)(y-x)/spl par//sup 2/,y,x/spl isin/R/sup n/, the asymptotic expression for the rate-distortion function of X/spl isin/R/sup n/ at distortion level D equals h(X)-/sub 2///sup n/log(2/spl pi/eD/n)+Elog|detW(X)| where h(X) is the differential entropy of X. Extensions to stationary sources and to high-resolution remote ("noisy") source coding are also given.

Entropy-coded vector quantization is studied using high-resolution multidimensional companding over a class of nondifference distortion measures. For distortion measures which are "locally quadratic" a rigorous derivation of the asymptotic distortion and entropy-coded rate of multidimensional companders is given along with conditions for the optimal choice of the compressor function. This optimum compressor, when it exists, depends on the distortion measure but not on the source distribution. The rate-distortion performance of the companding scheme is studied using an asymptotic expression for the rate-distortion function which parallels the Shannon lower bound for difference distortion measures. It is proved that the high-resolution performance of the scheme is arbitrarily close to the rate-distortion limit for large quantizer dimensions if the compressor function and the lattice quantizer used in the companding scheme are optimal, extending an analogous statement for entropy-coded lattice quantization and MSE distortion. The companding approach is applied to obtain a high-resolution quantizing scheme for noisy sources.

A pair of well-known inequalities, due to Shannon, upper/lower bound the rate-distortion function of a real source by the rate-distortion function of the Gaussian source with the same variance/entropy. We extend these bounds to multiple descriptions, a problem for which a general "single-letter" solution is not known. We show that the set D/sub X/(R/sub 1/, R/sub 2/) of achievable marginal (d/sub 1/, d/sub 2/) and central (d/sub 0/) mean-squared errors in decoding X from two descriptions at rates R/sub 1/ and R/sub 2/ satisfies D*(/spl sigma//sub x//sup 2/, R/sub 1/, R/sub 2/)/spl sube/D/sub X/(R/sub 1/, R/sub 2/)/spl sube/D*(P/sub x/, R/sub 1/, R/sub 2/) where /spl sigma//sub x//sup 2/ and P/sub x/ are the variance and the entropy-power of X, respectively, and D*(/spl sigma//sup 2/, R/sub 1/, R/sub 2/) is the multiple description distortion region for a Gaussian source with variance /spl sigma//sup 2/ found by Ozarow (1980). We further show that like in the single description case, a Gaussian random code achieves the outer bound in the limit as d/sub 1/, d/sub 2//spl rarr/0, thus the outer bound is asymptotically tight at high resolution conditions.

We consider separate encoding and joint decoding of correlated continuous information sources, subject to a difference distortion measure. We first derive a multiterminal extension of the Shannon lower bound for the rate region. Then we show that this Shannon outer bound is asymptotically tight for small distortions. These results imply that the loss in the sum of the coding rates due to the separation of the encoders vanishes in the limit of high resolution. Furthermore, lattice quantizers followed by Slepian-Wolf lossless encoding are asymptotically optimal. We also investigate the high-resolution rate region in the remote coding case, where the encoders observe only noisy versions of the sources. For the quadratic Gaussian case, we establish a separation result to the effect that multiterminal coding aimed at reconstructing the noisy sources subject to the rate constraints, followed by estimation of the remote sources from these reconstructions, is optimal under certain regularity conditions on the structure of the coding scheme.

Consider encoding a memoryless source using two descriptions, the first at rate R/sub 1/ and distortion d/sub 1/, the second at rate R/sub 2/ and distortion d/sub 2/. Combining the two descriptions the source can be reconstructed with distortion d/sub 0/. For a Gaussian source of variance /spl sigma//sup 2/, Ozarow (1980) found an explicit characterization of the region R*(/spl sigma//sup 2/; d/sub 1/,d/sub 2/,d/sub 0/)/spl sub/R/sup 2/ of achievable rate pairs (R/sub 1/, R/sub 2/) with given mean squared distortions d/sub 1/, d/sub 2/, and d/sub 0/. This is the only case for which the multiple description rate-distortion region is completely known. We show that for a general real valued source X and a locally quadratic distortion measure of the form /spl rho/(x,x/spl circ/)=w(x)/sup 2/(x-x/spl circ/)/sup 2/+o((x-x/spl circ/)/sup 2/), the region of admissible rate pairs is arbitrary well approximated in the limit of small distortions by the region R*(P/sub X/2/sup 2E{log m(X)}/; d/sub 1/,d/sub 2/,d/sub 0/) where R*(/spl sigma//sup 2/; d/sub 1/,/sub 2/, d/sub 0/) denotes the multiple description rate region of a Gaussian source with variance /spl sigma//sup 2/, and where P/sub X/ is the entropy-power of the source. Applications to companding quantization are also considered.

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.

The Fisher information J(X) of a random variable X under a translation parameter appears in information theory in the classical proof of the entropy-power inequality (EPI). It enters the proof of the EPI via the De-Bruijn identity, where it measures the variation of the differential entropy under a Gaussian perturbation, and via the convolution inequality J(X+Y)/sup -1//spl ges/J(X)/sup -1/+J(Y)/sup -1/ (for independent X and Y), known as the Fisher information inequality (FII). The FII is proved in the literature directly, in a rather involved way. We give an alternative derivation of the FII, as a simple consequence of a "data processing inequality" for the Cramer-Rao lower bound on parameter estimation.

We derive a version of the Brunn-Minkowski inequality which gives a nontrivial lower bound on the volume of the Minkowski sum of degenerate sets, namely, line sets. This inequality parallels a recently obtained matrix generalization of the entropy-power inequality.

The rate-distortion function for source coding with side information at the decoder (the "Wyner-Ziv problem") is given in terms of an auxiliary random variable, which forms a Markov chain with the source and the side information. This Markov chain structure, typical to the solution of multiterminal source coding problems, corresponds to a loss in coding rate with respect to the conditional rate-distortion function, i.e., to the case where the encoder is fully informed. We show that for difference (or balanced) distortion measures, this loss is bounded by a universal constant, which is the minimax capacity of a suitable additive-noise channel. Furthermore, in the worst case, this loss is equal to the maximin redundancy over the rate-distortion function of the additive noise "test" channel. For example, the loss in the Wyner-Ziv problem is less than 0.5 bit/sample in the squared-error distortion case, and it is less than 0.22 bit for a binary source with Hamming distance. These results have implications also in universal quantization with side information, and in more general multiterminal source coding problems.

We present several results regarding the properties of a random vector, uniformly distributed over a lattice cell. This random vector is the quantization noise of a lattice quantizer at high resolution, or the noise of a dithered lattice quantizer at all distortion levels. We find that for the optimal lattice quantizers this noise is wide-sense-stationary and white. Any desirable noise spectra may be realized by an appropriate linear transformation ("shaping") of a lattice quantizer. As the dimension increases, the normalized second moment of the optimal lattice quantizer goes to 1/2/spl pi/e, and consequently the quantization noise approaches a white Gaussian process in the divergence sense. In entropy-coded dithered quantization, which can be modeled accurately as passing the source through an additive noise channel, this limit behavior implies that for large lattice dimension both the error and the bit rate approach the error and the information rate of an additive white Gaussian noise (AWGN) channel.

We consider encoding of a source with pre-specified second-order statistics, but otherwise arbitrary, by entropy-coded dithered (lattice) quantization (ECDQ) incorporating linear pre- and post-filters. In the design and analysis of this scheme we utilize the equivalent additive-noise channel model of the ECDQ. For Gaussian sources and a square error distortion measure, the coding performance of the pre/post filtered ECDQ approaches the rate-distortion function, as the dimension of the (optimal) lattice quantizer becomes large; actually, in this case the proposed coding scheme simulates the optimal forward channel realization of the rate-distortion function. For non-Gaussian sources and finite-dimensional lattice quantizers, the coding rate exceeds the rate-distortion function by at most the sum of two terms: the "information divergence of the source from Gaussianity" and the "information divergence of the quantization noise from Gaussianity". Additional bounds on the excess rate of the scheme from the rate-distortion function are also provided.

The rate-distortion characteristics of a scheme for encoding continuous-time band limited stationary sources, with a prescribed band, is considered. In this coding procedure the input is sampled at Nyquist's rate or faster, the samples undergo dithered uniform or lattice quantization, using subtractive dither, and the quantizer output is entropy-coded, The rate-distortion performance, and the tradeoff between the sampling rate and the quantization accuracy is investigated, utilizing the observation that the coding scheme is equivalent to an additive noise channel. It is shown that the mean-square error of the scheme is fixed as long as the product of the sampling period and the quantizer second moment is kept constant, while for a fixed distortion the coding rate generally increases when the sampling rate exceeds the Nyquist rate. Finally, as the lattice quantizer dimension becomes large, the equivalent additive noise channel of the scheme tends to be white Gaussian, and both the rate and the distortion performance become invariant to the sampling rate.>

Presents several results regarding the properties of a random vector, uniformly distributed over a lattice cell. This random vector is the quantization noise associated with dithered lattice quantization, and at high resolution it is the noise generated in regular lattice quantization of "smooth" sources. The authors find that the noise associated with the optimal lattice quantizers is wide-sense stationary and white. Any desirable noise spectra may be realized by an appropriate linear transformation ("shaping") of a lattice quantizer. As the dimension increases, the normalized second moment of the optimal lattice quantizer goes to 1/2/spl pi/e, and consequently the quantization noise approaches a white Gaussian process. Actually, in entropy coded dithered quantization where the quantization procedure can be modeled as an additive noise channel, this limit behavior implies that both the asymptotic MSE distortion and the mutual-information between input and output of the quantization channel, approaches the MSE and the mutual-information between input and output of an additive white Gaussian noise (AWGN) channel.>

New results are proved on the convergence of the Shannon (1959) lower bound to the rate distortion function as the distortion decreases to zero. The key convergence result is proved using a fundamental property of informational divergence. As a corollary, it is shown that the Shannon lower bound is asymptotically tight for norm-based distortions, when the source vector has a finite differential entropy and a finite /spl alpha/ th moment for some /spl alpha/>0, with respect to the given norm. Moreover, we derive a theorem of Linkov (1965) on the asymptotic tightness of the Shannon lower bound for general difference distortion measures with more relaxed conditions on the source density. We also show that the Shannon lower bound relative to a stationary source and single-letter difference distortion is asymptotically tight under very weak assumptions on the source distribution.>

The authors prove the following generalization of the entropy power inequality: h(ax)>or=h(Ax) where h(.) denotes (joint-) differential-entropy x=x/sub 1/...x/sub n/, is a random vector with independent components, x=x...x/sub n/, is a Gaussian vector with independent components such that h(x/sub i/)=h(x/sub i/), i=1...n, and A is any matrix. This generalization of the entropy-power inequality is applied to show that a non-Gaussian vector with independent components becomes "closer" to Gaussianity after a linear transformation, where the distance to Gaussianity is measured by the information divergence. Another application is a lower bound, greater than zero, for the mutual-information between nonoverlapping spectral components of a non-Gaussian white process. They also describe a dual generalization of the Fisher information inequality.>

The authors analyze a scheme for encoding continuous time band-limited signals in which the input is sampled at Nyquist's rate or faster, the samples undergo dithered uniform or lattice quantization and the quantizer output is entropy coded. This analysis leads to explicit expressions for the trade-off between sampling rate and quantization accuracy. Also, they provide expression for the scheme's redundancy (i.e. its excess rate over the rate distortion function) in terms of the both the sampling rate and quantization resolution parameters.>

Uniform quantization with dither, or lattice quantization with dither in the vector case, followed by a universal lossless source encoder (entropy coder), is a simple procedure for universal coding with distortion of a source that may take continuously many values. The rate of this universal coding scheme is examined, and a general expression is derived for it. An upper bound for the redundancy of this scheme, defined as the difference between its rate and the minimal possible rate, given by the rate distortion function of the source, is derived. This bound holds for all distortion levels. Furthermore, a composite upper bound on the redundancy as a function of the quantizer resolution that leads to a tighter bound in the high rate (low distortion) case is presented.>