The performance of three versions of the Lempel-Ziv (1976) algorithm on individual sequences is investigated. It is shown that as the restart length goes to infinity, each compresses an individual sequence as well as any block-to-variable finite-state information lossless algorithm, and that the same conclusion holds for sliding-window LZ as the window width goes to infinity. Examples are given showing that an infinite-memory version outperforms such finite-memory forms and that such finite-memory forms can compress more than the Ziv (1978) entropy, which is the best compression attainable by finite-state block-to-block codes that have vanishing probability of error.

A conceptually simple coding method may be described as follows. The source sequence is parsed into fixed-length blocks and a list of these blocks is placed in a dictionary. In the lossless case, the dictionary is transmitted and each successive block is encoded by giving its dictionary location. In the lossy case, the smallest collection of blocks such that every member of the dictionary is within distortion /spl delta/ of the collection is determined, this codebook is transmitted, and each successive block is encoded by giving the location of a member of the code within /spl delta/ of it. We show that by optimizing on the block length, this method is universal, that is, for any ergodic process it achieves entropy in the limit in the lossless case and the rate-distortion function R(/spl delta/) in the lossy case.

Information theorists frequently use the ergodic theorem; likewise entropy concepts are often used in information theory. Recently, the two subjects have become partially intertwined as deeper results from each discipline find use in the other. A brief history of this interaction is presented in this paper, together with a more detailed look at three areas of connection, namely, recurrence theory, blowing-up bounds, and direct sample-path methods.

Upper and lower bounds, both of order /spl radic/n, are obtained on minimax redundancy of universal lossless codes for the class of renewal processes. This is the first example of an interesting model class with strong redundancy rate o(n) but not O(log n). For the same class, the nonexistence of weak-rate bounds of smaller order than /spl radic/n is also shown. The methods extend to provide upper and lower redundancy rate bounds of order n/sup (k+1)//(k+2) for the class of processes that are Markov renewal of order k. The weak-rate methods also extend to show the nonexistence of o(n) weak-rate bounds for the class of regenerative processes.

Shows that for any sequence /spl rho/(n)=o(n) and any sequence of prefix codes, there is a B-process of entropy arbitrarily close to the maximum possible entropy for which the expected redundancy is at least as large as /spl rho/(n) for infinitely many n. This extends work of Shields (1993), whose examples had O entropy. The class of B-processes, that is, stationary codings of independent and identically distributed (i.i.d.) processes, includes the aperiodic Markov chains and functions thereof, aperiodic renewal and regenerative processes, and m-dependent processes, as well as many other processes of interest. In particular, the results show that the search for a universal redundancy rate for the class of all B-processes is doomed to failure, and redundancy rates for any given subclass must be obtained by direct analysis of that subclass.>

The expected redundancy per symbol of an n-block prefix code C/sub n/ on a source mu measures how far the code is from being optimal for that source. The existence of sequences of codes with expected redundancy per symbol of O((log n)/n) for 'nice' classes of sources, such as Markov sources of a given order, is well known. It is shown that some restriction on the class of processes is necessary in order to obtain such redundancy bounds, for there is no universal redundancy rate for any sequence of prefix codes on the class of all ergodic sources.>

Cutting and stacking, a general method for constructing examples of stationary, ergodic, finite-alphabet processes with desired properties, is described. It has been used to construct counterexamples in ergodic theory. Recently, it has also been used to construct examples of interest in information theory and probability theory. The method builds a stationary ergodic process by describing sample paths as concatenations of nonoverlapping blocks of varying lengths. Induction is used to show how these blocks are concatenated to form longer and longer blocks, and a geometric model is used to guarantee stationarity. The basic ideas of the method and some recent applications to information theory problems are described.>

The entropy theorem (also known as the Shannon-McMillan-Breiman theory or the asymptotic equipartition theorem) asserts that, for a stationary ergodic finite alphabet process, the sequence-(1/n)log p(x/sub 1//sup n/) converges almost surely to the entropy-rate H of the process. The entropy theorem has been used to establish asymptotic bounds on the performance of noiseless codes. Here, the coding theorems are established without using the entropy theorem, and the coding theorems are then used to prove the entropy theorem. The principle feature is the direct use of coding ideas to obtain the entropy theorem.>

A new proof of Birkhoff's ergodic theorem is given using a sample path covering idea, an idea created by Ornstein and Weiss in their extension of the information convergence theorem to random fields. A sketch of the Ornstein-Weiss proof for processes is included in the Appendix.

The class of discrete stationary channels with memory that can be arbitrarily well approximated by indecomposable finite state channels is investigated. The\bar{d}concept of channel distance is used to quantify the notion of one channel approximating another, and it is shown that the class of interest equals the class of channels approximable by nonanticipating primitive channels. The latter class includes all nonanticipating finite memory channels and all nonanticipating\bar{d}-continuous, conditional almost block independent (CABI) channels. In addition, it is shown that for a large class of finite state channels,\bar{d}continuity and CABI imply indecomposability.

A stationary channel can have two kinds of memory--input memory and output memory. Recently, Gray and Ornstein introduced a condition on the decay of input memory called\bar{d}-continuity and established coding theorems for d-continuous channels. In this paper a condition for the decay of output memory is introduced which is called conditional almost block independence (CABI). It is believed that these two properties describe the character of many channels of interest. The principal result states that the\bar{d}-continuous CABI channels are precisely those which can be approximated in a very strong sense by a simple kind of finite memory channel, called a primitive channel, in which the source of randomness is memoryless and completely separated from the memory.

In 1969, Ornstein showed that two independent, identically distributed (i.i.d.) processes with the same entropy are isomorphic, that is, there is a stationary, invertible code from one onto the other. These results have led to a number of characterizations of the class of processes which are stationary codings of i.i.d, processes. Many of these ideas are now finding a use in information theory. Some of these results and ideas are discussed, using the process language familiar to information theorists.

The existence of a fixed-rate block source code whose performance for each source in a class of Markov sources is uniformly close to the distortion-rate function of that source is investigated. Such a code is called strong universal. It is found that strong universal codes of all rates exist for the class of all binary first-order Markov sources. But for a larger alphabet or for the class of allnth-order Markov sources withn > 2, there is a critical rateR\astsuch that strong universal codes exist for rates greater than or equal toR\ast, but not for rates less thanR\ast.

A new form of source coding subject to a fidelity criterion, called sliding-block coding, has recently been introduced by Gray, Neuhoff, and Ornstein. A method of conversion from block coding to sliding-block coding, or vice versa, with an arbitrarily small increase in rate is shown for ergodic sources. The ergodic theorem is used to convert from sliding-block codes to block codes. A theorem similar to one of Rohlin is used to convert from block codes to sliding-block codes. A proof of this theorem and some discussion of the nonergodic case appear in the appendices.