Nonblock Coding of Binary Sources by Probabilistic Enumeration
| Autor: | Jukka Teuhola |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
ta113
Theoretical computer science Range encoding Variable-length code Library and Information Sciences Huffman coding Computer Science Applications Arithmetic coding symbols.namesake Shannon–Fano coding symbols Entropy encoding Arithmetic Context-adaptive binary arithmetic coding Information Systems Mathematics Context-adaptive variable-length coding |
| Zdroj: | IEEE Transactions on Information Theory. 57:6170-6179 |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2011.2161910 |
| Popis: | 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 p3 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|