About this previous year paper
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
| Lossless | Lossy |
|---|---|
| No data loss | Some data loss |
| Exact reconstruction | Approximate reconstruction |
| ZIP, PNG | JPEG, MP3 |
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
| Golomb Code | Rice Code |
|---|---|
| General parameter m | m = 2ⁿ |
| Flexible | Simpler |
| More efficient | Faster implementation |
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
| LZ77 | LZ78 |
|---|---|
| Sliding window | Dictionary-based |
| Uses offsets | Uses explicit dictionary |
| Faster | More structured |
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