AQA 7517 · Paper 2 · 4.5.5

Compression
Algorithms

Lossless vs lossy · Run-length encoding · Huffman coding

WHAT YOU'LL LEARN

Lossless vs lossy · RLE · Huffman coding · Code tables · Compression ratio

AQA SPEC LINK

4.5.5 — Compression: lossless, lossy, RLE, Huffman coding

Why Compress?

Motivation for Compression

A 1-minute uncompressed HD video = ~1.5 GB of data. With H.265 compression: ~100 MB

Smaller files = faster transmission over networks and less storage required

Compression exploits redundancy — patterns and repeated values in data

Two categories: lossless (exact recovery) and lossy (some data discarded)

Lossless vs Lossy

Two Types of Compression

LOSSLESS — Perfect reconstruction

Original data fully recovered after decompression. Used for: text (.zip), programs (.gz), medical images, PNG.
Examples: ZIP, FLAC, PNG, GIF

LOSSY — Some data permanently lost

Data that is discarded cannot be recovered. Human senses often can't detect the loss. Better compression ratios.
Examples: MP3, JPEG, MP4/H.264

Run-Length Encoding

RLE — Lossless Compression

RLE replaces runs of repeated values with a count and the value. Simple and effective for images with large areas of the same colour.

      Original: W W W W W W W W B B B B W W

      RLE:      8W 4B 2W (14 values → 6 values)

Best for: fax documents, simple bitmaps with blocks of colour. Poor for photographic images with constantly varying colours.

Huffman Coding

Huffman Coding — Lossless

Frequently occurring characters get shorter codes; rare characters get longer codes

Based on symbol frequencies — builds a Huffman tree bottom-up

All codes are prefix-free — no code is the prefix of another (enables unambiguous decoding)

Used in ZIP, JPEG (internally), MP3, HTTP/2 header compression

Huffman Example

Building a Huffman Code Table

Text: "AABABCABD" — frequencies: A=5, B=3, C=1, D=1

Step 1: Combine two lowest: C(1)+D(1) = CD(2)
Step 2: Combine: CD(2)+B(3) = BCD(5)
Step 3: Combine: A(5)+BCD(5) = root(10)

Code table:
A → 0 (1 bit)
B → 10 (2 bits)
C → 110 (3 bits)
D → 111 (3 bits)

Encoding & Decoding

Using the Huffman Code Table

Encode "AABABCABD":
A=0, A=0, B=10, A=0, B=10, C=110, A=0, B=10, D=111
Result: 0 0 10 0 10 110 0 10 111 = 14 bits vs 9 × 2 bits (fixed) = 18 bits

Decode "0 10 111":
0 → A, 10 → B, 111 → D → "ABD"
Prefix-free property ensures unique decoding.

Compression Ratio

Measuring Compression

Compression ratio = Original size ÷ Compressed size

Original file: 10 MB → Compressed: 2 MB → Ratio = 5:1

Huffman example above: 18 bits → 14 bits → ratio ≈ 1.29:1

MP3 vs WAV: ~10:1 compression ratio (lossy)

Higher ratio = smaller file, but lossy may sacrifice quality

AQA Exam Style

Practice Question

AQA 7517 — Paper 2 Style

(a) Explain the difference between lossless and lossy compression. [2]
(b) A Huffman code for characters A, B, C, D gives: A=0, B=10, C=110, D=111. Decode the bit string: 10 0 111 0 110 [2]
(c) State why a text document should be compressed using lossless rather than lossy compression. [1]
(d) Give ONE advantage of Huffman coding over using a fixed-length binary code for each character. [1]

[6 marks]

2 marks

(a) Lossless: original data fully restored after decompression [1]. Lossy: some data is permanently discarded, cannot be recovered [1]

2 marks

(b) B, A, D, A, C → "BADAC"

1 mark

(c) Lossy compression permanently removes data — text must be perfectly readable and accurate

1 mark

(d) Uses fewer total bits / more efficient for data where some characters appear more frequently

Summary

Key Points to Remember

Lossless — exact recovery; used for text, programs, medical data (ZIP, PNG, FLAC)

Lossy — discards data human senses can't detect; better ratios (MP3, JPEG, H.264)

RLE — replaces repeated values with count + value; great for simple images

Huffman coding — variable-length codes; frequent chars → shorter codes; prefix-free

Compression ratio = original size ÷ compressed size

🎉 Lesson complete — move to the quiz!