Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Nonblock Coding of Binary Sour...

Nonblock Coding of Binary Sources by Probabilistic Enumeration

Jukka Teuhola, Nonblock Coding of Binary Sources by Probabilistic Enumeration. IEEE Transactions on Information Theory 57(9), 6170–6179, 2011.

http://dx.doi.org/10.1109/TIT.2011.2161910

Abstract:

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 non-combinatorial 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^3 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.

BibTeX entry:

@ARTICLE{jTeuhola_Jukka11a,
  title = {Nonblock Coding of Binary Sources by Probabilistic Enumeration},
  author = {Teuhola, Jukka},
  journal = {IEEE Transactions on Information Theory},
  volume = {57},
  number = {9},
  publisher = {IEEE Information Theory Society},
  pages = {6170–6179},
  year = {2011},
  keywords = {arithmetic coding, binary source, enumerative coding, nonblock coding, source coding},
}

Belongs to TUCS Research Unit(s): Algorithmics and Computational Intelligence Group (ACI)

Publication Forum rating of this publication: level 3

Edit publication