CST446

Data Compression Techniques

Module-wise Detailed Notes

APJ Abdul Kalam Technological University • 8th Semester [Link] (CSE) • 2019 Scheme

Course Code CST446

Credits 3 (2L + 1T)

Category PEC (Professional Elective)

Max Marks 100 (CIE: 50 + ESE: 50... scaled to 100)

Textbooks Solomon (Springer, 2007); Sayood (Morgan Kaufmann, 2003)

 Module 1: Modelling and Types of Compression
Topics: Lossless & Lossy compression, Performance measures, Modelling & Coding, Physical & Probability models

1.1 Introduction to Data Compression

Data compression is the process of reducing the number of bits required to represent data. It exploits
redundancy — statistical (repeated patterns), perceptual (irrelevant to human senses), or structural — to shrink
file size.

• Lossless Compression: Original data is perfectly reconstructed. Used for text, executables, medical images.
Examples: Huffman coding, LZ77, RLE.
• Lossy Compression: Some data is permanently discarded. Acceptable where perceptual quality matters
more than exact reproduction. Examples: JPEG, MP3, MPEG.

Key Point: Lossless is mandatory when data integrity is critical (e.g., ZIP, PNG). Lossy is preferred when high
compression ratio matters (e.g., JPEG, MP3).

1.2 Measures of Performance

A compression system is evaluated using the following metrics:

Metric Formula / Definition

Compression Ratio (CR) CR = Size(original) / Size(compressed)

Compression Factor (CF) CF = Size(original) / Size(compressed) [same as CR]

Bits per Symbol Average number of bits to represent one symbol

Entropy (H) H = -Σ p(x) log■ p(x) [lower bound of bits/symbol]

Coding Efficiency η = H / L■ × 100% where L■ = average code length

Redundancy R = 1 - η (fraction of wasted bits)

Signal-to-Noise Ratio (SNR) Used in lossy systems: SNR = 10 log■■(Signal power / Noise power) dB

PSNR Peak SNR — used for image quality assessment

1.3 Modelling and Coding

A compression system has two main stages:

• Modelling: Assigns a probability model to the source data. The model can be static (fixed before encoding),
semi-adaptive (built from data then applied), or adaptive (updated symbol by symbol during encoding).
• Coding: Uses the probability model to assign shorter codes to more probable symbols. The coding stage
converts symbols to a bitstream.
For the dataset 9, 11, 11, 11, 14, 13, 15, 17, 16, 17, 20, 21:

• Model: estimate probabilities from frequency counts.

• Apply Huffman or arithmetic coding using those probabilities.
• Transmit the model parameters + encoded bitstream to the receiver.

1.4 Mathematical Models for Compression

1.4.1 Physical Models (Lossless)

Physical models exploit the physical nature of the data:

• Run-Length Model: Consecutive repeated symbols are encoded as (count, symbol). Very effective for binary
images and fax.
• Move-to-Front Model: Frequently used symbols bubble to front of a list — their index becomes the code.
• Diatomic Model: Pairs of symbols (digrams) are modelled and coded together.

1.4.2 Probability Models (Lossless)

Based on statistical properties of the source:

• Memoryless (i.i.d.) model: Each symbol is independent. Entropy H = -Σ p(x) log■ p(x).
• Markov model: Probability of a symbol depends on previous symbols (context modelling).

1.4.3 Probability Models (Lossy)

Two common models for designing lossy compressors:

• Gaussian (Normal) Distribution: PDF: f(x) = (1/√(2πσ²)) exp(-(x-µ)²/2σ²). Used for audio and general
signals. Quantisation is designed around the Gaussian curve.
• Uniform Distribution: f(x) = 1/(b-a) for a ≤ x ≤ b. Simpler, used when signal range is bounded and flat
distribution is assumed.

Key Point: Self-Information: I(x) = log■(1/p(x)) = -log■ p(x) bits. Entropy H is the expected self-information across
all symbols.
 Module 2: Basic Compression Methods
Topics: RLE, Prefix codes, Binary & Non-binary Huffman coding, Arithmetic coding

2.1 Run-Length Encoding (RLE)

RLE replaces a run of identical symbols with a (count, symbol) pair. It is one of the simplest compression
techniques.

• Input: AAAAAABBBCDDDDDD → Output: 6A3B1C6D

• Compression Factor (CF) for RLE Text: CF = n / (2k) where n = original length, k = number of distinct runs.
• RLE is efficient when runs are long. It can expand the data if there are many short runs (CF < 1).
• Widely used in TIFF, BMP, fax (Group 3/4), and early graphics.
CF = n / (number of encoded pairs × 2) CF > 1: compression achieved; CF < 1: data expanded

Key Point: RLE becomes inefficient when the input has few or no repeated characters — e.g., 'ABCDEF'
compresses to '1A1B1C1D1E1F' which is twice as long.

2.2 Statistical Methods — Prefix Codes

A prefix code (also called a prefix-free code) is one where no codeword is a prefix of another. This ensures
unique decodability without delimiters.

• Kraft-McMillan Inequality: For a uniquely decodable code with lengths l■, l■, ..., l■ over a D-ary alphabet: Σ
D-l■ ≤ 1.
• Optimal prefix codes minimise average code length L■ = Σ p(x■) l■.
• Huffman coding always produces an optimal prefix code.

2.3 Binary Huffman Coding

Algorithm:

• Step 1: Sort symbols by probability (descending).

• Step 2: Combine the two lowest-probability symbols into a new node. The combined probability is their sum.
• Step 3: Repeat until only one node remains (the root).
• Step 4: Assign 0 to left branches and 1 to right branches (or vice versa). Read path from root to leaf =
codeword.
Properties of Huffman Code:

• Always produces an optimal prefix code (minimum average code length).

• More probable symbols get shorter codewords.
• The code tree is a full binary tree (every internal node has exactly 2 children).
• Average code length L■ is always ≥ entropy H (L■ ≥ H).
• For two methods (different tie-breaking), the method with lower variance is preferred for buffer management.

Key Point: Huffman coding is optimal but requires knowing probabilities in advance (static) or two-pass encoding
(adaptive Huffman).

2.4 Non-Binary Huffman Coding

Extends Huffman to D-ary trees (D symbols per branch, commonly D=3 or D=4):
• At each step combine the D lowest probability symbols.
• For a valid D-ary tree: add dummy symbols with probability 0 so that (n-1) mod (D-1) = 0.
• D-ary codes produce shorter average code lengths in bits only when D matches the channel alphabet size.

2.5 Arithmetic Coding

Arithmetic coding encodes an entire message as a single real number in [0, 1). It can approach entropy more
closely than Huffman coding for skewed distributions.

Encoding procedure:

• Start with interval [0, 1).

• For each symbol, narrow the interval to the sub-interval assigned to that symbol (based on cumulative
probabilities).
• After all symbols, output any number (tag) within the final interval.
• The tag can be represented in binary — number of bits ≈ -log■(interval width).
Decoding procedure:

• Given the tag, identify which symbol's sub-interval it falls in.

• Rescale the tag to that sub-interval and repeat until all symbols are decoded.
For sequence a■a■a■a■a■a■ with P(a■)=0.2, P(a■)=0.3, P(a■)=0.5: Cumulative ranges: a■ → [0, 0.2), a■ →
[0.2, 0.5), a■ → [0.5, 1.0)

Key Point: Arithmetic coding achieves average code length very close to entropy H, making it theoretically superior
to Huffman for sources with highly skewed probabilities.
 Module 3: Text and Image Compression
Topics: LZ77, LZ78, LZW dictionary coding; JPEG (Baseline & JPEG-LS)

3.1 Dictionary-Based Coding

Dictionary coders replace repeated patterns with references to a dictionary of previously seen strings. They do
not require prior knowledge of symbol probabilities — they are universal coders.

3.1.1 LZ77
• Uses a sliding window: search buffer (history) + look-ahead buffer (current input).
• Output triple: (offset, length, next_char).
• Offset = how far back in the search buffer the match starts.
• Length = number of characters matched.
• Next char = the character that broke the match.
• Merits: Simple, no explicit dictionary needed, good for text/binary.
• Demerits: Fixed window limits compression; encoding can be slow.
Example — 'cabracadabrarrarrad', window=13, look-ahead=6: C = (0,0,'c'), A = (0,0,'a'), B = (0,0,'b'), R = (0,0,'r'),
A = (3,1,'a')... etc.

3.1.2 LZ78
• Builds an explicit dictionary from scratch as encoding proceeds.
• Output pair: (index, next_char).
• Index = index of the longest matching prefix in the dictionary.
• Adds new entry = matched string + next character.
• Dictionary can grow unbounded (or be reset when full).
Example — 'ABCDABCABCDA': (0,A) → dict[1]=A, (0,B) → dict[2]=B, (0,C) → dict[3]=C, (0,D) → dict[4]=D, (1,B)
→ dict[5]=AB, (3,A) → dict[6]=CA...

3.1.3 LZW (Lempel-Ziv-Welch)

• Variant of LZ78 — starts with a pre-built dictionary of all single characters.
• Output: single index (no next char needed).
• Both encoder and decoder build the same dictionary in sync — dictionary need not be transmitted.
• Used in GIF, TIFF, PDF (older), Unix compress.
LZW Encode 'ratatatatbabratbatbabrat', initial dict: {a:1,b:2,r:3,t:4} Output: 3,1,4,1,4,1,4,2,1,3,1,5,7,2,3,1,4...

Key Point: LZ77 uses a sliding window with no explicit dictionary. LZ78 builds a dictionary explicitly. LZW is LZ78
with pre-initialised dictionary — most practically deployed form.

3.2 Image Compression — JPEG

3.2.1 Baseline JPEG (Lossy)

JPEG encoding pipeline (each step in sequence):

1. Colour Space Conversion: RGB → YCbCr. Y = luminance (more important to human eye); Cb, Cr =
chrominance. Chroma can be downsampled (4:2:0 or 4:2:2).
2. Block Partitioning: Image divided into non-overlapping 8×8 pixel blocks.
3. DCT (Discrete Cosine Transform): Each 8×8 block transformed to frequency domain. Low-frequency
coefficients (top-left) carry most energy.
4. Quantisation: DCT coefficients divided by a quantisation table (element-wise). High-frequency coefficients
are heavily quantised (zeroed out). THIS is where lossy compression occurs.
5. Zig-Zag Scan: 2D 8×8 block reordered into 1D sequence — low frequencies first, trailing zeros grouped at
the end.
6. Run-Length Encoding: Long run of zeros at the end of the zig-zag sequence efficiently encoded.
7. Huffman Coding: Final entropy coding of the RLE output.

Key Point: Decoding reverses all steps: Huffman decode → RLE decode → De-zig-zag → Dequantise → IDCT →
Colour convert.

3.2.2 JPEG-LS (Lossless / Near-Lossless)

• Designed for lossless (or near-lossless) compression of continuous-tone images.
• Two modes: (a) Lossless mode — exact reconstruction; (b) Near-lossless mode — bounded maximum error
per pixel.
• Based on the LOCO-I (Low Complexity Lossless Compression for Images) algorithm.
• Uses context modelling with local gradients to predict the next pixel.
• Residuals (prediction errors) are entropy-coded using Golomb codes.
• Much faster and simpler than JPEG 2000 while achieving good lossless ratios.
 Module 4: Video Compression
Topics: Analog & Digital Video, Motion Compensation, MPEG-1, MPEG-4

4.1 Basics of Video

4.1.1 Analog Video

• Video = sequence of frames (still images) displayed at a rate (fps) that creates perceived motion.
• Standards: NTSC (29.97 fps, 525 lines, USA/Japan), PAL (25 fps, 625 lines, Europe/India), SECAM
(France).
• Interlaced scanning: Each frame = 2 fields (odd + even lines). Reduces bandwidth, but motion artifacts
possible.
• Progressive scanning: Full frame at once. Better quality, used in modern displays.

4.1.2 Digital Video & Colour Models

• YUV: Y = luminance, U (Cb) and V (Cr) = colour difference. Human eye more sensitive to Y than UV.
• YIQ: Used in NTSC. I = in-phase (orange-cyan axis), Q = quadrature (green-magenta axis).
• Chroma subsampling: 4:4:4 (no subsampling), 4:2:2 (Cb/Cr at half horizontal res), 4:2:0 (Cb/Cr at quarter
spatial resolution — used in most video codecs).
• Composite video: Luminance and chrominance multiplexed onto single signal (e.g., S-Video, composite
RCA).
• Component video: Y, Cb, Cr on separate wires — better quality, used in professional video.

4.2 Motion Compensation

Temporal redundancy: adjacent frames in video are very similar. Motion compensation exploits this by encoding
only the differences between frames.

• Motion Estimation: Encoder searches for 16×16 pixel macro-blocks in the reference frame that best match
the current block.
• Motion Vector (MV): A displacement vector (dx, dy) pointing to the best matching block in the reference
frame.
• Prediction: Predicted block = block at (x+dx, y+dy) in reference frame.
• Residual: Difference = current block - predicted block. Only the residual + motion vectors are encoded.
• Block Matching Algorithms: Full search (exhaustive), 3-step search, diamond search — trade accuracy for
speed.

Key Point: Motion compensation is the key mechanism behind all modern video codecs (MPEG-1/2/4, H.264,
H.265/HEVC). Without it, video would require impractical bitrates.

4.3 Frame Types in Video Encoding

• I-frame (Intra-coded): Encoded independently (like a JPEG image). Random access point. Largest size.
• P-frame (Predictive): Encoded using motion compensation from the previous I or P frame. Moderate size.
• B-frame (Bidirectional): Uses motion compensation from both previous and future frames. Smallest size.
Requires reordering (decode order ≠ display order).
Typical GOP (Group of Pictures) structure: I B B P B B P B B I ... GOP size controls random access vs
compression tradeoff.
4.4 MPEG-1 Video Standard
MPEG-1 (ISO 13818) was designed for 1.5 Mbps (CD-ROM speed). It defines the following layers:

Layer Description

Sequence Top-level container; sequence header (resolution, frame rate, bit rate)

Group of Pictures (GOP) Collection of I, P, B frames; defines random access points

Picture Single frame; header specifies I/P/B type

Slice Horizontal strip of macro-blocks; resync point for error recovery

Macro-block 16×16 luma + 8×8 chroma blocks; motion vector at this level

Block 8×8 DCT block; lowest unit; DCT + quantisation applied here

Pel Reconstruction (MPEG-1): Half-pixel interpolation is used to improve motion estimation accuracy.
Reference frame pixels between integer positions are computed by bilinear interpolation.

4.5 MPEG-4 Video Standard

MPEG-4 (ISO 14496) goes beyond rectangular frames — it introduces object-based coding. Key functionalities:

• Content-based interactivity: Individual video objects (VOs) can be independently accessed, manipulated,
and streamed.
• Scalable video: Supports spatial, temporal, and quality scalability for different network conditions.
• Natural and synthetic objects: Can combine natural video with synthetic elements (animations, 3D
graphics).
• Error resilience: Built-in tools for robust delivery over error-prone channels (wireless, internet).
• Streaming and download: Supports both live streaming and progressive download.
• Universal access: Works from low-bitrate mobile streams (< 64 kbps) to high-quality broadcast.
 Module 5: Audio Compression
Topics: Digital audio basics, Psychoacoustic model, MPEG audio layers I, II, III (MP3)

5.1 Basics of Digital Audio

• Sound: Longitudinal pressure wave; characterised by frequency (pitch) and amplitude (loudness).
• Sound Pressure Level (SPL): SPL (dB) = 20 log■■(P/P■) where P = measured pressure, P■ = 20 µPa
(threshold of hearing).
• Sampling: Continuous-time signal sampled at frequency f■. Nyquist theorem: f■ ≥ 2 × f■■■ (CD audio: 44.1
kHz).
• Quantisation: Each sample represented as a fixed-width integer. CD audio: 16-bit → 65536 amplitude levels.
• PCM (Pulse Code Modulation): Standard uncompressed digital audio format.

5.2 Basic Audio Compression Techniques

5.2.1 Silence Compression

Detects silent intervals in audio and replaces them with short codes, rather than storing full zero-amplitude
samples. Effective for speech (long pauses).

5.2.2 Companding (Compressing + Expanding)

Non-linear quantisation that exploits the human ear's logarithmic loudness perception. Quiet sounds need finer
quantisation than loud sounds.

• µ-law (µ = 255, used in North America / Japan): F(x) = sgn(x) × ln(1 + µ|x|) / ln(1 + µ)
• A-law (A = 87.7, used in Europe): Piecewise linear approximation to logarithmic curve.
• Both laws reduce required bit depth by compressing the dynamic range of the signal.

Key Point: Companding is used in G.711 telephony codec (8 kHz sample rate, 8-bit companded = 64 kbps) and
provides equivalent quality to 12-13 bit linear PCM.

5.3 Human Auditory System (Psychoacoustic Model)

The psychoacoustic model identifies sounds that the human ear cannot perceive and discards them —
achieving perceptual compression.

5.3.1 Hearing Threshold (Absolute Threshold)

The minimum sound pressure level audible to the human ear in silence. Varies by frequency — most sensitive
near 3-4 kHz, less sensitive at very low and very high frequencies.

5.3.2 Critical Bands

The auditory system acts as a bank of bandpass filters. Each filter covers a 'critical band'. There are
approximately 24 critical bands across the audible frequency range (20 Hz to 20 kHz). Signals within the same
critical band compete to mask each other.

5.3.3 Frequency (Spectral) Masking

A loud tone at one frequency raises the hearing threshold of nearby frequencies — quieter sounds in the vicinity
become inaudible.

• The masking effect is stronger for frequencies just above the masker (upward masking) than below.
• Masking range extends within the same critical band.
• Allows discarding of spectral components below the masking threshold.

5.3.4 Temporal Masking

A loud sound masks quieter sounds that occur shortly before or after it in time:

• Pre-masking (backward masking): Loud sound masks sounds up to ~20 ms before it.
• Post-masking (forward masking): Masking effect lasts up to ~200 ms after the loud sound ends.
• Combined with spectral masking, this defines the masking threshold — any signal below this threshold need
not be encoded.

Key Point: The psychoacoustic model computes the global masking threshold for each audio frame. Quantisation
noise is kept below this threshold, so it is inaudible to the listener.

5.4 MPEG Audio Compression (Layers I, II, III)

MPEG audio coding uses a subband filter bank to decompose audio into frequency bands, then applies
psychoacoustic masking to allocate bits efficiently.

Feature Layer I Layer II Layer III (MP3)

Subband filters 32 32 32 + MDCT

Samples/frame 384 1152 1152

Bit allocation Per subband Per subband Huffman + Scalefactors

Psychoacoustic model Model 1 (simple) Model 1 or 2 Model 2 (complex)

Typical bitrate (stereo) 192 kbps 128 kbps 128 kbps (near CD quality)

Application DCC tape DAB radio, VideoCD Internet audio, iPod

Complexity Low Medium High

5.4.1 Layer I Encoding

• Audio frame = 384 samples (8 ms at 48 kHz). 32 subband signals computed using polyphase filter bank.
• Scale factor computed per subband per frame.
• Bits allocated to subbands based on psychoacoustic model 1.
• Format: allocation (4 bits/subband) + scale factors (6 bits) + samples.

5.4.2 Layer II Encoding

• Audio frame = 1152 samples (24 ms). Same 32-subband filter bank.
• Groups 3 consecutive 384-sample blocks → shares scale factors where possible (more efficient).
• Uses psychoacoustic model 1 or 2. Joint stereo supported.
• Achieves near-CD quality at 128 kbps for stereo.

5.4.3 Layer III (MP3) Encoding — Key Advantages over I and II

• Hybrid filter bank: 32-band polyphase filter + 18-point MDCT (Modified DCT) per subband = 576 frequency
lines total. Provides much finer frequency resolution.
• Non-uniform quantisation: Quantiser step size is chosen per scalefactor band to shape noise below the
masking threshold.
• Huffman entropy coding: Quantised values are entropy-coded using Huffman codes (unlike Layer I/II which
use fixed allocation). This gives significant additional compression.
• Psychoacoustic model 2: More accurate masking threshold computation using combined spectral and
temporal masking.
• Bit reservoir: Unused bits from easy frames can be borrowed by difficult frames — maintains constant bitrate
while adapting complexity.
• Joint stereo / mid-side stereo: Further reduces redundancy for stereo signals.
• Achieves transparent quality at 128 kbps stereo vs Layer II requiring ~192 kbps for similar quality.

Key Point: MP3 (Layer III) dominates because it achieves the best quality at lowest bitrate, using the most
sophisticated psychoacoustic model and Huffman coding unavailable in Layers I and II.
Quick Reference — Most Repeated Exam Topics

Topic Module Frequency

Motion compensation in video compression 4 Very High (3 papers)

JPEG encoding and decoding steps 3 Very High (3 papers)

Performance measures of compression algorithms 1 Very High (3 papers)

Layer I vs Layer II MPEG audio comparison 5 Very High (3 papers)

MPEG-1 video stream layers 4 Very High (3 papers)

MPEG-4 functionalities (6 points) 4 Very High (3 papers)

Features of Layer III vs I and II 5 Very High (3 papers)

RLE flowchart with example 2 High (3 papers)

Huffman coding with entropy + average length 2 High (recurring)

Arithmetic coding (encoding & decoding) 2 High (recurring)

LZ77 encode/decode with given sequence 3 High (recurring)

LZW decoding with initial dictionary 3 High (recurring)

Entropy definition and significance 1 High (recurring)

Psychoacoustic model, masking threshold 5 High (recurring)

Frequency & temporal masking with diagrams 5 High (recurring)

Critical bands and hearing threshold 5 High (recurring)

Probability models (Gaussian & Uniform) 1 Medium

JPEG-LS vs Baseline JPEG 3 Medium

LZ77 vs LZ78 comparison 3 Medium

CRT monitor working 4 Medium

Companding: mu-law and A-law 5 Medium