Year 9 · Spring 2

Representations: going audio-visual · Lesson 4 of 5

Lossy vs lossless compression

UnpluggedTopic 7 Compression

Year 9 · Representations: going audio-visual · Lesson 4 of 5

You will learn to

  • Explain the difference between lossless and lossy compression.
  • Compress a row of pixels with run-length encoding, and decode it again.
  • Build a Huffman code from letter counts, so common letters get shorter codes.
  • Calculate a compression ratio, and compare a zipped text file with a zipped photo.

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Success criteria

You have got it when you can say:

  • I can turn WWWWWWWWBBBW into 8W3B1W, and back again.
  • I can show that my Huffman code uses fewer bits than 8 bits per letter.
  • I can explain why a zipped photo hardly gets smaller.

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Retrieval starter

Questions from before. Write your answers, then show them.

  1. Last lesson

    Turning a wave into numbers is done by…

    A An ADCB A DAC

    A. An ADC

  2. Last unit

    A face-recognition model works badly on faces unlike its training photos. This is…

    A OverflowB Bias from unrepresentative training dataC A syntax error

    B. Bias from unrepresentative training data

  3. Earlier this year

    Double the width and the height. The file becomes…

    A 2 times biggerB 4 times bigger

    B. 4 times bigger

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Key words (1 of 2)

RLE
Run-length encoding: store how many and what, for repeats.
Huffman coding
Lossless compression giving common characters short codes.
Lossless
A reversible way of writing the same data in fewer bits. Every bit comes back exactly. ZIP, PNG, FLAC. Needed for text, code and spreadsheets.

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Key words (2 of 2)

Lossy
Throw away detail that people barely notice. The original cannot be recovered. JPEG, MP3, MP4. Fine for photos, music and video.
Compression ratio
Original size ÷ compressed size. A ratio of 4 means a quarter of the size. Percentage saved = (1 − compressed ÷ original) × 100.

The explanation · step 1 of 3

Lossless vs lossy

LosslessLossy
What happensWrites repetition more cleverlyRemoves detail for ever
Original back?Yes, exactlyNo
Size savingMediumLarge
Used forText, code, PNG, ZIP, FLACJPEG, MP3, MP4, streaming
!Watch out

Never use lossy on text or programs. One wrong bit can change a word, a number or an instruction.

The explanation · step 1 of 3

The maths: How much did compression save?

The explanation · step 2 of 3 · part 1 of 2

Run-length encoding (RLE)

RLE (lossless): instead of writing the same thing many times, write how many and what.

  1. AAAABBBCCD: four A's → 4A.
  2. Three B's → 3B.
  3. Two C's → 2C.
  4. One D → 1D.
  5. Result: 4A3B2C1D. 8 characters instead of 10.

The explanation · step 2 of 3 · part 2 of 2

Run-length encoding (RLE) (continued)

!Watch out

ABCD becomes 1A1B1C1D: twice as long. RLE only helps when things repeat in a row.

The explanation · step 3 of 3 · part 1 of 2

Huffman coding

Huffman coding (lossless) gives common characters short codes and rare ones long codes.

  1. Count each letter in BANANA: A = 3, N = 2, B = 1.
  2. Join the two smallest: B(1) + N(2) = group 3.
  3. Join again: A(3) + group(3) = 6. The tree is done.
  4. Label branches: left = 0, right = 1.
  5. Codes: A = 0, B = 10, N = 11.
  6. BANANA → 10 0 11 0 11 0 = 9 bits. ASCII needs 48.

The explanation · step 3 of 3 · part 2 of 2

Huffman coding (continued)

        (6)
       0/ \1
      A(3) (3)
          0/ \1
         B(1) N(2)
?Why?

How does it know where each code ends? No code is the start of another (0, 10, 11). Reading left to right, the first match is always right.

The explanation · step 3 of 3

The maths: Total bits with Huffman coding

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Try it: Run-length encoder

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Quick quiz · 1 of 3

MP3 saves space mainly by…

  1. A Sorting the samples
  2. B Writing runs of samples as pairs
  3. C Removing sounds people can't hear well

C. Removing sounds people can't hear well

Perceptual coding: very high sounds, and quiet sounds masked by loud ones, are dropped.

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Quick quiz · 2 of 3

RLE of WWWWBB is…

  1. A 6WB
  2. B 4W2B
  3. C W4B2

B. 4W2B

Four W's, then two B's: how many, then what.

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Quick quiz · 3 of 3

Which is lossy?

  1. A ZIP
  2. B JPEG
  3. C PNG

B. JPEG

JPEG throws detail away. ZIP and PNG are lossless.

Year 9 · Representations: going audio-visual · Lesson 4 of 5

Exit ticket

Answer on paper before you go. Then check.

  1. In Huffman coding, the most common letter gets…

    A The shortest codeB The longest codeC An 8-bit code

    A. The shortest code Common letters are used a lot, so short codes save the most.

  2. When building a Huffman tree, at each step you join…

    A The two smallestB The two biggestC The first two letters

    A. The two smallest Join the two smallest totals, put the new total back, repeat.