Title :
Causal coding of individual sequences and the Lempel-Ziv differential entropy
Author :
Linder, Tamás ; Zamir, Ram
Author_Institution :
Dept. of Math. & Stat., Queen´´s Univ., Kingston, Ont., Canada
fDate :
27 June-2 July 2004
Abstract :
In causal source coding, the reconstruction is restricted to be a function of the present and past source samples, while the variable-length code stream may be noncausal. Neuhoff and Gilbert [1982] showed that for memoryless sources, optimum performance among all causal lossy source codes is achieved by time-sharing at most two memoryless codes (scalar quantizers) followed by entropy coding. We extend this result to causal coding of individual sequences in the limit of small distortion. The optimum performance of finite-memory variable-rate causal codes in this setting is characterized by a deterministic analogue of differential entropy, which we call "Lempel-Ziv differential entropy." As a by-product, we also provide an individual-sequence version of the Shannon lower bound to the rate-distortion function.
Keywords :
entropy codes; memoryless systems; rate distortion theory; sequences; source coding; variable length codes; variable rate codes; Lempel-Ziv differential entropy; Shannon lower bound; finite-memory variable-rate causal code; individual-sequence version; memoryless source; optimum performance; rate-distortion function; source coding; variable-length code stream; Councils; Entropy coding; Mathematics; Performance loss; Rate-distortion; Source coding; Statistics; Time sharing computer systems;
Conference_Titel :
Information Theory, 2004. ISIT 2004. Proceedings. International Symposium on
Print_ISBN :
0-7803-8280-3
DOI :
10.1109/ISIT.2004.1365597