Data Compression (Elective-III)

Unit I

Compression Techniques: Lossless Compression, Lossy Compression, Measures of Performance, Modeling and Coding. Mathematical Preliminaries for Lossless Compression: Brief Introduction to Information Theory, Models — Physical, Probability, Markov, Composite Source Models, Coding — Uniquely Decodable Codes, Prefix Codes.

Unit II

Huffman Coding: The Huffman Coding Algorithm, Minimum Variance Huffman Codes, Adaptive Huffman Coding — Update, Encoding and Decoding Procedures, Golomb Codes, Rice Codes, Tunstall Codes, Applications — Lossless Image Compression, Text Compression, Audio Compression.

Unit III

Arithmetic Coding & Dictionary Techniques: Coding a Sequence, Generating a Binary Code, Comparison of Binary and Huffman Coding, Applications — Bi-Level Image Compression (JBIG, JBIG2), Image Compression. Dictionary Techniques: Static Dictionary — Digram Coding, Adaptive Dictionary — LZ77, LZ78, Applications — UNIX compress, GIF, V.42bis. Predictive Coding: Prediction with Partial Match (PPM) — Basic Algorithm, Escape Symbol, Length of Context, Exclusion Principle, Burrows-Wheeler Transform — Move-to-Front Coding, CALIC, JPEG-LS, Multi-Resolution Approaches, Facsimile Encoding, Dynamic Markov Compression.

Unit IV

Scalar Quantization: Distortion Criteria, Models, The Quantization Problem, Uniform Quantizer, Adaptive Quantization, Non-Uniform Quantization.

Unit V

Vector Quantization: Advantages of Vector Quantization over Scalar Quantization, The Linde-Buzo-Gray Algorithm, Tree-Structured Vector Quantizers, Structured Vector Quantizers.