Showing posts from May, 2015

Arithmetic Coding

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 => 1 D => 3 E => 2 O => 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 #