Coding Low-Entropy Markov Sources with Unknown Statistics

The problem is considered of coding information sources with small entropy. This problem is well known in information theory, since, for these sources, there exist simpler coding methods than for arbitrary sources. However, the available methods of coding low-entropy sources do not allow us to construct codes with preassigned redundancy. In [1, 2], a new method of coding low-entropy sources is proposed which allows us to construct codes with any preassigned redundancy. On the basis of the code construction of [1, 2], this article suggests a universal code for a low-entropy Markov source generating letters of the binary alphabet $A=\{0,1\}$ with unknown conditional probabilities.