For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Distortion-Complexity and Rate-Distortion Function
Jun MURAMATSU Fumio KANAYA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/08/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
complexity, distortion-complexity, rate-distortion function, universal code,
Full Text: PDF>>
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.