Universal codeword sets and representations of the integers

Abstract

Countable prefix codeword sets are constructed with the universal property that assigning messages in order of decreasing probability to codewords in order of increasing length gives an average code-word length, for any message set with positive entropy, less than a constant times the optimal average codeword length for that source. Some of the sets also have the asymptotically optimal property that the ratio of average codeword length to entropy approaches one uniformly as entropy increases. An application is the construction of a uniformly universal sequence of codes for countable memoryless sources, in which thenth code has a ratio of average codeword length to source rate bounded by a function ofnfor all sources with positive rate; the bound is less than two forn = 0and approaches one asnincreases.