arithmetic encoding

Arithmetic coding is a technique for achieving near-optimal entropy encoding.

An arithmetic encoder takes a string of symbols as input and produces a rational number in the interval $[0,1)$ as output. As each symbol is processed, the encoder will restrict the output to a smaller interval.

Let $N$ be the number of distinct symbols in the input; let $x_{1},x_{2}\\dots x_{N}$ represent the symbols, and let $P_{1},P_{2}\\dots P_{N}$ represent the probability of each symbol appearing. At each step in the process, the output is restricted to the current interval $[y,y+R)$ . Partition this interval into $N$ disjoint subintervals:

I_{1}=[y,y+P_{1}R)

I_{2}=[y+P_{1}R,y+P_{1}R+P_{2}R)

\\vdots

I_{N}=\\left[y+\\sum_{i=1}^{N-1}P_{i}R,y+R\\right)

Therefore the of $I_{i}$ is $P_{i}R$ . If the next symbol is $x_{i}$ , then restrict the output to the new interval $I_{i}$ .

Note that at each stage, all the possible intervals are pairwise disjoint. Therefore a specific sequence of symbols produces exactly one unique output range, and the process can be reversed.

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 $M$ symbols: then $x_{i}$ appears exactly $P_{i}M$ times in the input. Therefore, the size of the final interval will be

R_{f}=\\prod_{i=1}^{N}P_{i}^{P_{i}M}

The number of bits necessary to write a binary fraction in this range is

$\\displaystyle-\\log_{2}R_{f}$	$\\displaystyle=$	$\\displaystyle-\\log_{2}\\prod_{i=1}^{N}P_{i}^{P_{i}M}$
	$\\displaystyle=$	$\\displaystyle\\sum_{i=1}^{N}-\\log_{2}P_{i}^{P_{i}M}$
	$\\displaystyle=$	$\\displaystyle\\sum_{i=1}^{N}-P_{i}M\\log_{2}P_{i}$

By Shannon’s theorem, this is the total entropy of the original message. Therefore arithmetic encoding is near-optimal entropy encoding.