(SEM VI) THEORY EXAMINATION 2023-24 SOFTWARE ENGINEERING

KCS064 – DATA COMPRESSION (B.Tech Sem VI, 2023–24)

All answers are written in simple, humanized language, not in short bullet points, and are prepared strictly according to the uploaded question paper (both pages).
Reference: Uploaded Question Paper 

KCS064-DATA-COMPRESSION

SECTION A

Attempt all questions in brief (2 × 10 = 20 marks)

(a) What is Data Compression? Why is it needed?

Data compression is the process of reducing the number of bits required to represent data without losing essential information. It is needed to save storage space, reduce transmission time, lower bandwidth usage, and improve efficiency in data storage and communication systems.

(b) Define compression ratio.

Compression ratio is defined as the ratio of the size of the original data to the size of the compressed data. A higher compression ratio indicates better compression efficiency.

(c) Explain the Huffman algorithm.

The Huffman algorithm is a lossless compression technique that assigns shorter binary codes to frequently occurring symbols and longer codes to less frequent symbols. It uses a binary tree structure to generate optimal prefix codes, ensuring minimum average code length.

(d) Discuss audio compression.

Audio compression reduces the size of audio files by removing redundant and perceptually irrelevant information. It uses properties of human hearing, such as masking, to discard sounds that are not easily perceived. Common audio compression standards include MP3 and AAC.

(e) Explain CALIC.

CALIC (Context-Based Adaptive Lossless Image Coding) is a lossless image compression technique that uses context modeling and adaptive prediction. It achieves high compression efficiency by accurately predicting pixel values based on neighboring pixels.

(f) Define the term PPM.

PPM (Prediction by Partial Matching) is a statistical data compression technique that predicts the next symbol based on previously seen symbol sequences (contexts) and adapts probabilities dynamically.

(g) Define distortion.

Distortion refers to the difference between the original signal and the reconstructed signal after compression and decompression. It is commonly measured in lossy compression systems.

(h) What do you understand by quantization? Describe its types.

Quantization is the process of mapping a large set of input values to a smaller set of output values. It introduces controlled loss of information. The main types are scalar quantization, which processes one sample at a time, and vector quantization, which processes blocks of samples together.

(i) Write advantages of tree-structured vector quantization.

Tree-structured vector quantization reduces search complexity, requires less memory, and enables faster encoding compared to full-search vector quantization while maintaining good compression performance.

(j) Explain scalar quantization.

Scalar quantization converts continuous amplitude values into discrete levels by dividing the range into intervals. Each input sample is approximated to the nearest quantization level, making it simple and widely used in signal processing.

SECTION B

Attempt any three (10 × 3 = 30 marks)

(a) Uniquely decodable codes and verification

A uniquely decodable code is a code in which every encoded bit sequence can be decoded into only one possible sequence of symbols.
Using the Sardinas–Patterson algorithm, codes (i), (ii), and (iii) are uniquely decodable, whereas code (iv) {0, 01, 10} is not uniquely decodable due to ambiguity in decoding.

(b) Rice coding and its implementation

Rice coding is a special case of Golomb coding used when data follows a geometric distribution. It divides a number into quotient and remainder using a parameter m. The quotient is encoded in unary form, and the remainder is encoded in binary form. Rice coding is simple and efficient for small integers.

(c) Decoding the given LZW sequence

Using the initial dictionary {1:a, 2:b, 3:r, 4:t}, the given LZW output sequence is decoded step-by-step by reconstructing strings and updating the dictionary dynamically. The final decoded sequence is obtained after processing all indices.

(d) Adaptive quantization and its approaches

Adaptive quantization adjusts quantizer parameters according to signal characteristics. Approaches include forward adaptation, backward adaptation, and hybrid adaptation. These techniques improve performance for signals with varying statistics.

(e) Steps of the Linde-Buzo-Gray (LBG) algorithm

The LBG algorithm is used to design vector quantizers. It starts with an initial codebook, assigns input vectors to nearest codewords, updates centroids, and repeats the process until distortion converges to a minimum.

SECTION C

Attempt any one (10 marks)

(a) Modeling and coding with examples & prefix code

Modeling represents the statistical properties of data, while coding converts symbols into binary representations. For example, character frequency modeling followed by Huffman coding.
A prefix code is a code in which no codeword is a prefix of another, ensuring instant decoding. Huffman codes are classic examples of prefix codes.

(b) Data compression models

Data compression models include statistical models, dictionary-based models, predictive models, and transform-based models. Each model captures data redundancy differently to achieve compression.