Onion peeling codes address a distributed data compression scenario related to Slepian-Wolf (SW) data compression. In a 2-user onion peeling code, as in a 2-user SW code, two dependent sources are compressed independently; while the SW code decodes both sources jointly using both source descriptions, the onion peeling code reconstructs the first source using only the first source description and then uses the first source reconstruction and the second source description to reconstruct the second source. The authors' prior results show that first-stage compressors that are almost identical in first-source reconstruction reliability and efficiency can exhibit extremely different best-case performance for the second source. This paper proposes the use of low density parity check (LDPC) source coding in the first stage of an onion peeling code and shows that, with high probability, the random LDPC code design used in the evaluation of this approach generates a first-stage code that performs well both in compressing the first source and in assisting the compressor of the second source. The method works universally for any conditional distribution on the second source given the first, meaning that one does not have to know the conditional distribution of the second source given the first to design a first-stage code with good performance on the second source.

This work considers almost lossless onion peeling data compression. In onion peeling data compression, as in Slepian-Wolf data compression, multiple transmitters independently encode their respective sources and transmit their descriptions to a shared decoder. Onion peeling codes differ from Slepian-Wolf codes in that the onion peeling decoder must sequentially decode the individual sources rather than making a single joint decoding decision. This work considers an almost lossless two-stage code. The main result shows that when the first source is coded by a near-optimal code for a given first-stage error constraint, the conditional entropy rate of the second source, given this imperfect reconstruction, can vary within a gap that does not vanish when the blocklength grows without bound. It is also shown that the lower bound for the second-stage conditional entropy rate can be achieved using a classic random binning code in the first stage.

This work introduces a framework for an asynchronous random access source code (ARASC) and bounds the achievable performance under this framework. Like prior multiple access (or Slepian-Wolf) source codes, the ARASC enables multiple transmitters to efficiently, reliably, and independently describe dependent sources to a common receiver. As in prior "random access" codes, the number of active encoders is unknown a priori to both the transmitters and the receiver and single-bit stop-feedback from the receivers to the transmitters enables variable-rate coding. Unlike prior works, the proposed system eliminates all forms of block synchronization. The main result is a two-transmitter achievability bound demonstrating the achievability of a first-order average rate across blocks equal to the weighted average of the point-to-point source coding rate and multiple access achievable sum rate. The weights observed approach the fractions of time that separate and simultaneous observations are encoded. The result’s second order term bounds the speed at which the average rate approaches this weighted average.

We discuss two approaches for decoding at arbitrary rates in the Slepian-Wolf problem - time sharing and source splitting - both of which rely on constituent vertex decoders. We consider the error exponents for both schemes and conclude that source-splitting is more robust at coding at arbitrary rates, as the error exponent for time-sharing degrades significantly at rates near vertices. As a by-product of our analysis, we exhibit an interesting connection between minimum mean-squared error estimation and error exponents

Summary form only given. We study the source coding problem on a simple two-hop network with side information on the middle and end nodes. For the degraded case, where the side information at the end node is weaker than the side information at the middle node, a complete characterization of the rate-distortion region is derived.

Minimum-entropy decoding is a universal decoding algorithm used in decoding block compression of discrete memoryless sources as well as block transmission of information across discrete memoryless channels. Extensions can also be applied for multiterminal decoding problems, such as the Slepian-Wolf source coding problem. The 'method of types' has been used to show that there exist linear codes for which minimum-entropy decoders achieve the same error exponent as maximum-likelihood decoders. Since minimum-entropy decoding is NP-hard in general, minimum-entropy decoders have existed primarily in the theory literature. We introduce practical approximation algorithms for minimum-entropy decoding. Our approach, which relies on ideas from linear programming, exploits two key observations. First, the 'method of types' shows that that the number of distinct types grows polynomially in n. Second, recent results in the optimization literature have illustrated polytope projection algorithms with complexity that is a function of the number of vertices of the projected polytope. Combining these two ideas, we leverage recent results on linear programming relaxations for error correcting codes to construct polynomial complexity algorithms for this setting. In the binary case, we explicitly demonstrate linear code constructions that admit provably good performance.

Summary form only given. In this paper, we bound the rate-distortion region for a four-node network. The results are the first known expansion of rate-distortion theory from single-hop networks (every source has a direct connection to each of its destinations), to multihop networks, which allow intermediate nodes. While single-hop network source coding solutions may be applied in multihop networks, such applications require explicit rate allocation for each source-destination pair, and the resulting solutions may be suboptimal. We therefore tackle the multihop network source coding problem directly using a diamond network.

We introduce three new innovations for compression using LDPCs for the Slepian-Wolf problem. The first is a general iterative Slepian-Wolf decoding algorithm that incorporates the graphical structure of all the encoders and operates in a 'turbo-like' fashion. The second innovation introduces source-splitting to enable low-complexity pipelined implementations of Slepian-Wolf decoding at rates besides corner points of the Slepian-Wolf region. This innovation can also be applied to single-source block coding for reduced decoder complexity. The third approach is a linear programming relaxation to maximum-likelihood sequence decoding that exhibits the ML-certificate property. This can be used for decoding a single binary block-compressed source as well as decoding at vertex points for the binary Slepian-Wolf problem. All three of these innovations were motivated by recent analogous results in the channel coding domain.

In this paper, we build multiresolution source codes using entropy constrained dithered scalar quantizers. We demonstrate that for n-dimensional random vectors, dithering followed by uniform scalar quantization and then by entropy coding achieves performance close to the n-dimensional optimum for a multiresolution source code. Based on this result, we propose a practical code design algorithm and compare its performance with that of the set partitioning in hierarchical trees (SPIHT) algorithm on natural images.

The performance of the KLT for transform coding applications was examined. The KLT has long been viewed as the best available block transform for transform coding. The fixed-rate and variable-rate transform codes were also presented. The fixed-rate approach uses an optimal fixed-rate scalar quantizer to describe the transform coefficients; the variable-rate approach uses a uniform scalar quantizer followed by an optimal entropy code. Earlier work shows that for the variable-rate case, there exist sources on which the KLT is not unique and the optimal transform code matched to a "worst" KLT yields performance as much as 1.5 dB worse than the optimal transform code matched to a "best" KLT. The results were strengthened to show that in both the fixed-rate and the variable-rate coding frameworks, there exist sources for which the performance penalty for using a "worst" KLT can be made arbitrarily large. Further demonstrations in both frameworks show that there exist sources for which even a best KLT gives suboptimal performance. Finally, the results show that even for vector sources where the KLT yields independent coefficients, the KLT can be suboptimal for fixed-rate coding.

Summary form only given. Assuming the squared error distortion measure, the performance achieved is bounded by using scalar entropy constrained dithered quantization (SECDQ) to build multi-resolution (MR), multiple access (MA) and broadcast system (BS) source codes. The resulting performances for arbitrary source distribution are discussed.

The instantaneous side of information source code (SISC) design is considered. In the SISC configuration, the encoder describes source X to the decoder; the decoder uses this description and side information Y, to reconstruct X. Prior work on lossless and near-lossless SISC design demonstrates that globally optimal design is NP-hard. A family of polynomial complexity code design algorithms is introduced that approximates the optimal solution for lossless and near-lossless SISCs. The algorithm may be used to design both Huffman and arithmetic SISCs for an arbitrary probability mass function p(x,y). Experimental results comparing the resulting performances to each other and to the theoretical limit are included.

We consider the properties of optimal fixed-rate and entropy-constrained scalar quantizers for finite alphabet sources. In particular, we consider conditions under which the optimal scalar quantizer with contiguous codecells achieves performance no worse than the optimal scalar quantizer without the constraint of codecell contiguity. In addition to traditional scalar quantizers, we consider multi-resolution scalar quantizers and multiple description scalar quantizers and also look briefly at codes with decoder side information (Wyner-Ziv codes). While the conditions under which codecell contiguity is consistent with optimality in fixed-rate and entropy-constrained scalar quantization are quite broad, even with the squared error distortion measure, codecell contiguity in fixed-rate and entropy-constrained multi-resolution, multiple description, and Wyner-Ziv scalar quantization can preclude optimality for some sources.

We propose a polynomial-time algorithm for optimal scalar quantizer design on discrete-alphabet sources. Special cases of the proposed approach yield optimal design algorithms for fixed-rate and entropy-constrained scalar quantizers, multi-resolution scalar quantizers, multiple description scalar quantizers, and Wyner-Ziv scalar quantizers. The algorithm guarantees globally optimal solutions for fixed-rate and entropy-constrained scalar quantizers and constrained optima for the other coding scenarios. We derive the algorithm by demonstrating the connection between scalar quantization, histogram segmentation, and the shortest path problem in a certain directed acyclic graph.

A network source code is an optimal source code for a network. To design network source codes, we require each node to have a single encoder, which jointly encodes all messages transmitted by that node, and a single decoder, which jointly decodes all messages arriving at that node. Given a distribution over the sources, the design of the network source code jointly optimizes all encoders and decoders to obtain the best performance with respect to a user-defined priority schedule over the rates and distortions of the system. In this paper we focus on fixed-rate codes and address the implementation of an existing design algorithm for optimal network vector quantizers. Implementing the design algorithm is not straightforward since each encoder must choose its reproduction based on the expected behavior of sources that are unknown to it. We describe a new implementation approach and demonstrate its performance on a three-node network. In addition, we extend the design algorithm to allow the decoder at each node to use side information (specifically, the messages that are to be encoded by the encoder at the same node).

A multiple access source code (MASC) is a source code designed for the following network configuration: a pair of correlated information sequences {X/sub i/}/sub i=1//sup /spl infin// and {Y/sub i/}/sub i=1//sup /spl infin// is drawn i.i.d. according to the joint probability mass function (p.m.f.) p(x,y); the encoder for each source operates without knowledge of the other source; the decoder jointly decodes the encoded bit streams from both sources. The work of Slepian and Wolf (1973) describes all rates achievable by MASCs with arbitrarily small but non-zero error probabilities but does not address truly lossless coding or code design. We consider practical code design for lossless and near lossless MASCs. We generalize the Huffman and arithmetic code design algorithms to attain the corresponding optimal MASC codes for arbitrary p.m.f. p(x,y). Experimental results comparing the optimal achievable rate region to the Slepian-Wolf region are included.

This work combines a new fast context-search algorithm with the lossless source coding models of PPM to achieve a lossless data compression algorithm with the linear context-search complexity and memory of BWT and Ziv-Lempel codes and the compression performance of PPM-based algorithms. Both sequential and nonsequential encoding are considered. The proposed algorithm yields an average rate of 2.27 bits per character (bpc) on the Calgary corpus, comparing favorably to the 2.33 and 2.34 bpc of PPM5 and PPM/sup */ and the 2.43 bpc of BW94 but not matching the 2.12 bpc of PPMZ9, which, at the time of this publication, gives the greatest compression of all algorithms reported on the Calgary corpus results page. The proposed algorithm gives an average rate of 2.14 bpc on the Canterbury corpus. The Canterbury corpus Web page gives average rates of 1.99 bpc for PPMZ9, 2.11 bpc for PPM5, 2.15 bpc for PPM7, and 2.23 bpc for BZIP2 (a BWT-based code) on the same data set.

Multiple description codes are data compression algorithms designed with the goal of minimizing the distortion caused by data loss in packet-based or diversity communications systems. Recently, techniques that achieve multiple description coding by combining embedded source codes with unequal error protection channel codes have become popular in the literature. These codes allow for data reconstruction with any subset of the transmitted packets and achieve progressively better source reconstructions as more and more packets are decoded. The given methods may be applied to any embedded source description. While applicability to all embedded source codes provides great flexibility, this separation approach begs the question of whether better performance could be achieved by taking advantage of the internal structure of a particular embedded code. In this paper, we investigate an extremely simple method for using an embedded source code's internal state information in the construction of a multiple description code. In particular, we protect an embedded SPIHT bitstream by adding to that bitstream periodic descriptions of state information from the encoder, and we demonstrate how the state information can be used to recover lost bits. For low probabilities of network packet loss, the proposed algorithm achieves performance within 0.35 dB of the performance of a more sophisticated channel coding algorithm when both algorithms are applied to same SPIHT embedded source code.

Broadcast systems are a class of networks where one system node (transmitter) simultaneously sends both common and independent, information to multiple nodes (receivers) in the system. Compressing the messages transmitted in such systems using traditional (single-transmitter, single-receiver) techniques requires use of a collection of independent source codes, one for each message sent through the system. The result of this approach is a system with multiple independent encoders at the transmitter and multiple independent decoders at each receiver. An alternative approach is to design a single joint encoder at the transmitter and a single joint decoder at each receiver. We call the resulting code a "broadcast system source code". This paper treats the theory and practice of optimal lossless and lossy (fixed- and variable-rate) broadcast system source codes. The results given include: theoretical limits for lossless source code performance on broadcast systems; an optimal lossless source code design algorithm; an optimal lossy source code design algorithm that generalizes the generalized Lloyd algorithm to broadcast systems; and experimental results for fixed- and variable-rate code performance in a two-receiver broadcast system.

We here consider a theoretical evaluation of data compression algorithms based on the Burrows Wheeler transform (BWT). The main contributions include a variety of very simple new techniques for BWT-based universal lossless source coding on finite-memory sources and a set of new rate of convergence results for BWT-based source codes. The result is a theoretical validation and quantification of the earlier experimental observation that BWT-based lossless source codes give performance better than that of Ziv-Lempel-style codes and almost as good as that of prediction by partial mapping (PPM) algorithms.

Packet-based data communication systems suffer from packet loss under high network traffic conditions. As a result, the receiver is often left with an incomplete description of the requested data. Multiple description source coding addresses the problem of minimizing the expected distortion caused by packet loss. An equivalent problem is that of source coding for data transmission over multiple channels where each channel has some probability of breaking down. Recent work in practical multiple description coding explores the design of multiple description scalar and vector quantizers for the case of two channels or packets. This paper presents a new practical algorithm, based on a ternary tree structure, for the design of both fixed- and variable-rate multiple description vector quantizers for an arbitrary number of channels. Experimental results achieved by codes designed with this algorithm show that they perform well under a wide range of packet loss scenarios.

Consider a multi-resolution source code for describing a stationary source at L resolutions. The description at the first resolution is given at rate R/sub 1/ and achieves an expected distortion no greater than D/sub 1/. The description at the second resolution includes both the first description and a refining description of rate R/sub 2/ and achieves expected distortion no greater than D/sub 2/, and so on. Previously derived multi-resolution source coding bounds describe the family of achievable rate and distortion vectors ((R/sub 1/, R/sub 2/, ..., R/sub L/), (D/sub 1/, D/sub 2/, D/sub L/)). By examining these multi-resolution rate-distortion bounds, we gain insight into the problem of practical multi-resolution source coding. These insights lead to a new multi-resolution source code based on the tree-structured vector quantizer. This paper covers the algorithm, its optimal design, and preliminary experimental results.

Effros and Chou (see Proceedings of the IEEE International Conference on Image Processing, Washington, DC, 1995) introduce a two-stage universal transform code called the weighted universal transform code (WUTC). By replacing JPEG's single, non-optimal transform code with a collection of optimal transform codes, the WUTC achieves significant performance gains over JPEG. The computational and storage costs of that performance gain are effectively the computation and storage required to operate and store a collection of transform codes rather than a single transform code. We consider two complexity- and storage-constrained variations of the WUTC. The complexity and storage of the algorithm are controlled by constraining the order of the bases. In the first algorithm, called the fast WUTC (FWUTC), complexity is controlled by controlling the maximum order of each transform. On a sequence of combined text and gray-scale images, the FWUTC achieves performance comparable to the WUTC. In the second algorithm, called the jointly optimized fast WUTC (JWUTC), the complexity is controlled by controlling the average order of the transforms. On the same data set and for the same complexity, the performance of the JWUTC always exceeds the performance of the FWUTC. The JWUTC and FWUTC algorithm are interesting both for their complexity and storage savings in data compression and for the insights that they lend into the choice of appropriate fixed- and variable-order bases for image representation.

A new algorithm for variable dimension weighted universal coding is introduced. Combining the multi-codebook system of weighted universal vector quantization (WUVQ), the partitioning technique of variable dimension vector quantization, and the optimal design strategy common to both, variable dimension WUVQ allows mixture sources to be effectively carved into their component subsources, each of which can then be encoded with the codebook best matched to that source. Application of variable dimension WUVQ to a sequence of medical images provides up to 4.8 dB improvement in signal to quantization noise ratio over WUVQ and up to 11 dB improvement over a standard full-search vector quantizer followed by an entropy code. The optimal partitioning technique can likewise be applied with a collection of noiseless codes, as found in weighted universal noiseless coding (WUNC). The resulting algorithm for variable dimension WUNC is also described.>

Weighted universal vector quantization uses traditional codeword design techniques to design locally optimal multi-codebook systems. Application of this technique to a sequence of medical images produces a 10.3 dB improvement over standard full search vector quantization followed by entropy coding at the cost of increased complexity. In this proposed variation each codebook in the system is given a mean or 'prediction' value which is subtracted from all supervectors that map to the given codebook. The chosen codebook's codewords are then used to encode the resulting residuals. Application of the mean-removed system to the medical data set achieves up to 0.5 dB improvement at no rate expense.>