Tree encoding for symmetric sources with a distortion measure

A simple algorithm is developed for mapping the outputs of a source into the set of code sequences generated by a tree code. The algorithm is analyzed for a special case in which the source produces discrete independent equiprobable letters, and the distortion measure satisfies a symmetry condition. Letting be the code rate and be the minimum average distortion for that rate as given by Shannon\´s rate-distortion theorem, we show that the algorithm is capable of achieving average distortion as close to as desired. Furthermore an upper bound is developed on the average amount of computation for the algorithm. Asymptotically as the average distortion approaches the theoretical limit , the bound on average computation has the form for some constant .