Scribd
Upload
2 views18 pages

Lect-5 Floating Point Arithmetic Coding

The document discusses the drawbacks of Huffman coding and introduces arithmetic coding as an alternative method for data compression. It explains the arithmetic coding algorithm, including how to calculate symbol probabilities and ranges, and provides examples of encoding and decoding processes. The document emphasizes that arithmetic coding can represent a sequence of symbols with a single floating point number, improving efficiency in certain cases.

Uploaded by

dodyloly98
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views18 pages

Lect-5 Floating Point Arithmetic Coding

The document discusses the drawbacks of Huffman coding and introduces arithmetic coding as an alternative method for data compression. It explains the arithmetic coding algorithm, including how to calculate symbol probabilities and ranges, and provides examples of encoding and decoding processes. The document emphasizes that arithmetic coding can represent a sequence of symbols with a single floating point number, improving efficiency in certain cases.

Uploaded by

dodyloly98
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Information Theory and Data

Compression / Multimedia - 2024

Lecture 5 [Arithmetic Coding]


Dr. Asmaa Ahmed E. Osman
Faculty of Computers and Artificial Intelligence
Drawback of Huffman Coding
• The main drawback of Huffman scheme is that it has problems when there is a symbol with
very high probability
• Minimum Codeword Length for any Symbol is “ONE” bit, there is no “Half Bit” or
“Quarter Bit”
• Arithmetic coding completely bypasses the idea of replacing an input symbol with a
specific code.
• Instead, it takes a stream of input symbols and replaces it with a single floating point
number
• The longer and more complex the message, the more bits are needed to represents the
output number
Arithmetic Coding Algorithm
• Find the probability for each Symbol
• Calculate Low_Range, High_Range of Symbol
• Divide the initial subinterval based on the distribution
(Low_Range, High_Range of Symbols )
• The first Symbol is coded by extracting the subinterval corresponding to it, and
subdivide again based on the same relative distribution
• Repeat last step for each Symbol until a final interval is determined
• Any value within this subinterval can be used to represent the sequence of
Symbols
Example(1) Arithmetic Coding
Given a long Sequence of characters A, B, and C
the probabilities of Characters are
● P(A)=0.8
● P(B)=0.02
● P(C)= 0.18

Compress the following part of the sequence “


● ACBA” using Arithmetic
Coding
Arithmetic Coding
Rules To solve Low_range(A)=0
High_Range(A)=0.8

Low_range(B)=0.8
High_Range(B)=0.82

Low_range(C)=0.82
High_Range(C)=1.0

Lower (Symbol) = Lower+ Range * Low_Range(Symbol)


Upper (Symbol) = Lower+ Range * High_Range(Symbol)
Method 1: Using Graph

Example(1) Arithmetic Coding


1.0 0.8
Compress Symbol “A”
C C
0+ (0.8-0)*0.82 Low_range(A)=0
High_Range(A)=0.8
0.82 0.656
B B Low_range(B)=0.8
0.8 0.64 High_Range(B)=0.82
0+ (0.8-0)*0.8
Low_range(C)=0.82
High_Range(C)=1.0

A A

Lower (Symbol) = Lower+ Range * Low_Range(Symbol)


Upper (Symbol)= Lower+ Range * High_Range(Symbol)

0.0 0.0
Example(1) Arithmetic Coding
1.0 0.8 0.8

0.656+ (0.8-0.656)*0.82
C C C
Low_range(A)=0
High_Range(A)=0.8
0.82 0.656 0.77408
B B B Low_range(B)=0.8
0.8 0.64 0.7712 High_Range(B)=0.82

Low_range(C)=0.82
Compress Symbol “C” High_Range(C)=1.0

A A A 0.656+ (0.8-0.656)*0.8

0.0 0.0 0.656


Example(1) Arithmetic Coding
1.0 0.8 0.8 0.77408
0.7712+ (0.77408-0.7712)*0.82
C C C C

0.82 0.656 0.77408 0.77356


B B B B
0.8 0.64 0.7712 0.773504

0.7712+ (0.77408-0.7712)*0.80

A A A A

Compress Symbol “B”

0.0 0.0 0.656 0.7712


Example(1) Arithmetic Coding
1.0 0.8 0.8 0.77408

C C C C

0.82 0.656 0.77408 0.77356


B B B B
0.8 0.64 0.7712 0.773504

A A A A Pick any Value


in “A” Range

Compress Symbol “A” 0.773

0.0 0.0 0.656 0.7712


Example(1) Arithmetic Coding
Lower (Symbol) = Lower+ Range * Low_Range(Symbol) Method 2: Using
Upper (Symbol)= Lower+ Range * High_Range(Symbol) Equations

Low_range(A)=0
First Symbol is “A” High_Range(A)=0.8
Lower(A)=0
Low_range(B)=0.8
Upper(A)=0.8 High_Range(B)=0.82
Second Symbol is “C”
Low_range(C)=0.82
Lower(C)=0+ (0.8-0)*0.82=0.656 High_Range(C)=1.0
Upper(C)=0+ (0.8- 0)*1= 0.8
Third Symbol is “B”
Lower (B)= 0.656+ (0.8-0.656)*0.8=0.7712
Upper(B)=0.656+(0.8-0.656)*0.82=0.77408
Fourth Symbol is “A”
Lower (A)= 0.7712+ (0.77408-0.7712)*0=0.7712 Pick any Value
in “A” Range 0.773
Upper(A)=0.7712+(0.77408-0.7712)*0.8=0.773504
Decoding Algorithm
Algorithm Arithmetic Decoding
/*
Input: code: binary code
Low_Range(Symbol):Lower Range of Symbol (in Accumulative Probabilities Scale)
High_Range(Symbol):Upper Range of Symbol (in Accumulative Probabilities Scale)
Output: The decoded message
*/
value = convert2decimal(code);
Do {
find a symbol s so that
Low_Range(s) <= value <= High_Range(s);
output s;
lower = Low_Range(s); Upper = High_Range(s);
range = Upper – lower;
value = (value – lower) / range;
} while s is not the EOF symbol;
Example(1) Arithmetic Coding
Decoding Method 1: Using Graph

1.0
Compression Code = 0.773
C 0.0 <0.773 <0.8
First Symbol is “A” Low_range(A)=0
High_Range(A)=0.8
0.82
B Low_range(B)=0.8
0.8 High_Range(B)=0.82

Low_range(C)=0.82
High_Range(C)=1.0

0.773
A
Lower (Symbol) = Lower+ Range * Lower_Range(Symbol)
Upper (Symbol)= Lower+ Range * Upper_Range(Symbol)

Re-Calculate “Code” value for “New Range”


Code = (Code-Lower)/ (Upper - Lower)
0.0
Example(1) Arithmetic Coding
1.0 0.8
0.773 Compression Code = 0.966
0.82 <0.966 <1.0
C C Second Symbol is “C”

(0.773-0) / (0.8-0)= 0.966 Low_range(A)=0


0.82 0.656
B B High_Range(A)=0.8
0.8 0.64
Low_range(B)=0.8
0+ (0.8-0)*0.82 High_Range(B)=0.82

Low_range(C)=0.82
0+ (0.8-0)*0.8 High_Range(C)=1.0

A A
Lower (Symbol) = Lower+ Range * Lower_Range(Symbol)
Upper (Symbol)= Lower+ Range * Upper_Range(Symbol)

Re-Calculate “Code” value for “New Range”


Code = (Code-Lower)/ (Upper - Lower)
0.0 0.0
Example(1) Arithmetic Coding
1.0 0.8 0.8
Compression Code = 0.8125
0.8 <0.8125 <0.82
C C C Third Symbol is “B”

(0.773-0.656) / (0.8-0.656)= 0.8125


0.82 0.656 0.77408
B B B 0.773
0.8 0.64 0.7712

A A A 0.656+ (0.8-0.656)*0.82

0.656+ (0.8-0.656)*0.8

0.0 0.0 0.656


Example(1) Arithmetic Coding
1.0 0.8 0.8 0.77408

C C C C

Compression Code = 0.625


0.0 <0.625 <0.8
0.82 0.656 0.77408 0.77356
B
Fourth Symbol Bis “A” B B
0.8 0.64 0.7712 0.773504
0.773

(0.773-0.7712) / (0.77408-0.7712)= 0.625

A A A A
0.7712+ (0.77408-0.7712)*0.82

0.7712+ (0.77408-0.7712)*0.80

0.0 0.0 0.656 0.7712


Example(1) Arithmetic Coding
1.0 0.8 0.8 0.77408
0.773
C C C C

0.82 0.656 0.77408 0.77356


B B B 0.773 B
0.8 0.64 0.7712 0.773504

0.773
0.773

A A A A

0.773 is Compressed Code for Symbols “ACBA”


0.0 0.0 0.656 0.7712
Example(1) Arithmetic Coding
(Decompression) Method 2: Using
Equations

Compression Code = 0.773


0.0 <0.773 <0.8 Low_range(A)=0
High_Range(A)=0.8
First Symbol is “A”
Low_range(B)=0.8
Lower(A)=0 High_Range(B)=0.82
Upper(A)=0.8 Low_range(C)=0.82
High_Range(C)=1.0

Code=(0.773-0) / (0.8-0)= 0.966


0.82 <0.966 <1.0
Second Symbol is “C”
Lower(C)=0+ (0.8-0)*0.82=0.656
Upper(C)=0+ (0.8- 0)*1= 0.8
Code= (0.733-0.656)/ (0.8 – 0.656)=0.8125
0.8 <0.8125 <0.82 Low_range(A)=0
High_Range(A)=0.8
Third Symbol is “B”
Lower (B)= 0.656+ (0.8-0.656)*0.8=0.7712 Low_range(B)=0.8
Upper(B)=0.656+(0.8-0.656)*0.82=0.77408 High_Range(B)=0.82

Low_range(C)=0.82
High_Range(C)=1.0
Code=(0.773-0.7712)/(0.77408-0.7712)=0.625
0.0 <0.625 <0.8
Fourth Symbol is “A”

You might also like