Variable-Rate,Weakly-and Strongly-Universal Source Coding Subject to a Fidelity Constraint.

摘要

The goal of universal source coding is to find codes which are efficient for sources with unknown or incompletely specified probability distributions;this is equivalent to finding codes which are efficient for a collection of sources. Previous work in universal variable-rate source coding subject to a fidelity constraint has assumed a prior probability measure on a collection of stationary ergodic sources. It is then shown that there is a single code which gives an average distortion D at an optimum rate, R sub theta (D),for most sources theta in the collection. This code is necessarily variable-rate since R sub theta (D) is not constant over the collection of sources. In this dissertation,new results are presented on coding a collection of stationary ergodic sources when no prior probability measure is assumed. In particular,it is shown that there exist variable-rate universal codes whose rate-distortion performance converges to the optimum attainable performance for each source in the collection. Two types of universal codes are considered in which the above convergence is pointwise (weakly-universal) or uniform (strongly-universal) over the collection of sources. It is assumed that there is a letter in the reproducing alphabet giving finite average distortion when used with each source in the collection and that sup R sub theta (D) over the collection of sources of finite. Strongly-universal codes are shown to exist for collections of finite alphabet memoryless sources and certain types of Markov sources.