Arithmetic Coding Number of numbers in the unit interval is infinite.ppt

arthimatic coing can be used to code images.Generating code words for groups or sequences of symbols
A unique identifier or tag is generated for the sequence to be encoded
This tag is a fraction and it is binary encoded
The set of tags for representing symbols are the numbers in the unit interval [0,1)
Number of numbers in the unit interval is infinite.
Unique tag can be generated for each sequence.

1. Arithmetic Coding

2. Arithmetic Coding
Generating code words for groups or sequences of
symbols
A unique identifier or tag is generated for the
sequence to be encoded
This tag is a fraction and it is binary encoded
The set of tags for representing symbols are the
numbers in the unit interval [0,1)
Number of numbers in the unit interval is infinite.
Unique tag can be generated for each sequence.

3. Arithmetic Coding

Cumulative distribution function of the random
variables associated with the source is used for
mapping the sequence to a tag.
Generating the tag:

Example:

Consider a three-letter alphabet A = {a1, a2, a3} with

P(a1) = 0.7,P(a2) = 0.1, and P(a3) = 0.2.

Fx(1) = 0.7, Fx (2) = 0.8, and Fx(3) = 1.

This partitions the unit interval as shown in Figure.

4. Arithmetic Coding
0.0
0.7
0.8
1.0
a
1
a
2
a
3
0.0
0.49
0.56
0.70
a
1
a
2
a
3
a
1
a
2
a
3
a
1
0.56
0.546
0.49
0.5558
a
2
a
3
0.546
0.56
0.5572
0.539

5. Arithmetic Coding

The interval in which the tag for a particular sequence
resides is disjoint from all intervals in which the tag
for any other sequence may reside.

Any number in this interval can be used as the tag(say,
mid point/lower value).

the tag forms a unique representation for the sequence.
This means that the binary representation of the tag
forms a unique binary code for the sequence.

6. Arithmetic Coding
We can show that for any sequence
x = (x
1, x
2,….x
n)
The only information required by the tag generation
procedure is the cdf of the source, which can be
obtained directly from the probability model.
2
)(
)()(
)1()(
)()(
)1()1()1()(
)1()1()1()(
nn
X
nX
nnnn
nX
nnnn
lu
xT
xFlulu
xFlull







7. Example

Given a DMS A = {a1, a2, a3}

P(a1) = 0.8, P(a2) =0.02 P(a3)
=0.18

Obtain tag for a1 a3 a2 a1.

Ans. Tag = 0.772352

8. Deciphering (Decoding) the tag

Given Tag Value, Probability model & length of the
block

Tag value = 0.772352

The interval containing this tag value is the subset of
every interval obtained in the encoding process.
While decoding, decode the elements in such a way
that upper and lower limits always contain this tag
value.

9. Decoding

Start with l(0) =0, u(0) =1

Let the first element is decoded as x
1
. Then,

l(1)= 0 +(1-0)Fx(x
1-1)=Fx(x
1-1)

u(1) =0 +(1-0)Fx(x
1)=Fx(x
1)

Find the value of x
1 for which this interval contains the
tag value.

If we pick x
1
=1, the interval is [0,0.8). If we pick x
1
=2,
the interval is [0.8,0.82), and if we pick x
1=3, the
interval is [0.82,1.0). As 0.77232 lies in the interval
[0.0,0.8), we choose x
1
=1

10. Decoding

Let the second element is x
2.

l(2)= 0 +(0.8-0)Fx(x
2-1)=0.8 Fx(x
2-1)

u(2) =0 +(0.8-0)Fx(x
2)=0.8 Fx(x
2)

If we pick x
2=1, the updated interval is [0, 0.64,), which does
not contain the tag.

If we pick x
2
=2, the updated interval is [0.64, 0.656), which
also does not contain the tag.

If we pick x
2=3, the updated interval is [0.656, 0.8) which
contains the tag.
Therefore second element is 3.

11. Decoding

Let the third element is x
3.

l (3)= 0.656 +(0.8-0.656) Fx(x
3 -1) = 0.656 + 0.144 Fx(x
3 -1)

u (3) = 0.656 +(0.8-0.656) Fx(x
3) = 0.656 + 0.144 Fx(x
3)
Subtract the value of l(2) from both the limits and the tag.

Find the value of x
3
for which the interval [0.144 x Fx (x
3
-1),
0.144 x Fx (x
3
)) contains 0.772352 - 0.656 (Residual tag)
Divide the residual tag value by 0.144 to get 0.808.

Find the value of x
3 for which 0.808 falls in the interval [Fx(x
3-
1), Fx(x
3) ). It is possible if x
3 =2.
Then update the intervals.

12. Decoding

Let the fourth element is x
4
.

l (4)= 0.7712 +(0.77408-0.7712) Fx(x
4
-1) =
0.7712 + 0.00288 Fx(x
4
-1)

u (4) = 0.7712 +(0.77408-0.7712) Fx(x
4) =
0.7712 + 0.00288 Fx(x
4
)

Subtract the value of l(3) from both the limits and the tag. (0.772352 - 0.7712
=0.001152)

Find the value of x
4
for which the interval [0. 00288 x Fx (x
4
-1), 0.00288 x
Fx (x
4)) contains 0.001152 (Residual tag)

Divide the residual tag value by 0. 00288 to get 0.4.

Find the value of x
4 for which 0.4 falls in the interval [Fx(x
4-1), Fx(x
4) ). It is
possible if x
4 =1.

Data is decoded as 1321 i.e., a1 a3 a2 a1

13. Generating a binary code

To make the code efficient, the binary representation has
to be truncated. Tag is a number in the interval [0,1).

A binary code for the tag can be obtained by taking the
binary representation of this number and truncating it to
l(x) bits.
 1))(/1log()(  xpxl

14. Generating a binary code

Example
Symbol F
x
Tag In binary Code
10.5 .25 .010 2 01
20.75.625.101 3 101
30.875.8125.1101 4 1101
41.0 .9375.1111 4 1111
A ={a1, a2, a3,a4}
P(a1) = 1/2, P(a2) =1/4, P(a3) =1/8 , P(a4)=1/8
1
)(
1
log 






xp

15. Efficiency of Arithmetic Coding

Average codeword length (Rate)
m
2
)X(Hl
m
1
)X(H
A 