Efficient algorithm of low-entropy Markov source coding

The problem of coding low-entropy Markov sources is considered. Since the run-length code was offered about fifty years ago by Shannon (1948), it is known that for such sources there exist coding methods much simpler than for sources of a general type. However the known coding methods of low-entropy sources does not give possibility to reach the given redundancy. On the basis of code construction by Ryabko and Sharova (2000), a new method of coding low-entropy Markov sources is offered. It permits to reach a given redundancy r with almost the same encoder and decoder memory size as for general methods while encoding and decoding are much faster.