Variable-Rate, Weakly- and Strongly-Universal Source Coding Subject to a Fidelity Constraint.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1977
- Accession Number
- ADA041686
Entities
People
- Kenneth Marsh Mackenthun Jr
Organizations
- University of Illinois Urbana–Champaign