We consider the problem of encoding an i.i.d. source into a set of symbols or messages that may be altered by an adversary while en route to the decoder. We focus in particular on the regime in which the number of messages is fixed while the blocklength of the source and the size of each message tend to infinity. For this fixed-blocklength, “large alphabet” channel, we show that combining an optimal rate-distortion code with an optimal error-correction code yields an optimal overall code for Gaussian sources with quadratic distortion and binary uniform sources with Hamming distortion but that it can be suboptimal by an arbitrarily large factor in general. We also consider the scenario in which the distortion constraint that the decoder must satisfy depends on the number of errors that occur. We show that the problem can be reduced operationally to one with erasures instead of errors in two special cases: one involving lossless reproduction of functions of the source and one in which the encoder and decoder share common randomness.

A binary erasure version of -channel multiple descriptions (MD) with symmetric descriptions (i.e., the rates of the descriptions are equal and the distortion constraint depends only on the number of messages received) is considered. No excess rate for every out of descriptions, i.e., any messages have sum rate , where is Shannon's rate-distortion function for erasure distortion and is the distortion constraint to be met, is investigated. The goal is to characterize the achievable distortions . Reconstruction fidelity is measured using two criteria: a worst-case criterion which computes distortion by maximizing the per-letter distortion over all source sequences, and an average-case criterion which computes distortion by averaging the per-letter distortion over all source sequences. Achievability schemes are presented, based on systematic maximum distance separable codes for worst-case distortion and random binning for average-case distortion, and optimality results are proved for the corresponding distortion regions. The erasure MD setup is then used to propose a layered coding framework for multiple descriptions, which is then applied to vector Gaussian MD and shown to be optimal for symmetric scalar Gaussian MD with two levels of receivers and no excess rate at the central receiver.

We study a problem in which a source is encoded into n packets, any t of which may be altered in an arbitrary way by Byzantine adversaries. The decoder receives the n packets and, without knowing which packets were altered, seeks to reconstruct the original source to meet a distortion constraint. We examine a layered architecture for this problem that separates the lossy compression from the coding for adversarial errors. We show that this architecture is optimal in the binary-Hamming and quadratic-Gaussian cases yet suboptimal in general. Our optimality proofs use characterizations of the size of a maximal set with a given diameter in Hamming and Euclidean spaces.

We study the tradeoff between delay and partial reconstruction in peer-to-peer networks, i.e., the number of messages a peer must obtain to reconstruct a given fraction of the file. We present a coding scheme based on erasure compression and Slepian-Wolf binning, in which peers generate coded messages based on their current knowledge of the file. Assuming symmetric peers, we show that the coding scheme provides a Pareto optimal tradeoff between delay and reconstruction, which we characterize. In the process of proving the result, we establish an improved outer bound on the rate region of the general multi-terminal source coding problem. We further show that in the case of asymmetric peers, the coding scheme is not optimal.

We consider a binary erasure version of the n-channel multiple descriptions problem with no excess rate and no distortion for every k out of n descriptions, i.e., any subset of k messages has a total rate of one and allows for perfect reconstruction of the source. Using a worst-case distortion criterion, we present an explicit coding scheme based on Reed-Solomon codes and, for any n and k, characterize its achievable distortion region when m < k messages are received at the decoder. We prove that this scheme is Pareto optimal in the achievable distortions for all n and k for any number of received messages at the decoder, and is optimal for all n and k when a single message is received. We also provide optimality results for a certain range of values of n and k.

We consider a binary erasure version of the n-channel multiple descriptions problem with no excess rate and no distortion for every k out of n descriptions, i.e., any subset of k messages has a total rate of one and allows for perfect reconstruction of the source. We present an achievability scheme and characterize its distortion when mkles 1/2 and a single message is received. For the case where k = 2, n > 3 and a single message is received, we provide a lower bound that differs by exactly 1/n from the minimum distortion achieved by the scheme.

In an unreliable packet network setting, we study the performance gains of optimal transmission strategies in the presence and absence of coding capability at the transmitter, where performance is measured in delay and throughput. Although our results apply to a large class of coding strategies including maximum-distance separable (MDS) and Digital Fountain codes, we use random network codes in our discussions because these codes have a greater applicability for complex network topologies. To that end, after introducing a key setting in which performance analysis and comparison can be carried out, we provide closed-form as well as asymptotic expressions for the delay performance with and without network coding. We show that the network coding capability can lead to arbitrarily better delay performance as the system parameters scale when compared to traditional transmission strategies without coding. We further develop a joint scheduling and random-access scheme to extend our results to general wireless network topologies.

We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e., packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved.

We present decentralized algorithms that compute minimum-cost subgraphs for establishing multicast connections in networks that use coding. These algorithms, coupled with existing decentralized schemes for constructing network codes, constitute a fully decentralized approach for achieving minimum-cost multicast. Our approach is in sharp contrast to the prevailing approach based on approximation algorithms for the directed Steiner tree problem, which is suboptimal and generally assumes centralized computation with full network knowledge. We also give extensions beyond the basic problem of fixed-rate multicast in networks with directed point-to-point links, and consider the case of elastic rate demand as well as the problem of minimum-energy multicast in wireless networks.