Arithmetic-Coding-Students Report-Group B

Arithmetic coding
Arithmetic Coding: is amethod widely used,the only problem is its speed
but compression tends to be better than Huffman .
The principle of arithmetic coding was first proposed by Peter Elias in
the early 1960.
Algorithem for arithmetic coding:
Low=0
High=1
For all symbol of the input stream
Range= High-low
High=low+range*high_upper
Low=low+range*low_upper
End
Note:* the notation[a,b)means the range of real numbers from a to b ,
including a but not including b. the range is closed at a and open at b.
*the output of this method is real number.
Arithmetic coding
Ex:Given the alphabet {a,e,i,o,u,!}with the probabies
{0.2,0.3,0.1,0.2,0.1,0.1},respectively .compress the string "eaii!" by
using Arithmetic coding
Solution
Symbol pro range
a 0.2 [0,0.2)
e 0.3 [0.2,0.5)
i 0.1 [0.5,0.6)
o 0.2 [0.6,0.8)
u 0.1 [0.8,0.9)
! 0.1 [0.9,1)
e
Range= High-low ?¨1-0=1
High=low+range*high_upper ?¨0+1*0.5=0.5
Low=low+range*low_upper?¨0+1*0.2=0.2
Arithmetic coding
e?¨ [0.2,0.5)
a
Range= High-low ?¨0.5-0.2=0.3
High=low+range*high_upper ?¨0.2+(0.3*0.2)=0.26
Low=low+range*low_upper?¨0.2+0.3*0=0.2
[0.2,0.26)
i
Range= High-low ?¨0.26-0.2=0.06
High=low+range*high_upper ?¨0.2+(0.06*0.6)=0.236
Low=low+range*low_upper?¨0.2+(0.06*0.5)=0.23
[0.23,0.236)
i
Range= High-low ?¨0.236-0.23=0.006
High=low+range*high_upper ?¨0.23+(0.006*0.6)=0.2336
Low=low+range*low_upper?¨0.23+(0.006*0.5)=0.233
[0.233,0.2336)
!
Arithmetic coding
!
Range= High-low ?¨0.2336-0.233=0.0006
High=low+range*high_upper ?¨0.233+(0.0006*1.0)=0.2336
Low=low+range*low_upper?¨0.233+(0.0006*0.2)=0.23354
[0.23354,0.2336)
Q/Alphabet {a,b,c,d,e},compression "ace",the probabilities of each
symbol {0.30,0.15,0.25,0.10,0.20} ,respectively.