For a stationary random field {x(u): u /spl isin/ Z/sup d/}, the recurrence time R/sub n/(x) may be defined as the smallest positive k, such that the pattern {x(u): 0 /spl les/ u/sub i/ < n} is seen again, in a new position in the cube {0 /spl les/ |u/sub i/| < k}. In analogy with the case of d = 1, where the pioneering work was done by Wyner and Ziv (1989), we prove here that the asymptotic growth of R/sub n/(x) for ergodic fields is given by the entropy of the random field. The nonergodic case is also treated, as well as the recurrence times of central patterns in centered cubes. Both finite and countable state spaces are treated.

Some new ways of defining the entropy of a process by observing a single typical output sequence as well as a new kind of Shannon-McMillan-Breiman theorem are presented. This provides a new and conceptually very simple ways of estimating the entropy of an ergodic stationary source as well as new insight into the workings of such well-known data compression schemes as the Lempel-Ziv algorithm.>

A new class of discrete stationary noisy channels with memory and anticipation termed d-continuous channels is introduced and is shown to include all stationary discrete channels for which coding theorems exist. Roughly speaking, in a\bar{d}-continuous channel the effect of the "past" and "future" inputs on n successive outputs dies out asymptotically withnas measured in a\bar{d}or average Hamming distance sense. This is weaker than the corresponding uotious of Pfaffeihuber, Kadota, and Wyner, who require that probabilities of alln-tuples be close; that is, closeness in a variational or distribution sense. General block channel coding and block joint source and channel coding theorems are proved for stationary\bar{d}-continuous channels, and various definitions of channel capacity are compared.

Sliding-block codes are nonblock coding structures consisting of discrete-time time-invariant possibly nonlinear filters. They are equivalent to time-invariant trellis codes. The coupling of Forney's rigorization of Shannon's random-coding/typical-sequence approach to block coding theorems with the strong Rohlin-Kakutani Theorem of ergodic theory is used to obtain a sliding-block coding theorem for ergodic sources and discrete memoryless noisy channels. Combining this result with a theorem on sliding-block source coding with a fidelity criterion yields a sliding-block information transmission theorem. Thus, the basic existence theorems of information theory hold for stationary nonblock structures, as well as for block codes.