Nonblock Coding of Binary Sources by Probabilistic Enumeration

A simple and efficient nonblock coding scheme for binary sources is suggested. It uses a probability model to map any source string to a unique integer, and thereby defines an enumeration of all possible strings. Contrary to normal enumerative coding, the new method is noncombinatorial and operates sequentially, incrementing the code value symbol by symbol, by simple arithmetic. It is akin to arithmetic coding but does not use intervals. For memoryless sources, the redundancy per symbol is shown to be asymptotically less than p³ bits, where p is the smaller of symbol probabilities. Especially, for integer-valued 1/p , the code is asymptotically optimal. These results are confirmed by both analysis and experiments with arbitrary-precision arithmetic. In a practical implementation, the source is partitioned into substrings enabling restricted-precision arithmetic. Thanks to subtle implicit coding, the additional redundancy is marginal. The source model can be also context-based, and even adaptivity can be incorporated. A peculiarity of the method is that decoding is done backwards (LIFO). Hence, for higher-order models, the string suffix, not prefix, is used as the context domain. The speed of the practical version is close to that of binary arithmetic coders.