Computer Science – Information Theory
Scientific paper
2005-05-04
Computer Science
Information Theory
21 pages
Scientific paper
We consider a variation of the Wyner-Ziv problem pertaining to lossy compression of individual sequences using finite-state encoders and decoders. There are two main results in this paper. The first characterizes the relationship between the performance of the best $M$-state encoder-decoder pair to that of the best block code of size $\ell$ for every input sequence, and shows that the loss of the latter relative to the former (in terms of both rate and distortion) never exceeds the order of $(\log M)/\ell$, independently of the input sequence. Thus, in the limit of large $M$, the best rate-distortion performance of every infinite source sequence can be approached universally by a sequence of block codes (which are also implementable by finite-state machines). While this result assumes an asymptotic regime where the number of states is fixed, and only the length $n$ of the input sequence grows without bound, we then consider the case where the number of states $M=M_n$ is allowed to grow concurrently with $n$. Our second result is then about the critical growth rate of $M_n$ such that the rate-distortion performance of $M_n$-state encoder-decoder pairs can still be matched by a universal code. We show that this critical growth rate of $M_n$ is linear in $n$.
Merhav Neri
Ziv Jacob
No associations
LandOfFree
On the Wyner-Ziv problem for individual sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Wyner-Ziv problem for individual sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Wyner-Ziv problem for individual sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-591976