We consider the problem of tracking, in realtime, an unstable autoregressive (AR) source over a discrete memoryless channel (DMC). We present computable achievable bounds on the optimal tracking error for general DMCs, and we particularize these bounds to the binary erasure, packet erasure, and binary symmetric channels. The achievable bounds in this paper are proved using a partially separatesource quantizationandchannel codingarchitecture. We do not use complete or strict separation in usual Shannon sense: 1) the quantiser’s resolution is optimized against the error-correction capabilities of the channel code and the channel code is optimized against anAR Hamming distortion functionmatched to the source (a weighted Hamming distortion function that provides unequal error protection to different parts of the AR source). The achievability results for general DMCs are proved by combining the AR Hamming distortion function with new realtime (streaming) versions of therandom coding unionanddependence testing bounds. When applied to erasure channels, these general bounds combine with simple converses to demonstrate that the channel’s cutoff rate plays an important role in realtime tracking.

We study a variant of the successive refinement problem with receiver side information in which the receivers require identical, matching reconstructions. We present general inner and outer bounds for the rate region for this variant of the problem and present a single-letter characterization of the admissible rate region for several classes of the joint distribution of the source and the side information. Unlike in the general successive refinement problem, the characterization of the admissible rate region in the cases when the derived inner and outer bounds match requires only one auxiliary random variable. The characterization reveals that the side information can be fully used to reduce the communication rates via binning; however, the receiver reconstruction functions can depend only on a certain Gács-Körner common randomness between shared by the two receivers. Since the entropy of the Gács-Körner common randomness between two random variables is a discontinuous function of joint distribution of the variables, we establish the fact that the admissible rate region for this variant of the successive refinement problem is discontinuous in the underlying distribution of the source and side information even though the problem formulation does not involve the zero-error or functional reconstruction constraints.

A distributed binary hypothesis testing problem is studied with one observer and two decision centers. Achievable type-II error exponents are derived for testing against conditional independence when the observer communicates with the two decision centers over one common and two individual noise-free bit pipes and when it communicates with them over a noisy broadcast channel. The results are based on a coding and testing scheme that splits the observations into subblocks, so that transmitter and receivers can independently apply to each subblock either Gray-Wyner coordination coding with side-information or hybrid joint source-channel coding with side-information, followed by a Neyman-Pearson test over the subblocks at the receivers. This approach allows to avoid introducing further error exponents that one would expect from the receivers' decoding operations related to binning or the noisy transmission channel. The derived exponents are shown to be optimal in some special cases when communication is over noise-free links. The results reveal a tradeoff between the type-II error exponents at the two decision centers.

An erasure broadcast network is considered with two disjoint sets of receivers: a set of weak receivers with all-equal erasure probabilities and equal cache sizes and a set of strong receivers with all-equal erasure probabilities and no cache memories. Lower and upper bounds are presented on the capacity-memory tradeoff of this network (the largest rate at which messages can be reliably communicated for given cache sizes). The lower bound is achieved by means of a joint cache-channel coding scheme and significantly improves over traditional schemes based on the separate cache-channel coding. In particular, it is shown that the joint cache-channel coding offers new global caching gains that scale with the number of strong receivers in the network. The upper bound uses bounding techniques from degraded broadcast channels and introduces an averaging argument to capture the fact that the contents of the cache memories are designed before knowing users' demands. The derived upper bound is valid for all stochastically degraded broadcast channels. The lower and upper bounds match for a single weak receiver (and any number of strong receivers) when the cache size does not exceed a certain threshold. Improved bounds are presented for the special case of a single weak and a single strong receiver with two files and the bounds are shown to match over a large range of cache sizes.

In this paper, we consider a lossy single-user caching problem with correlated sources. We first describe the fundamental interplay between the source correlations, the capacity of the user's cache, the user's reconstruction distortion requirements, and the final delivery-phase (compression) rate. We then illustrate this interplay using a multivariate Gaussian source example and a binary symmetric source example. To fully explore the effect of the user's distortion requirements, we formulate the caching problem using f-separable distortion functions recently introduce by Shkel and Verdú. The class of f-separable distortion functions includes separable distortion functions as a special case, and our analysis covers both the expected- and excess-distortion settings in detail. We also determine what “common information” should be placed in the cache, and what information should be transmitted during the delivery phase. To this end, two new common-information measures are introduced for caching, and their relationship to the common-information measures of Wyner, Gács, and Körner is discussed in detail.

We study the capacity of a broadcast packet-erasure network with receiver caching. The receivers in the network are divided into two groups: A group of strong receivers with small packet erasure probabilities, and a group of weak receivers with large packet erasure probabilities. The weak receivers are provided with local cache memories as compensation for their poor channels. Achievable (lower) and converse (upper) bounds for the optimal capacity-memory tradeoff are derived. The lower bounds are proved using new joint cache-channel coding schemes that significantly outperform naive separate cache-channel coding schemes. For the case of two receivers, the capacity-memory tradeoff is completely characterized for a range of useful cache memory sizes.

This paper studies fixed-length compression with multiple constraints in the finite blocklength regime. We introduce two different average distortion measures and consider constraints for individual source outcomes. The concept of d-tilted information as well as recent finite-length bounds for the optimal coding rates are extended to this setting. We further particularise our results to the binary memoryless source and a sparse Gaussian source.

This paper presents a Shannon-type lower bound on the rate-distortion (RD) function of the Bernoulli-Gaussian spike source. The lower bound is valid in all distortion regimes and asymptotically tight for small distortions.

We present upper and lower bounds on the per-user multiplexing gain (MG) of Wyner's circular soft-handoff model and Wyner's circular full model with cognitive transmitters and receivers with cache memories. The bounds are tight for cache memories with prelog μ that exceeds 2/3D in the soft-handoff model and exceeds D in the full model, where D denotes the number of possibly demanded files. In these cases the per-user MG of the two models is 1 + μ/D, the same as for non-interfering point-to-point links with caches at the receivers. Large receiver cache-memories thus allow to completely mitigate interference in these networks.

We propose a rate-adaptive error-correction coding framework for transmission over finite-length block-fading channels, with causal channel state information at the transmitter. A dynamic programming optimization approach can be use to obtain the optimal rate adaptation strategy. A suboptimal rate adaptation strategy is developed for sequential random codes. Numerical results show that significant performance gains are achievable with the proposed adaptation scheme.

We propose a base-station (BS) cooperation model for broadcasting a discrete memoryless source in a cellular or heterogeneous network. The model allows the receivers to use helper BSs to improve network performance, and it permits the receivers to have prior side information about the source. We establish the model's information-theoretic limits in two operational modes: In Mode 1, the helper BSs are given information about the channel codeword transmitted by the main BS, and in Mode 2 they are provided information about the source. Optimal codes for Mode 1 use hash-and-forward coding at the helper BSs; while, in Mode 2, optimal codes use source codes from Wyner's helper side-information problem at the helper BSs. We prove the optimality of both approaches by way of a new list-decoding generalisation of [8, Thm. 6], and, in doing so, show an operational duality between Modes 1 and 2.

In this paper, we study how the number of conferencing rounds effects the capacity of large interference networks. We take Wyner's asymmetric linear (soft-handoff) model, include conferencing links between closely located transmitters and receivers, and we consider the per-user asymptotic multiplexing gain. Our results show, for example, that when the capacities of the conferencing links scale at most (1/4) log P with the power P and when one can choose which transmitters and receivers cooperate, then there is no loss in terms of asymptotic multiplexing gain in having only one round of conferencing. In contrast, when the capacities of the conferencing links grow faster than (1/4) log P, then the asymptotic multiplexing gain with one round of conferencing is strictly smaller than that achieved with multiple rounds.

We consider a joint source-channel coding problem on a finite-field multiway relay channel, and we give closed-form lower and upper bounds on the optimal source-channel rate. These bounds are shown to be tight for all discrete memoryless sources in a certain class P*, and we demonstrate that strict source-channel separation is optimal within this class. We show how to test whether a given source belongs to P*, we give a balanced-information regularity condition for P*, and we express P* in terms of conditional multiple-mutual information. Finally, we show that P* is useful for a centralized storage problem.

We propose a base-station (BS) cooperation model for broadcasting a discrete memoryless source in a cellular or heterogeneous network. The model allows the receivers to use helper BSs to improve network performance, and it permits the receivers to have prior side information about the source. We establish the model's information-theoretic limits in two operational modes: In Mode 1, the helper BSs are given information about the channel codeword transmitted by the main BS, and in Mode 2 they are provided correlated side information about the source. Optimal codes for Mode 1 use hash-and-forward coding at the helper BSs; while, in Mode 2, optimal codes use source codes from Wyner's helper source-coding problem at the helper BSs. We prove the optimality of both approaches by way of a new list-decoding generalisation used in Theorem 6 of Tuncel (2006), and in doing so, show an operational duality between Modes 1 and 2.

A streaming communications model with an autoregressive distortion function is proposed. We show that the model is useful for delay-sensitive systems, and we present asymptotic and non-asymptotic achievability results that exhibit some fundamental tradeoffs between rate, reliability and delay.

We study the variant of the successive refinement problem where the receivers require identical reconstructions.We characterize the rate region when the joint support of the source and the side information variables is the Cartesian product of their individual supports. The characterization indicates that the side information can be fully used to reduce the communication rates via binning; however, the reconstruction functions can depend only on the Gács-Körner common randomness shared by the two receivers. Unlike existing (inner and outer) bounds to the rate region of the general successive refinement problem, the characterization for the variant studied requires only one auxiliary random variable.

A computable expression for Heegard and Berger's rate-distortion function has eluded information theory for nearly three decades. Heegard and Berger's single-letter achievability bound is well known to be optimal for physically degraded side information; however, it is not known whether the bound is optimal for arbitrarily correlated side information (general discrete memoryless sources). In this paper, we consider a new setup where the side information at one receiver is conditionally less noisy than that at the other. The new setup includes degraded side information as a special case, and it is motivated by the literature on degraded and less noisy broadcast channels. Our key contribution is a converse proving the optimality of Heegard and Berger's achievability bound in a new setting, where the side information is conditionally less noisy and one distortion function is deterministic. The less noisy setup is also generalized to two different successive-refinement problems.

We consider the successive refinement of information problem with decoder side information. The rate-distortion region is unknown in general; Steinberg & Merhav and Tian & Diggavi solved it in the special case of degraded side information. We extend this special case to a new setup, conditionally less noisy side information, and we give a single-letter solution when one distortion function is deterministic.

The variant of the Heegard-Berger problem where the receivers require identical reconstructions is studied, and the rate-distortion function for the following three settings is derived: (a) the encoder is also required to generate the reconstructions common to the receivers; (b) the side information at the receivers are physically degraded; and (c) the side information at the receivers are stochastically degraded, and the source satisfies a particular full-support condition. The characterizations indicate that the receiver side information can be fully exploited to perform Wyner-Ziv-style binning. However, the reconstruction functions can depend only on the randomness common to the receivers in the Gács-Körner sense.

We consider a multi-way relay network with an orthogonal uplink and correlated sources, and we characterise reliable communication (in the usual Shannon sense) with a single-letter expression. The characterisation is obtained using a joint source-channel random-coding argument, which is based on a combination of Wyner et al.'s Cascaded Slepian-Wolf Source Coding and Tuncel's Slepian-Wolf Coding over Broadcast Channels. We prove a separation theorem for the special case of two nodes; that is, we show that a modular code architecture with separate source and channel coding functions is (asymptotically) optimal. Finally, we propose a practical coding scheme based on low-density parity-check codes, and we analyse its performance using multi-edge density evolution.

A pair of strings (X,Y) put out by a memoryless source needs to be reliably communicated over a memoryless broadcast channel. Receiver 1 hasYas side information and must reconstructXto within some distortion. Receiver 2 hasXand must reconstructYto within some distortion. The problem is motivated by the broadcast phase (downlink) of the two-way relay channel. We characterize reliable communication for Gaussian sources with quadratic distortion functions; conditionally independent sources; deterministic distortion functions; and small distortions with Hamming distortion functions. The last result is obtained by solving a new version of the broadcast problem with Steinberg's common-reconstruction decoding constraint.

We consider the capacity region of a three receiver broadcast channel with some message cognition at two receivers. The problem generalizes the bi-directional broadcast channel to include a third receiver, a common message, and (partial) message cognition. We characterize the capacity region for several classes of less noisy, more capable, and deterministic broadcast channels.

The multi-way relay channel (MWRC) models cooperative communication networks in which many users exchange messages via a relay. In this paper, we consider the finite field MWRC with correlated messages. The problem is to find all achievable rates, defined as the number of channel uses required per reliable exchange of message tuple. For the case of three users, we have previously established that for a special class of source distributions, the set of all achievable rates can be found [Ong et al., ISIT 2010]. The class is specified by an almost balanced conditional mutual information (ABCMI) condition. In this paper, we first generalize the ABCMI condition to the case of more than three users. We then show that if the sources satisfy the ABCMI condition, then the set of all achievable rates is found and can be attained using a separate source-channel coding architecture.

We consider a lossless multi-terminal source coding problem with one transmitter, two receivers and side information. The achievable rate region of the problem is not well understood. In this paper, we characterise the rate region when the side information at one receiver is conditionally less noisy than the side information at the other, given this other receiver's desired source. The conditionally less noisy definition includes degraded side information and a common message as special cases, and it is motivated by the concept of less noisy broadcast channels. The key contribution of the paper is a new converse theorem employing a telescoping identity and the Csiszár sum identity.

We consider the two-way relay network where two nodes communicate via a relay. We assume that the data at the nodes are correlated (e.g., measurements in a sensor network) and that there is no direct communication between the nodes. The nodes communicate via the relay using a two-phase protocol consisting of an uplink part over an orthogonal multiple access channel and a downlink part over a broadcast channel. The individual codes as well as the overall system can be represented by a joint factor graph consisting of a source code at each node, a channel code for the each uplink and a channel code for the downlink. The optimality of separation of source and channel coding implies that it is optimal to individually design these codes. We focus on low-density parity-check codes where code design corresponds to the optimisation of their degree distributions.

The problem of loss less joint source-channel coding for the two-way relay network with an orthogonal multiple access channel is studied. Necessary and sufficient conditions for reliable communication are given, and a separation theorem for source and channel coding is proved.

The three-user finite field multi-way relay channel with correlated sources is considered. The three users generate possibly correlated messages, and each user is to transmit its message to the two other users reliably in the Shannon sense. As there is no direct link among the users, communication is carried out via a relay, and the link from the users to the relay and those from the relay to the users are finite field adder channels with additive noise of arbitrary distribution. The problem is to determine the set of all possible achievable rates, defined as channel uses per source symbol for reliable communication. For two classes of source/channel combinations, the solution is obtained using Slepian-Wolf source coding combined with functional-decode-forward channel coding.

The rate-distortion (RD) function for source coding with complementary side-information is characterised for several special cases of the general problem. These include Steinberg's common-reconstruction setting, small distortions for both sources, zero distortion for one source, conditionally independent sources, and deterministic distortion measures.

We present an achievable rate region for the multistage successive-refinement problem with side-information. We also present an upper bound for the rate-distortion function for lossy source coding with side-information at many decoders. Characterising this rate-distortion function is a long-standing open problem, and it is widely believed that the tightest upper bound is provided by Theorem 2 of Heegard and Berger's paper “Rate distortion when side information may be absent” (IEEE Trans. Inf. Theory, 1985). We give a counterexample to Heegard and Berger's result.

We consider the problem of transmitting a Gaussian source over a Rayleigh fading channel where some side-information may be available to the receiver. Our objective is to minimize the average distortion at the receiver. We consider two source models with side-information: 1) the Heegard-Berger model where "side-information may be absent", and 2) successive refinement with degraded side-information. We show that the average distortion problem can be numerically solved by convex optimization techniques. Furthermore, in high SNR, we obtain an analytical solution that shows that the side-information does not affect the distortion exponent, but causes an offset with respect to the case without side information. Numerical results show that our analytical high SNR approximation gives accurate results even at medium SNR.

We present a new inner bound for the admissible rate region of the t-stage successive-refinement problem with side-information. We also present a new upper bound for the rate-distortion function for lossy-source coding with multiple receivers and side-information. A single-letter characterisation of this rate-distortion function is a long-standing open problem, and it is widely believed that the tightest upper bound is provided by Theorem 2 of Heegard and Berger's paper “Rate Distortion when Side Information may be Absent,” IEEE Trans. Inform. Theory, 1985. We give a counterexample to Heegard and Berger's result.

A word-valued source Y = Y1,Y2,...is discrete random process that is formed by sequentially encoding the symbols of a random process X = X1,X2,...with codewords from a codebookC. These processes appear frequently in information theory (in particular, in the analysis of source-coding algorithms), so it is of interest to give conditions onXandCfor whichYwill satisfy an ergodic theorem and possess an asymptotic equipartition property (AEP). In this paper, we prove the following: 1) ifXis asymptotically mean stationary (AMS), thenYwill satisfy a pointwise ergodic theorem and possess an AEP; and 2) if the codebookCis prefix-free, then the entropy rate ofYis equal to the entropy rate ofXnormalized by the average codeword length.

Single-letter characterisations of the admissible rate regions of the Gu-Effros two-hop network and the Gray-Wyner network with side-information are open problems. We show that both problems permit single-letter solutions under the assumption of causal side-information. In particular, the special structure of the causal side-information decoder allows one to match converse theorems to known coding theorems using standard information-theoretic tools. This observation complements similar results by Maor and Merhav for the Heegard-Berger problem and the successive-refinement problem with side-information, and suggests that more general results for causal side-information networks may be possible.

We consider the problem of source coding with receiver side information for the simple network proposed by R. Gray and A. Wyner in 1974. In this network, a transmitter must reliably transport the output of two correlated information sources to two receivers using three noiseless channels: a public channel which connects the transmitter to both receivers, and two private channels which connect the transmitter directly to each receiver. We extend Gray and Wyner's original problem by permitting side information to be present at each receiver. We derive inner and outer bounds for the achievable rate region and, for three special cases, we show that the outer bound is tight.

Node mobility and physical channel effects cause the quality of links in wireless networks to fluctuate randomly. At the network layer, these changes are accommodated by the control information (overhead) of routing protocols. We provide lower bounds on the minimum average control overhead of deterministic routing protocols. When routing devices use noisy, out-of-date, or guess topology information, routing errors will occur. The number of "routing errors" experienced by well known routing schemes grows non-trivially with increased estimation noise. Route error growth is a novel characterization of protocol robustness for switched packet networks. This work motivates an information theoretic view of routing protocols