Data Compression Techniques: Arithmetic Coding, Encoding, and Decoding

This document presents a comprehensive solution to a data compression assignment, specifically addressing arithmetic coding techniques. The solution encompasses detailed explanations and step-by-step calculations for both encoding and decoding processes. The assignment covers scenarios with different symbol probabilities and demonstrates the application of arithmetic coding to compress data. The solution also provides examples of how to encode and decode sequences of symbols using the arithmetic coding method. The document also includes references to relevant literature on data compression. The solution is structured with clear sections for each question, making it easy to follow and understand the concepts. This assignment is a valuable resource for students studying data compression and related fields, providing practical examples and insights into the application of arithmetic coding.

Data Compression
Student Name:
Register Number:
Submission Date:

Table of Contents
Question 1........................................................................................................................................................................ 1
a).................................................................................................................................................................................. 1
b).................................................................................................................................................................................. 3
Question 2........................................................................................................................................................................ 4
a).................................................................................................................................................................................. 4
b).................................................................................................................................................................................. 6
Reference......................................................................................................................................................................... 8

Question 1
a)
S={s1,s2,s3,s4} and diagram frequencies are given in,
[ Fij]=
[.08 .18 .12 .02
.08 .01 .04 .12
.14 .02 .04 0
.10 .04 0 .01 ]
The arithmetic coding
S1=0.08 s2=0.01 s3=0.04 s4=0.01
Encode s2 s2 s4 s1 (IsmailkhaPathan and Sinhal, 2013).
Next letter rescale
underflow
L H New code Underflow count
0 16 0
S2
x2x-16
12
8
13
0.26
0
1
1

S2
x2x
x2x-16
0.06
0.02
0.0204
0.04
0.020
0.0206
0
1
1
0
S4
x2x-16
x2x-8
0.0202
0.0204
0.00208
0.0204
0.0206
0.0210
0
0
1
0
S1
x2x-16
x2x
0.0206
0.0222
0.0238
0.0222
0.0238
0.0206
1
1
1
0
The encode s4 s1 s2 s3
Next letter rescale
underflow
L H New code Underflow count
0 16 0
S4
x2x-16
12
8
13
0.26
0
1
2

S1
x2x
x2x-16
0.0206
0.000206
0.000204
0.0204
0.00020
0.0204
0
1
1
0
S2
x2x-16
x2x-8
0.0003
0.0003
0.0004
0.0208
0.0004
0.0005
0
0
1
0
S3
x2x-16
x2x
0.00020
0.0097
0.00892
0.0208
0.00892
0.00894
1
1
1
0
The first order arithmetic coding with the source word length is, 1110111100.
b)
A b c d
01000001
01000010
01000011
01000100
v L H L1 , H1 L2 , H2 L3 , H3 LEOF , H EOF Decode
(01000)2=12 0 16 [0,12] [12,8] [22,23] [23,17] S1
x2x-16
( 00101 )2=16
01010
01000
5
5
16
23
16
8
[8,15] [16,13] [23,32] [23,14] S3
x2x
x2x-16
( 01001 )2=27
11011
01111
8
17
2
16
24
16
[8,12] [17,8] [24,4] [29,2] S2
x2x-16
( 01101 ) 2=14
10101
8
17
16
24
[12,14] [24,16] [24,17] [29,22] S3
x2x-16
3

00111 2 8 x2x
( 10101 )2=16
4 16 [14,15] [15,16] [23,15] [29,23] EOF
The encode method is,
0011000000110001
Question 2
a)
s={s1,s2,s3,EOF}
decoding with m=16(IsmailkhaPathan and Sinhal, 2013).
[ Fij]=
[.16 .17 .05 .01
.20 .08 .05 .01
.02 .08 .13 .01
.01 .01 .01 .0 ]
Encode s2 s1 s3 s2 EOF
We can assume the value as s2 s2 s3 s2 EOF
Let us consider the first order Encode of the arithmetic value is s1=0.16 , s2=0.08, s3=0.13
EOF=0
4

Let us assume the encode arithematic code as, s2 s1 s3 s2 EOF.
P=0.08-0.04=0.04
Encode=LL+d(p)
S2=0.04+0.08(0.04)=0.0432
0.0432+0.08(0.04)=0.0464
0.0464+0.08(0.04)=0.0496
0.0496+0.08(0.04)=0.0528
S1=0.01+(0.16)(0.01)=0.0116
0.0116+(0.16)(0.01)=0.0132
0.0132+(0.16)(0.01)=0.0148
0.0148+(0.16)(0.01)=0.0164
S3=0.0016+0.13(0.0016)=0.0018
0.0018+0.13(0.0016)=0.002016
0.002016+0.13(0.0016)=0.002224
0.002224+0.13(0.0016)=0.0024
S2=0.0124+(0.08)(0.01)=0.0204
5

0.0204+(0.08)(0.01)=0.0284
0.0284+(0.08)(0.01)=0.0292
0.0292+(0.08)(0.01)=0.03
EOF=0.0024+(0)(0.018)=0.0024
Next letter rescale
underflow
L H New code Underflow count
0 16 0
S2
x2x-16
12
8
13
0.26
0
1
S1
x2x
x2x-16
0.08
0.04
0.0528
0.0496
01
1
1
0
S3
x2x-16
x2x-8
0.0148
0.0018
0.0022
0.0132
0.0020
0.0024
0
0
0
0
S2
x2x-16
x2x
0.0148
0.0024
0.0028
0.0024
0.0092
0.03
1
1
0
0
EOF 0.0024 0.0024 0 0
The Encode is 0100011100.
b)
Decode 1011110101
m=16 decode
v L H L1 , H1 L2 , H2 L3 , H3 LEOF , H EOF Decode
(10111)2=23 0 16 [0,12] [12,22] [22,28] [23,16] S1
x2x-16
( 01010 )2=10 5 23 [8,16] [16,23] [23,16] [23,28] S3
6

01010
01000
5
16
16
8
x2x
x2x-16
( 11011 )2=27
11011
01111
8
17
2
16
24
16
[8,17] [17,24] [24,29] [29,32] S2
x2x-16
( 10101 )2=21
10101
00111
8
17
2
16
24
8
[12,22] [24,29] [24,29] [29,32] S3
x2x-16
x2x
( 10101 )2=7
4 16 [14,15] [15,23] [23,29] [29,16] EOF
The decode source message is S1S3S2S3EOF
Reference
7

IsmailkhaPathan, A. and Sinhal, A. (2013). Encode Decode Linux based Partitions to Hide and
Explore File System. International Journal of Computer Applications, 75(12), pp.40-45.
Nelson, M. (2016). The data compression book. Redwood City, CA: M & T.
8