Posts

Showing posts from May, 2015

Arithmetic Coding

Image
Arithmetic coding is a very interesting form of encoding that can be used in data compression.


In this post, we are going to look at a generalized form of arithmetic coding, as a generalized change of base (or radix).

This type of arithmetic coding works by counting the occurring frequency of each byte in a given message, then it computes the cumulative frequency of each byte from which it creates a polynomial in the base of the length of message, which will result in a large integer as output.

# Encoding First of all, we have to calculate the occurring frequency of each byte. To illustrate this, let's use the word "DECODED".
This word has the following frequency of occurring bytes:
f={C=>1D=>3E=>2O=>1}
From the above frequency, we will compute the cumulative frequency, which is the sum of the above frequencies for each byte, in ASCIIbetical order:

cf={C=>0# ()D=>1# (f['C'] -> 1)E=>4# (f['C']+f['D'] ->…