Data Compression(DC)

GUJARAT TECHNOLOGICAL UNIVERSITY

B.E. SEMESTER : VIII

INFORMATION TECHNOLOGY

Subject Name: DATA COMPRESSION

L. J. Institute of Engineering & Technology

S.G. Highway, Ahmedabad-382210

IT Department

Practical List

Subject Name:	Data Compression
Subject Code:	181602
Branch & Semester:	IT-VIII

SUBJECT	TEACHING SCHEME (HOURS)			CREDITS
	THEORY	TUTORIAL	PRACTICAL
DATA COMPRESSION	4	0	2	6

Sr. No.	Aim of Practical	Link to Syllabus	Link to Question Bank
1	Write a program to count the occurrences of different letters by reading the given text file and also find the probability of each letter with number of bits required for them using the formula: No. of bits=1/log2 probi	2	--
2	Write a program in C to determine whether the set of given codes is uniquely decodable or not.	1	11
3	Write a program in C for Huffman Compression.	3	2.43
4	Write a program in C to implement Shannon-Fano compression Algorithm.	3	2.4
5	Write a program to implement arithmetic coding	5	2.7
6	Write a program to implement lz77 algorithm.	7	13
7	Study of JPEG.	2,7	6.18
8	Study of DCT.	2,7	6.17
9	Study of Speech Compression.	8	--

 Facu

Syllabus
1. Introduction To Data Compression
The Audience, Why C?, Which C?, Keeping Score, The Structure

2. The Data Compression Lexicon, With A History
The Two Kingdoms, Data Compression = Modeling + Coding, The Dawn Age, Coding An Improvement Modeling, Statistical Modeling, Ziv & Lempel LZ77 LZ78, Lossy Compression, Programs to Know

3. The Dawn Age: Minimum Redundancy Coding
The Sahnnon-Fano Algorithm, The Huffman Algorithm, Huffman in C, BITIO.C, A Reminder about Prototypes, MAIN-C.C & MAIN-E.C, MAIN-C.C, ERRHAND.C, Into the Huffman Code, Counting the Symbols, Saving the Counts, Building the Tree, Using the Tree

4. A Significant Improvement: Adaptive Huffman Coding
Adaptive Coding, Updating the Huffman Tree, What swapping Does, The Algorithm, An Enhancement, The Escape Code, The Overflow Bonus, A Rescaling Bonus, The Code, Initialization of the Array, The Compress Main Program, The Expand Main Program, Encoding the Symbol, Decoding The Symbol

5. Huffman One Better: Arithmetic Coding
Difficulties, Arithmetic Coding: A Step Forward, Practical Matters, A Complication, Decoding, Where’s the Beef

6. Dictionary-Based Compression
An Example, Static vs. Adaptive, Adaptive Methods, A Representative Example, Israeli Roots, History, ARC: The Father of MS-DOS Dictionary Compression, Dictionary Compression, Danger Ahead-Patents, Conclusion

7. Sliding Window Compression
The Algorithm, Problems with LZ77, An Encoding Problem, LZSS compression, Data structures, A balancing Act Greedy vs. Best Possible. The Expansion Routine, Improvements.

8. Speech Compression
Digital Audio Concepts, Fundamentals, Sampling Variables, PC-Based sound, Lossless Compression of Sound, Problems and Results, Loss compression, Silence Compression, Other Techniques.

9. Lossy Graphics Compression
Enter Compression, Statistical And Dictionary Compression Methods Lossy Compression Differential Modulation Adaprive Coding, A Standard That Works: JPEG, JPEG Compression, The Discrete Cosine Transform, DCT Specifics, Why Bother? Implementing The DCT. Matrix Multiplication, Cpmtomied Improvements, Output Of The DCT, Quantization, Selecting A Qualtization Matrix. The Sample
Program, Input Format, Initialization, The Forward DCT Routine, Write DCT Data(), File Expansion, Read DCT Data(), The Inverse DCT.

Text Books:
1. “Data Compression”, Mark Nelson
2. “Data Compression”, Khalid shayood, Morgon Kaufmann
Reference Books:
1. “Data Compression : The Complete Reference”, David Saloman, Springer