Streaming erasure codes encode a source stream to guarantee that each source packet is recovered within a fixed delay at the receiver over a burst-erasure channel. This paper introduces diversity embedded streaming erasure codes (DE-SCo), that provide a flexible trade-off between the channel quality and receiver delay. When the channel conditions are good, the source stream is recovered with a low delay, whereas when the channel conditions are poor the source stream is still recovered, albeit with a larger delay. Information theoretic analysis of the underlying burst-erasure broadcast channel reveals that DE-SCo achieve the minimum possible delay for the weaker user, without sacrificing the performance of the stronger user. A larger class of multicast streaming erasure codes (MU-SCo) that achieve optimal tradeoff between rate, delay and erasure-burst length is also constructed.

We study the use of low-density generator matrix (LDGM) codes for lossy compression of the Bernoulli symmetric source. First, we establish rigorous upper bounds on the average distortion achieved by check-regular ensemble of LDGM codes under optimal minimum distance source encoding. These bounds establish that the average distortion using such bounded degree families rapidly approaches the Shannon limit as the degrees are increased. Second, we propose a family of message-passing algorithms, ranging from the standard belief propagation algorithm at one extreme to a variant of survey propagation algorithm at the other. When combined with a decimation subroutine and applied to LDGM codes with suitably irregular degree distributions, we show that such a message-passing/decimation algorithm yields distortion very close to the Shannon rate-distortion bound for the binary symmetric source.

We consider a set of S independent encoders that must transmit a set of correlated sources through a network of noisy, independent, broadcast channels to T receivers, with no interference at the receivers. For the general problem of sending correlated sources through broadcast networks, it is known that the source-channel separation theorem breaks down and the achievable rate region as well as the proper method of coding are unknown. For our scenario, however, we establish the optimal rate region using a form of joint source-channel coding. When the optimal channel input distribution from transmitter i to receiver j is independent of j, our result has a max-flow/min-cut interpretation. Specifically, in this case, our result implies that if it is possible to send the sources to each receiver separately while ignoring the others, then it is possible to send to all receivers simultaneously.

In this paper, we describe and analyze the source and channel coding properties of a class of sparse graphical codes based on compounding a low-density generator matrix (LDGM) code with a low-density parity-check (LDPC) code. Our first pair of theorems establishes that there exist codes from this ensemble, with all degrees remaining bounded independently of block length, that are simultaneously optimal for both channel coding and source coding with binary data when encoding and decoding are performed optimally. More precisely, in the context of lossy compression, we prove that finite-degree constructions can achieve any pair(R,D) on the rate-distortion curve of the binary symmetric source. In the context of channel coding, we prove that the same finite-degree codes can achieve any pair(C,p) on the capacity-noise curve of the binary symmetric channel (BSC). Next, we show that our compound construction has a nested structure that can be exploited to achieve the Wyner-Ziv bound for source coding with side information (SCSI), as well as the Gelfand-Pinsker bound for channel coding with side information (CCSI). Although the results described here are based on optimal encoding and decoding, the proposed graphical codes have sparse structure and high girth that renders them well suited to message passing and other efficient decoding procedures.

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

We describe a method to encode fingerprint biometrics securely for use, e.g., in encryption or access control. The system is secure because the stored data does not suffice to recreate the original fingerprint biometric. Therefore, a breach in database security does not lead to the loss of biometric data. At the same time the stored data suffices to validate a probe fingerprint. Our approach is based on the use of distributed source coding techniques implemented with graph-based codes. We present a statistical model of the relationship between the enrollment biometric and the (noisy) biometric measurement taking during authentication. We describe how to validate or reject a candidate biometric probe given the probe and the stored encoded data. We report the effectiveness of our method as tested on a database consisting of 579 data sets, each containing roughly 15 measurements of a single finger. We thereby demonstrate a working secure biometric system for fingerprints.

We introduce a novel source coding problem, compound conditional source coding. We describe how a number of media coding problems can be cast into this framework. We develop the achievable rate region for this problem and error exponent results. We show that the reliability function of compound conditional source coding is as least as large as the list-decoding error exponent of Slepian-Wolf coding, which we develop in addition. A message of the paper is that a number of media coding scenarios where distributed source coding techniques are being used are more exactly stated as compound conditional problems. This insight can lead to improved system performance, as we demonstrate for error exponents.

Delay-optimal burst erasure correction codes have the shortest possible decoding delay required to correct all bursts of a given length with a fixed redundancy. We provide a simple construction that yields linear convolutional delay-optimal burst erasure codes for any choice of coding parameters while keeping the finite field small.

We propose a new construction for low-density source codes with multiple parameters that can be tuned to optimize the performance of the code. In addition, we introduce a set of analysis techniques for deriving upper bounds for the expected distortion of our construction, as well as more general low-density constructions. We show that (with an optimal encoding algorithm) our codes achieve the rate-distortion bound for a binary symmetric source and Hamming distortion. Our methods also provide rigorous upper bounds on the minimum distortion achievable by previously proposed low-density constructions.

We consider multiview video compression: the problem of jointly compressing multiple views of a scene recorded by different cameras. To take advantage of the correlation between views, we propose using disparity compensated view prediction and view synthesis and describe how these features can be implemented by extending the H.264/AVC compression standard. Finally, we discuss experimental results on the test sequences from the MPEG call for proposals on multiview video.

We show that linear complexity capacity-approaching information embedding codes exist for information embedding problems. Specifically, we introduce the double-erasure information embedding channel model, and show that in at least some parameter regimes one can achieve rates arbitrarily close to capacity using suitably defined codes on graphs. Furthermore, we show that both encoding and decoding can be implemented with linear complexity by exploiting belief propagation techniques

We consider a set of S independent encoders that must transmit a set of correlated sources through a network of noisy, independent, broadcast channels to T receivers. For the general problem of sending correlated sources through broadcast networks, it is known that the source-channel separation theorem breaks down and the achievable rate region as well as the proper method of coding are unknown. For our scenario, however, we not only establish the optimal rate region, but we show that a type of source-channel separation is possible at the transmitter, provided joint source-channel decoding is used at the receiver. Furthermore, we show that while joint source-channel encoding is unnecessary, not using joint source-channel decoding is suboptimal. Finally, when the optimal input distribution from transmitter i to receiver j is independent of j, our result has a max-flow/min-cut interpretation. Specifically, in this case our result implies that if it is possible to send the sources to each receiver separately while ignoring the others, then it is possible to send to all receivers simultaneously

We use the distortion side information (DSI) framework to study the gains in information embedding when the encoder exploits sensitivity of the source samples. Our study for the Gaussian source model extends the dirty paper coding result by Costa to the case of a weighted power constraint with the weights only known to the transmitter. A coding scheme based on fixed codebook variable-partition codes is presented for this problem. We also present another coding scheme that exploits the knowledge of DSI and is robust against intentional attacks. Finally, we study a related problem of Wyner-Ziv coding with reliability side information (RSI) at the decoder. This latter setup illustrates that fixed codebook variable-partition codes could also be fundamental in systems that rely on conventional distortion measures

We describe and analyze sparse graphical code constructions for the problems of source coding with decoder side information (the Wyner-Ziv problem), and channel coding with encoder side information (the Gelfand-Pinsker problem). Our approach relies on a combination of low-density parity check (LDPC) codes and low-density generator matrix (LDGM) codes, and produces sparse constructions that are simultaneously good as both source and channel codes. In particular, we prove that under maximum likelihood encoding/decoding, there exist low-density codes (i.e., with finite degrees) from our constructions that can saturate both the Wyner-Ziv and Gelfand-Pinsker bounds

In this extended abstract, we provide a high-level overview of some of our recent work [10], [11], [9] on low-density graphical codes for various communication problems including lossy compression, binning, and coding with side information. Sparse graphical codes, particularly low-density parity check (LDPC) codes, are widely used and well understood in application to channel coding problems [16]. On the other hand, for other communication problems—especially those involving aspects of both channel and source coding—there remain various open questions associated with using low-density code constructions. Examples of such problems include (a) lossy source coding (data compression); (b) source coding with side information (the Wyner-Ziv problem [19]), and (c) channel coding with side information (the Gelfand-Pinsker problem [7]). Our work tackles these problems using sparse graphical constructions that are based on a combination of LDPC codes, and their dual versions, namely low-density generator matrix (LDGM) codes.

We describe the architecture for our distributed video coding (DVC) system. Some key differences between our work and previous systems include a new method of enabling decoder motion compensation, and the use of serially concatenated accumulate syndrome codes for distributed source coding. To evaluate performance, we compare our system to the H.263+ and H.264/AVC video codecs. Experiments show that our system is comparable to DVC systems from Stanford and Berkeley in the sense that our system performs better than H.263+Intra, but worse than H.263+Inter and H.264/AVC

We consider "bit stealing" scenarios where the rate of a source code must be reduced without prior planning. We first investigate the efficiency of source requantization to reduce rate, which we term successive degradation. We focus on finite-alphabet sources with arbitrary distortion measures as well as the Gaussian-quadratic and high-resolution scenarios. We show an achievable rate-distortion tradeoff and prove that this is the best guaranteeable tradeoff for any good source code. This tradeoff is in general different from the rate-distortion tradeoff with successive refinement, where there is prior planning. But, we show that with quadratic distortion measures, for all sources with finite differential entropy and at least one finite moment, the gap is at most 1/2 bit or 3 dB in the high-resolution limit. In the Gaussian-quadratic case, the gap is at most 1/2 bit for all resolutions. We further consider bit stealing in the form of information embedding, whereby an embedder acts on a quantized source and produces an output at the same rate and in the original source codebook. We develop achievable distortion-rate tradeoffs. Two cases are considered, corresponding to whether or not the source decoder is informed of the embedding rate. In the Gaussian-quadratic case, we show the informed decoder need only augment the regular decoder with simple post-reconstruction distortion compensation in the form of linear scaling for the resulting system to be as efficient as bit stealing via successive degradation. Finally, we show that the penalty for uninformed versus informed decoders is at most 3 dB or 0.21-bit in the Gaussian-quadratic case and that their performance also lies within the 1/2-bit gap to that of successive refinement.

We show that the deterministic broadcast channel, where a single source transmits to M receivers across a deterministic mechanism, may be reduced, via a rate-splitting transformation, to another (2M - 1)-receiver deterministic broadcast channel problem where a successive encoding approach suffices. Analogous to rate-splitting for the multiple access channel and source-splitting for the Slepian-Wolf problem, all achievable rates (including non-vertices) apply. This amounts to significant complexity reduction at the encoder

We motivate the consideration of deterministic broadcast channel coding as an interference management technique in wireless scenarios. We address practical coding strategies for such channels and discuss two approaches. The first relies upon enumerative source coding and can be applied for any deterministic broadcast channel problem as the first step in pipelined encoding for vertex rates. The second approach addresses a wireless interference management scenario and is a complete, practical, capacity-achieving strategy that dualizes the Luby transform code construction and encoding/decoding algorithms. This results in the first practical, nontrivial, capacity achieving code construction for the deterministic broadcast channel.

We consider transmitting a source across a pair of independent, nonergodic channels with random states (e.g., slow-fading channels) so as to minimize the average distortion. The general problem is unsolved. Hence, we focus on comparing two commonly used source and channel encoding systems which correspond to exploiting diversity either at the physical layer through parallel channel coding or at the application layer through multiple description (MD) source coding. For on-off channel models, source coding diversity offers better performance. For channels with a continuous range of reception quality, we show the reverse is true. Specifically, we introduce a new figure of merit called the distortion exponent which measures how fast the average distortion decays with signal-to-noise ratio. For continuous-state models such as additive white Gaussian noise (AWGN) channels with multiplicative Rayleigh fading, optimal channel coding diversity at the physical layer is more efficient than source coding diversity at the application layer in that the former achieves a better distortion exponent. Finally, we consider a third decoding architecture: MD encoding with joint source-channel decoding. We show that this architecture achieves the same distortion exponent as systems with optimal channel coding diversity for continuous-state channels, and maintains the advantages of MD systems for on-off channels. Thus, the MD system with joint decoding achieves the best performance from among the three architectures considered, on both continuous-state and on-off channels.

In a variety of applications, there is a need to authenticate content that has experienced legitimate editing in addition to potential tampering attacks. We develop one formulation of this problem based on a strict notion of security, and characterize and interpret the associated information-theoretic performance limits. The results can be viewed as a natural generalization of classical approaches to traditional authentication. Additional insights into the structure of such systems and their behavior are obtained by further specializing the results to Bernoulli and Gaussian cases. The associated systems are shown to be substantially better in terms of performance and/or security than commonly advocated approaches based on data hiding and digital watermarking. Finally, the formulation is extended to obtain efficient layered authentication system constructions.

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

This paper describes the source-channel coding diversity approaches for multimedia communication. The decision of which system to use should be based on both the benefits of a large distortion exponent as well cost, flexibility and ease of implementation

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

We present a new class of systematic, time-invariant, convolutional encoders suitable for low delay burst erasure correction. Specifically, we show that the new encoders have the shortest possible decoding delay required to correct all bursts of a given length with a fixed redundancy. By comparing the new encoders to maximum distance separable (MDS) codes, we show that the latter generally require either more redundancy or more delay to correct bursts of a given length. In addition, we show that the new encoders can achieve better performance than MDS codes on a simple two-state Markov erasure channel. Thus, we demonstrate the advantages of using cross packet coding for delay-sensitive applications such as Voice over Internet Protocol, video-conferencing, etc., on bursty packet networks. Finally, we discuss suitable performance measures for encoders designed to correct both burst and random erasures and report the results of a computer search for such hybrid encoders.

Diversity techniques often arise as appealing means for improving the performance of multimedia communication over certain types of channels with independent parallel components (e.g., multiple antennas, frequency bands or time slots). Diversity can be obtained by channel coding across parallel components at the physical layer. Alternatively, the physical layer ca present an interface to the parallel components as separate, independent links thus allowing the application layer to implement diversity in the form of multiple description source coding. We compare these two approaches in terms of average end-to-end distortion as a function of channel signal-to-noise ratio (SNR). When specialized to the case of an independent, identically distributed Gaussian source over Rayleigh fading channels, our results suggest that parallel channel coding at the physical layer is more efficient than independent channel coding combined with multiple description source coding. More generally, we provide intuitive guidelines for allowing system designers to identify which types of systems are preferable under different scenarios of practical interest.

The strict delay constraints of real-time communication applications in packet networks limit the use of automatic repeat request (ARQ) (retransmission systems) and error correction codes with extensive interleaving and decoding over long intervals. Since packet losses can introduce significant impairments, we study the effectiveness of low delay channel coding techniques to increase transmission quality across links with bursty losses. Specifically, we consider the benefits of the newly discovered class of low delay convolutional codes known as maximally short codes. By analyzing a Gaussian source transmitted over a Gilbert-Elliott channel, we demonstrate that these codes can achieve significant gains in comparison to uncoded transmission schemes or traditional coded schemes employing Reed-Solomon block codes. To complement and validate the theoretical analysis we also present results from informal listening tests with a voice-over-IP application.

We consider source requantization in two forms - successive degradation (i.e., source fidelity reduction) and bit stealing (i.e., information embedding) when no forward planning has been done to facilitate the requantization. We focus on finite-alphabet sources with arbitrary distortion measures as well as the Gaussian-quadratic scenario. For the successive degradation problem, we show an achievable distortion-rate trade-off for non-hierarchically structured rate-distortion achieving codes, and compare it to the distortion-rate trade-off of successively refinable codes. We further consider source requantization in the form of bit stealing, whereby an information embedder acts on a quantized source, producing an output at the same rate. Building on the successive degradation results, we develop achievable distortion-rate trade-offs. Two cases are considered, corresponding to whether the source decoder is informed of any bit stealing or not. In the latter case, the embedder must produce outputs in the original source codebook. For the Gaussian-quadratic scenario, all trade-offs are within 0.5 bits/sample of the distortion-rate bound. Furthermore, for bit stealing, the use of simple post-reconstruction processing that is only a function of the embedded rate can eliminate the loss experienced by uninformed decoders.

In a variety of networks, packet losses occur in bursts. Conventional application of error correction codes for packet recovery often requires interleaving and long decoder delays. These long delays are usually unacceptable in real-time multimedia communication applications such as voice over IP (VoIP). Consequently, erasure correction codes with severe limits on delay are desirable. We present various codes suitable for correcting bursts of lost packets. In addition, we show that these codes have the shortest possible decoding delay. To demonstrate the practical benefits of these codes for VoIP, we present results of informal mean opinion score listening tests conducted with various codes.

In many multimedia applications, there is a need to authenticate a source that has been subjected to benign degradations in addition to potential tampering attacks. We develop a meaningful formulation of this problem, and identify and interpret the associated information-theoretic performance limits. The associated systems are shown to perform dramatically better than frequently proposed approaches based on information embedding techniques.