Universal noiseless coding

TLDR

Universal coding refers to asymptotically optimal block‑to‑block memoryless source coding for unknown‑parameter sources, with particular emphasis on stationary and ergodic sources that are not jointly stationary. The paper investigates variable‑length noiseless coding for such sources, evaluating performance via coding redundancy relative to the per‑letter conditional source entropy. The authors illustrate the concepts with several examples and briefly discuss fixed‑rate universal coding measured by probability of error. Weighted universal coding is achievable only when the average mutual information between parameter and message is zero; maximin coding requires zero channel capacity; minimax coding requires a parameter‑independent pmf with zero relative entropy; for stationary ergodic sources weighted codes always exist with finite alphabet or entropy, while minimax codes arise under an entropy‑stability constraint.

Abstract

Universal coding is any asymptotically optimum method of block-to-block memoryless source coding for sources with unknown parameters. This paper considers noiseless coding for such sources, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter. It is found that universal (i.e., zero redundancy) coding in a weighted sense is possible if and only if the per-letter average mutual information between the parameter space and the message space is zero. Universal coding is possible in a maximin sense if and only if the channel capacity between the two spaces is zero. Universal coding is possible in a minimax sense if and only if a probability mass function exists, independent of the unknown parameter, for which the relative entropy of the known conditional-probability mass-function is zero. Several examples are given to illustrate the ideas. Particular attention is given to sources that are stationary and ergodic for any fixed parameter although the whole ensemble is not. For such sources, weighted universal codes always exist if the alphabet is finite, or more generally if the entropy is finite. Minimax universal codes result if an additional entropy stability constraint is applied. A discussion of fixed-rate universal coding is also given briefly with performance measured by a probability of error.