Conditional Lempel-Ziv Complexity and Its Application to Source Coding Theorem with Side Information

Tomohiko UYEMATSU
Shigeaki KUZUOKA

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A    No.10    pp.2615-2617
Publication Date: 2003/10/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Information Theory and Its Applications)
Category: Source Coding/Image Processing
Keyword: 
conditional LZ complexity,  conditional Ziv's inequality,  universal source coding,  

Full Text: PDF(134.3KB)>>
Buy this Article



Summary: 
This paper proposes the conditional LZ complexity and analyzes its property. Especially, we show an inequality corresponding to Ziv's inequality concerning a distinct parsing of a pair of sequences. Further, as a byproduct of the result, we show a simple proof of the asymptotical optimality of Ziv's universal source coding algorithm with side information.