This paper establishes the exact strong converse exponent of the soft covering problem in the classical setting. This exponent characterizes the slowest achievable convergence speed of the total variation to one when a code of rate below mutual information is applied to a discrete memoryless channel for synthesizing a product output distribution. The proposed exponent is expressed through a new two-parameter information quantity, differing from the more commonly studied Rényi divergence or Rényi mutual information. In addition, we demonstrate the non-tightness of random coding for rates both below and above mutual information. Discussions on the latter start with noiseless channels, where we develop a deterministic code construction that outperforms random codes in error exponents. We further observe that the conventional formulation, which assumes a uniform distribution over messages, inherently introduces a discrepancy in error exponents depending on whether the components of the target distribution are rational or irrational numbers. To eliminate this discrepancy, we propose a new formulation in which messages are allowed to be distributed non-uniformly, and the rate is given by the logarithm of the smallest nonzero message probability (corresponding to Rényi entropyH−∞of order −∞). The exact error exponent is characterized in this formulation for noiseless channels. Furthermore, for noisy channels, we provide a high-rate improvement in achievability and derive a converse bound on the error exponent.

We study the problem of transmission of information over classical-quantum (CQ) channels in the one-shot regime where the underlying codes are constrained to be shiftedgroup codes. Given a groupG, a group code of lengthnis a subgroup ofGn. In the achievability part, we introduce a new collection of input probability distributions that incorporates the encoding homomorphism and the underlying channel law. Using a random coding argument, we characterize the performance of group codes in terms of hypothesis testing relative-entropic quantities. In the converse part, we establish bounds by leveraging a hypothesis testing-based approach. Furthermore, we apply the one-shot result to the asymptotic stationary memoryless setting, and establish a single-letter lower bound on thegroup capacityof a CQ channel. Moreover, we derive a matching upper bound on the asymptotic group capacity.

In this paper, by employing a type-based approach, we provide a lower and an upper bound for the strong converse exponent of the soft covering problem in the classical setting. This exponent characterizes the slowest achievable convergence speed of the total variation to one when a code with a rate below mutual information is applied to a discrete memoryless channel for synthesizing a product output distribution. For fully noiseless and fully noisy channels, the proposed bounds can squeeze out an exact exponent.

This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source ($X^{d}, Y^{d}$) generated based on the joint distribution$P_{X, Y}$. The agents wish to produce a pair of discrete random variables$\left(U_{d}, V_{d}\right)$with joint distribution$P_{U_{d}, V_{d}}$, such that$P_{U_{d}, V_{d}}$converges in total variation distance to a target distribution$Q_{U, V}$. Two variations of the standard NISS scenario are considered. In the first variation, in addition to$\left(X^{d}, Y^{d}\right)$, the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with$\left(X^{d}, Y^{d}\right)$to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit$Z$, in addition to ($X^{d}, Y^{d}$). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.

We consider the task of faithfully simulating a quantum measurement, acting on a joint bipartite quantum state, in a distributed manner. In this setup, the constituent sub-systems of the joint quantum state are measured by two agents, Alice and Bob. A third agent, Charlie, receives the measurement outcomes sent by Alice and Bob. Charlie uses local and pairwise shared randomness to compute a bivariate function of the measurement outcomes. The objective of three agents is to faithfully simulate the given distributed quantum measurement acting on the given quantum state while minimizing the communication and shared randomness rates. We demonstrate a new inner bound to the rate region using random structured POVMs based on asymptotically good algebraic codes, and characterize the performance limit using single-letter quantum mutual information quantities. This new bound subsumes the largest known inner bound and improves upon it strictly for identified examples. One of the challenges in analyzing these structured POVMs is that they exhibit only pairwise independence and induce only uniform single-letter distributions. We address these in the non-commutative quantum setting, and provide a two-party distributed faithful simulation and function computation protocol.

The reliability function of a channel is the maximum achievable exponential rate of decay of the error probability as a function of the transmission rate. In this work, we derive bounds on the reliability function of discrete memoryless multiple-access channels (MAC) with noiseless feedback. We show that our bounds are tight for a variety of MACs, such as m-ary additive and two independent point-to-point channels. The bounds are expressed in terms of a new information measure called “variable-length directed information”. The outer bound is proved by analyzing stochastic processes defined based on the entropy of the message, given the past channel’s outputs. Our method relies on tools from the theory of martingales, variable-length information measures, and a new technique called time pruning. We further propose a variable-length achievable scheme consisting of three phases: (i) data transmission, (ii) hybrid data-confirmation, and (iii) full confirmation. We show that two-phase-type schemes are strictly suboptimal in achieving the MAC’s reliability function. Moreover, we study the shape of the lower-bound and show that it increases linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. As side results, we derive an outer bound on the capacity of MAC with noiseless feedback and study a new problem involving a hybrid of hypothesis testing and data transmission.

The rate-limited optimal transport problem is introduced for the continuous-variable quantum measurement systems in the form of output-constrained rate-distortion coding. The main coding theorem provides a single-letter characterization of the achievable rate region for lossy quantum-to-classical source coding that transforms a sufficiently large tensor product of IID continuous-variable quantum states from a quantum source to a sequence of IID samples from a classical continuous destination distribution with a prescribed distortion level. The evaluation of rate region is performed for the systems with quantum Gaussian source and Gaussian destination distribution. We establish a Gaussian observable optimality theorem for such systems and provide an analytical formulation of the rate-limited quantum-classical Wasserstein distance in the case of isotropic and one-mode Gaussian quantum systems.11The proofs of the theorems and the details of the results are provided in the extended online version [1] available at https://arxiv.org/abs/2305.10004 for further reference. This work was supported in part by NSF grants CCF 2007878 and CCF 2132815.

We propose quantum soft covering problems for fully quantum channels and classical-quantum (CQ) channels using relative entropy as a criterion of operator closeness. We prove covering lemmas by deriving one-shot bounds on the rates in terms of smooth min-entropies and smooth max-divergences, respectively. In the asymptotic regime, we show that for quantum channels, the rate infimum defined as the logarithm of the minimum rank of the input state is the coherent information between the reference and output state; for CQ channels, the rate infimum defined as the logarithm of the minimum number of input codewords is the Helovo information between the input and output state. Furthermore, we present a one-shot quantum decoupling theorem with relative entropy criterion. Our results based on the relative-entropy criterion are tighter than the corresponding results based on the trace norm considered in the literature due to the Pinsker inequality.

We study the one-shot channel coding problem over classical and classical-quantum channels, where the underlying codes are constrained to be group codes. In the achievability part, we introduce a new distribution that incorporates the encoding homomorphism and the underlying channel law. Using a random coding argument, we characterize the performance in terms of hypothesis testing relative-entropies. In the converse part, we es-tablish bounds by leveraging a hypothesis testing-based approach. Further we apply the one-shot result to the asymptotic use case and establish the group capacities for both channels.

This work considers an information-theoretic characterization of the set of achievable rates, costs, and distortions in a broad class of distributed communication and function computation scenarios with general continuous-valued sources and channels. A framework is presented which involves fine discretization of the source and channel variables followed by communication over the resulting discretized network. In order to evaluate the resulting achievable regions, convergence results for information measures are provided under the proposed discretization process. Prior works have considered such convergence results for mutual information quantities written in terms of univariate functions of random variables, and sums of independent random variables. These convergence results have been used to derive achievable regions in point-to-point communication scenarios and specific multiterminal scenarios with continuous alphabets. However, the best-known achievability results for distributed communication and function computation scenarios, which are based on structured coding strategies, involve mutual information quantities written in terms of bivariate functions of random variables, e.g., sum of two (not necessarily independent) random variables. A main contribution of this work is to show the convergence of mutual information quantities written in terms of sums of quantized random variables. This is an essential step in evaluating the achievable regions in continuous distributed computation scenarios by generalizing the structured coding strategies which have been previously used to derive the best-known achievable regions in discrete networks. The framework is used to provide achievability results for the problems of function computation over multiple-access channels, distributed source coding, function reconstruction (two-help-one), and multiple-descriptions source coding. In each scenario, discrete structured coding strategies along with the aforementioned convergence results are used to derive inner bounds to set of achievable rates, costs, and distortions. Furthermore, structured coding strategies are considered for distributed function computation scenarios involving computation of non-additive functions. The techniques are used to study an example where the objective is to compute the product of channel inputs over a multiple access channel, and an inner bound to the achievable rate region is evaluated. It is shown that, in contrast to many well-studied scenarios in multiterminal information theory, Gaussian input distribution is outperformed by the uniform input distribution.

We consider the lossy quantum source coding problem, where the task is to compress a given quantum source below its von Neumann entropy. Inspired by the duality connections between the rate-distortion and channel coding problems in the classical setting, we propose a new formulation for the lossy quantum source coding problem. This formulation differs from the existing quantum rate-distortion theory in two aspects. Firstly, we require that the reconstruction of the compressed quantum source fulfill a global error constraint as opposed to the sample-wise local error criterion used in the standard rate-distortion setting. Secondly, to measure the reconstruction error, instead of a distortion observable, we employ the notion of a backward quantum channel which we refer to as a “posterior reference map”. Using these, we characterize the asymptotic performance limit in terms of single-letter coherent information of the given posterior reference map. We also develop analogous formulations for the quantum-classical and classical variants and characterize their asymptotic performance limits in terms of single-letter mutual information quantities with respect to appropriately defined channels analogous to the posterior reference map. We also provide various examples for the three formulations, and shed light on their connection to the standard rate-distortion formulation wherever possible.

We consider the rate-limited quantum-to-classical optimal transport in terms of output-constrained rate-distortion coding for both finite-dimensional and continuous-variable quantum-to-classical systems with limited classical common randomness. The main coding theorem provides a single-letter characterization of the achievable rate region of a lossy quantum measurement source coding for an exact construction of the destination distribution (or the equivalent quantum state) while maintaining a threshold of distortion from the source state according to a generally defined distortion observable. The constraint on the output space fixes the output distribution to an IID predefined probability mass function. Therefore, this problem can also be viewed as information-constrained optimal transport which finds the optimal cost of transporting the source quantum state to the destination classical distribution via a quantum measurement with limited communication rate and common randomness. We develop a coding framework for continuous-variable quantum systems by employing a clipping projection and a dequantization block and using our finite-dimensional coding theorem. Moreover, for the Gaussian quantum systems, we derive an analytical solution for rate-limited Wasserstein distance of order 2, along with a Gaussian optimality theorem, showing that Gaussian measurement optimizes the rate in a system with Gaussian quantum source and Gaussian destination distribution. The results further show that in contrast to the classical Wasserstein distance of Gaussian distributions, which corresponds to an infinite transmission rate, in the Quantum Gaussian measurement system, the optimal transport is achieved with a finite transmission rate due to the inherent noise of the quantum measurement imposed by Heisenberg’s uncertainty principle.

We consider the rate-limited quantum-to-classical optimal transport in terms of output-constrained rate-distortion coding for discrete quantum measurement systems with limited classical common randomness. The main coding theorem provides the achievable rate region of a lossy measurement source coding for an exact construction of the destination distribution (or the equivalent quantum state) while maintaining a threshold of distortion from the source state according to a generally defined distortion observable. The constraint on the output space fixes the output distribution to an i.i.d. predefined probability mass function. Therefore, this problem can also be viewed as information-constrained optimal transport which finds the optimal cost of transporting the source quantum state to the destination state via an entanglement-breaking channel with limited communication rate and common randomness.1

In this work, we address the lossy quantum-classical (QC) source coding problem, where the task is to compress the classical information about a quantum source, obtained after performing a measurement, below the Shannon entropy of the measurement outcomes, while incurring a bounded reconstruction error. We propose a new formulation, namely, "rate-channel theory", for the lossy QC source coding problem based on the notion of a backward (posterior) channel. We employ a single-letter posterior channel to capture the reconstruction error in place of the single-letter distortion observable. The formulation requires the reconstruction of the compressed quantum source to satisfy a block error constraint as opposed to the average single-letter distortion criterion in the rate-distortion setting. We also develop an analogous formulation for the classical variant with respect to a corresponding posterior channel. Furthermore, we characterize the asymptotic performance limit of the lossy QC and classical source coding problems in terms of single-letter quantum mutual information and mutual information quantities of the given posterior channel, respectively. We provide examples for the above formulations.

In general, the generator matrix sparsity is a critical factor in determining the encoding complexity of a linear code. Further, certain applications, e.g., distributed crowdsourcing schemes utilizing linear codes, require most or even all the columns of the generator matrix to have some degree of sparsity. In this paper, we leverage polar codes and the well-established channel polarization to design capacity-achieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a low-complexity decoding algorithm. We first show that given a binary-input memoryless symmetric (BMS) channel$W$and a constant$s \in (0, 1]$, there exists a polarization kernel such that the corresponding polar code is capacity-achieving with the rate of polarization$s/2$, and the GM column weights being bounded from above by$N^{s}$. To improve the sparsity versus error rate trade-off, we devise a column-splitting algorithm and two coding schemes for BEC and then for general BMS channels. The polar-based codes generated by the two schemes inherit several fundamental properties of polar codes with the original$2 \times 2$kernel including the decay in error probability, decoding complexity, and the capacity-achieving property. Furthermore, they demonstrate the additional property that their GM column weights are bounded from above sublinearly in$N$, while the original polar codes have some column weights that are linear in$N$. In particular, for any BEC and$\beta < 0.5$, the existence of a sequence of capacity-achieving polar-based codes where all the GM column weights are bounded from above by$N^{\lambda} $with$\lambda \approx 0.585$, and with the error probability bounded by${\mathcal {O}}(2^{-N^{\beta }})$under a decoder with complexity${\mathcal {O}}(N\log N)$, is shown. The existence of similar capacity-achieving polar-based codes with the same decoding complexity is shown for any BMS channel and$\beta < 0.5$with$\lambda \approx 0.631$.

We consider a scenario wherein two parties Alice and Bob are provided$X_{1}^{n}$and$X_{2}^{n}$– samples that are IID from a PMF$P_{X_{1} X_{2}}$. Alice and Bob can communicate to Charlie over (noiseless) communication links of rates$R_{1}$and$R_{2}$, respectively. Their goal is to enable Charlie generate samples$Y^{n}$such that the triple$(X_{1}^{n},X_{2}^{n},Y^{n})$has a PMF that is close, in total variation, to$\prod P_{X_{1} X_{2} Y}$, enabling the three parties achieve strong coordination. In addition, the three parties may posses pairwise shared common randomness at rates$C_{1}$and$C_{2}$. We address the problem of characterizing the set of rate quadruples$(R_{1},R_{2},C_{1},C_{2})$for which the above goal can be accomplished. We propose a new coding scheme based on random algebraic codes–coset codes in particular–of asymptotically large block-length. We analyze its performance and derive a single-letter information-theoretic inner bound. This bound subsumes the largest known inner bound and improves upon it strictly for identified examples. Our findings build on a variant of soft-covering which generalizes its applicability to the algebraic code ensembles. In addition, we provide an outer bound to the rate region for this three party distributed setup.

We consider the task of distilling local purity from a noisy quantum state ρABC, wherein we provide a protocol for three parties, Alice, Bob and Charlie, to distill local purity (at a rate P) from many independent copies of a given quantum state ρABC. The three parties have access to their respective subsystems of ρABC, and are only allowed to use local unitary operations. In addition, Alice and Bob can communicate with Charlie using a one-way multiple-access dephasing channel of link rates R1and R2, respectively. The objective of the protocol is to minimize the usage of the dephasing channel (in terms of rates R1and R2) while maximizing the asymptotic purity that can be jointly distilled from ρABC. To achieve this, we employ ideas from distributed measurement compression protocols, and in turn, characterize a set of sufficient conditions on (P, R1,R2) in terms of quantum information theoretic quantities such that P amount of purity can be distilled using rates R1and R2.

As a class of state-dependent channels, Markov channels have been long studied in information theory for characterizing the feedback capacity and error exponent. This paper studies a more general variant of such channels where the state evolves via a general stochastic process, not necessarily Markov or ergodic. The states are assumed to be unknown to the transmitter and the receiver, but the underlying probability distributions are known. For this setup, we derive an upper bound on the feedback error exponent and the feedback capacity with variable length codes (VLCs). The bounds are expressed in terms of the directed mutual information and directed relative entropy. The bounds on the error exponent reduce to Burnashev’s expression for discrete memoryless channels. Our method relies on tools from the theory of martingales to analyze a stochastic process defined based on the entropy of the message given the past channel’s outputs.

Let A(n, d) denote the maximum number of code-words in a binary code of length n and minimum Hamming distance d. Deriving upper and lower bounds on A(n, d) has been a subject for extensive research in coding theory. In this paper, we examine upper and lower bounds on A(n, d) in the high-minimum distance regime, in particular, when $d = n/2 - \Theta (\sqrt n )$. We will first provide a lower bound based on a cyclic construction for codes of length n = 2m− 1 and show that $A\left({n,d = n/2 - {2^{c - 1}}\sqrt n }\right) \geq {n^c}$, where c is an integer with 1 ⩽ c ⩽ m/2 − 1. With a Fourier-analytic view of Delsarte’s linear program, novel upper bounds on $A(n,n/2 - \sqrt n ){\text{ and }}A(n,n/2 - 2\sqrt n )$ are obtained, and, to the best of the authors’ knowledge, are the first upper bounds scaling polynomially in n for the regime with $d = n/2 - \Theta (\sqrt n )$.

The paper addresses the fundamental information theoretic limits — in terms of achievable rates and distortions — in a broad class of multiterminal communication scenarios with general continuous-valued sources and channels. A general framework is presented which involves fine discretization of the source and channel variables followed by communication over the resulting discretized network. In order to evaluate fundamental performance limits under the proposed discretization process, convergence results for information measures are provided. The framework is used to study the distributed source coding in source coding, as well as the computation over multiple access channels in channel coding. In each case, a communication scheme is presented, the resulting achievable region is derived, and the region is evaluated for Gaussian sources and channels.

We consider the task of communicating a generic bivariate function of two classical sources over a Classical-Quantum Multiple Access Channel (CQ-MAC). The two sources are observed at the encoders of the CQ-MAC, and the decoder aims at reconstructing a bivariate function from the received quantum state. Inspired by the techniques developed for the classical setting, and employing the technique of simultaneous (joint) decoding developed for the CQ setup, we propose and analyze a coding scheme based on a classical superposition of algebraic structured codes and unstructured codes, and the idea of embedding functions on a prime field. We derive a new set of sufficient conditions that strictly enlarge the largest known set of sources (capable of communicating the bivariate function) for any given CQ-MAC. We provide these conditions in terms of single-letter quantum information-theoretic quantities.

We consider the task of faithfully simulating a distributed quantum measurement, wherein we provide a protocol for the three parties, Alice, Bob and Charlie, to simulate a repeated action of a distributed quantum measurement using a pair of non-product approximating measurements by Alice and Bob, followed by a stochastic mapping at Charlie. The objective of the protocol is to utilize minimum resources, in terms of classical bits needed by Alice and Bob to communicate their measurement outcomes to Charlie, and the common randomness shared among the three parties, while faithfully simulating independent repeated instances of the original measurement. To achieve this, we develop a mutual covering lemma and a technique for random binning of distributed quantum measurements, and, in turn, characterize a set of sufficient communication and common randomness rates required for asymptotic simulatability in terms of single-letter quantum information quantities. In the special case, where the Charlie’s action is restricted to a deterministic mapping, we develop a one-shot performance characterization of the distributed faithful simulation problem. Furthermore, using these results we address a distributed quantum rate-distortion problem, where we characterize the achievable rate distortion region through a single-letter inner bound. Finally, via a technique of single-letterization of multi-letter quantum information quantities, we provide an outer bound for the rate-distortion region.

We consider the task of communicating a generic bivariate function of two classical correlated sources over a Classical-Quantum Multiple Access Channel (CQ-MAC). The two sources are observed at the encoders of the CQ-MAC, and the decoder aims at reconstructing a bivariate function from the received quantum state. We first propose a coding scheme based on asymptotically good algebraic structured codes, in particular, nested coset codes, and provide a set of sufficient conditions for the reconstruction of the function of the sources over a CQ-MAC. The proposed technique enables the decoder to recover the desired function without recovering the sources themselves. We further improve this by employing a coding scheme based on a classical superposition of algebraic structured codes and unstructured codes. This coding scheme allows exploiting the symmetric structure common amongst the sources and also leverage the asymmetries. We derive a new set of sufficient conditions that strictly enlarges the largest known set of sources whose function can be reconstructed over any given CQ-MAC, and identify examples demonstrating the same. We provide these conditions in terms of single-letter quantum information-theoretic quantities.

We consider the task of faithfully simulating a distributed quantum measurement and function computation, and demonstrate a new achievable rate-region. For this, we develop the technique of randomly generating algebraic structured POVMs. To overcome the challenges caused by algebraic construction, we develop (i) a Pruning Trace inequality which is a tighter version of the known operator Markov inequality and (ii) a covering lemma which does not require the operator Chernoff inequality and hence applicable to pairwise-independent codewords. We demonstrate rate gains for this problem over traditional coding schemes and provide a multi-party distributed faithful simulation and function computation protocol.

We consider the problem of communicating a general bivariate function of two classical sources observed at the encoders of a classical-quantum multiple access channel. Building on the techniques developed for the case of a classical channel, we propose and analyze a coding scheme based on coset codes. The proposed technique enables the decoder recover the desired function without recovering the sources themselves. We derive a new set of sufficient conditions that are weaker than the current known for identified examples. This work is based on a new ensemble of coset codes that are proven to achieve the capacity of a classical-quantum point-to-point channel.

We consider the problem of characterizing an inner bound to the capacity region of a 3—user classical-quantum interference channel (3—CQIC). The best known coding scheme for communicating over CQICs is based on unstructured random codes and employs the techniques of message splitting and superposition coding. For classical 3—user interference channels (ICs), it has been proven that coding techniques based on coset codes - codes possessing algebraic closure properties - strictly outperform all coding techniques based on unstructured codes. In this work, we develop analogous techniques based on coset codes for 3to1—CQICs - a subclass of 3—user CQICs. We analyze its performance and derive a new inner bound to the capacity region of 3to1—CQICs that subsume the current known largest and strictly enlarges the same for identified examples.

In this problem, Alice and Bob, are provided$X_{1}^{n}$and$X_{2}^{n}$that are IID$px_{1}x_{2}$. Alice and Bob can communicate to Charles over (noiseless) links of rate$R_{1}$and$R_{2}$, respectively. Their goal is to enable Charles generate samples$Y^{n}$such that the triple$(X_{1}^{n},\ X_{2}^{n},\ Y^{n})$has a PMF that is close, in total variation, to$\prod p_{X_{1}X_{2}\mathrm{Y}}$. In addition, the three parties may posses shared common randomness at rate$C$. We address the problem of characterizing the set of rate triples$(R_{1},\ R_{2},\ C)$for which the above goal can be accomplished. We build on our recent findings and propose a new coding scheme based on coset codes. We analyze its information-theoretic performance and derive a new inner bound. We identify examples for which the derived inner bound is analytically proven to contain rate triples that are not achievable via any known unstructured code based coding techniques. Our findings build on a variant of soft-covering which generalizes its applicability to the algebraic structured code ensembles. This adds to the advancement of the use structured codes in network information theory.

In this work, lossy distributed compression of a pair of correlated sources is considered. Conventionally, Shannon's random coding arguments - using randomly generated unstructured codebooks whose blocklength is taken to be asymptotically large - are used to derive achievability results. However, in some multi-terminal communications scenarios, using random codes with constant finite blocklength in certain coding architectures leads to improved achievable regions compared to the conventional approach. In other words, in some network communication scenarios, there is a finite optimal value in the blocklength of the randomly generated code used for distributed processing of information sources. Motivated by this, a coding scheme is proposed which consists of two codebook layers: i) the primary codebook which has constant finite blocklength, and ii) the secondary codebook whose blocklength is taken to be asymptotically large. The achievable performance is analyzed in two steps. In the first step, a characterization of an inner bound to the achievable region is derived in terms information measures which are functions of multi-letter probability distributions. In the next step, a computable single-letter inner-bound to the achievable region is extracted. It is shown through an example that the resulting rate-distortion region is strictly larger than the Berger-Tung achievable region.

We consider the problem of decentralized sequential active hypothesis testing (DSAHT), where two transmitting agents, each possessing a private message, are actively helping a third agent-and each other-to learn the message pair over a discrete memoryless multiple access channel (DM-MAC). The third agent (receiver) observes the noisy channel output, which is also available to the transmitting agents via noiseless feedback. We formulate this problem as a decentralized dynamic team, show that optimal transmission policies have a time-invariant domain, and characterize the solution through a dynamic program. Several alternative formulations are discussed involving time-homogenous cost functions and/or variable-length codes, resulting in solutions described through fixed-point, Bellman-type equations. Subsequently, we make connections with the problem of simplifying the multi-letter capacity expressions for the noiseless feedback capacity of the DM-MAC. We show that restricting attention to distributions induced by optimal transmission schemes for the DSAHT problem, without loss of optimality, transforms the capacity expression, so that it can be thought of as the average reward received by an appropriately defined stochastic dynamical system with time-invariant state space.

We consider a scenario wherein two parties Alice and Bob are provided X1nand X2n-samples that are IID from a PMF pX1X2. Alice and Bob can communicate to Charles over (noiseless) communication links of rate R1and R2respectively. Their goal is to enable Charles generate samples Ynsuch that the triple (X1n, X2nYn). In addition, the three parties may posses shared common randomness at rate C. We address the problem of characterizing the set of rate triples (R1, R2, C) for which the above goal can be accomplished. We provide a set of sufficient conditions, i.e., an achievable rate region for this three party setup. Our work also provides a complete characterization of a point-to-point setup wherein Bob is absent and Charles is provided with side-information.

In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binary-input memoryless symmetric (BMS) channel and any ε> 2ε*, where ε8 = 1/6 - [5/3log4/3] ≈ 0.085, we show an explicit sequence of capacity-achieving codes with all the column weights of the generator matrix upper bounded by (log N)1+ε, where N is the code block length. The constructions are based on polar codes. Applications to crowdsourcing are also shown.

In this work, we study two problems: three-user Multiple-Access Channel (MAC) with correlated sources, and MAC with Feedback (MAC-FB) with independent messages. For the first problem, we identify a structure in the joint probability distribution of discrete memoryless sources, and define a new common information called “conferencing common information”. We develop a multi-user joint-source channel coding methodology based on structured mappings to encode this common information efficiently and to transmit it over a MAC. We derive a new set of sufficient conditions for this coding strategy using single-letter information quantities for arbitrary sources and channel distributions. Next, we make a fundamental connection between this problem and the problem of communication of independent messages over three-user MAC-FB. In the latter problem, although the messages are independent to begin with, they become progressively correlated given the channel output feedback. Subsequent communication can be modeled as transmission of correlated sources over MAC. Exploiting this connection, we develop a new coding scheme for the problem. We characterize its performance using single-letter information quantities, and derive an inner bound to the capacity region. For both problems, we provide a set of examples where these rate regions are shown to be optimal. Moreover, we analytically prove that this performance is not achievable using random unstructured random mappings/codes.

We investigate faithful simulation of distributed quantum measurements as an extension of Winter's measurement compression theorem. We characterize a set of communication and common randomness rates needed to provide faithful simulation of distributed measurements. To achieve this, we introduce binning and mutual packing lemma for distributed quantum measurements. These techniques can be viewed as the quantum counterpart of their classical analogues. Finally, using these results, we develop a distributed quantum-to-classical rate distortion theory and characterize a rate region analogous to Berger-Tung's in terms of single-letter quantum mutual information quantities.

This paper considers the problem of approximating a Boolean function f using another Boolean function from a specified class. Two classes of approximating functions are considered: k-juntas, and linear Boolean functions. The n input bits of the function are assumed to be independently drawn from a distribution that may be biased. The quality of approximation is measured by the mismatch probability between f and the approximating function g. For each class, the optimal approximation and the associated mismatch probability is characterized in terms of the biased Fourier expansion of f. The technique used to analyze the mismatch probability also yields an expression for the noise sensitivity of f in terms of the biased Fourier coefficients, under a general i.i.d. input perturbation model.

This paper models the crowdsourced labeling/classification problem as a sparsely encoded source coding problem, where each query answer, regarded as a code bit, is the XOR of a small number of labels, as source information bits. In this paper we leverage the connections between this problem and well-studied codes with sparse representations for the channel coding problem to provide querying schemes with almost optimal number of queries, each of which involving only a constant number of labels. We also extend this scenario to the case where some workers can be unresponsive. For this case, we propose querying schemes where each query involves only log n items, where n is the total number of items to be labeled. Furthermore, we consider classification of two correlated labeling systems and provide two-stage querying schemes with almost optimal number of queries each involving a constant number of labels.

In this paper, we establish a new bound tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper bound on the correlation between the outputs of these functions. The upper bound may find applications in problems in many areas which deal with common information. We build upon Witsenhausen's result [1] on maximum correlation. The present upper bound takes into account the effective length of the Boolean functions in characterizing the correlation. We use the new bound to characterize the communication-cooperation tradeoff in multi-terminal communications. We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider an ensemble of BBCs which is randomly generated using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to bound the correlation between the outputs of two distributed BBCs. Finally, the upper bound is used to show that the large blocklength single-letter coding schemes studied in the literature are sub-optimal in various multi-terminal communication settings.

A new class of structured codes called quasi group codes (QGCs) is introduced. A QGC is a subset of a group code. In contrast with the group codes, QGCs are not closed under group addition. The parameters of the QGC can be chosen, such that the size of C + C is equal to any number between C and |C|2. We analyze the performance of a specific class of QGCs. This class of QGCs is constructed by assigning single-letter distributions to the indices of the codewords in a group code. Then, the QGC is defined as the set of codewords whose index is in the typical set corresponding to these singleletter distributions. The asymptotic performance limits of this class of QGCs are characterized using single-letter information quantities. Corresponding covering and packing bounds are derived. It is shown that the point-to-point channel capacity and optimal rate-distortion function are achievable using QGCs. Coding strategies based on QGCs are introduced for three fundamental multi-terminal problems: the Körner-Marton problem for modulo prime-power sums, computation over the multiple access channel (MAC), and MAC with distributed states. For each problem, a single-letter achievable rate-region is derived. It is shown, through examples, that the coding strategies improve upon the previous strategies based on the unstructured codes, linear codes, and group codes.

In this paper we consider the information-theoretic characterization of performance limits of a broad class of multiterminal communication problems with general continuous-valued sources and channels. In particular, we consider point- to-point source coding and channel coding with side information, distributed source coding with distortion constraints and function reconstruction problems (two-help-one). We develop an approach that uses fine quantization of the source and the channel variables followed by random coding with unstructured as well as structured (linear) code ensembles. This approach leads to lattice-like codes for general sources and channels.

In this paper, we investigate the necessity of finite blocklength codes in distributed transmission of independent message sets over channels with feedback. We provide two examples of three user interference channels with feedback where codes with asymptotically large effective lengths are sub-optimal. As a result, we conclude that coded transmission using finite effective length codes is necessary to achieve optimality. We argue that the sub-optimal performance of large effective length codes is due to their inefficiency in preserving the correlation between the inputs to the distributed terminals in the communication system. This correlation is made available by the presence of feedback at the terminals and is used as a means for coordination between them when using finite effective length coding strategies.

We derive a lower and upper bounds on the reliability function of discrete memoryless multiple-access channel (MAC) with noiseless feedback and variable-length codes (VLCs). For the upper-bound, we use proof techniques of Burnashev for the point-to-point case. Also, we adopt the techniques used to prove the converse for the feedback-capacity of MAC. For the lower-bound on the error exponent, we present a coding scheme consisting of a data and a confirmation stage. In the data stage, any arbitrary feedback capacity-achieving code is used. In the confirmation stage, each transmitter sends one bit of information to the receiver using a pair of codebooks of size two, one for each transmitter. The codewords at this stage are selected randomly according to an appropriately optimized joint probability distribution. The bounds increase linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. The lower and upper bounds match for a class of MACs.

We consider the problem of multiple descriptions (MDs) source coding and propose new coding strategies involving both unstructured and structured coding layers. Previously, the most general achievable rate-distortion (RD) region for the l -descriptions problem was the combinatorial message sharing with binning (CMSB) region. The CMSB scheme utilizes unstructured quantizers and unstructured binning. In the first part of the paper, we show that this strategy can be improved upon using more general unstructured quantizers and a more general unstructured binning method. In the second part, structured coding strategies are considered. First, structured coding strategies are developed by considering the specific MD examples involving three or more descriptions. We show that the application of structured quantizers results in strict RD improvements when there are more than two descriptions. Furthermore, we show that a structured binning also yields improvements. These improvements are in addition to the ones derived in the first part of the paper. This suggests that structured coding is essential when coding over more than two descriptions. Using the ideas developed through these examples, we provide a new unified coding strategy by considering several structured coding layers. Finally, we characterize its performance in the form of an inner bound to the optimal RD region using computable single-letter information quantities. The new RD region strictly contains all of the previous known achievable regions.

We consider the problem of developing coding techniques and deriving achievable rate regions for discrete memoryless broadcast channels with three receivers (3-DBC). We begin by identifying a novel vector additive 3-DBC for which we characterize an upper bound on the the largest achievable rate region based on unstructured codes, henceforth referred to as 1 M-region. We propose a coding technique based on coset codes that yield an achievable rate triple not contained within 1 M-region. We generalize the proposed coding technique using a new ensemble of codes-partitioned coset codes (PCC)-containing both empirical and algebraic properties, and evaluate its performance to derive an achievable rate region for the general 3-DBC. The new elements in this derivation are binning and joint typicality encoding and decoding of statistically correlated PCCs. We validate the utility of this technique by identifying non-additive instances of 3-DBC for which the proposed coding techniques based on PCC yield strictly larger rates.

The group capacity of a discrete memoryless channel$(\mathcal {X},\mathcal {Y},W_{Y|X})$is characterized with maximal probability of error in of[1, Sec. II]. There is a mistake in the proof of achievability as given in Section VII.A. It is correctly shown on page 2408–2409 that\begin{equation*} \lim _{n \rightarrow \infty } \max _{a} \mathbb {E} \left [{ P(E(a)) }\right ] =0 \end{equation*}if for all$\hat {\theta } \neq \boldsymbol {s}$,\begin{align*}&\hspace {-0.5pc}R \frac {\sum _{(p,s)\in \mathcal {S}(G)} (s- \hat {\theta }_{p,s}) w_{p,s} \log p}{\sum _{(p,s) \in \mathcal {S} (G)} s w_{p,s} \log q} \\&\qquad \qquad \quad \qquad <\log |H_{\eta ^{*}+\hat {\theta }}|-H(X_{\eta ^{*},b}|Y,[X_{\eta ^{*},b}]_{\hat {\theta }}) - O(\epsilon ). \end{align*}However it is incorrectly claimed that the achievability conditions are: for all$\hat {\theta } \neq \pmb {s}$,\begin{equation*} R\le \frac {1}{1-\omega _{\hat {\theta }}} I(X_{\eta ^{*},b};Y|[X_{\eta ^{*},b}]_{\hat {\theta }}). \end{equation*}Our original objective was to characterize the average error group capacity of a discrete memoryless channel. The average error is more widely used than the maximal error. Although we had the proof of achievability for the average error case, we could not prove the converse. So we settled for characterizing the maximal error group capacity. In light of the above error, we have the following resolution.

In this paper, we establish a new inequality tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper-bound on the correlation between the outputs of these functions. The upper-bound is useful in various disciplines which deal with common-information. We build upon Witsenhausen's [2] bound on maximum-correlation. The previous upper-bound did not take the effective length of the Boolean functions into account. One possible application of the new bound is to characterize the communication-cooperation tradeoff in multi-terminal communications. In this problem, there are lower-bounds on the effective length of the Boolean functions due to the rate-distortion constraints in the problem, as well as lower bounds on the output correlation at different nodes due to the multi-terminal nature of the problem.

We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider BBCs which are generated randomly, and using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to upper-bound the correlation between the outputs of two distributed BBCs. Finally, the upper-bound is used to show that the large blocklength single-letter coding schemes in the literature are sub-optimal in some multiterminal communication settings.

The problem of reliable communication over the multiple-access channel (MAC) with states is investigated. We propose a new coding scheme for this problem which uses quasi-group codes (QGC). We derive a new computable single-letter characterization of the achievable rate region. As an example, we investigate the problem of doubly-dirty MAC with modulo-4 addition. It is shown that the sum rate R1+ R2=1 bits per channel use is achievable using the new scheme. Whereas, the natural extension of the Gel'fand-Pinsker scheme, sum-rates greater than 0.32 are not achievable.

The problem of three-user multiple-access channel (MAC) with noiseless feedback is investigated. A new coding strategy is presented. The coding scheme builds upon the natural extension of the Cover-Leung (CL) scheme [1]; and uses quasi-linear codes. A new single-letter achievable rate region is derived. The new achievable region strictly contains the CL region. This is shown through an example. In this example, the coding scheme achieves optimality in terms of transmission rates. It is shown that any optimality achieving scheme for this example must have a specific algebraic structure. Particularly, the codebooks must be closed under binary addition.

A new ensemble of structured codes is introduced. These codes are called Quasi Linear Codes (QLC). The QLC's are constructed by taking subsets of linear codes. They have a looser structure compared to linear codes and are not closed under addition. We argue that these codes provide gains in terms of achievable Rate-Distortions (RD) in different multi-terminal source coding problems. We derive the necessary covering bounds for analyzing the performance of QLC's. We then consider the Multiple-Descriptions (MD) problem, and prove through an example that the application of QLC's gives an improved achievable RD region for this problem. Finally, we derive an inner bound to the achievable RD region for the general MD problem which strictly contains all of the previous known achievable regions.

We consider the problem of coding over the multiuser Interference Channel (IC). It is well-known that aligning the interfering signals results in improved achievable rates in certain setups involving more than two users. We argue that in the general interference problem, senders face a tradeoff between communicating their message to their corresponding decoder or cooperating with other users by aligning their signals. Traditionally, interference alignment is carried out using structured codes such as linear codes and group codes. We show through an example that the usual structured coding schemes used for interference neutralization lack the necessary flexibility to optimize this tradeoff. Based on this intuition, we propose a new class of codes for this problem. We use the example to show that the application of these codes gives strict improvements in terms of achievable rates. Finally, we derive a new achievable region for the three user IC which strictly improves upon the previously known inner bounds for this problem.

The problem of three-user Multiple-Access Channel (MAC) with correlated sources is investigated. An extension to the Cover-El Gamal-Salehi (CES) scheme is introduced. We argue that if the sources impose certain algebraic structures, then the application of structured codes improves upon the CES scheme. Based on this notion, we use a combination of the CES scheme with linear codes, and propose a new coding strategy. We derive new sufficient conditions to transmit correlated sources reliably. We consider an example of a three-user MAC with binary inputs. Using this example, we show strict improvements over the CES scheme.

The problem of computing modulo prime-power sums is investigated in distributed source coding as well as computation over Multiple-Access Channel (MAC). We build upon group codes and present a new class of codes called Quasi Group Codes (QGC). A QGC is a subset of a group code. These codes are not closed under the group addition. We investigate some properties of QGC's, and provide a packing and a covering bound. Next, we use these bounds to derived achievable rates for distributed source coding as well as computation over MAC. We show that strict improvements over the previously known schemes can be obtained using QGC's.

We consider the problem of communication over a three-user discrete memoryless interference channel (3-IC). The current known coding techniques for communicating over an arbitrary 3-IC are based on message splitting, superposition coding, and binning using independent and identically distributed (i.i.d.) random codebooks. In this paper, we propose a new ensemble of codes-partitioned coset codes (PCCs)-that possess an appropriate mix of empirical and algebraic closure properties. We develop coding techniques that exploit the algebraic closure property of PCC to enable interference alignment over general 3-IC. We analyze the performance of the proposed coding technique to derive an achievable rate region for the general discrete 3-IC. Additive and non-additive examples are identified for which the derived achievable rate region is the capacity, moreover, strictly larger than the current known largest achievable rate regions based on the i.i.d. random codebooks.

A new coding scheme for the L-descriptions problem is proposed. In particular we consider continuous sources and lattice quantizers. New covering and packing bounds for using nested lattices are derived. We prove through an example that using nested lattice quantizers instead of independently generated codebooks results in gains.

A new structured coding scheme based on transversal group codes is proposed. We investigate the information theoretic performance limits for this strategy in multi-terminal communications. Achievability results are derived for lossless reconstruction of sum of two sources. In addition, a new rate region is presented for the problem of computation over multiple access channel. We show that the application of the new coding strategy, results in strict gains in terms of achievable rates in both settings.

We present a case for the use of codes possessing algebraic closure properties - coset codes - in developing coding techniques and characterizing achievable rate regions for generic multi-terminal channels. In particular, we consider three diverse communication scenarios - 3-user interference channel (many-to-many), 3-user broadcast channel (one-to-many), and multiple access with distributed states (many-to-one) - and identify non-additive examples for which coset codes are analytically proven to yield strictly larger achievable rate regions than those achievable using IID codes. On the one hand, our findings motivate the need for multi-terminal information theory to step beyond IID codes. On the other, it encourages current research of linear code-based techniques to go beyond particular additive communication channels. Detailed proofs of our results are available in [1]-[3].

The problem of bounding the reliability function of a multiple access channel (MAC) is studied. Two new upper bounds on the error exponent of a two-user discrete memoryless (DM)-MAC are derived. The first bound (sphere packing) is an upper bound on the exponent of the average probability of error and is the first bound of this type that is zero outside the capacity region and thus results in a tighter sphere-packing exponent when compared with the tightest known exponent derived by Haroutunian. The second bound (minimum distance) is an upper bound on the exponent of the maximal (as opposed to average) probability of error. To obtain this bound, first, an upper bound on the minimum Bhattacharyya distance between codeword pairs is derived. For a certain class of two-user DM-MACs, an upper bound on the exponent of maximal probability of error is derived as a consequence of the upper bound on the minimum Bhattacharyya distance. We analytically evaluate the sphere packing bound for uniform composition codes for an additive and nonsymmetric channel and show that it is tight near the boundary of the capacity region, i.e., equal to the random coding lower bound.

In this paper, we study the asymptotic performance of Abelian group codes for the channel coding problem for arbitrary discrete (finite alphabet) memoryless channels as well as the lossy source coding problem for arbitrary discrete (finite alphabet) memoryless sources. For the channel coding problem, we find the capacity characterized in a single-letter information-theoretic form. This simplifies to the symmetric capacity of the channel when the underlying group is a field. For the source coding problem, we derive the achievable rate-distortion function that is characterized in a single-letter information-theoretic form. When the underlying group is a field, it simplifies to the symmetric rate-distortion function. We give several illustrative examples. Due to the nonsymmetric nature of the sources and channels considered, our analysis uses a synergy of information-theoretic and group-theoretic tools.

A multiple-descriptions (MD) coding strategy is proposed and an inner bound to the achievable rate-distortion region is derived for discrete memoryless sources. The scheme utilizes linear codes. It is shown in two different MD set-ups that the linear coding scheme achieves a larger rate-distortion region than previously known random coding strategies. Furthermore, it is shown via an example that the best known random coding scheme for the set-up can be improved by including additional randomly generated codebooks.

A new coding scheme for the distributed source coding problem for general discrete memoryless sources is presented. The scheme involves a two-layered coding strategy, the first layer code is of constant finite block-length whereas the second layer contains codes of block-length approaching infinity. It is argued that small block-length codes preserve correlations between sources more efficiently, while suffering rate-loss in a point-to-point compression perspective. Consequently, there is a sweet-spot for the length of the code. An achievable rate-distortion region is characterized using single-letter distributions. It is shown that this region strictly contains previous known achievable rate-distortion regions for the distributed source coding problem.

It is shown that polar coding schemes achieve the known achievable rate regions for several multi-terminal communications problems including lossy distributed source coding, multiple access channels and multiple descriptions coding. The results are valid for arbitrary alphabet sizes (binary or non-binary) and arbitrary distributions (symmetric or asymmetric).

A unified approach is presented for the derivation of reliability function lower bounds for the two-user discrete memoryless (DM) multiple-access channel (MAC). In particular, three lower bounds are presented. The first one (random coding) is identical to the best known lower bound on the reliability function of DM-MACs. It is shown that the random coding bound characterizes the performance of the average code in the constant-type code ensemble. The second bound (typical random coding) characterizes the typical performance (the performance of a high probability subset of the ensemble) of the constant-type code ensemble. To derive the third bound (expurgated), we eliminate some of the codewords from each of the codebooks. This is the first bound of this type that explicitly uses the method of expurgation for DM-MACs. It is shown that the exponent of the typical random coding and the expurgated bounds are greater than or equal to the exponent of the known random coding bounds for all rate pairs. Moreover, an example is given where the exponent of the expurgated bound is strictly larger for a certain input distribution. Each of the presented bounds is universal in the sense that there exists a code that attains the bound for all channels with given input and output alphabets. The approach presented for the DM-MAC is first demonstrated for the point-to-point discrete memoryless channel (DMC), by rederiving the random coding and expurgated exponents, and deriving a bound that characterizes the typical performance of the constant-type code ensemble.

We introduce a scheme for the binary one-help-one distributed source coding problem using two layers of codes. The primary code is of constant finite block-length and the secondary code has a block-length approaching infinity. The achievable rate-distortion region for this scheme is derived for the binary one-help-one problem. It is shown that the scheme achieves the common component rate-distortion region in the case when the sources have a common component, while if a common component is not present (i.e. replaced with highly correlated functions of the two inputs) it improves upon existing achievable bounds. We show that as the block-length of the primary code is increased, the transmission rate required in the scheme decreases, reaches its minimum at some finite value and then increases. This phenomenon is not typically seen in traditional schemes used in multi-terminal source coding.

We present an achievable rate region for the general three user discrete broadcast channel (DBC), based on coset codes. We identify an example of a three user DBC for which the proposed achievable rate region strictly enlarges that obtained by a natural extension of Marton's [1] rate region. As a step towards deriving the achievable rate region for the general three user DBC, we characterize and derive an achievable rate region for a new class - 3-to-1 DBC- of broadcast channels of which the aforementioned is an example.

We prove that the ensemble of the nested coset codes built on finite fields achieves the capacity of arbitrary discrete memoryless point-to-point channels. Exploiting its algebraic structure, we develop a coding technique for communication over general discrete multiple access channel with channel state information distributed noncausally at the transmitters. We build an algebraic coding framework for this problem using the ensemble of Abelian group codes and, thereby, derive a new achievable rate region. We identify non-additive and non-symmetric examples for which the proposed achievable rate region is strictly larger than the one achievable using random unstructured codes.

Let X1, ..., Xmbe a set of m statistically dependent sources over the common alphabet Fq, that are linearly independent when considered as functions over the sample space. We consider a distributed function computation setting in which the receiver is interested in the lossless computation of the elements of an s-dimensional subspace W spanned by the elements of the row vector [X1, ..., Xm]Γ in which the (m × s) matrix Γ has rank s. A sequence of three increasingly refined approaches is presented, all based on linear encoders. The first approach uses a common matrix to encode all the sources and a Korner-Marton like receiver to directly compute W. The second improves upon the first by showing that it is often more efficient to compute a carefully chosen superspace U of W. The superspace is identified by showing that the joint distribution of the {Xi} induces a unique decomposition of the set of all linear combinations of the {Xi}, into a chain of subspaces identified by a normalized measure of entropy. This subspace chain also suggests a third approach, one that employs nested codes. For any joint distribution of the {Xi} and any W, the sum-rate of the nested code approach is no larger than that under the Slepian-Wolf (SW) approach. Under the SW approach, W is computed by first recovering each of the {Xi}. For a large class of joint distributions and subspaces W, the nested code approach is shown to improve upon SW. Additionally, a class of source distributions and subspaces are identified, for which the nested-code approach is sum-rate optimal.

This paper establishes rates attainable by several lossy schemes for coding a continuous parameter source to a specified mean-squared-error distortion based on sampling at asymptotically large rates. First, a densely sampled, spatiotemporal, stationary Gaussian source is distributively encoded. The Berger–Tung bound to the distributed rate-distortion function and three convergence theorems are used to obtain an upper bound, expressed in terms of the source spectral density, to the smallest attainable rate at asymptotically large sampling rates. The bound is tighter than that recently obtained by KashyapBoth indicate that with ideal distributed lossy coding, dense sensor networks can efficiently sense and convey a field, in contrast to the negative result obtained by Marcofor encoders based on scalar quantization and Slepian–Wolf distributed lossless coding. The second scheme is transform coding with scalar coefficient quantization. A new generalized transform coding analysis, as well as the aforementioned convergence theorems, is used to find the smallest attainable rate at asymptotically large sampling rates in terms of the source spectral density and the operational rate-distortion function of the family of quantizers, which in contrast to previous analyses need not be convex. The result shows that when a transform is used, scalar quantization need not cause the poor performance found by MarcoAs a corollary, the final result pursues an approach, originally proposed by Berger, to show that the inverse water-pouring formula for the rate-distortion function can be attained at high sampling rates by transform coding with ideal vector quantization to encode the coefficients. Also established in the paper are relations between operational rate-distortion and distortion-rate functions for a continuous parameter source and those for the discrete parameter source that results from sampling.

It is shown that polar codes, with their original (u,u+v) kernel, achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes. It is shown that in general, channel polarization happens in several, rather than only two levels so that the synthesized channels are either useless, perfect or “partially perfect.” Any subset of the channel input alphabet which is closed under addition induces a coset partition of the alphabet through its shifts. For any such partition of the input alphabet, there exists a corresponding partially perfect channel whose outputs uniquely determine the coset to which the channel input belongs. By a slight modification of the encoding and decoding rules, it is shown that perfect transmission of certain information symbols over partially perfect channels is possible. Our result is general regarding both the cardinality and the algebraic structure of the channel input alphabet; i.e., we show that for any channel input alphabet size and any Abelian group structure on the alphabet, polar codes are optimal. Due to the modifications, we make to the encoding rule of polar codes, the constructed codes fall into a larger class of structured codes called nested group codes.

A single-letter achievable rate region is proposed for the two-receiver discrete memoryless broadcast channel with generalized feedback. The coding strategy involves block-Markov superposition coding using Marton's coding scheme for the broadcast channel without feedback as the starting point. If the message rates in the Marton scheme are too high to be decoded at the end of a block, each receiver is left with a list of messages compatible with its output. Resolution information is sent in the following block to enable each receiver to resolve its list. The key observation is that the resolution information of the first receiver is correlated with that of the second. This correlated information is efficiently transmitted via joint source-channel coding, using ideas similar to the Han-Costa coding scheme. Using the result, we obtain an achievable rate region for the stochastically degraded additive white Gaussian noise broadcast channel with noisy feedback from only one receiver. It is shown that this region is strictly larger than the no-feedback capacity region.

It is well known that for discrete-time, stationary sources, most lossy source coding techniques have operational rate-distortion functions that approach the Shannon ratedistortion function with respect to squared error to within an additive constant as distortion approaches zero. With the goal of investigating similar phenomena for continuous-time sources, this paper investigates the low-distortion performance of distributed coding of continuous-time, stationary, Gaussian sources based on high-rate sampling. It is found that for bandlimited sources and nonbandlimited sources whose spectra have sufficiently light, e.g., exponentially decreasing, tails, distributed source coding is asymptotically as good as centralized coding in the small distortion regime. On the other hand, for spectra with tails that decay as a power (greater than one) of frequency, it is found that for small distortions the distributed rate-distortion function is a constant times larger than the Shannon rate-distortion, where the constant decreases as the power increases. For example, it is approximately 1.2 when the power is 2. The conclusion is that for a stationary Gaussian source and asymptotically small distortion, the ratio of the distributed to centralized rate-distortion function is a function of the weight of the tail of the source spectrum. In the process of finding the ratio, the low distortion form of the centralized rate-distortion function is found for sources whose spectra have exponential and power law tails.

The 3-user discrete memoryless interference channel is considered in this paper. We provide a new inner bound (achievable rate region) to the capacity region for this channel. This inner bound is based on a new class of code ensembles based on asymptotically good nested linear codes. This achievable region is strictly superior to the straightforward extension of Han-Kobayashi rate region from the case of two-users to three-users. This rate region is characterized using single-letter information quantities. We consider examples to illustrate the rate region.

In this paper, we show that nested lattice codes achieve the capacity of arbitrary continuous channels with or without non-causal state information at the transmitter. We also show that nested lattice codes are optimal for source coding with or without non-causal side information at the receiver for arbitrary continuous sources. We show the optimality of lattice codes for the Gelfand-Pinsker and Wyner-Ziv problems in their most general settings.

In this paper, we show that good structured codes over non-Abelian groups do exist. Specifically, we construct codes over the smallest non-Abelian group D6and show that the performance of these codes is superior to the performance of Abelian group codes of the same alphabet size. This promises the possibility of using non-Abelian codes for multi-terminal settings where the structure of the code can be exploited to gain performance. We also show that for the problem of computation over MAC, these codes are superior to random codes in certain cases.

With mean-squared error D as a goal, it is well known that one may approach the rate-distortion function R(D) of a nonbandlimited, continuous-time Gaussian source by sampling at a sufficiently high rate, applying the Karhunen-Loeve transform to sufficiently long blocks, and then independently coding the transform coefficients of each type. Motivated by the question of the efficiency of dense sensor networks for sampling, encoding and reconstructing spatial random fields, this paper studies the following three cases. In the first, we consider a centralized encoding setup with a sample-transform-quantize scheme where the quantization is assumed to be optimal. In the second, we consider a distributed setup, where a spatio-temporal source is sampled and distributively encoded to be reconstructed at a receiver. We show that with ideal distributed lossy coding, dense sensor networks can efficiently sense and convey a field, in contrast to the negative result obtained by Marco et al. for encoders based on time- and space-invariant scalar quantization and ideal Slepian-Wolf distributed lossless coding. In the third, we consider a centralized setup, with a sample-and-transform coding scheme in which ideal coding of coefficients is replaced by coding with some specified family of quantizers. It is shown that when the sampling rate is large, the operational rate-distortion function of such a scheme comes within a finite constant of that of the first case.

In several multi-terminal communication systems, it has been noted that the average performance of linear code ensemble is better than that of the standard unstructured code ensemble. However, it is well-known that linear code ensembles cannot achieve the point-to-point capacity of an arbitrary discrete memoryless channel. In this paper, we study nested linear codes and prove they achieve capacity of arbitrary discrete memoryless point to point channel with and without channel state information at the transmitter. Furthermore, we prove nested linear codes achieve Marton's inner bound, the largest known inner bound for the general discrete broadcast channel.

For most discrete memoryless channels, there does not exist a linear code which uses all of the channel's input symbols. Therefore, linearity of the code for such channels is a very restrictive condition and there should be a loosening of the algebraic structure of the code to a degree that the code can admit any channel input alphabet. For any channel input alphabet size, there always exists an Abelian group structure defined on the alphabet. We investigate the capacity of Abelian group codes over discrete memoryless channels and provide lower and upper bounds on the capacity.

In wireless communication systems, users with heterogeneous information content constrain the network by having different reliability requirements. In this paper an information-theoretic framework is proposed to study communication systems which provide heterogeneous reliabilities for the users. This is done by defining individual probabilities of error for the users in the network and obtaining their fundamental tradeoffs. Using this framework, a system can be realized, which can provide a tradeoff of reliabilities among the users for a fixed vector of users' rates. This adds a completely new dimension to the performance tradeoff in such networks, which is beyond what is given by the conventional performance versus rate tradeoff in single-user systems. Although this is a very general concept and can be applied to any multi-terminal communication system, in this paper we consider multiple-input multiple-output (MIMO) fading broadcast channel. In particular, we quantify the reliability tradeoff by introducing the notion of diversity gain region (DGR), which specifies the set of diversity gain vectors that are simultaneously achievable by the users for a fixed vector of users' multiplexing gains. We show the existence of a tradeoff among the users' diversity gains by deriving inner and outer bounds for the DGR.

A distributed source coding problem with a joint distortion criterion that depends on the sources and the reconstruction is considered in this work. While the prevalent trend in information theory has been to prove achievability results using Shannon's random coding arguments, using structured random codes offer rate gains over unstructured random codes for many problems. Motivated by this, a new achievable rate-distortion region (an inner bound to the performance limit) is presented for this problem for discrete memoryless sources based on “good” structured random nested codes built over abelian groups. For certain sources and distortion functions, the new rate region is shown to be strictly bigger than the Berger-Tung rate region, which has been the best known achievable rate region for this problem till now. This is done using numerical plots. Achievable rates for single-user source coding using abelian group codes are also obtained as a corollary of the main coding theorem. It is shown that nested linear codes achieve the Shannon rate-distortion function in the arbitrary discrete memoryless case.

The two-channel multiple descriptions problem for an independent and identically distributed (i.i.d.) source, with feed-forward to one or both side-decoders is considered. A single-letter achievable rate-region is derived; it enlarges the best known rate-region for multiple descriptions without feed-forward. The proof of the result uses a block-Markov superposition source coding strategy. In point-to-point source coding, feed-forward does not decrease the rate-distortion function of an i.i.d. source. In contrast, an example is provided to show that the derived region can be strictly larger than the optimal multiple description rate-distortion region without feed-forward.

A new single-letter achievable rate region is proposed for the two-user discrete memoryless multiple-access channel(MAC) with noiseless feedback. The proposed region includes the Cover–Leung rate region, and it is shown that the inclusion is strict. The proof uses a block-Markov superposition strategy based on the observation that the messages of the two users are correlated given the feedback. The rates of transmission are too high for each encoder to decode the other's message directly using the feedback, so they transmit correlated information in the next block to learn the message of one another. They then cooperate in the following block to resolve the residual uncertainty of the decoder. The coding scheme may be viewed as a natural generalization of the Cover–Leung scheme with a delay of one extra block and a pair of additional auxiliary random variables. We compute the proposed rate region for two different MACs and compare the results with other known rate regions for the MAC with feedback. Finally, we show how the coding scheme can be extended to obtain larger rate regions with more auxiliary random variables.

Let X and Y be finite alphabets and PXYa joint distribution over them, with PXand PYrepresenting the marginals. For any ϵ > 0, the set of n-length sequences xnand ynthat are jointly typical according to PXYcan be represented on a bipartite graph. We present a formal definition of such a graph, known as a typicality graph, and study some of its properties. These properties arise in the study of several multiuser communication problems.

A single-letter achievable rate region is proposed for the two-receiver discrete memoryless broadcast channel with feedback. It is shown through an example that the rate-region can be strictly larger than the no-feedback capacity region. The coding strategy involves block-Markov superposition coding using Marton's scheme as the starting point. If the message rates in the Marton scheme are too high to be decoded at the end of a block, each receiver is left with a list of messages compatible with its output. In the next block, we send resolution information for each receiver to resolve its list. The key observation is that the resolution information of the first receiver is correlated with that of the second. We transmit this correlated information efficiently in the following block using ideas from the Han-Costa coding scheme.

The problem of computing the capacity-cost function of channels with feedback and the rate-distortion function of sources with feed-forward is considered. Sufficient conditions are derived on : a) the structure of the cost function for a chosen joint distribution to achieve the optimal feedback capacity-cost function, b) the structure of the distortion function for a chosen joint distribution to achieve the optimal feed-forward rate-distortion function. These structural results are useful since it is infeasible in general to directly compute the optimizations. Examples are provided to show how the results can help compute the performance limits with feedback and feed-forward.

In the above titled paper (ibid., vol. 52, no. 7, pp. 2986-3002, Jul. 06), there is an error on line 8 in the first paragraph on the left column on page 2992 regarding broadcast channels. The equation is not correct and thus the argument given in the rest of the paragraph is not valid. A correct argument is presented here.

The problem of bounding the reliability function of a multiple-access channel (MAC) is studied. An upper bound on the minimum Bhattacharyya distance between codeword pairs is derived. For a certain large class of two-user discrete memoryless (DM) MAC, a lower bound on the maximal probability of decoding error is derived as a consequence of the upper bound on Bhattacharyya distance. Further, an upper bound on the average probability of decoding error is studied. It is shown that the corresponding upper and lower bounds have a similar structure. Using a conjecture about the structure of the multi-user code, a tighter lower bound for the maximal probability of decoding error is derived and is shown to be tight at zero rates.

A single-letter achievable rate region for the two-user discrete memoryless multiple-access channel is proposed. The rate region includes the Cover-Leung region, and it is shown that the inclusion is strict. The proof uses a block-Markov superposition strategy based on the observation that the messages of the two users are correlated given the feedback. The rates of transmission are too high for each encoder to decode the other's message directly using the feedback, so they transmit correlated information in the next block in order to learn the message of one another. They then cooperate in the following block to resolve the residual uncertainty of the decoder. Our scheme may be viewed as a natural generalization of the Cover-Leung scheme with a delay of one extra block and a pair of additional auxiliary random variables. The scheme can also be extended to obtain larger rate-regions with more auxiliary random variables.

Consider a pair of correlated Gaussian sources(X1,X2). Two separate encoders observe the two components and communicate compressed versions of their observations to a common decoder. The decoder is interested in reconstructing a linear combination ofX1andX2to within a mean-square distortion of D. We obtain an inner bound to the optimal rate-distortion region for this problem. A portion of this inner bound is achieved by a scheme that reconstructs the linear function directly rather than reconstructing the individual componentsX1andX2first. This results in a better rate region for certain parameter values. Our coding scheme relies on lattice coding techniques in contrast to more prevalent random coding arguments used to demonstrate achievable rate regions in information theory. We then consider the case of linear reconstruction of K sources and provide an inner bound to the optimal rate-distortion region. Some parts of the inner bound are achieved using the following coding structure: lattice vector quantization followed by ldquocorrelatedrdquo lattice-structured binning.

A new rate region is presented for a general framework of distributed source coding where the decoder is interested in lossy reconstruction of an arbitrary function of the sources. The coding scheme involves vector quantization of the sources followed by "correlated" binning. Nested linear codes are used for quantization and binning as against the more prevalent random codes. Our rate region recovers many known rate regions in distributed source coding while unifying them under the same general framework.

In this work, a new lower bound for the maximal error probability of a two-user discrete memoryless (DM) multiple-access channel (MAC) is derived. This is the first bound of this type that explicitly imposes independence of the userspsila input distributions (conditioned on the time-sharing auxiliary variable) and thus results in a tighter sphere-packing exponent when compared to the tightest known exponent derived by Haroutunian.

The two-channel multiple descriptions problem for an i.i.d source, with feed-forward to one or both side-decoders is considered. A single-letter achievable rate-region is derived; it enlarges the best known rate-region for multiple descriptions without feed-forward. The proof of the result uses a block-Markov superposition source coding strategy. In point-to-point source coding, feed-forward does not decrease the rate-distortion function of an i.i.d source. In contrast, an example is provided to show that the derived region can be larger than the optimal multiple description rate region without feed-forward.

In this paper, we consider the communication problem that involves transmission of correlated sources over broadcast channels. We consider a graph-based framework for this information transmission problem. The system involves a source coding module and a channel coding module. In the source coding module, the sources are efficiently mapped into a nearly semi-regular bipartite graph, and in the channel coding module, the edges of this graph are reliably transmitted over a broadcast channel. We consider nearly semi-regular bipartite graphs as discrete interface between source coding and channel coding in this multiterminal setting. We provide an information-theoretic characterization of 1) the rate of exponential growth (as a function of the number of channel uses) of the size of the bipartite graphs whose edges can be reliably transmitted over a broadcast channel and 2) the rate of exponential growth (as a function of the number of source samples) of the size of the bipartite graphs which can reliably represent a pair of correlated sources to be transmitted over a broadcast channel.

In modern communication systems, different users have different requirements for quality of service (QoS). In this work, QoS refers to the average codeword error probability experienced by the users in the network. Although several practical schemes (collectively referred to as unequal error protection schemes) have been studied in the literature and are implemented in existing systems, the corresponding performance limits have not been studied in an information-theoretic framework.

With mean-squared error D as a goal, it is well known that one may approach the rate-distortion function R(D) of a nonbandlimited, continuous-time Gaussian source by sampling at a sufficiently high rate, applying the Karhunen-Loeve transform to sufficiently long blocks, and then independently coding the transform coefficients of each type. In particular, the coefficients of a given type are ideally encoded with performance attaining a suitably chosen point on the first-order rate-distortion function of that type of coefficient. This paper considers a similar sample-and-transform coding scheme in which ideal coding of coefficients is replaced by coding with some specified family of quantizers, whose operational rate-distortion function is convex. A prime example is scalar quantization with entropy-coding and, if needed for convexity, time sharing. It is shown that when the sampling rate is large, the operational rate-distortion function of such a scheme comes within a finite constant of R(D). Applied to the scalar quantization family, the finiteness of this bound contrasts with a recent result showing that direct scalar quantization of samples (without a transform) has unbounded rate when distortion is held constant and sampling rate becomes large, even when the quantized samples are compressed to their entropy-rate. Thus, at high sampling rates, the transform reduces the loss due to scalar quantization from something infinite to something finite.

We study the problem of computing the rate-distortion function for sources with feed-forward and the capacity for channels with feedback. The formulas (involving directed information) for the optimal rate-distortion function with feed-forward and channel capacity with feedback are multi- letter expressions and cannot be computed easily in general. In this work, we derive conditions under which these can be computed for a large class of sources/channels with memory and distortion/cost measures. Illustrative examples are also provided.

Source coding with noiseless feedforward deals with efficient quantization of information sources into indexes, where to reconstruct a source sample, the decoder in addition to this index, has access to all the previous noiseless source samples. This problem may find applications in sensor networks, economics, and control theory. In the first part of this paper, we consider a deterministic block coding scheme for independent and identically distributed (i.i.d.) Gaussian sources. We show that this scheme is asymptotically optimal in terms of its rate-distortion function and the error exponent. In the second part of this paper we consider two-channel multiple description source coding with noiseless feedforward. We consider i.i.d. Gaussian sources and obtain the optimal rate-distortion region. The key result is that there is no penalty to be paid for constraining the descriptions to be mutually refineable. That is when one of the channels is active, the decoder which operates on one of the descriptions achieves the optimal rate-distortion function, and when both channels are active, the joint decoder still attains the optimal rate-distortion function. This implies that for memoryless sources with additive distortion measures, in the case of multiple description source coding, noiseless feedforward provides significant improvements in performance. We then evaluate the optimal multiple description source coding error exponents for the symmetric case

In this paper, we consider a graph-based framework for transmission of correlated sources over multiple-access channels. It is well known that the separation approach is not optimal for this multiuser communication. Our objective in this work is to reintroduce modularity in this problem using a graph-based discrete interface and to minimize the performance loss as compared to the optimal joint source-channel coding scheme. The proposed framework envisages a transmission systems with two modules: a source-coding module and a channel-coding module. In the former module, the correlated sources are encoded distributively into correlated messages whose correlation structure can be associated with a bipartite graph. These correlated messages are then encoded by using correlated codewords and are reliably transmitted over the multiple-access channel in the latter module. This leads to performance gains in terms of enlarging the class of correlated sources that can be reliably transmitted over a multiple-access channel as compared to the conventional separation approach. We provide an information-theoretic characterization of 1) the rate of exponential growth (as a function of the number of channel uses) of the size of the bipartite graphs whose edges can be reliably transmitted over a multiuser channel and 2) the rate of exponential growth (as a function of the number of source samples) of the size of the bipartite graphs which can reliably represent a pair of correlated sources to be transmitted over a multiuser channel.

In this work, we consider a source coding model with feed-forward. We analyze a system with a noiseless, feed-forward link where the decoder has knowledge of all previous source samples while reconstructing the present sample. The rate-distortion function for an arbitrary source with feed-forward is derived in terms of directed information, a variant of mutual information. We further investigate the nature of the rate-distortion function with feed-forward for two common types of sources- discrete memoryless sources and Gaussian sources. We then characterize the error exponent for a general source with feed-forward. The results are then extended to feed-forward with an arbitrary delay larger than the block length.

Motivated by the question of the efficiency of dense sensor networks for sampling, encoding and reconstructing spatial random fields, this paper uses the Berger-Tung upper bound to the discrete-time distributed rate-distortion function and Grenander-Szego asymptotic eigenvalue theory to obtain an upper bound to the smallest possible rate when using distributed lossy encoding of densely spaced samples that is tighter than the bound recently obtained by Kashyap et al. Both bounds indicate that with ideal distributed lossy coding, dense sensor networks can efficiently sense and convey a field, in contrast to the negative result obtained by Marco et al. for encoders based on time- and space-invariant scalar quantization and ideal Slepian-Wolf distributed lossless coding

In this paper we consider the communication problem that involves transmission of correlated sources over broadcast channels. We consider a graph-based framework for this information transmission problem. The system involves a source coding module and a channel coding module. In the source coding module, the sources are efficiently represented using a nearly semi-regular bipartite graph, and the in the channel coding module, the edges of this graph are reliably transmitted over a broadcast channel. We consider nearly semi-regular bipartite graphs as discrete interface between source coding and channel coding in this multiterminal setting. In particular, in this paper, we restrict our attention to the source coding module, building on our earlier work on the channel coding module. We provide an information-theoretic characterization of the rate of growth of the exponent (as a function of the number source samples) of the size of such graphs that can reliably represent a pair of correlated sources

This paper derives a lower bound of the form ngamma-1to the per-node throughput achievable by a wireless network when n source-destination pairs are randomly distributed throughout a disk of radius ngamma, 0alpha, alpha > 2

In this paper, we address duality in a variety of multiuser source and channel coding problems under different scenarios of "one-sided" inter-terminal collaboration at either the transmitter or at the receiver. First we consider duality between broadcast channel coding and distributed source coding problems. We also consider a new source coding problem in this paper, which we refer to as distributed reconstruction source coding. This problem is closely related to the multiple description source coding problem. We then consider duality between this problem and the multiple access channel coding problem. Our notion of duality in this paper is in a functional sense, where the optimal encoder mapping for a multiuser source coding problem becomes identical to the optimal decoder mapping for the dual multiuser channel coding problem, and vice versa. For ease of illustration we give the formulation only for systems which involve either two encoders or two decoders. Our formulation can be easily extended to the multiuser (more than two noncollaborating terminals) case. We present the precise mathematical conditions under which these encoder-decoder mappings are swappable in the two dual multiuser communication problems, identifying the key roles played by the source distortion and channel cost measures respectively in the multiuser source and channel coding problems in capturing this duality.

We study the problem of estimating a physical process at a central processing unit (CPU) based on noisy measurements collected from a distributed, bandwidth-constrained, unreliable, network of sensors, modeled as an erasure network of unreliable "bit-pipes" between each sensor and the CPU. The CPU is guaranteed to receive data from a minimum fraction of the sensors and is tasked with optimally estimating the physical process under a specified distortion criterion. We study the noncollaborative (i.e., fully distributed) sensor network regime, and derive an information-theoretic achievable rate-distortion region for this network based on distributed source-coding insights. Specializing these results to the Gaussian setting and the mean-squared-error (MSE) distortion criterion reveals interesting robust-optimality properties of the solution. We also study the regime of clusters of collaborative sensors, where we address the important question: given a communication rate constraint between the sensor clusters and the CPU, should these clusters transmit their "raw data" or some low-dimensional "local estimates"? For a broad set of distortion criteria and sensor correlation statistics, we derive conditions under which rate-distortion-optimal compression of correlated cluster-observations separates into the tasks of dimension-reducing local estimation followed by optimal distributed compression of the local estimates.

In many multiterminal communication problems, constructions of good source codes involve finding distributed partitions (into bins) of a collection of quantizers associated with a group of source encoders. Further, computationally efficient procedures to index these bins are also required. In this work, we consider a constructive approach for distributed binning in an algebraic framework. Several application scenarios fall under the scope of this paper including the CEO problem, distributed source coding, and n-channel symmetric multiple description source coding with n>2. Specifically, in this exposition we consider the case of two codebooks while focusing on the Gaussian CEO problem with mean squared error reconstruction and with two symmetric observations. This problem deals with distributed encoding of correlated noisy observations of a source into descriptions such that the joint decoder having access to them can reconstruct the source with a fidelity criterion. We employ generalized coset codes constructed in a group-theoretic setting for this approach, and analyze the performance in terms of distance properties and decoding algorithms.

In this Part II of a two-part paper, we present a new achievable rate-distortion region for the symmetric n-channel multiple-descriptions coding problem (n>2) where the rate of every description is the same, and the reconstruction distortion depends only on the number of descriptions received. Using a new approach for the random coding constructions, along with a generalization of the technique used in the two-channel El Gamal and Cover region to any n, the rate region presented here achieves points that have not been known in the literature previously. This rate region is derived from a concatenation of source-channel erasure codes developed in Part I of this work by deploying the framework of source coding with side information ("random binning"). The key idea is that by using the framework of source coding with side information, multiple statistically identical realizations representing the coarse version of a source can be simultaneously refined by a single encoding. We point out that there is an important conceptual difference in random coding construction for the multiple-descriptions coding problem between the case of n=2 and n>2. To illustrate the framework, we also present the important case of the Gaussian source in detail.

Slepian-Wolf coding tackles the problem of distributed encoding of correlated discrete-alphabet sources for decoding at a common receiver. In this work, we propose a distributed linear block code construction for attaining any point on the Slepian-Wolf achievable rate region for arbitrarily correlated sources using only a single code. Specifically, our prescription allows for any arbitrary memoryless joint probability distribution over any arbitrary number of distributed sources, and allows for any arbitrary rate combination that lies in the Slepian-Wolf achievable region. Special cases of our framework include the single source case (wherein our construction reduces to an entropy coder), source coding with side-information at the receiver (so-called corner points of the Slepian-Wolf region), and specific source correlation models (such as induced by a virtual Binary Symmetric Channel model). In this work, we describe how to use low density parity check (LDPC) codes in the proposed framework to solve the general Slepian-Wolf problem constructively.

This paper describes the source coding of the information signals with feedforward Gaussian sources. A stationary memoryless Gaussian source with zero-mean and variance, and with mean squared error as the distortion measure, gives a deterministic scheme that achieves the optimal rate-distortion bound using simple uniform scalar quantizers. To reconstruct source codes, the decoder uses the optimal Shannon rate-distortion function and achieves channel coding with feedback.

In this paper, the multiterminal sources is mapped independently into a message set characterized by a graph which preserves a predetermined amount of correlation between the sources, and the message set becomes the input to channel encoder. In this work joint source-channel coding scheme is considered as a part with associated message graph for transmitting distributed correlated sources over MAC. Thus the parameters are allowed to increase exponentially with number of channels and the performance of this characterized set is measured using minimum average probability of error.

In this paper, we derive an inner bound (achievable region) and an outer bound for the error exponent region of a Gaussian multiple access channels (GMAC). We define a probability of error for each user, which, in general may be different for different users. Therefore, there are multiple error exponents, one for each user, for a given multiuser channel.

In this work, we consider a source coding model with feedforward. We analyze a system with a noiseless feedforward link where the decoder has knowledge of all previous source samples while reconstructing the present sample. The rate-distortion function for an arbitrary source with feedforward is derived in terms of directed information, a variant of mutual information. The special cases of discrete memoryless sources and Gaussian sources with feedforward are further examined. We also derive a random coding error exponent which is used to bound the probability of decoding error for a source code (with feedforward) of finite block length. The results are then extended to feedforward with an arbitrary delay larger than the block length.

In this work, we introduce the notion of the diversity gain region for a multiuser channel. This region specifies the set of diversity-gain vectors that are simultaneously achievable by all users in the multiuser channel. This is done by associating different probabilities of error for different users, contrary to the traditional approach where a single probability of system error is considered. We derive an inner bound (achievable region) and an outer bound for the diversity gain region of a MIMO fading broadcast channel.

In this two-part paper, we present a new achievable rate region for the general n-channel symmetric multiple descriptions problem. In part I, inspired by the concept of maximum-distance separable (MDS) erasure channel codes, we consider a special case of this rate region, where the source is encoded into n descriptions each with rate R. These descriptions are transmitted over n bandwidth constrained and errorless channels. During transmission, a subset of these channels can break down, thus erasing the corresponding descriptions. The decoder is interested in recovering the source with the reception of at least k descriptions. Thus, the encoder is allowed to sample only one realization of this breakdown process during the entire transmission. For Gaussian sources, we have the following interesting result: when any k descriptions arrive, the achievable distortion exactly matches the optimal distortion-rate performance corresponding to a source rate of kR bits; with the reception of any m > k descriptions, the source reconstruction quality is strictly better, the improvement being nearly linear in the number of descriptions received.

The problem of rate-distortion efficient constructions is studied for the problem of source coding with side information (SCSI), which has assumed heightened interest. While the Wyner-Ziv theorem from information theory has prescribed rate-distortion performance bounds for the SCSI problem, the gap between theory and practice has remained large. To reduce this gap, two different frameworks are proposed based on a trellis construction and a turbo-based construction respectively. Simulation results on the Gaussian SCSI problem reveal the promise of the proposed approaches: at 1 bit per sample, 0.5 bits/sample, 0.25 bits/sample and 0.125 bits/sample, these constructions attain performance within 1.3 dB, 1.1 dB, 0.85 dB and 0.5 dB respectively of the theoretical Wyner-Ziv rate-distortion bound.

We explore the information-theoretic duality between source coding with side information at the decoder and channel coding with side information at the encoder. We begin with a mathematical characterization of the functional duality between classical source and channel coding, formulating the precise conditions under which the optimal encoder for one problem is functionally identical to the optimal decoder for the other problem. We then extend this functional duality to the case of coding with side information. By invoking this duality, we are able to generalize the result of Wyner and Ziv (1976) relating to no rate loss for source coding with side information from Gaussian to more arbitrary distributions. We consider several examples corresponding to both discrete- and continuous-valued cases to illustrate our formulation. For the Gaussian cases of coding with side information, we invoke geometric arguments to provide further insights into their duality. Our geometric treatment inspires the construction and dual use of practical coset codes for a large class of emerging applications for coding with side information, such as distributed sensor networks, watermarking, and information-hiding communication systems.

We address the problem of compressing correlated distributed sources, i.e., correlated sources which are not co-located or which cannot cooperate to directly exploit their correlation. We consider the related problem of compressing a source which is correlated with another source that is available only at the decoder. This problem has been studied in the information theory literature under the name of the Slepian-Wolf (1973) source coding problem for the lossless coding case, and as "rate-distortion with side information" for the lossy coding case. We provide a constructive practical framework based on algebraic trellis codes dubbed as DIstributed Source Coding Using Syndromes (DISCUS), that can be applicable in a variety of settings. Simulation results are presented for source coding of independent and identically distributed (i.i.d.) Gaussian sources with side information available at the decoder in the form of a noisy version of the source to be coded. Our results reveal the promise of this approach: using trellis-based quantization and coset construction, the performance of the proposed approach is 2-5 dB from the Wyner-Ziv (1976) bound.

We present new achievable rate regions and code constructions for the symmetric n-channel multiple descriptions (MD) coding problem (Puri et al. (2002)) for n>2. Our approach is inspired by unexplored connections between MD and the problem of distributed source coding (Slepian et al. (1973); Wyner et al. (1976)). For illustrative clarity, we restrict our focus to the important special case relating to (n, k) source-channel erasure codes (Pradhan et al. (2001)). This involves n encodings of a source with the goal of maximizing its reconstruction fidelity with the availability of any k of them, while strictly improving this reconstruction fidelity with the availability of more than k descriptions. We describe the underlying information-theoretic framework, and then formulate practical constructions based on scalar quantizers and linear channel codes for the n=3 case to illustrate our concepts.

We address duality in a variety of multiple-input-multiple-output (MIMO) source and channel coding problems of interest under different scenarios of "one-sided" inter-terminal collaboration at either the transmitter or at the receiver, including certain cases of. duality between (i) broadcast channel coding and distributed source coding, and (ii) multi-access channel coding and multiple-descriptions source coding. Our notion of duality in this paper is in a functional sense, where the optimal encoder mapping for a MIMO source coding problem becomes identical to the optimal decoder mapping for the dual MIMO channel coding problem, and vice versa. For ease of illustration we give the formulation only for two-input-two-output systems, which can be easily extended to the MIMO case. We present the precise mathematical conditions under which these encoder-decoder mappings are swappable in the two dual MIMO problems, identifying the key roles played by the source distortion and channel cost measures respectively in the MIMO source and channel coding problems in capturing this duality.

We tackle the problem of efficient layered or multiresolution (MR) data transmission over multicarrier modulation (MCM) systems. We treat the source as being characterized by multiple layers of importance, i.e., having different bit error rate (BER) requirements. First we consider the MCM systems in a multiresolution framework using multiplexing techniques. Then we present the idea of embedded multicarrier modulation (E-MCM) as an effective way of achieving this, and introduce a fast table-lookup-based power allocation algorithm that optimizes the multicarrier constellation design in terms of maximizing the deliverable throughput bit-rate, subject to a total power constraint. Simulation results of our E-MCM system reveal substantial gains (up to about 25%) in deliverable bit-rates over optimized time-division-multiplexed-based designs.

We address digital transmission for enhancing, in a backward compatible way, the quality of analog image transmission systems. We propose a practical algorithm that treats the problem as one of wavelet image compression with side information (available in the form of a noisy analog version of the image) present at the decoder. We propose a rate allocation technique to efficiently allocate the rate among the wavelet coefficients of the image. In typical instances of the problem, we get gain up to 2.5 dB over conventional methods that ignore the side information. Surprisingly, this is typically achieved by modifying a very small fraction of the wavelet coefficients (typically around 10-20%) of the conventional source coder. Extensions of our proposed image transmission framework to that of video transmission finds application in the upgrade of current analog television broadcast systems to digital TV.

We address the problem of distributed source coding using a practical and constructive approach, referred to as distributed source coding using syndromes (DISCUS), with applications to sensor networks. We propose low complexity encoding and decoding methods based on linear codes, to achieve all points in the achievable rate region of the Slepian-Wolf (1973) problem. The extension of these concepts to the construction of Euclidean-space codes is also studied and analyzed for the case of trellis and lattice codes. The performance of these symmetric methods for encoding with a fidelity criterion is shown to be the same as that of asymmetric encoding. Simulations are presented to corroborate these results.

Inspired by a previously proposed constructive framework for the distributed source coding problem. We propose a powerful constructive approach to the watermarking problem, emphasizing the dual rules of distributed source coding with side information at the decoder and channel coding with side information at the encoder. In our framework, we explore various source and channel codes to close the gap on the achievable capacity of watermarking systems. We propose two methods of solution, one which is based on optimal rate-distortion quantizers and the other based on robust optimization and convex programming. The resulting watermarking schemes, when subjected to additive white gaussian noise (AWGN) attacks, achieve results which are comparable to or better than the best watermarking schemes in the literature.

We propose a powerful new solution to the multimedia watermarking problem by exploiting its duality with another problem for which we have recently made pioneering constructive contributions. This latter problem is that of distributed source coding, or compression of correlated sources that are distributed. We show how these two seemingly unrelated problems are actually duals of each other. We exploit this duality by transforming our recently introduced powerful constructive framework for the distributed compression problem in [13] to a corresponding dual framework for the watermarking problem. Simulations expose the significant performance gains attained by our proposed watermarking approach and reveal its exciting potential for next-generation watermarking techniques. This can be accredited to the exploitation of the dual roles played by source codes and channel codes in the two problems.

In this work, we consider the application of unitary filter banks for multiple description coding of independent, identically distributed Gaussian vector sources. We derive the redundancy-rate-distortion bound for this class of signals. It is shown that for two-dimensional (2-D) Gaussian vector sources (resulting in a two-description system), 2/spl times/2 block transforms give all the achievable optimal points in the redundancy-rate-distortion function among the class of all unitary filter banks. Similar results can be obtained for higher-dimensional transforms.

We address the problem of distributed source coding, i.e. compression of correlated sources that are not co-located and/or cannot communicate with each other to minimize their joint description cost. In this work we tackle the related problem of compressing a source that is correlated with another source which is available only at the decoder. In contrast to prior information-theoretic approaches, we introduce a new construction and practical framework for tackling the problem based on the judicious incorporation of channel coding principles into this source coding problem. We dub our approach as distributed source coding using syndromes (DISCUS). We focus in this paper on trellis-structured constructions of the framework to illustrate its utility. Simulation results confirm the power of DISCUS, opening up a new and exciting constructive playing-ground for the distributed source coding problem. For the distributed coding of correlated i.i.d. Gaussian sources that are noisy versions of each other with "correlation-SNR" in the range of 12 to 20 dB, the DISCUS method attains gains of 7-15 dB in SNR over the Shannon-bound using "naive" independent coding of the sources.

We tackle the problem of efficient image transmission over multicarrier modulation (MCM) systems, proposing the use of a layered or multiresolution (MR) framework. We treat the source as being characterized by multiple layers of importance, and therefore deserving of multiple levels of noise immunity, i.e, having different BER requirements. We present the idea of embedded multicarrier modulation (EMCM) as a very effective way of achieving this, and introduce a fast table-lookup based power allocation algorithm that optimizes the multicarrier constellation design in terms of maximizing the deliverable throughput bit rates for the different resolution layers, subject to a total power constraint. Simulation results of our EMCM system reveal substantial gains (up to about 25%) in deliverable bit rates over optimized TDM-based MCM designs. Further, in typical image transmission simulations using an embedded wavelet image coder, the EMCM approach yields almost 3 dB gains in delivered quality over conventional single-resolution MCM systems.

We tackle the problem of efficient image transmission over multi-carrier modulation (MCM) systems, proposing the use of a layered or multiresolution (MR) framework. In this work, we treat the source as being characterized by multiple layers of importance, and therefore deserving of multiple levels of noise immunity, i.e. having different BER requirements. We present the idea of embedded multi-carrier modulation (EMCM) as a very effective way of achieving this, and introduce a fast table-lookup based power allocation algorithm that optimizes the multicarrier constellation design in terms of maximizing the deliverable throughput bitrates for the different resolution layers, subject to a total power constraint. Simulation results of our EMCM system reveal substantial gains (up to about 25%) in deliverable bit rates over optimized TDM-based MCM designs. Further, in typical image transmission simulations using an embedded wavelet image coder, the EMCM approach yields almost 3 dB gains in delivered quality over conventional single-resolution MCM systems.