Coding of sources with unknown statistics--I: Probability of encoding error

Abstract

It is well known that it is often possible to obtain considerable data compression by encoding messages in long blocks. Usually the coding scheme for a specific source depends parametrically on the statistics of the source. Universal codes which are independent of the source statistics are introduced. These codes are shown to be asymptotically optimal in the sense that the probability of encoding error can be made vanishingly small for output rates no larger than those of optimal codes that do in fact depend on the statistics of the source. A particular universal coding scheme is introduced for which the encoding complexity increases no faster than the second power of the block lengthnand for which the encoding error vanishes exponentially withn. The discussion is limited to discrete-time finite-alphabet sources.