DATA COMPRESSION — PART 1 (EXPLANATION NOTES)
1. INTRODUCTION
Data compression refers to reducing the size of data for storage or transmission. Modern systems
handle huge amounts of data, and raw data is often extremely large. For example:
• 1 second of uncompressed digital video (720×480 resolution, 24-bit colour, 30 fps)
requires approximately 20 MB.
• A 4■minute audio song (44,100 samples/sec, 16■bit, stereo) requires a large transmission
bandwidth.
To transmit such bulk data, compression becomes necessary.
2. WHY WE NEED COMPRESSION
• Large data consumes large storage.
• Large data rate requires large bandwidth.
• For a channel of bandwidth B, the maximum bit■rate is 2B bits/s. If we want to send
more data than this, we must compress.
3. APPLICATIONS
• Data transmission and storage
• Progressive image transmission (PIT)
• Video coding — HDTV, videoconferencing
• Digital libraries, medical images, satellite images
4. PRINCIPLES BEHIND COMPRESSION
Compression is possible because most real-world signals contain redundancy.
Types of redundancy:
• Coding redundancy
• Spatial redundancy
• Temporal redundancy
• Perceptual redundancy
5. TYPES OF REDUNDANCY
A. Coding Redundancy
Some symbols occur more frequently than others. Example: In English, 'E' occurs far more often
than 'Z'. Hence, we assign shorter codes to frequent symbols and longer codes to rare symbols.
Example: Morse Code uses this principle.
B. Spatial Redundancy
Neighbouring samples are correlated — especially in images. If pixels around a pixel are known,
the pixel can be predicted.
C. Temporal Redundancy
In video, consecutive frames often contain the same objects. Thus future frames can be predicted
from past frames.
D. Perceptual Redundancy
Human perception is limited. We cannot perceive very small changes in brightness or colour.
Example: We are less sensitive to high■frequency colour details. Lossy compression exploits this.
6. TYPES OF COMPRESSION
A. Lossless Compression
• Restored data is identical to the original.
• Used mainly for text.
Examples:
- Run■Length Encoding (RLE)
- Huffman Coding
- Arithmetic Coding
B. Lossy Compression
• Output is not identical, but visually or perceptually acceptable.
• Used in audio, video, and images.
Examples: JPEG, MP3, MPEG, DCT-based compression.
7. INFORMATION THEORY BASICS
Information is a measure of uncertainty.
If a symbol is less probable, it carries more information.
Self■information of a symbol x■ is:
I(x■) = log■(1 / p(x■)) bits
Entropy (average information content of a source X):
H(X) = Σ p(x■) log■(1 / p(x■)) bits/symbol
Properties of entropy:
•H≥0
• Maximum entropy occurs when all symbols occur with equal probability.
Example: If there are N symbols, maximum entropy = log■(N).
Binary entropy (symbols 0 and 1 with probabilities p and 1 − p):
H_b = −p log■ p − (1 − p) log■(1 − p)
8. REQUIREMENTS FOR CODES
A code should be:
• Uniquely decodable
• Instantaneous (prefix■free)
Prefix Property: No codeword is a prefix of another.
Average codeword length:
L_avg = Σ p(x■) * l■
We want L_avg as small as possible.
9. KRAFT’S INEQUALITY
A set of codeword lengths can form a prefix code iff:
Σ 2^(−l■) ≤ 1