A progressive universal noiseless coder

The authors combine pruned tree-structured vector quantization (pruned TSVQ) with Itoh's (1987) universal noiseless coder. By combining pruned TSVQ with universal noiseless coding, they benefit from the “successive approximation” capabilities of TSVQ, thereby allowing progressive transmission of images, while retaining the ability to noiselessly encode images of unknown statistics in a provably asymptotically optimal fashion. Noiseless compression results are comparable to Ziv-Lempel and arithmetic coding for both images and finely quantized Gaussian sources     

Grammar-based codes: a new class of universal lossless source codes

We investigate a type of lossless source code called a grammar-based code, which, in response to any input data string x over a fixed finite alphabet, selects a context-free grammar G_x representing x in the sense that x is the unique string belonging to the language generated by G_x. Lossless compression of x takes place indirectly via compression of the production rules of the grammar G_x. It is shown that, subject to some mild restrictions, a grammar-based code is a universal code with respect to the family of finite-state information sources over the finite alphabet. Redundancy bounds for grammar-based codes are established. Reduction rules for designing grammar-based codes are presented     

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     

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.     

Robust noiseless source coding through a game theoretical approach

Noiseless coding of a discrete source with partially known statistics is formulated as a two-person game. The payoff is the average codeword length, using Shannon codes. The code designer picks a source probability distribution for the design of the code, while an opponent picks the actual source probability distribution. It is shown that if the class of probability distributions allowed is convex, then there is a saddle point solution which is determined by the maximum entropy distribution of the convex class. The maximum entropy element is derived for three families of source probability mass functions (pmf): a) the class of c-contaminated pmf's; b) the class of pmf's for which each probability is known only through an upper and lower bound; c) the class of pmf's which is a convex hull of a finite number of known pmf's. An extension of the robust noiseless source coding problem for families of sources modeled as first-order Markov chains is discussed.     

Efficient balanced codes

Coding schemes in which each codeword contains equally many zeros and ones are constructed in such a way that they can be efficiently encoded and decoded.     

Causal source codes

Causal source codes are defined. These include quantizers, delta modulators, differential pulse code modulators, and adaptive versions of these. Several types of causal codes are identified. For memoryless sources it is shown that the optimum performance attainable by causal codes can be achieved by memoryless codes or by time-sharing memoryless codes. This optimal performance can be evaluated straightforwardly.     

Approximately universal codes over slow-fading channels

Performance of reliable communication over a coherent slow-fading multiple-input multiple-output (MIMO) channel at high signal-to-noise ratio (SNR) is succinctly captured as a fundamental tradeoff between diversity and multiplexing gains. This paper studies the problem of designing codes that optimally tradeoff the diversity and multiplexing gains. The main contribution is a precise characterization of codes that are universally tradeoff-optimal, i.e., they optimally tradeoff the diversity and multiplexing gains for every statistical characterization of the fading channel. This characterization is referred to as approximate universality; the approximation is in the connection between error probability and outage capacity with diversity and multiplexing gains, respectively. The characterization of approximate universality is then used to construct new coding schemes as well as to show optimality of several schemes proposed in the space-time coding literature.     

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.     

Surrogate-channel design of universal LDPC codes

A universal code is a code that may be used across a number of different channel types or conditions with little degradation relative to a good single-channel code. The explicit design of universal codes, which simultaneously seeks to solve a multitude of optimization problems, is a daunting task. This letter shows that a single channel may be used as a surrogate for an entire set of channels to produce good universal LDPC codes. This result suggests that sometimes a channel for which LDPC code design is simple may be used as a surrogate for a channel for which LDPC code design is complex. We explore here the universality of LDPC codes over the BEC, AWGN, and flat Rayleigh fading channels in terms of decoding threshold performance. Using excess mutual information as a performance metric, we present design results which support the contention that an LDPC code designed for a single channel can be universally good across the three channels.     

Efficient erasure correcting codes

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sides of the graph which is necessary and sufficient for the decoding process to finish successfully with high probability. By carefully designing these graphs we can construct for any given rate R and any given real number ϵ a family of linear codes of rate R which can be encoded in time proportional to ln(1/ϵ) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+ϵ)Rn or more. The recovery algorithm also runs in time proportional to n ln(1/ϵ). Our algorithms have been implemented and work well in practice; various implementation issues are discussed     

Efficient burst-correcting cyclic codes

A class of single burst error-correcting cyclic codes is introduced. The binary version of these codes has block length n = 2m ? 1, number of parity check digits n ? k = 2m?1, and correct bursts of length b = 2m?2, where m is an integer. These codes achieve the upper bound b ?(n ? k)/2, and normally have more information digits than interleaved codes of the same burst-correcting power. The multilevel case is also treated in the letter.     

Efficient multiplication-free arithmetic codes

Arithmetic coding is a powerful lossless data compression technique that has attracted much attention. It provides more flexibility and better efficiency than Huffman coding does. However, the multiplications needed in its encoding and decoding algorithms are very undesirable. Rissanen and Mohiuddin (1989) have proposed a simple scheme to avoid the multiplications. The present authors found that the performance of their proposed scheme might degrade significantly in some cases. They propose a multiplication-free multialphabet arithmetic code which can be shown to have minor performance degradation in all cases. In the proposed scheme, each multiplication is replaced by a single shift-and-add. The authors prove, by both theoretical analysis and simulation results, that the degradation of the proposed multiplication-free scheme is always several times (2-7 times in the present experiments) smaller than that of the Rissanen-Mohiuddin's scheme     

Efficient ternary transmission codes

To limit distortion in digital cable systems due to low-frequency cuts, it has been usual either to use quantised feedback or use a code with a finite digital-sum variation. It is shown that these restrictions are unnecessarily stringent. Systems typically use 3-level codes, and some codes requiring less bandwidih than the 4B3T type are analysed.     

Finite-state adaptive block to variable-length noiseless coding ofa nonstationary information source

The author associates with a given nonstationary finite-alphabet information source a certain class of stationary processes that he terms the stationary hull of the given source. He shows that the optimum average rate at which the given source can be noiselessly coded by means of a finite-state adaptive block to variable-length coding schemes is the largest entropy rate among those processes in the stationary hull. He explains what he means by an adaptive block to variable-length coding scheme     

Comparison of two optimum rates for noiseless encoding of anonstationary information source

A nonstationary finite-alphabet information source μ is noiselessly encoded, first by adaptive block to variable-length codes and then by finite-state codes of this kind. It is shown that if μ belongs to a certain class of sources that includes those with finite-order Markov memory, then a stationary input-restricted channel exists such that in the first case the optimum encoding rate is equal to the largest conditional entropy for channel input given channel output, whereas in the second case it is the largest channel output entropy. A sufficient condition for the two rates to be equal is also given     

A universal finite memory source

An irreducible parameterization for a finite memory source is constructed in the form of a tree machine. A universal information source for the set of finite memory sources is constructed by a predictive modification of an earlier studied algorithm-Context. It is shown that this universal source incorporates any minimal data-generating tree machine in an asymptotically optimal manner in the following sense: the negative logarithm of the probability it assigns to any long typical sequence, generated by any tree machine, approaches that assigned by the tree machine at the best possible rate     

Efficient constructions of frameproof codes

If C is a code of length n over a p-ary alphabet, then x is called a descendant of the codewords a, b,.... e if x_i∈{a_i , h_i,..., e_i} for i=1..., 1 n. The authors study codes with the following property: the descendant of any coalition of codewords of a given maximal size does not belong to C     

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