Title :
Large deviations for the asymptotics of Ziv-Lempel codes for 2-D Gibbs fields
Author :
Amit, Yali ; Miller, Michael I.
Author_Institution :
Dept. of Stat., Chicago Univ., IL, USA
fDate :
7/1/1992 12:00:00 AM
Abstract :
The theory of large deviations for Gibbs random fields is used to show that the asymptotic number of bits per symbol for Ziv-Lempel codes in two dimensions is given by the maximal entropy of all Gibbs fields with the same interaction. The error-probability is shown to converge exponentially fast to zero. In addition, the stronger version of the Shannon-McMillan theorem proved by D.S. Ornstein and B. Weiss (1990) is formulated and proved in terms of the exponential decay of the probability of the nontypical sequences
Keywords :
codes; coding errors; data compression; entropy; 2-D Gibbs fields; Gibbs random fields; Shannon-McMillan theorem; Ziv-Lempel codes; asymptotics; error-probability; large deviations theory; maximal entropy; nontypical sequences; Databases; Decoding; Entropy; Error probability; Image coding; Image converters; Lattices; State-space methods; Statistics; Two dimensional displays;
Journal_Title :
Information Theory, IEEE Transactions on
