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.     

Causal coding of stationary sources and individual sequences with high resolution

In a causal source coding system, the reconstruction of the present source sample is restricted to be a function of the present and past source samples, while the code stream itself may be noncausal and have variable rate. Neuhoff and Gilbert showed that for memoryless sources, optimum performance among all causal source codes is achieved by time-sharing at most two memoryless codes (quantizers) followed by entropy coding. In this work, we extend Neuhoff and Gilbert's result in the limit of small distortion (high resolution) to two new settings. First, we show that at high resolution, an optimal causal code for a stationary source with finite differential entropy rate consists of a uniform quantizer followed by a (sequence) entropy coder. This implies that the price of causality at high resolution is approximately 0.254 bit, i.e., the space-filling loss of the uniform quantizer. Then, we consider individual sequences and introduce a deterministic analogue of differential entropy, which we call "Lempel-Ziv differential entropy." We show that for any bounded individual sequence with finite Lempel-Ziv differential entropy, optimum high-resolution performance among all finite-memory variable-rate causal codes is achieved by dithered scalar uniform quantization followed by Lempel-Ziv coding. As a by-product, we also prove an individual-sequence version of the Shannon lower bound.     

The redundancy of source coding with a fidelity criterion. 1. Knownstatistics

The problem of redundancy of source coding with respect to a fidelity criterion is considered. For any fixed rate R>0 and any memoryless source with finite source and reproduction alphabets and a common distribution p, the nth-order distortion redundancy D_n(R) of fixed-rate coding is defined as the minimum of the difference between the expected distortion per symbol of any block code with length n and rate R and the distortion rate function d(p,R) of the source p. It is demonstrated that for sufficiently large n, D_n(R) is equal to -(∂/∂R)d(p,R) ln n/2n+o(ln n/n), where (∂/∂R)d(p,R) is the partial derivative of d(p,R) evaluated at R and assumed to exist. For any fixed distortion level d>0 and any memoryless source p, the nth-order rate redundancy R_n(d) of coding at fixed distortion level d (or by using d-semifaithful codes) is defined as the minimum of the difference between the expected rate per symbol of any d-semifaithful code of length n and the rate-distortion function R(p,d) of p evaluated at d. It is proved that for sufficiently large n, R_n(d) is upper-bounded by ln n/n+o(ln n/n) and lower-bounded by In n/2n+o(In n/n). As a by-product, the lower bound of R_n(d) derived in this paper gives a positive answer to a conjecture proposed by Yu and Speed (1993)     

On the redundancy of lossy source coding with abstract alphabets

The redundancy problem of lossy source coding with abstract source and reproduction alphabets is considered. For coding at a fixed rate level, it is shown that for any fixed rate R>0 and any memoryless abstract alphabet source P satisfying some mild conditions, there exists a sequence {C_n}_n=1^∞ of block codes at the rate R such that the distortion redundancy of C_n (defined as the difference between the performance of C_n and the distortion rate function d(P, R) of P) is upper-bounded by |(∂d(P,R))/(∂R)| ln n/2n+o(ln n/n). For coding at a fixed distortion level, it is demonstrated that for any d>0 and any memoryless abstract alphabet source P satisfying some mild conditions, there exists a sequence {C_n}_n=1^∞ of block codes at the fixed distortion d such that the rate redundancy of C_n (defined as the difference between the performance of C _n and the rate distortion function R(P,d) of P) is upper-bounded by (7ln n)/(6n)+o(ln n/n). These results strengthen the traditional Berger's (1968, 1971) abstract alphabet source coding theorem, and extend the positive redundancy results of Zhang, Yang, and Wei (see ibid., vol.43, no.1, p.71-91, 1997, and ibid., vol.42, p.803-21, 1996) on lossy source coding with finite alphabets and the redundancy result of Wyner (see ibid., vol.43, p.1452-64, 1997) on block coding of memoryless Gaussian sources     

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     

Strong converses in source coding relative to a fidelity criterion

Two strong converses are obtained for an abstract alphabet stationary ergodic source coded relative to an appropriate fidelity criterion. It is shown that given a distortion rate point (D, R) that lies below the rate distortion curve, (1) block codes that operate at rate level R must encode sample source blocks at a rate exceeding D with probability tending to one as the block length tends to infinity, and (2) variable-rate codes that operate at distortion level D must encode sample source blocks at a rate exceeding R with probability tending to one as the block length tends to infinity. The previously known weak converses guarantee only that the indicated probabilities remain bounded away from zero as block length tends to infinity. The proofs of the strong converses involve sample converses in source coding theory     

Variable rate coding for nonergodic sources and classes of ergodic sources subject to a fidelity constraint

This paper is concerned with two problems in the theory of source coding subject to a maximum average distortion constraint. The first problem involves the coding of a nonergodic discrete time source and the second involves coding for a class of ergodic discrete time sources. Coding theorems are given for both of these situations for very general source alphabets. The codes that are obtained here will, in general, be variable length codes so that average code rate and average distortion are the measures of performance.     

Variable Length Encoding of Binary Memoryless Sources with a Fidelity Measure

This concise paper deals with variable length source coding for binary memoryless sources with a fidelity criterion. The encoding scheme under consideration is an (M_{c}, N, K) code consisting of a distortionless run-length inner code of size Mcand an outer code that maps each source vector of lengthNto a codeword of length less than or equal toK. The encoding of the outer code is accomplished by means of a trellis search, and the distortion measure used is a Hamming distance. For composite binary memoryless sources an adaptive (M_{c}, N) code can be constructed by varying the constraintKon codeword length according to the source statistics. The (M_{c}, N, K), and (M_{c}, N) codes are insensitive to the inaccuracy in estimating the source probabilities. Rate-distortion curves, obtained by computer simulation, are plotted along with the theoretical rate-distortion functionR(D).     

Linear codes for sources and source networks: Error exponents, universal coding

For Slepian-Wolf source networks, the error exponents obtained by Körner,Marton, and the author are shown to be universally attainable by linear codes also. Improved exponents are derived for linear codes with "large rates." Specializing the results to simple discrete memoryless sources reveals their relationship to the random coding and expurgated bounds for channels with additive noise. One corollary is that there are universal linear codes for this class of channels which attain the random coding error exponent for each channel in the class. The combinatorial approach of Csiszár-Körner-Marton is used. In particular, all results are derived from a lemma specifying good encoders in terms of purely combinatorial properties.     

A trellis code construction and coding theorem for stationary Gaussian sources (Corresp.)

For stationary discrete-time Gaussian sources and the squared-error distortion measure, a trellis source code is constructed. The encoder consists of a Karhunen-Loeve transform on the source output followed by a search on a trellis structured code, where the decoder is a time-variant nonlinear filter. The corresponding code theorem is proved using the random coding argument. The proof technique follows that of Viterbi and Omura, who proved the trellis coding theorem for memoryless sources. The resultant coding scheme is implementable and applicable at any nonzero rate to a stationary Gaussian source with a bounded and continuous power spectrum. Therefore. for stationary sources, it is more general than Berger's tree coding scheme, which is restricted to autoregressive Gaussian sources in a region of high rate (low distortion).     

Tree coding of image subbands

The authors consider the encoding of image subbands with a tree code that is asymptotically optimal for Gaussian sources and the mean squared error (MSE) distortion measure. They first prove that optimal encoding of ideally filtered subbands of a Gaussian image source achieves the rate distortion bound for the MSE distortion measure. The optimal rate and distortion allocation among the subbands is a by-product of this proof. A bound is derived which shows that subband coding is closer than full-band coding to the rate distortion bound for a finite length sequence. The tree codes are then applied to encode the image subbands, both nonadaptively and adaptively. Since the tree codes are stochastic and the search of the code tree is selective, a relatively few reproduction symbols may have an associated squared error a hundred times larger than the target for the subband. Correcting these symbols through a postcoding procedure improves the signal-to-noise ratio and visual quality significantly, with a marginal increase in total rate.     

Permutation codes for sources

Source encoding techniques based on permutation codes are investigated. For a broad class of distortion measures it is shown that optimum encoding of a source permutation code is easy to instrument even for very long block lengths. Also, the nonparametric nature of permutation encoding is well suited to situations involving unknown source statistics. For the squared-error distortion measure a procedure for generating good permutation codes of a given rate and block length is described. The performance of such codes for a memoryless Gaussian source is compared both with the rate-distortion function bound and with the performance of various quantization schemes. The comparison reveals that permutation codes are asymptotically ideal for small rates and perform as well as the best entropy-coded quantizers presently known for intermediate rates. They can be made to compare favorably at high rates, too, provided the coding delay associated with extremely long block lengths is tolerable.     

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     

Slepian-Wolf coding over broadcast channels

We discuss reliable transmission of a discrete memoryless source over a discrete memoryless broadcast channel, where each receiver has side information (of arbitrary quality) about the source unknown to the sender. When there are K=2 receivers, the optimum coding strategy using separate and stand-alone source and channel codes is to build two independent binning structures and send bin indices using degraded message sets through the channel, yielding a full characterization of achievable rates. However, as we show with an example, generalization of this technique to multiple binning schemes does not fully resolve the K>2 case. Joint source-channel coding, on the other hand, allows for a much simpler strategy (i.e., with no explicit binning) yielding a successful single-letter characterization of achievable rates for any Kges2. This characterization, which utilizes a trivial outer bound to the capacity region of general broadcast channels, is in terms of marginal source and channel distributions rather than a joint source-channel distribution. This contrasts with existing results for other multiterminal scenarios and implies that optimal schemes achieve "operational separation." On the other hand, it is shown with an example that an optimal joint source-channel coding strategy is strictly advantageous over the combination of stand-alone source and channel codes, and thus "informational separation" does not hold     

Tradeoff between source and channel coding

A fundamental problem in the transmission of analog information across a noisy discrete channel is the choice of channel code rate that optimally allocates the available transmission rate between lossy source coding and block channel coding. We establish tight bounds on the channel code rate that minimizes the average distortion of a vector quantizer cascaded with a channel coder and a binary-symmetric channel. Analytic expressions are derived in two cases of interest: small bit-error probability and arbitrary source vector dimension; arbitrary bit-error probability and large source vector dimension. We demonstrate that the optimal channel code rate is often substantially smaller than the channel capacity, and obtain a noisy-channel version of the Zador (1982) high-resolution distortion formula     

On random coding error exponents of watermarking systems

Watermarking codes are analyzed from an information-theoretic viewpoint as a game between an information hider and an active attacker. While the information hider embeds a secret message (watermark) in a covertext message (typically: text, image, sound, or video stream) within a certain distortion level, the attacker processes the resulting watermarked message, within limited additional distortion, in attempt to invalidate the watermark. For the case where the covertext source is memoryless (or, more generally where there exists some transformation that makes it memoryless), we provide a single-letter characterization of the maximin game of the random coding error exponent associated with the average probability of erroneously decoding the watermark. This single-letter characterization is in effect because if the information hider utilizes a memoryless channel to generate random codewords for every covertext message, the (causal) attacker will maximize the damage by implementing a memoryless channel as well. Partial results for the dual minimax game and the conditions for the existence of a saddle point are also presented     

A per letter converse to the channel coding theorem

By relating the average probability of error to the distortion measure of a source-sink pair, we prove a converse to the channel coding theorem. This converse lower-bounds the probability of error per source letter. It differs from the more familiar "weak" and "strong" converses which bound the probability of error of an entire message. The result is applicable to all stationary sources, all channels, and all block lengths. Lower-bounding the rate distortion function of the source-sink pair with which the channel is to be used reduces the new result to a lower bound on the achievable probability of error per source letter expressed in terms of the source entropy, alphabet size, and maximum achievable average mutual information on the channel. This latter result had been proved previously only for a memoryless channel operating with an independent letter source.     

Duality theorems for joint source-channel coding

We consider joint source-channel coding for a memoryless Gaussian source and an additive white Gaussian noise (AWGN) channel. For a given code defined by an encoder-decoder pair (α, β), its dual code is obtained by interchanging the encoder and decoder: (β, α). It is shown that if a code (α, β) is optimal at rate p channel uses per source sample and if it satisfies a certain uniform continuity condition, then its dual code (β, α) is optimal for rate 1/ρ channel uses per source sample. Further, it is demonstrated that there is a code which is optimal but its dual code is not optimal. Finally, using random coding, we show that there is an optimal code which has an optimal dual. The duality concept is also presented for the cases of (i) binary memoryless equiprobable source and binary-symmetric channel (BSC), and (ii) colored Gaussian source and additive colored Gaussian noise (ACGN) channel     

Capacity Achieving LDPC Codes Through Puncturing

The performance of punctured low-definition parity-check (LDPC) codes under maximum-likelihood (ML) decoding is studied in this correspondence via deriving and analyzing their average weight distributions (AWDs) and the corresponding asymptotic growth rate of the AWDs. In particular, it is proved that capacity-achieving codes of any rate and for any memoryless binary-input output-symmetric (MBIOS) channel under ML decoding can be constructed by puncturing some original LDPC code with small enough rate. Moreover, it is shown that the gap to capacity of all the punctured codes can be the same as the original code with a small enough rate. Conditions under which puncturing results in no rate loss with asymptotically high probability are also given in the process. These results show high potential for puncturing to be used in designing capacity-achieving codes, and in rate-compatible coding under any MBIOS channel.