(SEM VI) THEORY EXAMINATION 2022-23 DATA COMPRESSION

DATA COMPRESSION – KCS-064

Section-wise Important Questions & Ready Answers

SECTION A

(Attempt all questions in brief – 2 marks each)

(a) Measures of Performance of Data Compression Algorithms

The performance of a data compression algorithm is measured using compression ratio, bit rate, redundancy, computational complexity, memory requirement, and distortion (for lossy compression). These measures indicate efficiency, speed, and quality of compression.

(b) First-Order Entropy Calculation

Given alphabet A={a1,a2,a3,a4}A = \{a_1,a_2,a_3,a_4\}A={a1​,a2​,a3​,a4​} with equal probabilities:

H=−∑p(ai)log⁡2p(ai)=−4(14log⁡214)=2 bits/symbolH = -\sum p(a_i)\log_2 p(a_i) = -4\left(\frac{1}{4}\log_2\frac{1}{4}\right) = 2\ \text{bits/symbol}H=−∑p(ai​)log2​p(ai​)=−4(41​log2​41​)=2 bits/symbol 

(c) Applications of Huffman Coding

Huffman coding is widely used in text compression, image compression (JPEG), audio compression (MP3), fax transmission, and file compression utilities due to its optimal lossless coding property.

(d) Golomb Code for n=9n=9n=9 and n=13n=13n=13, m=5m=5m=5

Golomb coding divides the number into quotient and remainder.
For n=9n=9n=9: quotient q=1q=1q=1, remainder r=4r=4r=4.
For n=13n=13n=13: quotient q=2q=2q=2, remainder r=3r=3r=3.
Unary coding is used for quotient and truncated binary for remainder.

(e) Applications of Dictionary-Based Compression

Dictionary-based techniques such as LZ77, LZ78, and LZW are used in ZIP files, GIF images, PDF compression, modem communication, and data storage systems.

(f) Binary Code vs Huffman Code

Binary code assigns fixed-length codewords, whereas Huffman code assigns variable-length codewords based on symbol probabilities. Huffman coding achieves better compression efficiency.

(g) Distortion Criteria

Distortion criteria include mean squared error, absolute error, signal-to-noise ratio, peak signal-to-noise ratio, and perceptual distortion measures.

(h) Mismatch Effect

Mismatch effect occurs when the assumed probability model differs from the actual source distribution, resulting in increased redundancy and reduced compression efficiency.

(i) Code Vectors

Code vectors are representative vectors stored in a codebook in vector quantization. Each input vector is mapped to the closest code vector during encoding.

(j) Concept of Pruning

Pruning removes unnecessary branches or codewords from coding structures to reduce complexity and improve efficiency without significantly affecting performance.

SECTION B

(Attempt any three – 10 marks each)

2(a) Uniquely Decodable Codes vs Prefix Codes

Uniquely decodable codes allow unambiguous decoding of symbol sequences, while prefix codes ensure no codeword is a prefix of another, making instant decoding possible. Prefix codes are always uniquely decodable, but the reverse is not necessarily true. The code set {0,10,110,111} is uniquely decodable, whereas {1,10,110,111} is not.

2(b) Huffman Coding with Given Probabilities

Entropy is calculated using probability values. Huffman tree is constructed by repeatedly combining least probable symbols. The average code length is computed and redundancy is obtained by subtracting entropy from average length. Minimum variance Huffman coding minimizes variance in codeword lengths.

2(c) Prediction with Partial Match (PPM) & Facsimile Encoding

PPM predicts symbols based on previous context and adapts probabilities dynamically. Facsimile encoding uses run-length coding to compress long runs of identical pixels, making it suitable for black-and-white documents.

2(d) Adaptive Quantization

Adaptive quantization dynamically adjusts step size or quantizer parameters based on signal characteristics. Approaches include forward adaptive, backward adaptive, and hybrid adaptive quantization.

2(e) Vector Quantization (VQ)

Vector quantization maps blocks of samples into code vectors instead of individual samples. Compared to scalar quantization, VQ offers better compression efficiency and exploits inter-sample correlation.

SECTION C

3(a) Two-State Markov Model for Binary Images

A two-state Markov model represents transitions between binary pixel states (0 and 1). The ignorance model assumes equal probabilities. Probability models help estimate symbol likelihoods for efficient compression.

3(b) Modeling, Coding & Information Theory

Modeling captures source statistics, while coding converts them into compressed form. Information theory provides concepts such as entropy, redundancy, and mutual information, which define theoretical limits of lossless compression.