Encoding of intervals with conditional coding
Urs Graf · 1997
Summary form only given. With conditional coding a new technique is presented that encodes equally likely symbols of an input alphabet A (|A|=m) efficiently. The code consists of bitstrings with size n=[log/sub 2/(m)] and (n+1) and is a prefix code. The encoding needs only one comparison, one shift, and one addition per encoded symbol. Compared to the theoretical limit the method loses only at most 0.086071... bits per encoding and 0.057304... bits in average. Opposed to radix conversion (which achieves the theoretical limit) the algorithm works without multiplication and division and does not need a single-bit writing loop or bitstring arithmetic in the encoding step. Therefore it works a lot faster than radix conversion and can easily be implemented in hardware. The decoding step has the same properties. Encoding and decoding can be exchanged for better adaption to the code alphabet size.