Fast Encoding of Low-Entropy Sources

We consider the problem of coding for low-entropy information sources. Since the run-length code was proposed by Shannon about fifty years ago, it has been known that such sources can be coded by much simpler methods than arbitrary sources can. However, the known coding methods for low-entropy sources are unable to achieve a preassigned redundancy. In the paper, we suggest a new method of encoding low-entropy sources, for the cases of known and unknown statistics, which enables us to reach any predefined redundancy. The encoding/decoding rate in this method, which is measured by the number of binary operations on one-bit words, is considerably higher than in the general methods.