Arithmetic Coding
Neena Raj N. R.
Department of Computer Science and Engineering
Mar Baselios College of Engineering and Technology, Nalanchira
January 2024
Syllabus
Module 2
Run length encoding, RLE Text compression, Statistical methods-Prefix Codes,
Binary Huffman coding, Illustration of Binary Huffman coding, Non-binary
Huffman Algorithms, Arithmetic Coding algorithm, Illustration of Arithmetic
Coding algorithm
Neena Raj N. R. CS1U43D DCT January 2024 2 / 13
Course Outcomes
Course Outcomes
CO1 Describe the fundamental principles of data Understand
compression.
CO2 Apply
Make use of statistical and dictionary based
compression techniques for various applications
CO3 Illustrate various image compression standards. Apply
CO4 Summarize video compression mechanisms to re- Understand
duce the redundancy in video.
CO5 Use the fundamental properties of digital audio Understand
to compress audio data.
Neena Raj N. R. CS1U43D DCT January 2024 3 / 13
Arithmetic Coding algorithm
Arithmetic Coding algorithm
Arithmetic coding overcomes the problem of assigning integer codes
to the individual symbols by assigning one (normally long) code to
the entire input file.
The method starts with a certain interval, it reads the input file
symbol by symbol, and uses the probability of each symbol to narrow
the interval.
Specifying a narrower interval requires more bits, so the number
constructed by the algorithm grows continuously.
Neena Raj N. R. CS1U43D DCT January 2024 4 / 13
Arithmetic Coding algorithm
Arithmetic Coding algorithm
To achieve compression, the algorithm is designed such that a
high-probability symbol narrows the interval less than a
low-probability symbol, with the result that high-probability symbols
contribute fewer bits to the output.
Neena Raj N. R. CS1U43D DCT January 2024 5 / 13
Arithmetic Coding algorithm
Arithmetic Coding algorithm
The main steps of arithmetic coding:
Neena Raj N. R. CS1U43D DCT January 2024 6 / 13
Arithmetic Coding algorithm
Arithmetic Coding algorithm
Example: Encode the string SWISStMISS
Table. Frequencies and Probabilities of Five Symbols.
Neena Raj N. R. CS1U43D DCT January 2024 7 / 13
Arithmetic Coding algorithm
Arithmetic Coding algorithm
Neena Raj N. R. CS1U43D DCT January 2024 8 / 13
Arithmetic Coding algorithm
Arithmetic Coding algorithm
Table. The Process of Arithmetic Encoding.
Neena Raj N. R. CS1U43D DCT January 2024 9 / 13
Arithmetic Coding algorithm
Arithmetic Coding algorithm
Table. The Process of Arithmetic Decoding.
Neena Raj N. R. CS1U43D DCT January 2024 10 / 13
Syllabus
Module 2
Run length encoding, RLE Text compression, Statistical methods-Prefix Codes,
Binary Huffman coding, Illustration of Binary Huffman coding, Non-binary
Huffman Algorithms, Arithmetic Coding algorithm, Illustration of Arithmetic
Coding algorithm
Neena Raj N. R. CS1U43D DCT January 2024 11 / 13
Course Outcomes
Course Outcomes
CO1 Describe the fundamental principles of data compression. Understand
CO2 Apply
Make use of statistical and dictionary based compression tech-
niques for various applications
CO3 Illustrate various image compression standards. Apply
CO4 Summarize video compression mechanisms to reduce the re- Understand
dundancy in video.
CO5 Use the fundamental properties of digital audio to compress Understand
audio data.
Neena Raj N. R. CS1U43D DCT January 2024 12 / 13
References
References
[1] K. Sayood, Introduction to data compression. Morgan Kaufmann,
2003.
[2] D. Solomon, Data compression: the complete reference. Springer,
2007.
Neena Raj N. R. CS1U43D DCT January 2024 13 / 13
