GUJARAT TECHNOLOGICAL UNIVERSITY
Bachelor of Engineering
Subject Code: 3171615
Semester – VII
Subject Name: Data Compression
Type of course: Elective
Prerequisite: None
Rationale: Information is generated and used in digital form in the form of numbers represented by bytes of
data. Number of bytes required to represent multimedia data can be huge. Given the explosive growth of
data that needs to be transmitted and stored, compression techniques need to be used .
Teaching and Examination Scheme:
Teaching Scheme Credits Examination Marks Total
L T P C Theory Marks Practical Marks Marks
ESE (E) PA (M) ESE (V) PA (I)
3 0 2 4 70 30 20 30 150
Content:
Sr. No. Content Total
Hrs
1 Introduction: 3
Compression Techniques, Modeling and Coding
Mathematical Preliminaries for Lossless Compression:
Models – Physical Models, Probability Models, Markov Models
Coding – Uniquely Decodable Codes, Prefix codes
2 Huffman coding: 12
The Huffman Coding Algorithm – Minimum variance Huffman codes
Adaptive Huffman coding – Update Procedure,Encoding Procedure,Decoding Procedure
Golomb Codes
Rice codes
Tunstall Codes
Applications of Huffman Coding – Lossless Image compression, Text compression, Audio
Compression
Arithmetic coding:
Coding a sequence – Generating a Tag, Deciphering the Tag
Generating Binary Code – Uniqueness and Efficiency of the Arithmetic code, Algorithm
implementation, Integer Implementation
Comparison of Huffman and Arithmetic coding
Applications
3 Dictionaty Techniques: 7
Static Dictionary – Diagram Coding
Adaptive Dictionary – The LZ77 approach, The LZ78 Approach
Page 1 of 3
w.e.f. AY 2018-19
GUJARAT TECHNOLOGICAL UNIVERSITY
Bachelor of Engineering
Subject Code: 3171615
Applications – Image compression
4 Context based Compression : 5
Prediction with partial match(ppm) – The Basic Algorithm, The Escape symbol, Length of
context, The Exclusion Principle
The Burrows-Wheeler Transform – Move-to-Front Coding
5 Lossless Image Compression: 7
The Old JPEG Standard, CALIC, JPEG-LS
6 Mathematical Preliminaries for Lossy Coding: 8
Distortion criteria – The Human Visual System, Auditory Perception
Models – Probability Models, Linear System Models, Physical Models
Scalar Quantization:
The Quantization Problem
Uniform Quantizer
Adaptive Quantization – Forward Adaptive , Backward Adaptive
Non uniform Quantization – pdf optimized Quantization, Companded Quantization
Entropy Coded Quantization – Entropy coding of Lloyd – Max Quantizer Outputs
Vector Quantization :
Advantages of Vector Quantization over Scalar Quantization
The Linde-Buzo-Gray Algorithm
Tree structured Vector Quantization
Structured Vector Quantization
Suggested Specification table with Marks (Theory):
Distribution of Theory Marks
R Level U Level A Level N Level E Level C Level
10 40 10 10
Legends: R: Remembrance; U: Understanding; A: Application, N: Analyze and E: Evaluate C:
Create and above Levels (Revised Bloom’s Taxonomy)
Note: This specification table shall be treated as a general guideline for students and teachers. The actual
distribution of marks in the question paper may vary slightly from above table.
Reference Books:
1) Introduction to Data Compression –By Khalid Sayood, publication Elsevier
2) The Data Compression book, By Mark Nelson,Jean Loup Gaily
3) Data Compression : The Complete Reference”, By David Saloman, publication Springer
4) Data Compression Methods and Theory - by James A. Storer
Page 2 of 3
w.e.f. AY 2018-19
GUJARAT TECHNOLOGICAL UNIVERSITY
Bachelor of Engineering
Subject Code: 3171615
Course Outcomes:
Sr. CO statement Marks % weightage
No.
CO-1 Understand the Mathematical Preliminaries involved in compression 15
techniques.
CO-2 Use Loseless compression algorithm to compress Image, Text and 35
Audio.
CO-3 Use Lossy compression algorithm considering the Criteria. 35
CO-4 Differentiate Loseless and Lossy algorithms and test appropriate 15
algorithm for compression of given digital information.
List of Experiments:
1) Given the code as sequence of characters and given the probability of characters, write a program to
calculate average length of each code.
2) Write a program to generate Huffman code.
3) Write a program to generate binary code for the sequence abacabb, Given the frequency count of a
– 37, b-38, c-25.
4) Write a program to implement digram coding for given text file.
5) Write a program to Implement LZ77 algorithm.
6) Write a program to Implement LZ78 algorithm.
7) 8. Write a program to Implement LZW algorithm.
8) Given the sequence of characters, write a program to find unique characters, and write a program to
implement ppma algorithm.
Page 3 of 3
w.e.f. AY 2018-19
