(SEM VI) THEORY EXAMINATION 2024-25 DATA COMPRESSION

BCS064 – DATA COMPRESSION

Time: 3 Hours | Max Marks: 70

SECTION A – Short Answer Questions

(2 × 7 = 14 marks | Attempt ALL)
Write definition + 1–2 clear points / diagram

a. What is Data Compression?

Data compression is the process of reducing the number of bits required to represent data by removing redundancy, without losing essential information.

Block diagram:
Source → Encoder → Channel → Decoder → Destination

b. Real-World Applications of Data Compression            Image compression (JPEG, PNG)

Audio compression (MP3, AAC)                                       Video compression (MPEG, H.264)

File compression (ZIP, RAR)                                              Network data transmission

c. Principle Behind Huffman Coding

Huffman coding assigns shorter codes to more frequent symbols and longer codes to less frequent symbols, resulting in minimum average code length.

d. Role of Linde-Buzo-Gray (LBG) Algorithm

The LBG algorithm is used in vector quantization to design an optimal codebook by minimizing distortion iteratively.

e. Lossless vs Lossy Compression

f. Distortion Criteria Used in Quantization

Mean Square Error (MSE)                 Mean Absolute Error (MAE)            Signal-to-Noise Ratio (SNR)

Importance: Measures quality loss after compression.

g. Golomb Code (m = 5)

For 9 → quotient = 1, remainder = 4                     For 13 → quotient = 2, remainder = 3
(Use unary + truncated binary representation)

SECTION B – Medium Answer Questions

(7 × 3 = 21 marks | Attempt ANY THREE)
Write concept → explanation → numerical/example

a. Huffman Coding – Bits Saved (Numerical)

Steps:                                                                     Construct Huffman tree using frequencies

Assign codes

Compute total bits before compression                Compute bits after compression

Bits saved = Original − Compressed

Very important numerical

b. Golomb Code vs Rice Code

c. Burrows-Wheeler Transform (BWT)

BWT rearranges data to group similar characters together, improving compression efficiency when combined with RLE and Huffman coding.

d. Key Elements of Quantization Problem

Input source                                                            Quantizer

Codebook                                                                Distortion measure

Bit rate

e. Role of LBG Algorithm in Vector Quantization      Initializes codebook

Assigns vectors to nearest codewords                      Updates centroids

Minimizes distortion iteratively

 SECTION C – Attempt ANY ONE

(7 marks)

a. LZ77 vs LZ78

b. Short Notes (Any Five)                                                   Compression Standards: JPEG, MPEG, MP3

PPM: Statistical context-based compression                    BWT: Reversible data transformation

Audio Compression: Exploits human hearing limits        Markov Model: Predicts symbol probabilities