This paper introduces a new formal mathematical problem initially motivated by an application of Network Coding (NC) to Information Centric Networks (ICN). It is of more limited scope but is remotely inspired by the well-known index coding problem. It is presented as follows: "given a vector space, can one construct several subsets of vectors, such that when drawing arbitrarily one vector from each subset, the selected vectors would be always linearly independent?". Answering this question is a step to construct an ICN efficient scheme with NC. We prove that our previously introduced construction is the only possible solution for a large family of constructions. This is an important result by itself. It also implies that any alternate solutions are outside this family and we propose one example.

This paper investigates two classes of relay channels, the Gaussian relay channel and the Gaussian two-way relay channel, when additive noises at the relay and destination(s) are correlated. Lattice codes are used to achieve the rate region for Compress-and-Forward (relay channel) and Compress/Decode-and-Forward (two-way relay channel). Numerical calculations show that there exist particular values of the correlation co-efficient such that the gap between the Cut-Set Bound (CSB) and the proposed schemes is minimal.

This paper studies the extension of the multiway relay channel model with restricted encoders (introduced by Gündüz et al.) by adding unit-gain intra-cluster links. In this model, multiple clusters of users communicate with the help of one relay and the users within a cluster wish to exchange messages among themselves. We obtain achievable rates and gaps to the cut-set bound as a function of the number of users and the cluster-to-relay gain g.

This paper presents a new iterative decoding algorithm for the source coding with coded side information problem. Side information (SI) is compressed to an index by a many-to-one (quantization) function. Instead of using the reconstruction corresponding to the quantization index as a single representative SI word to aid the main decoder, one can modify it by projecting an intermediate estimate of the source word onto the Voronoi cell associated to the SI index. The hope is that the projection brings the representative SI word closer to the source word, and thus accelerates iterative decoding. Simulations using LDPC syndrome coding in the main branch and trellis-coded quantization in the SI branch show that for a fixed number of decoder iterations, this method indeed increases the number of correctly decoded source words. In fact, the decoding threshold is shifted, which may be attributed to a partial compensation of the suboptimality of the quantizer.

This paper addresses the design of joint source-channel variable-length codes with maximal free distance for given codeword lengths. While previous design methods are mainly based on bounds on the free distance of the code, the proposed algorithm exploits an exact characterization of the free distance. The code optimization is cast in the framework of mixed-integer linear programming and allows to tackle practical alphabet sizes in reasonable computing time.

This paper revisits earlier work on the achievable rate-region for the coded side-information problem. For specific source distributions we provide computable extreme rate points. As opposed to previous works, we present short and concise proofs and additional rate points below the time-sharing line of previously known rate points. Our results are based on a formulation as an optimization problem.

This paper proposes branch-and-prune algorithms for searching prefix-free joint source-channel codebooks with maximal free distance for given codeword lengths. For that purpose, it introduces improved techniques to bound the free distance of variable-length codes.

This paper studies coding schemes for theq-ary symmetric channel based on binary low-density parity-check (LDPC) codes that work for any alphabet sizeq=2m,m∈N, thus complementing some recently proposed packet-based schemes requiring largeq. First, theoretical optimality of a simple layered scheme is shown; then, a practical coding scheme based on a simple modification of standard binary LDPC decoding is proposed. The decoder is derived from first principles and using a factor-graph representation of a front end that mapsq-ary symbols to groups ofmbits connected to a binary code. The front end can be processed with a complexity that is linear inm=log2q. An extrinsic information transfer chart analysis is carried out and used for code optimization. Finally, it is shown how the same decoder structure can also be applied to a larger class ofq-ary channels.

The rate distortion behavior of sparse memoryless sources is studied. These serve as models of sparse signal representations and facilitate the performance analysis of “sparsifying” transforms like the wavelet transform and nonlinear approximation schemes. For strictly sparse binary sources with Hamming distortion, R(D) is shown to be almost linear. For nonstrictly sparse continuous-valued sources, termed compressible, two measures of compressibility are introduced: incomplete moments and geometric mean. The former lead to low- and high-rate upper bounds on mean squared error D(R), while the latter yields lower and upper bounds on source entropy, thereby characterizing asymptotic R(D) behavior. Thus, the notion of compressibility is quantitatively connected with actual lossy compression. These bounding techniques are applied to two source models: Gaussian mixtures and power laws matching the approximately scale-invariant decay of wavelet coefficients. The former are versatile models for sparse data, which in particular allow to bound high-rate compression performance of a scalar mixture compared to a corresponding unmixed transform coding system. Such a comparison is interesting for transforms with known coefficient decay, but unknown coefficient ordering, e.g., when positions of highest-variance coefficients are unknown. The use of these models and results in distributed coding and compressed sensing scenarios are also discussed.

This paper revisits earlier work on rate distortion behavior of sparse sources, namely it highlights the fact that a graphical sparsity characterization proposed in [1] is a Lorenz curve, a tool for summarizing income inequality that has been used by economists for over a century. The Lorenz curve associated to a memoryless source can be used to obtain upper bounds on the distortion rate function, thus characterizing source compressibility. It is shown that an order relation on Lorenz curves induces an analogous relation on distortion rate upper bounds. This can be used to characterize the compressibility of certain parametric families of source distributions, for which an order on the parameters induces an order on Lorenz curves.

This paper considers the optimization of a class of joint source-channel codes described by finite-state encoders (FSEs) generating variable-length codes. It focuses on FSEs associated to joint source-channel integer arithmetic codes, which are uniquely decodable codes by design. An efficient method for computing the free distance of such codes using Dijkstra's algorithm is proposed. To facilitate the search for codes with good distance properties, FSEs are organized within a tree structure, which allows the use of efficient branch-and-prune techniques avoiding a search of the whole tree.

This paper considers the optimization of Error-Correcting Variable-Length Codes (EC-VLC), which are a class of joint-source channel codes. The aim is to find a prefix-free codebook with the largest possible free distance for a given set of codeword lengths, ℓ = (ℓ1, ℓ2, ..., ℓM). The proposed approach consists in ordering all possible codebooks associated to ℓ on a tree, and then to apply an efficient branch-and-prune algorithm to find a codebook with maximal free distance. Three methods for building the tree of codebooks are presented and their efficiency is compared.

The class of variable-length finite-state joint sourcechannel codes is defined and a polynomial complexity algorithm for the evaluation of their distance spectrum presented. Issues in truncating the spectrum to a finite number of (possibly approximate) terms are discussed and illustrated by experimental results.

Practical schemes for distributed video coding with side information at the decoder need to consider non-standard correlation models in order to take non-stationarities into account. In this paper we introduce two correlation models for Gaussian sources, the Gaussian- Bernoulli-Gaussian (GBG) and the Gaussian-Erasure (GE) models, and evaluate lower and upper bounds on their rate-distortion functions. Provided that the probability of impulse noise or of erasures remains small, these bounds remain close to the rate-distortion function for Gaussian correlation. Two practical schemes for the GE correlation model are also presented, with performance about 1.5 dB away from the lower bound.

We study coding schemes for the q-ary symmetric channel with moderate alphabet sizes q that are much smaller than the q = 2256considered as ldquoentry levelrdquo in some recently proposed packet-based schemes. First, we show theoretical optimality of a simple layered scheme, then we propose a practical coding scheme based on a simple modification of standard binary LDPC decoding.

In this correspondence, we consider one-to-one encodings for a discrete memoryless source, which are "one-shot" encodings associating a distinct codeword with each source symbol. Such encodings could be employed when only a single source symbol rather than a sequence of source symbols needs to be transmitted. For example, such a situation can arise when the last message must be acknowledged before the next message can be transmitted. We consider two slightly different types of one-to-one encodings (depending on whether the empty codeword is used or not) and obtain lower and upper bounds on the expected length of optimal one-to-one codes. We first give an extension of a known tight lower bound on the expected length of optimal one-to-one codes for the case that the the size of the source alphabet is finite and partial information about the source symbol probabilities is available. As expected, our lower bound is no less than the previously known lower bound obtained without side information about the source symbol probabilities. We then consider the case that the source entropy is available and derive arbitrarily tight lower bounds on the expected length of optimal one-to-one codes. We also derive arbitrarily tight lower bounds for the case that the source entropy and the probability of the most likely source symbol are available. Finally, given that the probability of the most likely source symbol is available, we obtain an upper bound on the expected length of optimal one-to-one codes. Our upper bound is tighter than the best upper bound known in the literature

This paper presents a coding scheme suitable for transmission of multimedia data over mixed Internet and wireless channels. To resist packet losses and provide good compression performance, an entropy-constrained multiple description trellis-coded quantizer is combined with a variable-length code. Furthermore, to be robust to transmission errors, an iterative decoding scheme is developed, which exploits the redundancy between the generated descriptions. Experimental results show the performance of this scheme in terms of efficiency and robustness.

In joint source-channel (JSC) schemes based on arithmetic coding (AC), additional redundancy may be introduced in order to reduce transmission errors. The purpose of this work is to provide analytical tools to predict and evaluate the effectiveness of that redundancy. Integer binary AC is modeled by a reduced-state automaton in order to obtain a bit-clock trellis of the AC. Considering AC as a trellis code, distance spectra are then derived. In particular, an algorithm to compute the free distance of an arithmetic code is proposed. The obtained code properties allow to compute upper bounds on both bit error and symbol error probabilities and thus provide an objective criterion to analyze the behavior of JSCAC schemes when used on noisy channels

Data partitioning in H.264 extended profile video coding enables unequal error protection. Its performance can be improved if the decoder tries to also decode packets containing errors. We propose a soft-input sequential decoding algorithm for the prediction residuals encoded in low-priority packets. Information from the decoding process is then used to control additional error concealment. This combined technique provides significant PSNR gains compared to a simple packet-loss scenario.

Many transform coders use a type of nonlinear approximation that selects all coefficients with magnitudes above threshold, encodes their positions, and and quantizes their values. This kind of two-stage scheme is very effective at low rates. We derive an upper bound on the operational rate distortion function of such threshold-based nonlinear approximations. The bound is applied to the spike process, which is a generic model for sparse transform coefficients, and to a Gaussian mixture process that is a better model for wavelet coefficients in image transform codes. The results exhibit the same change in distortion decay between low and high rates which is typical for such image coders.

Recent rate-distortion analyses of image transform coders are based on a trade-off between the lossless coding of coefficient positions versus the lossy coding of the coefficient values. We propose spike processes as a tool that allows a more fundamental trade-off, namely between lossy position coding and lossy value coding. We investigate the Hamming distortion case and give analytic results for single and multiple spikes. We then consider upper bounds for a single Gaussian spike with squared error distortion. The obtained results show a rate distortion behavior which switches from linear at low rates to exponential at high rates.

Biorthogonal wavelets have been used with great success in most of the recent transform image coders. By using the new balanced multiwavelets, one can now easily design fully orthogonal linear phase FIR transform schemes. The aim of our work is to assess whether the added orthogonality yields a performance gain compared to traditional biorthogonal transforms. As comparison platform we use the well-known SPIHT codec, which is based on the significance tree quantization (STQ) principle. Without any particular fine-tuning the multiwavelet codec performs within 0.5 dB of SPIHT. A closer inspection shows however that it is hard to improve on this, therefore re-establishing the rule of thumb that strict orthogonality is not a key factor in image transform coding. More details can be obtained on the [WEB] at http://lcavwww.epfl.ch/~weidmann/mwcoder.

This paper presents a novel approach to image caching for image databases, Web browsers, proxies and other similar applications. Current caches employ a hard strategy: either the image is stored in the cache, or it is not. In a soft cache, a variable amount of memory is assigned to each image. This is ideally matched to progressive image file formats. Our strategy for optimal soft caching considers the image download delay as a distortion measure. Then the minimization of the expected delay can be carried out in an operational rate-distortion framework. We present optimal theoretical solutions as well as simulation results.