In a distributed information application an encoder compresses an arbitrary vector while a similar reference vector is available to the decoder as side information. For the Hamming-distance similarity measure, and when guaranteed perfect reconstruction is required, we present two contributions to the solution of this problem. One result shows that when a set of potential reference vectors is available to the encoder, lower compression rates can be achieved when the set satisfies a certain clustering property. Another result reduces the best known decoding complexity from exponential in the vector length$n$to$O(n^{1.5})$by generalized concatenation of inner coset codes and outer error-correcting codes. One potential application of the results is the compression of DNA sequences, where similar (but not identical) reference vectors are shared among senders and receivers.

The unrestricted-dictionary type LZ78 universal data-compression algorithm (as well as the LZ77 and LZW versions) achieves asymptotically, as the block-length tends to infinity, the FS compressibility, namely the best compression-ratio that may be achieved by any Information-lossless(IL) block-to-variable finite-state(FS) algorithm, for any infinitely-long individual sequence.

Consider the case where consecutive blocks of N letters of a semi-infinite individual sequence X over a finite alphabet are being compressed into binary sequences by some one-to-one mapping. No a priori information about X is available at the encoder, which must therefore adopt a universal data-compression algorithm. It is known that there exist a number of asymptotically optimal universal data compression algorithms (e.g., the Lempel-Ziv (LZ) algorithm, context tree algorithm and an adaptive Hufmann algorithm) such that when successively applied to N-blocks then, the best error-free compression for the particular individual sequence X is achieved as N tends to infinity. The best possible compression that may be achieved by any universal data compression algorithm for finite N-blocks is discussed. Essential optimality for the compression of finite-length sequences is defined. It is shown that the LZ77 universal compression of N-blocks is essentially optimal for finite N-blocks. Previously, it has been demonstrated that a universal context tree compression of N blocks is essentially optimal as well.

Consider the case where consecutive blocks of letters of a semi-infinite individual sequence over a finite-alphabet are being compressed into binary sequences by some one-to-one mapping. No a priori information about is available at the encoder, which must therefore adopt a universal data-compression algorithm. It is known that if the universal Lempel-Ziv (LZ) data compression algorithm is successively applied to -blocks then the best error-free compression, for the particular individual sequence is achieved as tends to infinity. The best possible compression that may be achieved by any universal data compression algorithm for finite -blocks is discussed. It is demonstrated that context tree coding essentially achieves it. Next, consider a device called classifier (or discriminator) that observes an individual training sequence . The classifier's task is to examine individual test sequences of length and decide whether the test -sequence has the same features as those that are captured by the training sequence , or is sufficiently different, according to some appropriate criterion. Here again, it is demonstrated that a particular universal context classifier with a storage-space complexity that is linear in , is essentially optimal. This may contribute a theoretical ldquoindividual sequencerdquo justification for the Probabilistic Suffix Tree (PST) approach in learning theory and in computational biology.

This paper tightens previous information combining bounds on the performance of iterative decoding of binary low-density parity-check (LDPC) codes over binary-input symmetric-output channels by tracking the probability of erroneous bit in conjunction with mutual information. Evaluation of the new bounds as well as of other known bounds on different LDPC ensembles demonstrates sensitivity of the finite dimensional iterative bounds to lambda2, the fraction of edges connected to degree 2 variable nodes

We consider the class of strong-mixing probability laws with positive transitions that are defined on doubly infinite sequences in a finite alphabet A. A device called the classifier (or discriminator) observes a training sequence whose probability law Q is unknown. The classifier's task is to consider a second probability law P and decide whether P = Q, or P and Q are sufficiently different according to some appropriate criterion Delta(Q,P) > Delta. If the classifier has available an infinite amount of training data, this is a simple matter. However, here we study the case where the amount of training data is limited to N letters. We define a function NDelta(Q|P), which quantifies the minimum length sequence needed to distinguish Q and P and the class M(NDelta) of all probability laws pairs (Q,P) that satisfy NDelta(Q|P) les NDeltafor some given positive number NDelta. It is shown that every pair Q,P of probability laws that are sufficiently different according to the Delta criterion is contained in M(NDelta). We demonstrate that for any universal classifier there exists some Q for which the classification probability lambda(Q) = 1 for some N-sequence emerging from Q, for some P : (Q,P) epsi M circ(NDelta).Delta(Q,P) > Delta, if NDelta. Conversely, we introduce a classification algorithm that is essentially optimal in the sense that for every (Q,P) epsi M(NDelta), the probability of classification error lambda(Q) is uniformly vanishing with N for every P : (Q,P) epsi M circ(NDelta) if N ges NDelta1+O(loglogNDelta/logNDelta). The proposed algorithm finds the largest empirical conditional divergence for a set of contexts which appear in the tested N-sequence. The computational complexity of the classification algorithm isO(N2(log N)3). Also, we introduce a second simplified context classification algorithm with a computational complexity of onlyO(N(log N)4) that is efficient in the sense that foreverypair(Q,P) epsi M(NDelta), thepairwiseprobability of classification error lambda(Q,P) for the pair Q,P vanishes with N if N ges NDelta1+O(loglogNDelta/logNDelta). Conversely, lambda(Q,P) = 1 at least for some (Q,P) epsi M(NDelta), if NDelta.

Motivated by the evident success of context-tree based methods in lossless data compression, we explore, in this correspondence, methods of the same spirit in universal prediction of individual sequences. By context-tree prediction, we refer to a family of prediction schemes, where at each time instant t, after having observed all outcomes of the data sequence x1,...,xt-1, but not yet xt, the prediction is based on a "context" (or a state) that consists of the k most recent past outcomes xt-k,...,xt-1, where the choice of k may depend on the contents of a possibly longer, though limited, portion of the observed past, xt-kmax,...,xt-1. This is different from the study reported in the paper by Feder, Merhav, and Gutman (1992), where general finite-state predictors as well as "Markov" (finite-memory) predictors of fixed order, were studied in the regime of individual sequences. Another important difference between this study and the work of Feder is the asymptotic regime. While in their work, the resources of the predictor (i.e., the number of states or the memory size) were kept fixed regardless of the length N of the data sequence, here we investigate situations where the number of contexts, or states, is allowed to grow concurrently with N. We are primarily interested in the following fundamental question: What is the critical growth rate of the number of contexts, below which the performance of the best context-tree predictor is still universally achievable, but above which it is not? We show that this critical growth rate is linear in N. In particular, we propose a universal context-tree algorithm that essentially achieves optimum performance as long as the growth rate is sublinear, and show that, on the other hand, this is impossible in the linear case

We discuss a device called "classifier" (or discriminator) that observes an individual "training" sequence of length of m letters, Xm1. The classifier's task is to examine individual test sequences of length N and decide whether the test N-sequence has the same features as those that are captured by the training sequence, or is sufficiently different, according to some appropriate criterion. No a-priori information about the test sequences is available to the classifier, aside from the training sequence. A universal classifier d(N,ZN1isin AN) for N-vectors is a mapping from ANonto {0,1}. Upon observing ZN1, the classifier declares ZN1to be "similar" to the training sequence Xm1, iff d(N,ZN1) = 1. A trivial way to proceed is to compare the test sequence XN1with each of the distinct N-vectors that appear in the training sequence Xm1. However, this procedure calls for a storage-space complexity that may grow exponentially with N. It is demonstrated that a particular universal context-tree classifier with a computational and storage complexity that is linear in N is essentially optimal. Another task for an N-sequence classifier is to decide whether two N-sequences YN1and ZN1, or more, are similar to each other in the sense that each of the N-sequences is similar (as defined above) to the same unknown training sequence which is not available, (e.g "do these N-sequences sequences have a "common ancestor" - a frequent topic in computational biology). It is demonstrated that such an hypothesis may be essentially optimally tested based on the same context-tree classifier. This contributes a theoretical "individual sequence" justification for the probabilistic suffix tree approach in computational biology

Motivated by the evident success of context-tree based methods in lossless data compression, we explore, in this paper, methods of the same spirit in universal prediction of individual sequences. By context-tree prediction, we refer to a family of prediction schemes, where at each time instant t, after having observed all outcomes of the data sequence x1,...,xt-1, but not yet xt, the prediction is based on a "context" (or a state) that consists of the k most recent past outcomes xt-k,...,xt-1, where the choice of k may depend on the contents of a possibly longer, though limited, portion of the observed past, xt-k(max),...,xt-1. This is different from the study reported in Feder et al. (1992), where general finite-state predictors as well as "Markov" (finite-memory) predictors of fixed order, where studied in the regime of individual sequences. Another important difference between this study and Feder et al. is the asymptotic regime. While in Feder et al., the resources of the predictor (i.e., the number of states or the memory size) were kept fixed regardless of the length N of the data sequence, here we investigate situations where the number of contexts, or states, is allowed to grow concurrently with N. We are primarily interested in the following fundamental question: What is the critical growth rate of the number of contexts, below which the performance of the best context-tree predictor is still universally achievable, but above which it is not? We show that this critical growth rate is linear in N. In particular, we propose a universal context-tree algorithm that essentially achieves optimum performance as long as the growth rate is sublinear, and show that, on the other hand, this is impossible in the linear case.

We consider a variation of the Wyner-Ziv (W-Z) problem pertaining to lossy compression of individual sequences using finite-state encoders and decoders. There are two main results in this paper. The first characterizes the relationship between the performance of the best M-state encoder-decoder pair to that of the best block code of size lscr for every input sequence, and shows that the loss of the latter relative to the former (in terms of both rate and distortion) never exceeds the order of (logM)/lscr, independently of the input sequence. Thus, in the limit of large M, the best rate-distortion performance of every infinite source sequence can be approached universally by a sequence of block codes (which are also implementable by finite-state machines). While this result assumes an asymptotic regime where the number of states is fixed, and only the length n of the input sequence grows without bound, we then consider the case where the number of states M=Mnis allowed to grow concurrently with n. Our second result is then about the critical growth rate of Mnsuch that the rate-distortion performance of Mn-state encoder-decoder pairs can still be matched by a universal code. We show that this critical growth rate of Mnis linear in n

Extreme densities for information combining are found for two important channel models: the binary-input symmetric parallel broadcast channel and the parity-constrained-input symmetric parallel channels. Following, upper and lower mutual information thresholds are stated for per-bit maximum a posteriori probability (MAP) decoding and low-density parity-check (LDPC) code ensembles.

Inspired by C. E. Shannon's celebrated paper: "Prediction and entropy of printed English" (1951), we consider the optimal prediction error for unknown finite-alphabet ergodic Markov sources, for prediction algorithms that make inference about the most probable incoming letter, where the distribution of the unknown source is apparent only via a short training sequence of N + 1 letters. We allow N to be a polynomial function of K, the order of the Markov source, rather than the classical case where N is allowed to be exponential in K. A lower bound on the prediction error is formulated for such universal prediction algorithms, that are based on suffixes that were observed somewhere in the past "training sequence" X/sub -N//sup -1/ (i.e. it is assumed that the universal predictor, given the past (N + 1)-sequence which serves as a training sequence is no better than the optimal predictor given only the longest suffix that appeared somewhere in the past X/sub -N//sup -1/ vector). For a class of stationary Markov sources (which includes all Markov sources with positive transition probabilities), a particular universal predictor is introduced, and it is demonstrated that its performance is "optimal" in the sense that it yields a prediction error which is close to the lower bound on the universal prediction error, with limited training data. The results are nonasymptotic in the sense that they express the effect of limited training data on the efficiency of universal predictors. An asymptotically optimal universal predictor which is based on pattern matching appears elsewhere in the literature. However, the prediction error of these algorithms does not necessarily come close to the lower bound in the nonasymptotic region.

A universal prediction lemma is derived for the class of prediction algorithms that only make inferences about the conditional distribution of an unknown random process based on what has been observed in the training data. The lemma is then used to derive lower bounds on the efficiency of a number of universal prediction and data compression algorithms. These bounds are nonasymptotic in the sense that they express the effect of limited training data on the efficiency of universal prediction and universal data compression.

An algorithm is proposed for universal decoding of convolutional/trellis codes employed over unknown channels. On discrete memoryless channels and at rates below the channel's computational cutoff rate (for a uniform input distribution), the algorithm achieves an asymptotic complexity-performance tradeoff similar to the tradeoff achieved by the Viterbi (1979) algorithm, but with the benefit that the algorithm's implementation does not require knowledge of the channel law. The algorithm is also applicable to channels with memory, and in particular to intersymbol interference (ISI) channels, to channels with nonlinear ISI, and even to general finite-state channels.

Nonasymptotic coding and converse theorems are derived for universal data compression algorithms in cases where the training sequence ("history") that is available to the encoder consists of the most recent segment of the input data string that has been processed, but is not large enough so as to yield the ultimate compression, namely, the entropy of the source.

A universal decoder for a family of channels is a decoder that can be designed without prior knowledge of the particular channel in the family over which transmission takes place, and it yet attains the same random-coding error exponent as the optimal decoder tuned to the channel in use. We study Ziv's (1985) decoding algorithm, which is based on Lempel-Ziv (1978) incremental string parsing, and demonstrate that while it was originally proposed as a universal decoder for the family of finite-state channels with deterministic (but unknown) transitions, it is in fact universal for the broader class of all finite-state channels. We also demonstrate that the generalized likelihood decoder may not be universal even for finite families for which a universal decoder always exists.

In this paper, the role of pattern matching in information theory is motivated and discussed. We describe the relationship between a pattern's recurrence time and its probability under the data-generating stochastic source. We show how this relationship has led to great advances in universal data compression. We then describe nonasymptotic uniform bounds on the performance of data-compression algorithms in cases where the size of the training data that is available to the encoder is not large enough so as to yield the asymptotic compression: the Shannon entropy. We then discuss applications of pattern matching and universal compression to universal prediction, classification, and entropy estimation.

The amount of fixed side information required for lossless data compression is discussed. Nonasymptotic coding and converse theorems are derived for data-compression algorithms with fixed statistical side information ("training sequence") that is not large enough so as to yield the ultimate compression, namely, the entropy of the source.

Consider a vector quantizer that is equipped with N side information bits of an arbitrary representation of the statistics of the input source. We investigate the minimum value of N such that rate-distortion performance of this quantizer would be essentially the same as the optimum quantizer for the given source.

The use of information theory concepts for universal estimation of delay for classes of discrete channels is discussed. The problem is presented as one of hypothesis testing. Although the channel statistics are not known, for large enough signal duration, the exponent of the average error probability is equal to that associated with the optimal maximum-likelihood (ML) decision procedure which utilizes full knowledge of the channel parameters. Two categories of problems are discussed: the single-channel problem, where the random transmitted signal is known to the receiver, and the two-sensor problem, where the random signal is unknown.

Consider the following situation. A device called a classifier observes a probability law P on l-vectors from an alphabet of size A. Its task is to observe a second probability law Q and decide whether P/spl equiv/Q or P and Q are sufficiently different according to some appropriate criterion. If the classifier has available an unlimited memory (so that it can remember P(z) exactly for all z), this is a simple matter. In fact for most differentness criteria, a finite memory of 2/sup (log/ /sup A)l+o(l)/ bits will suffice (for large l), i.e., store a finite approximation of P(z) for all A/sup l/z's. In a sense made precise in this paper, it is shown that a memory of only about 2/sup Rl/ bits is required, where the quantity R

The sliding-window version of the Lempel-Ziv data-compression algorithm (sometimes called LZ '77) has been thrust into prominence recently. A version of this algorithm is used in the highly successful "Stacker" program for personal computers. If is also incorporated into Microsoft's new MS-DOS-6. Although other versions of the Lempel-Ziv algorithm are known to he optimal in the sense that they compress a data source to its entropy, optimality in this sense has never been demonstrated for this version. In this self-contained paper, we will describe the algorithm, and show that as the "window size," a quantity which is related to the memory and complexity of the procedure, goes to infinity, the compression rate approaches the source entropy. The proof is surprisingly general, applying to all finite-alphabet stationary ergodic sources.>

S. De Agostino and M. Cohn from Brandeis University called attention to a flaw in Theorem 2 of the above-named correspondence [ibid., vol. 36, pp. 861-863, July 1990]. The various corrections noted should be inserted on p. 863.

A new notion of empirical informational divergence (relative entropy) between two individual sequences is introduced. If the two sequences are independent realizations of two finite-order, finite alphabet, stationary Markov processes, the empirical relative entropy converges to the relative entropy almost surely. This empirical divergence is based on a version of the Lempel-Ziv data compression algorithm. A simple universal algorithm for classifying individual sequences into a finite number of classes, which is based on the empirical divergence, is introduced. The algorithm discriminates between the classes whenever they are distinguishable by some finite-memory classifier for almost every given training set and almost any test sequence from these classes. It is universal in the sense that it is independent of the unknown sources.>

The authors propose a general model for a sequential coder, and investigate the associated coding delay. This model is employed to derive lower and upper bounds on the delay associated with commonly used encoders and decoders for noiseless data compression.>

An upper bound on the probability of a sequence drawn from a finite-state source is derived. The bound is given in terms of the number of phrases obtained by parsing the sequence according to the Lempel-Ziv (L-Z) incremental parsing rule, and is universal in the sense that it does not depend on the statistical parameters that characterize the source. This bound is used to derive an upper bound on the redundance of the L-Z universal data compression algorithm applied to finite-state sources, that depends on the length N of the sequence, on the number K of states of the source, and, eventually, on the source entropy. A variation of the L-Z algorithm is presented, and an upper bound on its redundancy is derived for finite-state sources. A method to derive tighter implicit upper bounds on the redundancy of both algorithms is also given, and it is shown that for the proposed variation this bound is smaller than for the original L-Z algorithm, or every value of N and K.>

The estimation and universal compression of discrete sources are considered, and a sequential algorithm for the universal coding of finite memory sources, attaining asymptotically minimum redundancy, is presented. The algorithm performs an online estimation of the source states and uses an arithmetic code.>

The authors consider the problem of ordering strings of a fixed length over a discrete alphabet according to decreasing probabilities of having been emitted by an unknown finite-state source. Data compression is applied to derive a universal algorithm that solves this problem with an optimal asymptotic performance. This result is employed in the solution of the following problem: discriminate an individual sequence as emitted by an independently identically distributed random source of equally likely symbols or as a signal corrupted by noise. Tight lower and upper bounds on the asymptotic performance of finite-state discriminators are given.>

The generalized likelihood ratio test (GLRT), which is commonly used in composite hypothesis testing problems, is investigated. Conditions for asymptotic optimality of the GLRT in the Neyman-Pearson sense are studied and discussed. First, a general necessary and sufficient condition is established, and then based on this, a sufficient condition, which is easier to verify, is derived. A counterexample where the GLRT is not optimal, is provided as well. A conjecture is stated concerning the optimality of the GLRT for the class of finite-state sources.>

The problem of estimating the number of states of a finite-alphabet, finite-state source is investigated. An estimator is developed that asymptotically attains the minimum probability of understanding the number of states, among all estimators with a prescribed exponential decay rate of overestimation probability. The proposed estimator relies on the Lempel-Ziv data compression algorithm in an intuitively appealing manner.>

Motivated by the study of various kinds of machines as recognizers of formal languages, the authors compare the encoding and decoding power of finite state sequential machines and extensions thereof. They show that, with a forward moving head, the best compression achievable for a given sequence, to be decoded by a finite state decoder, is the same as the best ratio attainable for that sequence when encoded by a finite state information lossless encoder. They cannot gain in compression by allowing a finite state encoder to move its head back and forth on an input sequence, even if the decoder has unrestricted power. However, better compression can be achieved for specific infinite sequences using an unrestricted encoder and a two-way finite state decoder.>

The authors consider the problem of ordering of strings of a fixed length over a discrete alphabet, according to decreasing probabilities of having been emitted by an unknown finite-state source. Data compression is applied to derive a universal algorithm that solves this problem with an optimal asymptotic performance. The result is applied to discriminate an individual sequence as emitted by an i.i.d. random source or as a signal corrupted by noise. Tight lower and upper bounds on the asymptotic performance of finite-state discriminators are given.>

It is demonstrated that a variant of the algorithm, where the data base is held fixed and is reused to encode successive strings of incoming input symbols, is optimal provided that the source is stationary and satisfies certain conditions (e.g. a finite-order Markov source).>

A Bayesian approach for classification of Markov sources whose parameters are not explicitly known is developed and studied. A universal classifier is derived and shown to achieve, within a constant factor, the minimum error probability in a Bayesian sense. The proposed classifier is based on sequential estimation of the parameters of the sources, and it is closely related to earlier proposed universal tests under the Neyman-Pearson criterion.>

It is demonstrated that a variant of the Lempel-Ziv data compression algorithm where the database is held fixed and is reused to encode successive strings of incoming input symbols is optimal, provided that the source is stationary and satisfies certain conditions (e.g., a finite-order Markov source). A finite memory version of the Lempel-Ziv algorithm compresses (on the average) to about the entropy rate. The necessary memory size depends on the nature of the source.>

Distortion-free compressibility of individual pictures by finite-state encoders is investigated. In a recent paper (see IEEE Trans. Inform. Theory, vol.32, no.1, p.1-8, 1986) the compressibility of a given picture I was defined and shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved for I by any finite-state encoder. Here, a different and more direct approach is taken to prove similar results, which are summarized in a converse-to-coding theorem and a constructive-coding-theorem that leads to a universal asymptotically optimal compression algorithm.>

A universal nearly efficient estimator is proposed for the first-order autoregressive (AR) model where the probability distribution of the driving noise is unknown. It is shown that universal estimators for the AR model can be derived from universal data compression algorithms and universal tests for randomness. In other words, estimators derived appropriately from efficient universal codes can be expected to inherit good estimation performance under some conditions. The proposed estimator has a simple information-theoretic interpretation related to universal coding, which can be easily generalized to the higher-order case and to other parametric models, e.g. the one-sample location model, the two-sample location model, and the linear regression model.>

It is demonstrated that for finite-alphabet, kth-order ergodic Markov sources (i.e. memory of k letters), a variable-to-fixed length code is better than the best fixed-to-variable length code (Huffman code). It is shown how to construct a variable-to-fixed length code for a kth order ergodic Markov source, which compresses more effectively than the best fixed-to-variable code.>

The authors estimate the order of a finite Markov source based on empirically observed statistics. The performance criterion adopted is to minimize the probability of underestimating the model order while keeping the overestimation probability exponent at a prescribed level. A universal asymptotically optimal test, in the sense just defined, is proposed for the case where a given integer is known to be the upper bound of the true order. For the case where such a bound is unavailable, an alternative rule based on the Lempel-Ziv data compression algorithm is shown to be asymptotically optimal also and computationally more efficient.>

Parameter estimation based on data emitted from a finite ergodic Markov source is discussed. This can be considered an extension of the memoryless case. First, an asymptotically optimal estimator is suggested for the case where the parametric model is completely known. For an unknown parametric model (e.g unknown noise distribution with training sequences available) a necessary condition is given for the existence of a universally optimum estimate. A universal estimate is then suggested that is asymptotically nearly optimal. The results hold under fairly mild regularity conditions.>

Theorems concerning the entropy of a stationary ergodic information source are derived and used to obtain insight into the workings of certain data-compression coding schemes, in particular the Lempel-Siv data compression algorithm.>

The authors obtained lower bounds to the capacity of the continuous-time filtered additive Gaussian noise channel with two-valued inputs. Essentially, the problem reduces to the continuous-time peak-limited case, which remains an unsolved problem of primary importance in communication theory.>

Classification with empirically observed statistics is studied for finite alphabet sources. Efficient universal discriminant functions are described and shown to be related to universal data compression. It is demonstrated that if one of the probability measure of the two classes is not known, it is still possible to define a universal discrimination function which performs as the optimal (likelihood ratio) discriminant function (which can be evaluated only if the probability measures of the two classes are available). If both of the probability measures are not available but training vectors from at least one of the two classes are available, it is demonstrated that no discriminant function can perform efficiency of the length of the training vectors does not grow at least linearly with the length of the classified vector. A universal discriminant function is introduced and shown to perform efficiently when the length of the training vectors grows linearly with the length of the classified sequence, in the sense that it yields an error exponent that is arbitrarily close to that of the optimal discriminant function.>

Distortion-free compressibility of individual pictures, i.e., two-dimensional arrays of data, by finite-state encoders is investigated. For every individual infinite pictureI, a quantity\rho(I)is defined, called the compressibility ofI, which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved forIby any finite-state information-lossless encoder. This is demonstrated by means of a constructive coding theorem and its converse that, apart from their asymptotic significance, might also provide useful criteria for finite and practical data-compression tasks. The proposed picture compressibility is also shown to possess the properties that one would expect and require of a suitably defined concept of two-dimensional entropy for arbitrary probabilistic ensembles of infinite pictures. While the definition of\rho(I)allows the use of different machines for different pictures, the constructive coding theorem leads to a universal compression scheme that is asymptotically optimal for every picture. The results are readily extendable to data arrays of any finite dimension.

The quantization ofn-dimensional vectors inR^{n}with an arbitrary probability measure, under a mean-square error constraint, is discussed. It is demonstrated that a uniform, one-dimensional quantizer followed by a noiseless digital variable-rate encoder ("entropy encoding") can yield a rate that is, for anyn, no more than0.754bit-per-sample higher than the rate associated with the optimaln-dimensionai quantizer, regardless of the probabilistic characterization of the inputn-vector for the allowable mean-square error.

Universal decoding procedures for finite-state channels are discussed. Although the channel statistics are not known, universal decoding can achieve an error probability with an error exponent that, for large enough block length (or constraint length in case of convolutional codes), is equal to the random-coding error exponent associated with the optimal maximum-likelihood decoding procedure for the given channel. The same approach is applied to sequential decoding, yielding a universal sequential decoding procedure with a cutoff rate and an error exponent that are equal to those achieved by the classical sequential decoding procedure.

For every infinite sequencexand a given side-information sequencey, we define a qualityH(x|y)called the finite-state conditional complexity ofxgiveny. It is shown thatH(x|y)is the smallest asymptotically attainable fixed-rate at whichxcan be transmitted with negligibly small distortion, giveny. Moreover, it is demonstrated that in order to achieve an arbitrary small distortion for all sequences such thatH(x|y)is less than the allowable transmission rate it is not necessary for the encoder to have access to the side-information sequencey(provided it is available to the decoder). This result is a generalization of the classical Slepian-Wolf result for cases where the probabilistic characterization ofxandyis not known, or does not exist.

It is shown that a lower hound ofn^{3}or more on the straight-line complexity of a functionfover GF(2^{n})is also a lower bound on the network complexity offand, hence, on the product of run time and program size of Turing machines. It is further shown that most functions over a finite field are hard to compute and that for most hard functions there exists no approximation via an easy algorithm.

For every individual infinite sequenceuwe define a distortion-rate functiond(R|u)which is shown to be an asymptotically attainable lower bound on the distortion that can be achieved foruby any finite-state encoder which operates at a fixed output information rateR. This is done by means of a coding theorem and its converse. No probabilistic characterization ofuis assumed. The coding theorem demonstrates the existence of {\em universal} encoders which are asymptotically optimal for every infinite sequence over a given finite alphabet. The transmission of individual sequences via a noisy channel with a capacityCis also investigated. It is shown that, for every given sequenceuand any finite-state encoder, the average distortion with respect to the channel statistics is lower bounded byd(C|u). Furthermored(C|u)is asymptotically attainable.

A quantity called the {\em finite-state} complexity is assigned to every infinite sequence of elements drawn from a finite sot. This quantity characterizes the largest compression ratio that can be achieved in accurate transmission of the sequence by any finite-state encoder (and decoder). Coding theorems and converses are derived for an individual sequence without any probabilistic characterization, and universal data compression algorithms are introduced that are asymptotically optimal for all sequences over a given alphabet. The finite-state complexity of a sequence plays a role similar to that of entropy in classical information theory (which deals with probabilistic ensembles of sequences rather than an individual sequence). For a probabilistic source, the expectation of the finite state complexity of its sequences is equal to the source's entropy. The finite state complexity is of particular interest when the source statistics are unspecified.

Compressibility of individual sequences by the class of generalized finite-state information-lossless encoders is investigated. These encoders can operate in a variable-rate mode as well as a fixed-rate one, and they allow for any finite-state scheme of variable-length-to-variable-length coding. For every individual infinite sequencexa quantity\rho(x)is defined, called the compressibility ofx, which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved forxby any finite-state encoder. This is demonstrated by means of a constructive coding theorem and its converse that, apart from their asymptotic significance, also provide useful performance criteria for finite and practical data-compression tasks. The proposed concept of compressibility is also shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences. While the definition of\rho(x)allows a different machine for each different sequence to be compressed, the constructive coding theorem leads to a universal algorithm that is asymptotically optimal for all sequences.

An improved lower bound on the local mean-square error and upper and lower bounds on the bias which are tighter than previously known bounds are derived.

A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source.

A new approach to the problem of evaluating the complexity ("randomness") of finite sequences is presented. The proposed complexity measure is related to the number of steps in a self-delimiting production process by which a given sequence is presumed to be generated. It is further related to the number of distinct substrings and the rate of their occurrence along the sequence. The derived properties of the proposed measure are discussed and motivated in conjunction with other well-established complexity criteria.

Let\{(X_{k}, Y_{k}) \}^{ \infty}_{k=1}be a sequence of independent drawings of a pair of dependent random variablesX, Y. Let us say thatXtakes values in the finite set\cal X. It is desired to encode the sequence\{X_{k}\}in blocks of length n into a binary stream of rateR, which can in turn be decoded as a sequence\{ \hat{X}_{k} \}, where\hat{X}_{k} \in \hat{ \cal X}, the reproduction alphabet. The average distortion level is(1/n) \sum^{n}_{k=1} E[D(X_{k},\hat{X}_{k})], whereD(x,\hat{x}) \geq 0, x \in {\cal X}, \hat{x} \in \hat{ \cal X}, is a preassigned distortion measure. The special assumption made here is that the decoder has access to the side information\{Y_{k}\}. In this paper we determine the quantityR \ast (d), defined as the infimum ofratesRsuch that (with\varepsilon > 0arbitrarily small and with suitably largen)communication is possible in the above setting at an average distortion level (as defined above) not exceedingd + \varepsilon. The main result is thatR \ast (d) = \inf [I(X;Z) - I(Y;Z)], where the infimum is with respect to all auxiliary random variablesZ(which take values in a finite set\cal Z) that satisfy: i)Y,Zconditionally independent givenX; ii) there exists a functionf: {\cal Y} \times {\cal Z} \rightarrow \hat{ \cal X}, such thatE[D(X,f(Y,Z))] \leq d. LetR_{X | Y}(d)be the rate-distortion function which results when the encoder as well as the decoder has access to the side information\{ Y_{k} \}. In nearly all cases it is shown that whend > 0thenR \ast(d) > R_{X|Y} (d), so that knowledge of the side information at the encoder permits transmission of the\{X_{k}\}at a given distortion level using a smaller transmission rate. This is in contrast to the situation treated by Slepian and Wolf [5] where, for arbitrarily accurate reproduction of\{X_{k}\}, i.e.,d = \varepsilonfor any\varepsilon >0, knowledge of the side information at the encoder does not allow a reduction of the transmission rate.

An improved technique for bounding the mean-square error of signal parameter estimates is presented. The resulting bounds are independent of the bias and stronger than previously known bounds.

Let\xi = \{\xi(t), 0 \leq t \leq T\}be a process with covariance functionK(s,t)andE \int_0^T \xi^2(t) dt < \infty. It is proved that for every\varepsilon > 0the\varepsilon-entropyH_{\varepsilon}(\xi)satisfies \begin{equation} H_{\varepsilon}(\xi_g) - \mathcal{H}_{\xi_g} (\xi) \leq H_{\varepsilon}(\xi) \leq H_{\varepsilon}(\xi_g) \end{equation} where\xi_gis a Gaussian process with the covarianeeK(s,t)and\mathcal{H}_{\xi_g}(\xi)is the entropy of the measure induced by\xi(in function space) with respect to that induced by\xi_g. It is also shown that if\mathcal{H}_{\xi_g}(\xi) < \inftythen, as\varepsilon \rightarrow 0\begin{equation} H_{\varepsilon}(\xi) = H_{\varepsilon}(\xi_g) - \mathcal{H}_{\xi_g}(\xi) + o(1). \end{equation} Furthermore, ff there exists a Gaussian processg = \{ g(t); 0 \leq t \leq T \}such that\mathcal{H}_g(\xi) < \infty, then the ratio betweenH_{\varepsilon}(\xi)andH_{\varepsilon}(g)goes to one as\varepsilongoes to zero. Similar results are given for the rate-distortion function, and some particular examples are worked out in detail. Some cases for which\mathcal_{\xi_g}(\xi) = \inftyare discussed, and asymptotic bounds onH_{\varepsilon}(\xi), expressed in terms ofH_{\varepsilon}(\xi_g), are derived.

Upper and lower bounds on the\varepsilon-entropy of the Wiener process and theRCprocess are derived. The bounds are quite tight for small\varepsilon. The associated rate-distortion function is discussed and upper and lower bounds on this function are derived.

In this, the first part of a two-part paper, we establish a theorem concerning the entropy of a certain sequence of binary random variables. In the sequel we will apply this result to the solution of three problems in multi-user communication, two of which have been open for some time. Specifically we show the following. LetXandYbe binary randomn-vectors, which are the input and output, respectively, of a binary symmetric channel with "crossover" probabilityp_0. LetH\{X\}andH\{ Y\}be the entropies ofXandY, respectively. Then \begin{equation} \begin{split} \frac{1}{n} H\{X\} \geq h(\alpha_0), \qquad 0 \leq \alpha_0 &\leq 1, \Rightarrow \\ \qquad \qquad \&\qquad \frac{1}{n}H\{Y\} \geq h(\alpha_0(1 - p_0) + (1 - \alpha_0)p_0) \end{split} \end{equation} whereh(\lambda) = -\lambda \log \lambda - (1 - \lambda) \log(l - \lambda), 0 \leq \lambda \leq 1.

It is shown that the rate-distortion bound(R(d) \leq C)remains true when-\log xin the definition of mutual information is replaced by an arbitrary concave(\cup)nonincreasing function satisfying some technical conditions. Examples are given showing that for certain choices of the concave functions, the bounds obtained are better than the classical rate-distortion bounds.

The optimal nonlinear filtering of certain vector-valued diffusion processes embedded in white noise is considered. We derive upper and lower bounds on the minimal causal mean-square error. The derivation of the lower bound is based on information-theoretic considerations, namely the rate-distortion function (\varepsilon-entropy). The upper bounds are based on linear-filtering arguments. It is demonstrated that for a wide class of high-precision systems, the upper and lower bounds are tight within a factor of 2 or better.

It is well known that it is often possible to obtain considerable data compression by encoding messages in long blocks. Usually the coding scheme for a specific source depends parametrically on the statistics of the source. Universal codes which are independent of the source statistics are introduced. These codes are shown to be asymptotically optimal in the sense that the probability of encoding error can be made vanishingly small for output rates no larger than those of optimal codes that do in fact depend on the statistics of the source. A particular universal coding scheme is introduced for which the encoding complexity increases no faster than the second power of the block lengthnand for which the encoding error vanishes exponentially withn. The discussion is limited to discrete-time finite-alphabet sources.

The encoding of sources with unknown statistics is considered. The average distortion that is obtained with universal coding schemes that are independent of the source statistics is shown to be asymptotically identical to the smallest average distortion that can be achieved with the best individual coding scheme (i.e., a code that is based on the specific statistics of the source). This result is shown to hold for any stationary source, as well as for a class of nonstationary sources. The discussion is limited to a certain important class of metric spaces.

We consider the class of sequential estimation systems containing additive Gaussian noise channels. Letmbe a random variable representing the source andx(t),y(t)be stochastic processes representing the signal and the channel output, respectively. Denote by\hat{m}an estimate ofmbased on observingy(t)from 0 to\tau, where\tauis a random variable determined by a certain stopping rule of the decoder depending on a realization ofy. Letd(m,\hat{m})be the distortion of\hat{m}relative tomandR(\cdot)be the rate distortion function ofmwith respect to the distortion measured. Denote byP_oandN_othe available average signal power and the noise power level, respectively. We show thatE_{\tau} \geq (2 N_o / P_o)R. (Ed(m,\hat{m}))and henceEd(m,\hat{m}) \geq R ^ {-1} (P_o E_ \tau /2N_o ).. That is, given the average distortionEd(m,\hat{m}), the average transmission time required can be no smaller than(2N_o/P_o)R(Ed(m,\hat{m})). Conversely, given the average transmission timeE_{\tau}, the average distortion can be no smaller thanR ^ {-1} (P_o E _ {\tau} /2N_o).

The following model for the white Gaussian channel with or without feedback is considered: \begin{equation} Y(t) = \int_o ^{t} \phi (s, Y_o ^{s} ,m) ds + W(t) \end{equation} wheremdenotes the message,Y(t)denotes the channel output at timet,Y_o ^ {t}denotes the sample pathY(\theta), 0 \leq \theta \leq t. W(t)is the Brownian motion representing noise, and\phi(s, y_o ^ {s} ,m)is the channel input (modulator output). It is shown that, under some general assumptions, the amount of mutual informationI(Y_o ^{T} ,m)between the messagemand the output pathY_o ^ {T}is directly related to the mean-square causal filtering error of estimating\phi (t, Y_o ^{t} ,m)from the received dataY_o ^{T} , 0 \leq t \leq T. It follows, as a corollary to the result forI(Y_o ^ {T} ,m), that feedback can not increase the capacity of the nonband-limited additive white Gaussian noise channel.

Shannon showed that the capacity of a discrete memoryless channel can not be increased by noiseless feedback. It has been conjectured that this should be true for a continuous memoryless channel, provided such a channel is appropriately defined. We precisely define such a channel from two mathematically different points of view and rigorously prove that its capacity can not be increased by feedback.

In this paper, we study discrete-time stationary sourcesSwith memory. The rateR(\beta)of the source relative to a distortion measure is compared withR^ \ast (\beta), the rate of the memoryless sourceS^ /astwith the same marginal statistics asS. We show thatR^ \ast (\beta) - \Delta \leq R(\beta) \leq R^ \ast (\beta), where\Deltais a measure of the memory of the source. A number of interesting applications of these bounds are given.

This paper is concerned with the transmission of information with a fidelity criterion where the source output may be distorted prior to encoding and, furthermore, where the output of the decoder may be distorted prior to its delivery to the final destination. The criterion for optimality is that the normalized average of the squared norm of the difference between theT- second undistorted source sample and the correspondingT-second sample delivered to the final destination be minimum. The optimal structure of the encoder and decoder is derived for anyT.

We consider the problem of transmission of analog data over a noisy channel. It is assumed that the channel input is of the form\surd S f(t, X), whereXis ann-dimensional source vector, andSis the allowable transmitted power. The performance of any given modulation schemef(t, \cdot )as a function of the transmitted powerSis studied. Lower bounds on the average distortion produced by noise for a class of distortion functions are derived. These bounds relate the "smoothness" of modulation techniques to the minimum error that can be achieved with them. It is shown that when the analog source emits a sequence of mutually independent real random variables at a rate ofRper second, the mean-square error that is associated with any practical modulation schemef(t, \cdot)decays no faster thanS^{-2}as the signal powerS \rightarrow \infty. It follows that in the case of a band-limited additive white Gaussian channel no single modulation schemef(t, \cdot )can achieve the ideal rate-distortion bound on the mean-square error for all values ofS, if the channel bandwidth is larger than the source rateR.

We consider binary communication over the additive white Gaussian noise channel with no bandwidth constraint on the channel input signals, assuming the availability of a noiseless delayless feedback link. Although the signals at timetcan depend on the noise at times\tau < tand are therefore random functions, we require that the signal energy never exceed a fixed level. We show that the optimal probability of error is attainable without the use of the feedback channel by using antipodal signals.

The problem of estimating the position of a position-modulated rectangular pulse in additive white noise is considered. The maximum likelihood estimation procedure is assumed. Bounds are derived for the probability of large estimation errors.

New bounds are presented for the maximum accuracy with which parameters of signals imbedded in white noise can be estimated. The bounds are derived by comparing the estimation problem with related optimal detection problems. They are, with few exceptions, independent of the bias and include explicitly the dependence on the a priori interval. The new results are compared with previously known results.

The purpose of this paper is to show that decoding complexity need not grow exponentially with the code block length at rates close to channel capacity and also to show the expediency of the approach of imbedding codes in each other. It is demonstrated that it is possible to communicate over a memoryless channel of capacityCat any rateR < Cwith a probability of error of less than2^{-E(R)\nu}, E(R) > 0, per block of a length approximately proportional to\nu^{2}and with a computational decoding complexity per digit which is asymptotically proportional to\nu^{\alpha}when\nuis large,\nu^{\alpha}being finite forR < C.(\alpha \rightarrow \mbox{as} R \rightarrow C, \alpha \rightarrow 2 \mbox{as} R \rightarrow 0).

The purpose of this paper is to demonstrate that it is possible to communicate over a memoryless channel of capacityCat any rateR < Cwith a probability of error less than2^{-E(R)\nu},E(R)>0, per block of a length approximately proportional to\nu^{2}and with a computational decoding complexity which is asymptotically proportional to\nu^{2}when\nuis large. The decoding scheme presented in this paper is based on a two-cycle iteration of a decoding procedure which has been described in an earlier paper [1 ].

In this paper, the probability of error of two time-varying channels with memory, 1) the random phase channel and 2) the Rayleigh fading channel, is discussed. The input is assumed to be one of M equiprobable waveforms. An upper bound to the probability of error is derived by convetting the channel into a memoryless one by means of scrambling. A lower bound to the probability of error is derived by assuming that except for an additive noise, all the channel parameters are completely known at the receiver and, therefore, are not considered to be random variables any more. Following this assumption, it is shown that the channel is converted into a memoryless channel. For each one of the two channels, there is a region of SNR where the upper and lower bounds are close together and therefore yield a good estimate to the actual probability of error. Furthermore, using random coding and scrambling, this probability of error may actually be achieved (for a certain region of rates).

In this paper a new decoding scheme for random convolutional codes is described. This scheme is different from other effective decoding schemes, such as sequential decoding [1] and low-density parity check codes [2]. The new scheme yields (for a certain region of information rates) an upper bound on the average number of computations which is {\em independent} of the coding constraint length. Furthermore, unlike sequential decoding, a bound on the total number of computations (rather than just on the "incorrect subset") is derived in this paper.

In this research paper, we consider some aspects of the general problem of encoding and decoding for time-discrete, amplitude-continuous memoryless channels. A scheme for constructing a discrete signal space, for which sequential encoding-decoding methods are possible for the general continuous memoryless channel, is described. Random code selection from a finite ensemble, with each code word sequentially generated from a small number of basic waveforms, is considered. The effects of these signal-space constraints on the average probability of error, for different signal-power constraints, are also discussed. The application of sequential decoding to the continuous asymmetric channel, and a new decoding scheme for convolutional codes, successive decoding, are considered. This new decoding scheme yields a tighter bound on the average number of decoding computations for asymmetric channels than has yet been obtained for sequential decoding. The probabilities of error of the two decoding schemes are also discussed. We consider the quantization at the receiver, and its effects on probability of error and receiver complexity.