Distortion-Complexity and Rate-Distortion Function

Jun MURAMATSU  Fumio KANAYA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.8   pp.1224-1229
Publication Date: 1994/08/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: 
Keyword: 
complexity,  distortion-complexity,  rate-distortion function,  universal code,  

Full Text: PDF>>
Buy this Article




Summary: 
We define the complexity and the distortion-complexity of an individual finite length string from a finite set. Assuming that the string is produced by a stationary ergodic source, we prove that the distortion-complexity per source letter and its expectation approximate arbitrarily close the rate-distortion function of this source as the length of the string grows. Furthermore, we apply this property to construct a universal data compression scheme with distortion.