Tree encoding of memoryless time-discrete sources with a fidelity criterion

Abstract

In this paper we show that for memoryless time-discrete sources with a bounded fidelity criterion, the limiting average distortion achievable by tree codes of rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</tex> , the solution of the equation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R = R(D)</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R( )</tex> denotes the usual rate distortion function. Thus the performance of tree codes is as good as that of block codes. Some theoretical and experimental results are also discussed indicating that tree codes and corresponding encoding algorithms exist having for given values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</tex> an implementation complexity that is far smaller than the one obtainable from block codes.