DATA COMPRESSION (KCS-064)
B.Tech Semester VI – Theory Examination (2021–22)
DATA-COMPRESSION-KCS064
Data Compression is a fundamental subject in computer science and information technology that deals with reducing the size of data without losing essential information. With the rapid growth of digital data in the form of text, images, audio, and video, efficient storage and fast transmission have become critical requirements. Data compression techniques help in saving storage space, reducing transmission bandwidth, lowering communication cost, and improving system performance.
From the uploaded question paper, it is clearly visible that the examination focuses on lossless and lossy compression, entropy and information theory, Huffman coding, dictionary-based coding, Markov models, quantization, vector quantization, predictive coding, PPM, CALIC, LZW, BWT, facsimile encoding, and distortion measures. To score well, answers must be written in continuous, well-explained paragraphs, combining theory, mathematical reasoning, and algorithmic understanding rather than short bullet points.
SECTION A – FUNDAMENTAL CONCEPTS OF DATA COMPRESSION
(Based on Section A, Page-1)
Fidelity and quality are two important but distinct concepts in data compression. Fidelity refers to how closely the decompressed data matches the original data, usually in a technical or mathematical sense, whereas quality is a subjective measure that depends on human perception, especially in audio and image compression.
The kth-order Markov model of compression is calculated by assuming that the probability of a symbol depends on the previous k symbols. This model improves compression efficiency by exploiting statistical dependencies in data.
Huffman coding has limitations such as its inability to produce optimal codes when symbol probabilities are not powers of two and its inefficiency for sources with very large alphabets or adaptive data streams.
The difference between Huffman and adaptive Huffman coding lies in the way probabilities are handled. Huffman coding requires prior knowledge of symbol probabilities, whereas adaptive Huffman coding updates probabilities dynamically as data is processed.
CALIC (Context-based Adaptive Lossless Image Coding) is an advanced lossless image compression technique that uses context modeling and adaptive prediction to achieve high compression efficiency.
PPM (Prediction by Partial Matching) is a statistical data compression technique that predicts the next symbol based on previously seen symbol contexts and adapts as more data is processed.
Distortion criteria are used in lossy compression to measure the difference between original and reconstructed data. These criteria help evaluate compression performance.
Quantization is the process of mapping a large set of input values to a smaller set of output values. It plays a central role in lossy compression and directly affects distortion.
Tree-structured vector quantization offers advantages such as reduced search complexity and faster encoding compared to full search vector quantization.
The difference between scalar and vector quantization lies in how data is processed. Scalar quantization operates on individual samples, whereas vector quantization processes blocks of samples together, resulting in better compression efficiency.
SECTION B – ENTROPY, CODING AND QUANTIZATION
(Based on Section B, Page-1)
The average codeword length of an optimal code is always greater than or equal to the entropy of the source. This result is fundamental in information theory and proves that entropy represents the theoretical lower bound on compression.
For a given alphabet with known probabilities, entropy calculation quantifies the average information content of the source. Using Huffman coding, an optimal prefix code is generated, and the average code length is computed to evaluate coding efficiency.
Dictionary-based coding techniques, such as LZ77, LZ78, and LZW, compress data by replacing repeated patterns with dictionary references. These techniques are widely used in practical compression systems.
Adaptive quantization adjusts quantization parameters dynamically based on signal characteristics, offering better performance than uniform quantization for non-stationary signals.
Vector quantization groups samples into vectors and maps them to representative codewords from a codebook. This technique is highly effective in image and speech compression.
SECTION C – DATA COMPRESSION MODELS AND UNIQUE DECODABILITY
(Based on Section C, Page-1)
Data compression is the process of encoding information using fewer bits than the original representation. Compression is needed to save storage, reduce transmission time, and optimize resource utilization. Various compression models include statistical models, dictionary models, and predictive models.
A uniquely decodable code is one in which any encoded bit sequence can be decoded in only one way. Determining whether a code is uniquely decodable ensures reliable decoding without ambiguity.
HUFFMAN, TUNSTALL AND DICTIONARY DECODING
(Based on Page-2 of the paper)
The construction of a Huffman tree using given symbol frequencies demonstrates optimal prefix code generation. Decoding a bitstream using the Huffman tree verifies correctness of compression.
The Tunstall coding technique generates fixed-length codewords for variable-length symbol sequences, achieving efficient compression for memoryless sources.
The LZW decoding process reconstructs the original data sequence using an evolving dictionary. Comparing LZ77, LZ78, and LZW highlights differences in dictionary handling and compression performance.
FACSIMILE, BWT, PPM AND QUANTIZATION
(Based on Questions 5–7, Page-2)
Facsimile encoding was an early image compression technique that relied heavily on run-length coding to compress black-and-white images.
The Burrows–Wheeler Transform (BWT) rearranges data to make it more compressible by grouping similar characters together, improving the effectiveness of subsequent compression stages.
The PPM algorithm predicts symbols based on partial context matching, making it one of the most powerful statistical compression techniques.
The Linde–Buzo–Gray (LBG) algorithm is used to design optimal codebooks for vector quantization through iterative refinement.
Structured and pyramid vector quantization reduce complexity and improve scalability, while the advantages of vector quantization include high compression efficiency and good signal quality.
HOW TO WRITE DATA COMPRESSION ANSWERS IN THE EXAM
In Data Compression, never write answers in short bullet points. Always begin with a clear definition, followed by theoretical explanation, mathematical justification, algorithmic steps, and practical relevance. Use correct terminology such as entropy, prefix code, quantization, distortion, dictionary coding, and prediction models. Examiners give maximum importance to conceptual clarity, logical flow, and correct interpretation of compression techniques.
