Tuesday, February 23, 2010

ARITHMETIC CODING

ARITHMETIC CODING:

In arithmetic coding, Input data is represented by an interval of real numbers between 0 and 1. As the input data is large, the interval required to represent is smaller, i.e. the number of bits required to specify the interval increases. Successive symbols of the input data reduce the size of the interval according with the symbol probabilities generated by the arithmetic encoding. The repeated symbols reduce the range by less than the unlikely symbols and hence add fewer bits to the input data. The range of input data is the entire interval zero to one (0, l), which denotes the half-open interval 0.5 <> 1

ARITHMETIC CODING Example:

The Fixed model (alphabet is (a, e, i, o, u,!)) is used with the following probabilities shown in the Table.



Let’s take the input data become eaii!. Initially, both encoder and decoder know that the range is (0, 1).

From first symbol, e, the encoder narrows it to [0.2, 04],
The second symbol, a, will narrow this new range to the first one-fifth of it. Like the following









Representation of the Arithmetic Coding Process:



Suppose the input data is like a, aa, aaa, aaaa, the encoded number will be 0.0. To solve this ambiguity, In data model each data ends with a special EOF symbol known to both encoder and decoder. In the above table ! would be the EOF.

The Entropy of eaii! Is
-log0.3 – log0.2 – log0.1 – log0.1 – log0.1
= - log0.00006 ≈ 4.22

















Arithmetic Encoding Algorithm:


/* Call Encode_Data repeatedly for each symbol in the input data. */
/* Ensure that a distinguished "terminator" symbol is encoded last, then */
/* transmit any value in the range [low, high]. */

Encode_Data(symbol, cum-freq)
range = high - low
high = low + range*cum-freq [symbol-1]
low = low + range*cum-freq [symbol]
/* ARITHMETIC DECODING ALGORITHM. */
/* "Value" is the number that has been received. */
/* Continue calling Decode_Data until the terminator symbol is returned. */

Decode_Data(cum-freq)
find symbol such that
cum-freq[symbol] <= (value-low)/(high-low) <>
range = high - low
high = low + range*cum-freq[symbol-1]
low = low + range*cum-freq[symbol]
return symbol




0 comments:

Twitter Delicious Facebook Digg Stumbleupon Favorites More