# Arithmetic Coding.

The main idea of Arithmetic coding is to represent sequence of symbols by single number of very high precision. Lets try to define the basic algorithm for Binary Arithmetic Coding.

### Decoding of Binary Arithmetic Code.

Decoding of Arithmetic code is generally symmetric to encoding. However there can be some minor differences.
Notice that in decoding process we do not have to keep the underflow counter. During the encoding we did not know what bits must be put out until the next overflow. In the decoding
1. We have this bits in a.
2. We do not have any use for this information.

#### The n-ry Arithmetic Coding.

The described coding is
Binary because the output of the coding is high-precision floating point number in binary representation. The Binary Arithmetic Coding is not the only possible Arithmetic Coding. Lets try to construct n-ry Arithmetic Coder.

The algorithm of constructing n-ry Coder is quit similar to the Binary Coder including care for underflow and overflow.
We decide that we are in the underflow position if:
• αs0 = βs0 - 1.
• βs1 = 0.
• αs1 = n - 1.
Here I signed γsi as a digit i of number γ, starting from the most significant digit γs0.
All shifts, used in the Binary Coder are now shifts of digits instead of bits. When shifting β, it must be filled with digits n-1 instead of 1`s. In the rest of this document I will refer to the Binary Arithmetic Coder.

#### Precision of Arithmetic Coder.

In the definition of Arithmetic Coding algorithm I was using symbol L to sign precision of values α and β. That mean L is amount of bits used to represent α and β. If precision is too low, we can end-up in the middle of encoding with α equal to β and even this interval can fit for more then one symbol. For this reason precision L must be big enough that for any symbol s, fs can be coded by L-3 bits of binary floating point number or simple fs1/2L-3.

Why do I insist on probability to be encoded with L-3 non-zero bits:
• The maximal value of α without overflow is .0(1)L-1 or (2L-1-1/2L)
• The minimal value of β without overflow is .1(0)L-1 or (2L-1/2L)
• With given α, minimal β` that is not causing underflow is .11(0)L-2 or (2L-1+2L-2/2L)
• β`-α = (2L-1+2L-2/2L) - (2L-1-1/2L) = (2L-2-1/2L) = .00(1)L-2
• With given β, maximal α` that is not causing underflow is .00(1)L-2 or (2L-2-1/2L)
• β-α` = (2L-1/2L) - (2L-2-1/2L) = (2*2L-2-2L-2+1/2L) = ((2-1)*2L-2+1/2L) = (2L-2+1/2L) = .01(0)L-31
• β`-α < β-α`, therefore β`-α is the minimal width of ranges [α, β) that can appear during the computation of Binary Arithmetic Coding and not in state of overflow or underflow.
• To distinguish symbol s from the next symbol s+1, subrange [αs, βs) must be big enough. Particularly, βss1/2L.
• βss = (β`-α)*fs
• (β`-α)*fs1/2L
• (2L-2-1/2L)*fs1/2L
• fs ≥ (1/2L-2-1)
• (1/2L-3) > (1/2L-2-1), therefore if fs ≥ (1/2L-3) then fs > (1/2L-2-1)
• 1/2L-3 = .(0)L-41
This mean fs must be big enough to be represented with not more then L-3 non-zero bits.

### Gather Statistics.

The next open question is how to gather and pass statistics data.
Both of this schemes will benefit from representing symbol probabilities by symbol counts and not real floating point probabilities. In this case updating symbol probability is single operation, where computing real probabilities require recomputation for each symbol.

### Advanced possibilities for Arithmetic Coding.

• MTF - Move To Front scheme is applicable to Arithmetic Coding.
• PPM - Prediction by Partial Match is applicable too.
• BWT - Burrows-Wheeler Transform can improve compression ratio.

References:

[1] Fundamental Compression Algorithms.
Compression Team (compresswww@rasip.fer.hr)
http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/

[2] Data Compression.
Debra A. Lelewer and Daniel S. Hirschberg
http://www.ics.uci.edu/~dan/pubs/DataCompression.html

[3] Introduction to Information Theory and Data Compression.
Darrel Hankerson, Greg A. Harris and Peter D. Johnson,Jr.
http://www.dms.auburn.edu/compression/

[4] Basic Arithmetic Coding.
Arturo San Emeterio Campos
http://www.arturocampos.com/ac_arithmetic.html

[5] Compression Basics.
Pasi Albert Ojala
http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html