An arithmetic encoder takes a string of symbols as input and produces a rational number in the interval as output. As each symbol is processed, the encoder will restrict the output to a smaller interval.
Let be the number of distinct symbols in the input; let represent the symbols, and let represent the probability of each symbol appearing. At each step in the process, the output is restricted to the current interval . Partition this interval into disjoint subintervals:
Therefore the of is . If the next symbol is , then restrict the output to the new interval .
Since arithmetic encoders are typically implemented on binary computers, the actual output of the encoder is generally the shortest sequence of bits representing the fractional part of a rational number in the final interval.
Suppose our entire input string contains symbols: then appears exactly times in the input. Therefore, the size of the final interval will be
The number of bits necessary to write a binary fraction in this range is
|Date of creation||2013-03-22 12:32:20|
|Last modified on||2013-03-22 12:32:20|
|Last modified by||vampyr (22)|