A vector quantization approach to universal noiseless coding andquantization

A two-stage code is a block code in which each block of data is coded in two stages: the first stage codes the identity of a block code among a collection of codes, and the second stage codes the data using the identified code. The collection of codes may be noiseless codes, fixed-rate quantizers, or variable-rate quantizers. We take a vector quantization approach to two-stage coding, in which the first stage code can be regarded as a vector quantizer that “quantizes” the input data of length n to one of a fixed collection of block codes. We apply the generalized Lloyd algorithm to the first-stage quantizer, using induced measures of rate and distortion, to design locally optimal two-stage codes. On a source of medical images, two-stage variable-rate vector quantizers designed in this way outperform standard (one-stage) fixed-rate vector quantizers by over 9 dB. The tail of the operational distortion-rate function of the first-stage quantizer determines the optimal rate of convergence of the redundancy of a universal sequence of two-stage codes. We show that there exist two-stage universal noiseless codes, fixed-rate quantizers, and variable-rate quantizers whose per-letter rate and distortion redundancies converge to zero as (k/2)n ^-1 log n, when the universe of sources has finite dimension k. This extends the achievability part of Rissanen's theorem from universal noiseless codes to universal quantizers. Further, we show that the redundancies converge as O(n^-1) when the universe of sources is countable, and as O(n^-1+ϵ) when the universe of sources is infinite-dimensional, under appropriate conditions     

Arbitrary source models and Bayesian codebooks in rate-distortion theory

We characterize the best achievable performance of lossy compression algorithms operating on arbitrary random sources, and with respect to general distortion measures. Direct and converse coding theorems are given for variable-rate codes operating at a fixed distortion level, emphasizing: (a) nonasymptotic results, (b) optimal or near-optimal redundancy bounds, and (c) results with probability one. This development is based in part on the observation that there is a precise correspondence between compression algorithms and probability measures on the reproduction alphabet. This is analogous to the Kraft inequality in lossless data compression. In the case of stationary ergodic sources our results reduce to the classical coding theorems. As an application of these general results, we examine the performance of codes based on mixture codebooks for discrete memoryless sources. A mixture codebook (or Bayesian codebook) is a random codebook generated from a mixture over some class of reproduction distributions. We demonstrate the existence of universal mixture codebooks, and show that it is possible to universally encode memoryless sources with redundancy of approximately (d/2) log n bits, where d is the dimension of the simplex of probability distributions on the reproduction alphabet.     

Minimax universal noiseless coding for unifilar and Markov sources (Corresp.)

Constructive upper bounds are presented for minimax universal noiseless coding of unifilar sources without any ergodicity assumptionS. These bounds are obtained by quantizing the estimated probability distribution of source letters with respect to the relative entropy. They apply both to fixed-length to variable-length (FV) and variable-length to fixed-length (VF) codes. Unifilar sources are a generalization of the usual definition of Markov sources, so these results apply to Markov sources as well. These upper bounds agree asymptotically with the lower bounds given by Davisson for FV coding of stationary ergodic Markov sources.     

Universal noiseless coding

Universal coding is any asymptotically optimum method of block-to-block memoryless source coding for sources with unknown parameters. This paper considers noiseless coding for such sources, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter. It is found that universal (i.e., zero redundancy) coding in a weighted sense is possible if and only if the per-letter average mutual information between the parameter space and the message space is zero. Universal coding is possible in a maximin sense if and only if the channel capacity between the two spaces is zero. Universal coding is possible in a minimax sense if and only if a probability mass function exists, independent of the unknown parameter, for which the relative entropy of the known conditional-probability mass-function is zero. Several examples are given to illustrate the ideas. Particular attention is given to sources that are stationary and ergodic for any fixed parameter although the whole ensemble is not. For such sources, weighted universal codes always exist if the alphabet is finite, or more generally if the entropy is finite. Minimax universal codes result if an additional entropy stability constraint is applied. A discussion of fixed-rate universal coding is also given briefly with performance measured by a probability of error.     

Precise minimax redundancy and regret

Recent years have seen a resurgence of interest in redundancy of lossless coding. The redundancy (regret) of universal fixed-to-variable length coding for a class of sources determines by how much the actual code length exceeds the optimal (ideal over the class) code length. In a minimax scenario one finds the best code for the worst source either in the worst case (called also maximal minimax) or on average. We first study the worst case minimax redundancy over a class of stationary ergodic sources and replace Shtarkov's bound by an exact formula. Among others, we prove that a generalized Shannon code minimizes the worst case redundancy, derive asymptotically its redundancy, and establish some general properties. This allows us to obtain precise redundancy for memoryless, Markov, and renewal sources. For example, we present the exact constant of the redundancy for memoryless and Markov sources by showing that the integer nature of coding contributes log(logm/(m-1))/logm+o(1) where m is the size of the alphabet. Then we deal with the average minimax redundancy and regret. Our approach here is orthogonal to most recent research in this area since we aspire to show that asymptotically the average minimax redundancy is equivalent to the worst case minimax redundancy for some classes of sources. After formulating some general bounds relating these two redundancies, we prove our assertion for memoryless and Markov sources. Nevertheless, we provide evidence that maximal redundancy of renewal processes does not have the same leading term as the average minimax redundancy (however, our general results show that maximal and average regrets are asymptotically equivalent).     

On the redundancy of optimal binary prefix-condition codes for finite and infinite sources (Corresp.)

A new lower bound, which is the tightest possible, is obtained for the redundancy of optimal bimuy prefix-condition (OBPC) codes for a memoryless source for which the probability of the most likely source letter is known. It is shown that this bound, and upper bounds obtained by Gallager and Johnsen, hold for infinite as well as finite source alphabets. Also presented are bounds on the redundancy of OBPC codes for sources satisfying the condition that each of the first several probabilities in the list of source probabilities is sufficiently large relative to the sum of the remaining probabilities.     

Universal denoising for the finite-input general-output channel

We consider the problem of reconstructing a finite-alphabet signal corrupted by a known memoryless channel with a general output alphabet. The goodness of the reconstruction is measured by a given loss function. We (constructively) establish the existence of a universal (sequence of) denoiser(s) attaining asymptotically the optimum distribution-dependent performance for any stationary source that may be generating the noiseless signal. We show, in fact, that there is a whole family of denoiser sequences with this property. These schemes are shown to be universal also in a semistochastic setting, where the only randomness assumed is that associated with the channel noise. The scheme is practical, requiring O(n/sup 1+/spl epsiv//) operations (for any /spl epsiv/>0) and working storage size sublinear in the input data length. This extends recent work that presented a discrete universal denoiser for recovering a discrete source corrupted by a discrete memoryless channel (DMC).     

Syndrome-source-coding and its universal generalization

A method of using error-correcting codes to obtain data compression, called syndrome-source-coding, is described in which the source sequence is treated as an error pattern whose syndrome forms the compressed data. It is shown that syndrome-source-coding can achieve arbitrarily small distortion with the number of compressed digits per source digit arbitrarily close to the entropy of a binary memoryless source. A "universal" generalization of syndrome-source-coding is formulated which provides robustly effective distortionless coding of source ensembles. Two examples are given comparing the performance of noiseless universal syndrome-source-coding to 1) run-length coding and 2) Lynch-Davisson-Schalkwijk-Cover universal coding for an ensemble of binary memoryless sources.     

Extension of source coding theorems for block codes to sliding-block codes

For arbitrary alphabets and single-letter fidelity criteria, two theorems are given which allow any fixed-rate or variable-rate source coding theorem for block codes to be extended to sliding-block codes. Applications are given to universal coding and to the coding of a stationary nonergodic source.     

Variable-rate trellis source encoding

The fixed slope lossy algorithm derived from the kth-order adaptive arithmetic codeword length function is extended to finite-state decoders or trellis-structured decoders. When this algorithm is used to encode a stationary, ergodic source with a continuous alphabet, the Lagrangian performance converges with probability one to a quantity computable as the infimum of an information-theoretic functional over a set of auxiliary random variables and reproduction levels, where λ>0 and -λ are designated to be the slope of the rate distortion function R(D) of the source at some D; the quantity is close to R(D)+λD when the order k used in the arithmetic coding or the number of states in the decoders is large enough, An alternating minimization algorithm for computing the quantity is presented; this algorithm is based on a training sequence and in turn gives rise to a design algorithm for variable-rate trellis source codes. The resulting variable-rate trellis source codes are very efficient in low-rate regions. With k=8, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Gaussian sources is comparable to that afforded by trellis-coded quantizers; with k=8 and the number of states in the decoder=32, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Laplacian sources is about 1 dB better than that afforded by the trellis-coded quantizers with 256 states, with k=8 and the number of states in the decoder=256, the mean-squared error encoding performance at the rates of a fraction of 1 bit/sample for highly dependent Gauss-Markov sources with correlation coefficient 0.9 is within about 0.6 dB of the distortion rate function     

Universal variable-to-fixed length source codes

A universal variable-to-fixed length algorithm for binary memoryless sources which converges to the entropy of the source at the optimal rate is known. We study the problem of universal variable-to-fixed length coding for the class of Markov sources with finite alphabets. We give an upper bound on the performance of the code for large dictionary sizes and show that the code is optimal in the sense that no codes exist that have better asymptotic performance. The optimal redundancy is shown to be H log log M/log M where H is the entropy rate of the source and M is the code size. This result is analogous to Rissanen's (1984) result for fixed-to-variable length codes. We investigate the performance of a variable-to-fixed coding method which does not need to store the dictionaries, either at the coder or the decoder. We also consider the performance of both these source codes on individual sequences. For individual sequences we bound the performance in terms of the best code length achievable by a class of coders. All the codes that we consider are prefix-free and complete     

Time-invariant trellis encoding of ergodic discrete-time sources with a fidelity criterion

The theory of sliding-block codes (nonlinear, time-invariant, discrete-time filters) is employed to obtain general source coding theorems for ergodic sources using time-invariant trellis coding (time-invariant decoding filter and replicating trellis). The results are coupled with the theory of universal block source codes to obtain universal trellis source coding theorems for classes of sources. It is shown for a certain class of sources that the problem of designing good trellis codes is equivalent to that of simulating general random processes by filtering digital memoryless sources.     

Sliding-block joint source/noisy-channel coding theorems

Sliding-block codes are nonblock coding structures consisting of discrete-time time-invariant possibly nonlinear filters. They are equivalent to time-invariant trellis codes. The coupling of Forney's rigorization of Shannon's random-coding/typical-sequence approach to block coding theorems with the strong Rohlin-Kakutani Theorem of ergodic theory is used to obtain a sliding-block coding theorem for ergodic sources and discrete memoryless noisy channels. Combining this result with a theorem on sliding-block source coding with a fidelity criterion yields a sliding-block information transmission theorem. Thus, the basic existence theorems of information theory hold for stationary nonblock structures, as well as for block codes.     

Universally optimum block codes and convolutional codes with maximum likelihood decoding

A new proof is presented for the existence of block codes whose error probability under maximum likelihood decoding is bounded asymptotically by the random coding bound universally over all discrete memoryless channels. On the basis of this result, the existence of convolutional codes with universally optimum performance is shown. Furthermore the existence of block codes which attain the expurgated bound universally over all discrete memoryless channels is proved under the use of maximum likelihood decoding.     

The redundancy of source coding with a fidelity criterion .II.Coding at a fixed rate level with unknown statistics

The redundancy problem of universal lossy source coding at a fixed rate level is considered. Under some condition on the single-letter distortion measure, which implies that the cardinality K of the reproduction alphabet is not greater than the cardinality J of the source alphabet, it is shown that the redundancy of universally coding memoryless sources p by nth-order block codes of rate R goes like |(∂/∂R)d(p,R)|Kln n/2n+o(ln n/n) for all memoryless sources p except a set whose volume goes to 0 as the block length n goes to infinity, where d(p,R) denotes the distortion rate function of p. Specifically, for any sequence {C_n}_n=1^∞ of block codes, where C_n is an nth-order block code at the fixed rate R, and any ϵ>0, the redundancy D_n(C _n,p) of C_n for p is greater than or equal to |(∂/∂R)d(p,R)|(K-ϵ)ln n/2n for all p satisfying some regular conditions except a set whose volume goes to 0 as n→∞. On the other hand, there exists a sequence {C_n}_n=1^∞ of block codes at the rate R such that for any p satisfying some regular conditions, the super limit of D_n(C_n,p)|(ln n/n) is less than or equal to |(∂/∂R)d(p,R)|K/2     

Universal Context Based Decoding with Low-Density Parity-Check Codes

Universal estimation strategies are proposed to improve channel decoding of sequences that contain context based redundancy. The new methods combine techniques from universal compression, such as the Burrows-Wheeler Transform (BWT) and segmentation of piecewise stationary memoryless sources (PSMS's) with recently proposed methods of discrete denoising. Simulation results with systematic low density parity check (LDPC) codes show significant improvements of the proposed methods on standard decoding, even when the actual sequence context model is unknown in advance. The combined methods inherit advantages of each of the separate methods.     

On the redundancy of trellis lossy source coding

It is well known that trellis lossy source codes have better performance/complexity tradeoff than block codes, as shown by simulations. This makes the trellis coding technique attractive in practice. To get a better understanding of this fact, this paper studies the redundancy of trellis coding for memoryless sources and compares it with a similar result for block codes     

Feedback Capacity of the Compound Channel

In this work, we find the capacity of a compound finite-state channel (FSC) with time-invariant deterministic feedback. We consider the use of fixed length block codes over the compound channel. Our achievability result includes a proof of the existence of a universal decoder for the family of FSCs with feedback. As a consequence of our capacity result, we show that feedback does not increase the capacity of the compound Gilbert-Elliot channel. Additionally, we show that for a stationary and uniformly ergodic Markovian channel, if the compound channel capacity is zero without feedback then it is zero with feedback. Finally, we use our result on the FSC to show that the feedback capacity of the memoryless compound channel is given by inf_thetas max_QX I(X; Y |thetas).     

On variable-length-to-block coding

Variable-length-to-block codes are a generalization of run-length codes. A coding theorem is first proved. When the codes are used to transmit information from fixed-rate sources through fixed-rate noiseless channels, buffer overflow results. The latter phenomenon is an important consideration in the retrieval of compressed data from storage. The probability of buffer overflow decreases exponentially with buffer length and we determine the relation between rate and exponent size for memoryless sources. We obtain codes that maximize the overflow exponent for any given transmission rate exceeding the source entropy and present asymptotically optimal coding algorithms whose complexity grows linearly with codeword length. It turns out that the optimum error exponents of variable-length-to-block coding are identical with those of block-to-variable-length coding and are related in an interesting way to Renyi's generalized entropy function.