We survey recent results on Bratteli-Vershik information sources, which are sources that live on a Bratteli diagram, a type of graph with a countable infinity of vertices and edges that are split into levels. The results are valid when the underlying Bratteli diagram satisfies a regularity condition. These results include an ergodic decomposition theorem, Shannon-McMillan-Breiman theorem, and theorems in source coding theory. The results are obtained using the Vershik transformation that is associated with a Bratteli diagram. It is explained how some previously known results in source coding for finite-alphabet stationary sequential information sources are obtainable from source coding results for Bratteli-Vershik sources.

We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.

Let T denote the set of all structurally inequivalent finite rooted ordered binary trees. For each t ϵ e T, let D(t) be the unique minimal DAG representation of t, and let r(t) ϵ (0,1] be the ratio of the number of vertices of D(t) to the number of leaves oft. A lossless prefix encoder φ on {D(t) : t ϵ T} is proposed, and then a two-step lossless encoder φ* on T is defined by φ*(t) =Δφ(D(t)) for t ϵ T. Let γ be the function γ(x) =Δ(x/2)log2(2/x) for x ϵ (0,1]. It is shown that the normalized pointwise redundancy in encoding each t ϵ T via φ* is O(γ(r(t))). Furthermore, given a binary tree source whose output is a sequence of random trees growing in size, weak sufficient conditions on the source are presented under which the normalized average redundancy of φ* with respect to the source vanishes asymptotically. This result allows for the identification of some families of binary tree sources on which φ* acts as a universal code.

A memoryless equiprobable source with four-letter alphabet is to be trellis encoded at an encoding rate of one code bit per source sample with respect to the Hamming fidelity criterion. Each possible trellis code for this encoding task is characterized by a binary generating matrix of fixed dimensions via which reproduction labels from the source alphabet are linearly assigned to the trellis edges. The selected code is required to be structured in the sense that the irreducible factors of the generating matrix rows are binary primitive polynomials of pre-specified degrees and multiplicities, and the code must be optimal in the sense that the time-averaged expected Hamming reproduction error per source sample is minimized subject to the structural constraint. Methodology is presented to assist in solving this optimal structured code design problem, based upon an embedding of a structured set of trellis codes within an abelian group of odd order.

Let Gkbe the de Bruijn graph with 2kvertices. When reproduction labels from a 4-letter alphabet A4are assigned linearly to the edges of Gkusing a three row binary generating matrix, a 2k-state trellis code results which is suitable for encoding a source with alphabet A4at a rate of one bit per source sample with respect to the Hamming fidelity criterion. There is a special type of code which results in this way called systematic code. A systematic code belongs to three sets of codes, each set isomorphic to a residue class ring of polynomials over GF(2). A systematic code sweeps out a cycle in each of its three residue class rings via repeated multiplication by the residue class of polynomial x. The local coordinates of a systematic code are non-negative integer parameters which describe how the code is positioned in each of its three cycles. Our main result is that a systematic code is uniquely determined by its local coordinates, except in rare instances. The paper concludes with some preliminary work indicating how a code with good distortion performance in coding a memoryless source with alphabet A4can be found in relatively small sets of systematic codes whose local coordinates are of a certain type.

Let α be an integer ≥ 2. We define a finite rooted oriented tree to be α-balanced if (1) there is no vertex with > α children, (2) for each vertex having exactly α children, the subtrees rooted at these children have numbers of leaves differing by at most 1, and (3) each child of each internal vertex withα(n) be logarithm to base two of the number of α-balanced trees having n leaves, which is roughly the codeword length needed to losslessly compress these trees via fixed-length binary codewords. Let {{x}} J denote the fractional part of x. The compression rate curve Cαis defined to be the set of limit points of the set of points of form ({{logαn}}, Hα(n)/n). Two results about Cαare presented. The first result is that Cαis the graph of a unique real-valued nonconstant continuous function defined on [0,1]. The second result is that Cαis a 2-D fractal which is the attractor of an iterated function system S(α) consisting of α piecewise contractive 2-D mappings. For α = 2, 3, 4, we illustrate how a large number of points on Cαcan be rapidly generated via S(α).

For each positive integer n, let Tnbe a random rooted full binary tree having 2n-1 vertices. We can view H(Tn), the entropy of Tn, as a measure of the structural complexity of tree Tnin the sense that approximately H(Tn) bits suffice to construct Tn. We analyze some random binary tree sequences (Tn: n = 1,2...) for which the normalized entropies H(Tn)/n converge to a limit as n rarr infin, as well as some other sequences (Tn) in which the normalized entropies fail to converge.

Let a binary memoryless source assign positive probabilities p, q to the binary letters 0,1 (respectively), where p ges q, and let t = log2q/ log2p. There is a well-known incremental algorithm due to B. Tunstall which, for each positive integer n, constructs the coding tree of the n codeword Tunstall code for the source. We present a faster incremental algorithm which constructs the n codeword Tunstall coding tree from the first knmiddot terms of the rotation sequence {lflooriTrfloor}infini=1, where knrarr infin very slowly as n rarr infin.

We consider the channel model obtained by averaging binary symmetric channel (BSC) components with respect to a weighting distribution. A nonempty open interval (A, B) is called a capacity gap for this channel model if no channel component has capacity in (A, B) and this property fails for every open interval strictly containing (A, B). For a fixed epsi>0, suppose one wishes to compute the epsi-capacity of the channel, which is the maximum asymptotic rate at which the channel can be encoded via a sequence of channel codes each achieving block error probability lesepsi. In 1963, Parthasarathy provided a formula for epsi-capacity which is valid for all but at most countably many values of epsi. When the formula fails, there exists a unique capacity gap (A, B) such that the epsi-capacity lies in [A, B], but one does not know precisely where. Via a coding theorem and converse, we establish a formula for computing epsi-capacity as a function of the endpoints A, B of the associated capacity gap (A, B); the formula holds whenever the capacity gap is sufficiently narrow in width

Given a fixed source model, a fixed trellis, and a fixed finite set of quantizer levels, one obtains a trellis source code for coding the given source by assigning each trellis edge a label from the set of quantizer levels. We consider the problem of finding which edge label assignment gives an optimal (or near optimal) trellis source code, i.e., a code yielding minimum (or near minimum) expected distortion per source sample. Group structures are imposed on the set of edges of the trellis and the set of quantizer levels, and the edge label assignment is required to be a group homomorphism. We define a trellis source code to be a perturbation of a given trellis source code if the set of edges where the edge label mappings of the two codes disagree is of smallest possible cardinality. We present the results of computer experiments showing that for a finite alphabet memoryless source model and Hamming distortion, an optimal or near optimal trellis source code may be found which is "intermediately perturbable" in the sense that the number of perturbations of the code is close to halfway between the minimum and maximum number of perturbations a trellis source code on the given trellis can have. This principle, where valid, can be used as a means to narrow the search for good trellis source codes

The redundancy rate of the Lempel-Ziv algorithm has been widely investigated. Much of the data compression community believed that the redundancy rate of the LZ78 algorithm should be O((log n)-1), where n is the data length. However, until the present paper, this conjecture had not been proved for sources beyond Markov sources. In this paper, we investigate the upper bound on the pointwise redundancy rate of the Lempel-Ziv algorithm for mixing sources and finite-state sources. The technique we applied in this paper is simple. By studying the dictionary tree resulting from the LZ78 algorithm, we derive certain relationships between the self-information of a sequence emitted by a source and the number of phrases resulting from the LZ78 parsing of the sequence. From these relationships, upper bounds on the pointwise redundancy rate of the LZ78 algorithm on mixing sources and finite-state sources can be obtained. These results show that for mixing sources and finite-state sources, the pointwise redundancy rate is upper bounded by O((log n)-1) for the LZ78 algorithm. We also compare our results with previous results of Savari and Kieffer-Yang

When the number of bits per symbol is odd, the peak and average power of transmission can be reduced by using cross quadrature amplitude modulations (QAMs) instead of rectangular QAMs. However, since perfect Gray coding is not possible for cross QAMs, using Smith-style Gray coding, this paper derives the exact bit error rate (BER) for cross QAM constellations over additive white Gaussian noise (AWGN) and Rayleigh fading channels.

A highly parallel maximum a posteriori (MAP) decoding algorithm is proposed for high code rate, R = (n-1)/ n , ordinary (nonpunctured) convolutional codes using trellises of reciprocal dual convolutional codes. The advantages of this approach include a substantial reduction of decoding latency and decoding complexity, and a substantial increase of decoding throughput. Applying the proposed parallel decoding algorithm to a class of serial concatenation codes that consist of high rate ordinary convolutional codes, over additive white Gaussian noise (AWGN) channels, good bit error rate (BER) and block error rate performance, comparable to that of turbo codes and low density parity check (LDPC) codes, can be obtained with smaller overall decoding complexity than that of LDPC codes.

Grammar-based coding is investigated from three new perspectives. First, we revisit the performance analysis of grammar-based codes by proposing context-based run-length encoding algorithms as new performance benchmarks. A redundancy result stronger than all previous corresponding results is established. We then extend the analysis of grammar-based codes to sources with countably infinite alphabets. Let /spl Lambda/ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any /spl Lambda/ for which there exists a universal code. Moreover, upper bounds on the worst-case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Finally, we propose a new theoretic framework for compression in which grammars rather than sequential stochastic processes are used as source generating models, and point out some open problems in the framework.

The method of modeling and ordering in wavelet domain is very important to design a successful algorithm of embedded image compression. In this paper, the modeling is limited to "pixel classification," the relationship between wavelet pixels in significance coding. Similarly, the ordering is limited to "pixel sorting," the coding order of wavelet pixels. We use pixel classification and sorting to provide a better understanding of previous works. The image pixels in wavelet domain are classified and sorted, either explicitly or implicitly, for embedded image compression. A new embedded image code is proposed based on a novel pixel classification and sorting (PCAS) scheme in wavelet domain. In PCAS, pixels to be coded are classified into several quantized contexts based on a large context template and sorted based on their estimated significance probabilities. The purpose of pixel classification is to exploit the intraband correlation in wavelet domain. Pixel sorting employs several fractional bit-plane coding passes to improve the rate-distortion performance. The proposed pixel classification and sorting technique is simple, yet effective, producing an embedded image code with excellent compression performance. In addition, our algorithm is able to provide either spatial or quality scalability with flexible complexity.

A sequence y=(y/sub 1/,...,y/sub n/) is said to be a coarsening of a given finite-alphabet source sequence x=(x/sub 1/,...,x/sub n/) if, for some function /spl phi/, y/sub i/=/spl phi/(x/sub i/) (i=1,...,n). In lossless refinement source coding, it is assumed that the decoder already possesses a coarsening y of a given source sequence x. It is the job of the lossless refinement source encoder to furnish the decoder with a binary codeword B(x|y) which the decoder can employ in combination with y to obtain x. We present a natural grammar-based approach for finding the binary codeword B(x|y) in two steps. In the first step of the grammar-based approach, the encoder furnishes the decoder with O(/spl radic/nlog/sub 2/n) code bits at the beginning of B(x|y) which tell the decoder how to build a context-free grammar G/sub y/ which represents y. The encoder possesses a context-free grammar G/sub x/ which represents x; in the second step of the grammar-based approach, the encoder furnishes the decoder with code bits in the rest of B(x|y) which tell the decoder how to build G/sub x/ from G/sub y/. We prove that our grammar-based lossless refinement source coding scheme is universal in the sense that its maximal redundancy per sample is O(1/log/sub 2/n) for n source samples, with respect to any finite-state lossless refinement source coding scheme. As a by-product, we provide a useful notion of the conditional entropy H(G/sub x/|G/sub y/) of the grammar G/sub x/ given the grammar G/sub y/, which is approximately equal to the length of the codeword B(x|y).

We consider the problem of embedded image transmission with feedback of channel state information (CSI) and retransmission request. Adaptive modulation is employed to improve the spectral efficiency. Constrained retransmission is employed to provide reliable packet transmission with limited delay. Performance analysis and numerical results over Nakagami block fading channels are provided for the transmission system with statistical or instantaneous CSI at the transmitter. The results show that CSI at the transmitter is very important for adaptive modulation/coding over fading channels.

A new embedded image compression algorithm is proposed, based on progressive Pixel Classification And Sorting (PCAS) in wavelet domain. To exploit the intraband and interband correlation in wavelet domain, EZW [1] and SPIHT [2] implicitly classify wavelet pixels as zerotree pixels or not, while MRWD[3], SLCCA[4], and EBCOT[5] implicitly classify wavelet pixels as neighbors of significant pixels or not. In this paper, the wavelet pixels to be encoded are explicitly and finely classified based on their predicted probabilities, which is more sophisticated and effective. Furthermore, wavelet pixel sorting is introduced to help improve rate-distortion performance within each bit-plane coding. The technique of pixel classification and sorting is simple, yet effective to produce the image code with excellent compression performance. In addition, our algorithm provides both SNR and resolution scalability.

A grammar transform is a transformation that converts any data sequence to be compressed into a grammar from which the original data sequence can be fully reconstructed. In a grammar-based code, a data sequence is first converted into a grammar by a grammar transform and then losslessly encoded. Among several previously proposed grammar transforms is the multilevel pattern matching (MPM) grammar transform. In this paper, the MPM grammar transform is first extended to the case of side information known to both the encoder and decoder, yielding a conditional MPM (CMPM) grammar transform. A new simple linear-time and space complexity algorithm is then proposed to implement the MPM and CMPM grammar transforms. Based on the CMPM grammar transform, a universal lossless data compression algorithm with side information is developed, which can achieve asymptotically the conditional entropy rate of any stationary, ergodic source pair. It is shown that the algorithm's worst case redundancy/sample against the k-contest conditional empirical entropy among all individual sequences of length n is upper-bounded by c(1/logn), where c is a constant. The proposed algorithm with side information is the first in the coming family of conditional grammar-based codes, whose expected high efficiency is due to the efficiency of the corresponding unconditional codes.

Given a square image with number of rows and columns a power of two, we obtain an image sequence by continued downsampling by a factor of two until only a single pixel remains. We use each downsampled image as context for lossless coding of the next image in the sequence. The image coder makes use of a grammar called the conditional quadrisection grammar for building the next image given the context image; the production rules of the conditional quadrisection grammar are encoded via a simple arithmetic encoding technique. We present a universal coding theorem establishing that the redundancy/pixel of our scheme with respect to finite-state resolution scalable lossless image coding schemes tends to zero as the size of the image grows without bound. We present the results of compression experiments in which our scheme is evaluated on real images.

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/sub x/ representing x in the sense that x is the unique string belonging to the language generated by G/sub x/. Lossless compression of x takes place indirectly via compression of the production rules of the grammar G/sub 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 universal lossless data compression code called the multilevel pattern matching code (MPM code) is introduced. In processing a finite-alphabet data string of length n, the MPM code operates at O(log log n) levels sequentially. At each level, the MPM code detects matching patterns in the input data string (substrings of the data appearing in two or more nonoverlapping positions). The matching patterns detected at each level are of a fixed length which decreases by a constant factor from level to level, until this fixed length becomes one at the final level. The MPM code represents information about the matching patterns at each level as a string of tokens, with each token string encoded by an arithmetic encoder. From the concatenated encoded token strings, the decoder can reconstruct the data string via several rounds of parallel substitutions. A O(1/log n) maximal redundancy/sample upper bound is established for the MPM code with respect to any class of finite state sources of uniformly bounded complexity. We also show that the MPM code is of linear complexity in terms of time and space requirements. The results of some MPM code compression experiments are reported.

A grammar transform is a transformation that converts any data sequence to be compressed into a grammar from which the original data sequence can be fully reconstructed. In a grammar-based code, a data sequence is first converted into a grammar by a grammar transform and then losslessly encoded. In this paper, a greedy grammar transform is first presented; this grammar transform constructs sequentially a sequence of irreducible grammars from which the original data sequence can be recovered incrementally. Based on this grammar transform, three universal lossless data compression algorithms, a sequential algorithm, an improved sequential algorithm, and a hierarchical algorithm, are then developed. These algorithms combine the power of arithmetic coding with that of string matching. It is shown that these algorithms are all universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source. Moreover, it is proved that their worst case redundancies among all individual sequences of length n are upper-bounded by c log log n/log n, where c is a constant. Simulation results show that the proposed algorithms outperform the Unix Compress and Gzip algorithms, which are based on LZ78 and LZ77, respectively.

If x is a string of finite length over a finite alphabet A, let LZ(x) denote the length of the binary codeword assigned to x by the 1978 version of the Lempel-Ziv data compression algorithm, let t(x) be the number of phrases in the Lempel-Ziv parsing of x, and let /spl mu/(x) be the probability assigned to x by a memoryless source model. Using a very simple technique, we probe the pointwise redundancy bound LZ(x)+log/sub 2//spl mu/(x)/spl les/8t(x)max{-log/sub 2//spl mu/(a):a/spl isin/A}.

Summary form only given. The multilevel pattern matching data compression system is one of a class of compression algorithms introduced by Kieffer and Yang (see ERA Amer. Math. Soc., vol.3, p.11-16, 1997). The MPM system is currently of interest because of its good redundancy performance in losslessly compressing data strings of arbitrary length over a finite alphabet. An MPM system consists of a preprocessor, encoder/decoder, and a reconstruction engine. The preprocessor detects matching patterns in the input data string (substrings of the data appearing in two or more nonoverlapping positions). The preprocessor operates at several levels sequentially, with the number of levels selected by the user. The matching patterns detected at each level are of a fixed length which decreases by a constant factor from level to level, until this fixed length becomes one at the final level. The preprocessor represents information about matching patterns at each level as a string of tokens which is passed to the encoder of the MPM system. The decoder of the MPM system recovers these token strings, from which the reconstruction engine rebuilds the input data string. The preprocessor is the most complex component of the MPM system. We exhibit an implementation of the preprocessor of linear complexity in terms of execution time and space requirements; the number of levels satisfies O(log/sub 2/log/sub 2/n) for input data strings of length n.

In a given binary image, we identify two disjoint sets of image subblocks of varying size which we call range blocks and domain blocks. The range blocks form a partition of the image called a self-referential partition because each range block is represented via a pointer to a matching domain block. The encoder transmits encoded versions of these pointers together with one pixel from each domain block. This information, when decoded, allows progressive reconstruction of the image. On several archival images, our progressive lossless image coder gave better compression performance than that provided by the 2-D Lempel-Ziv (1986) algorithm, multi-window quadtree coding, and Huffman coding of runlengths. The progressive image coder is fast and has a worst-case redundancy performance better than the best currently known worst-case redundancy upper bound for the 2-D Lempel-Ziv algorithm.

Lossless and lossy data compression algorithms based on string matching are considered. In the lossless case, a result of Wyner and Ziv (1989) is extended. In the lossy case, a data compression algorithm based on approximate string matching is analyzed in the following two frameworks: (1) the database and the source together form a Markov chain of finite order; (2) the database and the source are independent with the database coming from a Markov model and the source from a general stationary, ergodic model. In either framework, it is shown that the resulting compression rate converges with probability one to a quantity computable as the infimum of an information theoretic functional over a set of auxiliary random variables; the quantity is strictly greater than the rate distortion function of the source except in some symmetric cases. In particular, this result implies that the lossy algorithm proposed by Steinberg and Gutman (1993) is not optimal, even for memoryless or Markov sources.

As image coders evolve from DCT-based to wavelet-based designs, the latter must be enhanced to include capabilities currently supported by standards such as JPEG. Said and Pearlman (see IEEE Transactions on Circuits and Systems for Video Tech., vol.6, p.243-50, 1996) and Schwartz, Zandi and Boliek (see Proc. of SPIE, vol.2564, July 1995) have described approaches for incorporating progressive transmission capabilities within wavelet-based coders. All of these coders apply scalar quantization to wavelet transform coefficients and then apply sophisticated entropy coding methods to the quantized coefficients. In this paper, we present coding techniques that enable progressive transmission when trellis coded quantization (TCQ) is applied to the wavelet coefficients. While the trellis coded quantizer is more complex than the uniform scalar quantizer, comparable PSNR performance is achieved with a simple entropy coder. In addition, our use of sophisticated quantization and bit rate allocation algorithms enables the development of coders that are tuned for improved perceptual image quality.

The redundancy problem of the fixed-database Lempel-Ziv (1977) algorithm is considered. It is demonstrated that for a class of /spl phi/-mixing sources which includes Markov sources, unifilar sources, and finite-state sources as special cases, the redundancy of the fixed-database Lempel-Ziv algorithm with database size n is lower-bounded by H(loglogn)/logn+O((logloglogn)/logn) and upper-bounded by 2H(loglogn)/logn+O((logloglogn)/logn) where H is the entropy rate of the source. The method of proof is new and uses the concept of variable-length to variable-length codes.

A general class of sequential codes for lossless compression of individual sequences on a finite alphabet is defined, including many types of codes that one would want to implement. The principal requirement for membership in the class is that the encoding and decoding operations be performable on a computer. The OPTA function for the class of codes is then considered, which is the function that assigns to each individual sequence the infimum of the rates at which the sequence can be compressed over this class of sequential codes. Two results about the OPTA function are obtained: (1) it is shown that any sequential code in the class compresses some individual sequence at a rate strictly greater than the rate for that sequence given by the OPTA function; and (2) it is shown that the OPTA function takes a value strictly greater than that of the Kolmogorov (1965) complexity rate function for some individual sequences.

Two universal lossy data compression schemes, one with fixed rate and the other with fixed distortion, are presented, based on the well-known Lempel-Ziv algorithm. In the case of fixed rate R, the universal lossy data compression scheme works as follows: first pick a codebook B/sub n/ consisting of all reproduction sequences of length n whose Lempel-Ziv codeword length is /spl les/nR, and then use B/sub n/ to encode the entire source sequence n-block by n-block. This fixed-rate data compression scheme is universal in the sense that for any stationary, ergodic source or for any individual sequence, the sample distortion performance as n/spl rarr//spl infin/ is given almost surely by the distortion rate function. A similar result is shown in the context of fixed distortion lossy source coding.

Observations are made of data generated by a stationary ergodic finite-alphabet information source according to an unknown statistical model. Two modeling problems, the identification problem and the order estimation problem, are considered. It is required that the given model class in the identification problem and each given model class in the order estimation problem be a constrained finite-state model class, which is a type that includes many model classes of information-theoretic interest. Strongly consistent decision rules are exhibited in both the identification problem and the order estimation problem. The decision rules are code-based in that a model class is chosen based on how well a certain code for that class encodes the observed data. The code used for a model class is based on the maximum likelihood code for that class, and asymptotic code performance is gauged by means of a key property of divergence-rate distance.>

The purpose of this paper is threefold: 1) to acquaint the reader with the types of problems that have been considered in the area of source coding with a fidelity criterion; 2) to survey results that have been obtained on these problems; and 3) to outline future research trends in the area.>

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.>

The rate and distortion performance of a sequence of codes along a sample sequence of symbols generated by a stationary ergodic information source are studied. Two results are obtained: (1) the source sample sequence is encoded by an arbitrary sequence of block codes which operate at a fixed rate level R, and a sample converse is obtained which states that, with probability one, the lower limit of the code sample distortions is lower bounded by D(R), the value of the distortion rate function at R; (2) the source sample sequence is encoded by an arbitrary sequence of variable-rate codes which operate at a fixed distortion level D, and a sample converse is obtained which states that, with probability one, the lower limit of the code sample rates is lower bounded by R(D), the value of the rate distortion function at D. A novel ergodic theorem is used to obtain both sample converses.>

A class of one-bit feedback encoders that includes sigma-delta modulation encoders, data modulation encoders, and some DPCM encoders is defined. For any encoder from the class, it is shown that the encoder output sequence in response to a DC input sequence is a typical sequence for a certain strict-sense stationary, ergodic process whose power spectral density is determined. The result is applied to give the performance of an analog-to-digital conversion system operated at high sampling rates.>

A nonstationary finite-alphabet information source mu 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 mu 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.>

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.>

Given h>0, the problem is considered of finding an N-level quantizer Q which is optimal in the sense of encoding a given continuously distributed random variable X with minimum expected squared error, subject to the constraint H(Q(X))>

An expression is obtained for the optimum distortion theoretically attainable when an information source with finite alphabet is encoded at a fixed rate with respect to a single-letter fidelity criterion. The expression is demonstrated by means of an appropriate coding theorem and converse; This new result generalizes the coding theorem of Shannon for stationary ergodic sources, the coding theorem of Gray-Davisson for stationary nonergodic sources, that of Gray-Saadat for asymptotically mean stationary sources, and that of Ziv for an individual sequence.

It is desired to encode a random variableXusing anN-level quantizerQto minimize the expected distortionE \rho(|X-Q(X))I), where the error weighting function\rhois convex, strictly increasing and continuously differentiable. It is shown that ifXhas a log-concave density, then there exists a unique locally optimal quantizerQ \astand Lloyd's Method I may be used to findQ \ast. Trushkin had earlier shown this result for the error weighting functions\rho (t) \equiv tand\rho(t) \euiv t^{2}.

It is shown for a class of symbol-by-symbol encoding schemes, including delta modulation and some adaptive quantization schemes, that the joint input-state-output sequence is asymptotically mean stationary if the input sequence is stationary. Asymptotic mean stationarity is also obtained for the sequence of outputs produced by a general kind of variable-length to variable-length scheme, as well as for some sequences of waiting times arising in queueing theory.

For a weakly continuous stationary channel with operational sliding-block capacityC_{s}, it is shown that every stationary, ergodic, aperiodic source with entropy less thanC_{s}is sliding-block transmissible over the channel. It had been shown earlier that a stationary and ergodic source is block transmissible over the channel if its entropy is less than the operational block capacityC_{b}. If, in addition, the channel is ergodic, it is shown thatC_{s}=C_{b}. An example of a nonergodic weakly continuous channel is given for which0<C_{s}

Strong universal coding is possible for any dass of ergodic sources on a finite alphabet which is totally bounded in the\bar{d}distance. In order to implement this theorem, several necessary and sufficient conditions are given in order for a class ofBsources to be\bar{d}-totally bounded. The conditions are applied to several examples. Of independent interest is a result which allows one to model a\bar{d}-totally bounded class ofBsources as an encoding of the dass of memoryless sources, where the encoder satisfies a certain continuity property.

For a random variable with finite second moment and log-concave density, a unique quantizer exists which produces the minimum expected encoding error, using squared-error distortion. An algorithm given by Lloyd (Lloyd's Method I) yields a sequence of quantizers which converges to the optimum quantizer. Using results of Fleischer, it is shown that the convergence takes place exponentially fast if the logarithm of the density is not piecewise affine. As a consequence the number of iterations of Lloyd's algorithm needed to obtain the optimum distortion correct to n decimal places approaches infinity no faster than linearly inn. Another consequence is that if the output of a stationary information source at each time is distributed according to the given density, the source output can be encoded at each timeiusing the quantizer obtained on theith iteration of Lloyd's method obtaining the same asymptotic behavior one would have obtained if the optimum quantizer had been used to encode at each time.

Feedback quantization schemes (such as delta modulation. adaptive quantization, differential pulse code modulation (DPCM), and adaptive differential pulse code modulation (ADPCM) encode an information source by quantizing the source letter at each timeiusing a quantizer, which is uniquely determined by examining some function of the past outputs and inputs called the state of the encoder at timei. The quantized output letter at timeiis fed back to the encoder, which then moves to a new state at timei+1which is a function of the state at timeiand the encoder output at timei. In an earlier paper a stochastic stability result was obtained for a class of feedback quantization schemes which includes delta modulation and some adaptive quantization schemes. In this paper a similar result is obtained for a class of feedback quantization schemes which includes linear DPCM and some ADPCM encoding schemes. The type of stochastic stability obtained gives almost-sure convergence of time averages of functions of the joint input-state-output process. This is stronger than the type of stochastic stability obtained previously by Gersho, Goodman, Goldstein, and Liu, who showed convergence in distribution of the timeiinput-state-output asi \rightarrow \infty.

A necessary and sufficient condition for a source to satisfy the ergodic theorem and the Shannon-McMillan theorem--the two basic mathematical tools of the Shannon theory--is that it be asymptotically mean stationary (AMS). A channel is defined here to be AMS if whenever an AMS input source is connected to the channel, the resulting input/output process is AMS. We develop several characterizations and properties of AMS channels that resemble those of AMS sources. As an application we show that these ideas are useful in characterizing composite sources, and in particular that there exist sources that exhibit distinct short term and long term stationarity properties. Thus "locally stationary" or "quasi-stationary" processes such as those used to model speech waveforms may also be stationary. In addition, some preliminary results on coding for AMS channels are presented.

The two-step method used by Wyner and Ziv to prove the Wyner-Ziv theorem is extended to prove sliding-block source coding theorems for coding a general finite-alphabet ergodic multiterminal source with respect to a single-letter fidelity criterion. The first step replaces every stochastic encoding in the network by a deterministic sliding-block encoding. The second step involves using the Slepian-Wolf theorem to adjust the sliding-block encodings so that they will have the desired rate. while introducing little additional distortion. The method is applied to give quick proofs of sliding-block versions of theorems of Berger, Kaspi, and Tung. Since the method obtains sliding-block coders directly without first obtaining block coders, the block coding results can be obtained as an easy corollary. The direct methods for proving results on block coding are more difficult and do not imply the corresponding results on sliding-block coding. Indeed, in the multiterminal case it is, in general, not known how to construct good sliding-block coders from good block coders.

Given a discrete stationary channelvfor which the map\mu \rightarrow \mu vcarrying each stationary, ergodic input\muinto the input-output measure\mu vis continuous (with respect to weak convergence) at at least one input, it is shown that every stationary and ergodic source with sufficiently small entropy is block transmissible over the channel. If this weak continuity condition is satisfied at every stationary ergodic input, one obtains the class of weakly continuous channels for which the usual source/channel block coding theorem and converse hold with the usual notion of channel capacity. An example is given to show that the class of weakly continuous channels properly includes the class of\bar{d}-continuous channels. It is shown that every stationary channelvis "almost" weakly continuous in the sense that every input-output measure\mu vforvcan be obtained by sending\muover an appropriate weakly continuous channel (depending on\mu). This indicates that weakly continuous channels may be the most general stationary channels for which one would need a coding theorem.

Several new properties as well as simplified proofs of known properties are developed for the mutual information rate between discrete-time random processes whose alphabets are Borel subsets of complete separable metric spaces. In particular, the asymptotic properties of quantizers for such spaces provide a fink with finite-alphabet processes and yield the ergodic decomposition of mutual information rate. This result is used to prove the equality of stationary and ergodic process distortion-rate functions with the usual distortion-rate function. An unusual definition of mutual information rate for continuous-alphabet processes is used, but it is shown to be operationally appropriate and more useful mathematically; it provides an intuitive link between continuous-alphabet and finite-alphabet processes, and it allows generalizations of some fundamental results of ergodic theory that are useful for information theory.

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.

For a class of ergodic sources\Lambdaon a given finite alphabet satisfying certain conditions, a formula is given for the minimum rate above which strong universal fixed-rate and variable-rate block coding of\Lambdawith respect to an arbitrary single-letter fidelity criterion can be done. The result extends several previous strong universal block coding theorems. As an application it is shown that there is a metric on the class of stationary sources weaker than\bar{d}-metric for which compactness of\Lambdain the metric implies that strong universal coding can be done at all rates.

An effective rate for block coding of a stationary ergodic source relative to a zero-one valued fidelity criterion is defined. Under some mild restrictions, a source coding theorem and converse are given that show that the defined rate is optimum. Several examples are given that satisfy the restrictions imposed. A new generalization of the Shannon-McMman Theorem is employed.

A new method of constructing a universal sequence of block codes for coding a class of ergodic sources is given. With this method, a weakly universal sequence of codes is constructed for variable-rate noise. less coding and for fixed- and variable-rate coding with respect to a fidelity criterion. In this way a unified approach to weak universal block source coding is obtained. For the noiseless variable-rate coding and the fixed-rate coding with respect to fidelity criterion, the assumptions made on the alphabets, distortion measures, and class of sources are both necessary and sufficient. For fixed-rate coding with respect to a fidelity criterion, the sample distortion of the universal code sequence converges inL^{l}norm for each source to the optimum distortion for that source. For both variable-rate noiseless coding and variable-rate coding with respect to a fidelity criterion, the sample rate of the universal code sequence converges inL^{1}norm for each source to the optimum rate for that source. Using this fact, a universal sequence of codes for fixed-rate noiseless coding is obtained. Some applications to stationary nonergodic sources are also considered. The results of Davisson, Ziv, Neuhoff, Gray, Pursley, and Mackenthun are extended.

Suppose nature selects a source from among a class of sources according to some prior probability distribution. With respect to a given fidelity criterion and a given distortion level, it is shown that there exists a variable-rate code such that the following is true. It is highly likely that nature will choose a source whose average distortion with respect to the given code achieves the given distortion level and whose average rate is approximately the optimum rate theoretically attainable. Only a very weak assumption has to be made. The assumption is satisfied, for example, for separable metric space alphabets and a distortion measure which is a nondecreasing continuous function of the metric. This generalizes work of Pursley, Davisson, and Mackenthun and settles a conjecture of Pursley and Davisson.

A simple proof is given for the Gray-Davisson result on the ergodic decomposition of the optimum average distortion attainable by fixed-rate coding of a nonergodic source, for the special ease of a bounded distortion measure. A second proof is given for a more general class of distortion measures using a result of Ziv.

A new lower bound on the probability of decoding error for transmission at high rates over a finite-state channel is obtained. It is a dual to the random coding bound of Yudkin and is a generalization of the Arimoto converse to the coding theorem for discrete memoryless channels. It also implies the strong converse to the coding theorem for indecomposable channels.