Students paint black and white pixels and watch each row's run-length code, to explain why data is compressed, apply run-length encoding, calculate the saving and see when it fails (AC9TDI10K03 nodes 1 and 2).
Load these into Waypoints Prepare: choose Load URL and paste the copied address, or download the file and import it. In Prepare, the worksheet's Teacher edition shows the answers; the student copy hides them.
SlidesDownload Present from the browser, or export to PowerPoint or PDF.
WorksheetDownload Print the student copy; the Teacher edition has the answers.
Students will be able to
I can explain why data is compressed.
I can encode and decode a row with run-length encoding.
I can say when run-length encoding saves space and when it doesn't.
Timing
Predict and Try 6 min · Worked example 12 min · Vary 12 min · Practise and Make 15 min
Before class
CS Unplugged's Image representation activity (the fax-machine pixel codes) is the same model on paper; doing one page of it first works well.
The one idea: store runs instead of every value; decompressing gives back the data exactly (lossless). It saves when the data has long runs, and can make data bigger when it has none.
Simplification: real formats use a count and a value, as the lossy lesson does; the black-and-white form here (taking turns from white) is CS Unplugged's.
Running the lesson
Predict: students who chose 4 lose the position; ask them to rebuild the row from 4.
Try: ask what code a row of one black pixel at the end would get (7, 1).
Worked example: pause before row 2 and ask how to say "no white".
Vary: the checkerboard task usually surprises; ask what kind of real picture is like it.
Make: swap codes between pairs: one draws a picture, the other decodes it.
The hard part (on purpose)
Rows that start black. Insist the first number always counts white, even when it is 0.
When students get stuck
What you will see
A question to ask
The fix
A student writes 2, 6 for a row that starts black (Sam's mistake).
What colour does the first number count?
White, always: start with 0.
A student thinks every picture shrinks.
What is the code for a checkerboard row?
Eight 1s: no saving.
Answers to the checks
a shorter row: A row of 8 pixels is 3 white, then 4 black, then 1 white. Stored pixel by pixel, that is 8 numbers. Which is the shortest way to store it so you get **exactly** the same row back? 3, 4, 1. Taking turns from white, those three numbers rebuild the row exactly. Storing only 4 loses where the black pixels are.
Try: paint a run: Paint pixels 4 to 7 black to match the picture. What code does the board write for the row?
3 white, 4 black, 1 white: 3, 4, 1. Three numbers instead of eight.
Four rows: A row's code is **0, 2, 6**. What is the row? 2 black, then 6 white 0 white, then 2 black, then 6 white.
Find the mistake: Sam encodes a row that starts with black. Click the line where it first goes wrong. line 3 Line 3: the first number always counts white. The row starts black, so the code starts with 0: 0, 2, 6. Read as 2, 6 it would come back as 2 white, 6 black.
Why compress?: Why compress data at all? Smaller data takes less storage and is quicker and cheaper to send Fewer numbers means less storage, faster downloads and streaming, and less energy and cost to move data around.
A whole run: Paint the whole row black. What is its code?
0, 8: no white pixels first, then 8 black. Two numbers for eight pixels.
No runs: Paint every second pixel black: white, black, white, black… How many numbers is the code?
Every pixel is its own run, so the code is eight 1s: no saving at all.
Fewest numbers: Change this picture so its codes use as few numbers as possible.
Every row one colour: an all-white row is 8 (one number) and an all-black row is 0, 8 (two), so all white is fewest: 4 numbers for 32 pixels.
Compression ratio: An 8 × 8 icon (64 pixels) compresses to 16 numbers. What percentage of the original size is that? 25 16 ÷ 64 = 0.25, so 25% of the size (a quarter).
When RLE works: Which picture would run-length encoding shrink the most? A diagram with large areas of one colour RLE saves when the data has long runs of the same value.
Encode: What is the code for the row: white, white, black, black, black, black, black, black? 2, 6 2 white, then 6 black.
Decode the length: A row is decoded from **1, 3, 2, 2**. How many pixels long is it? 8 1 + 3 + 2 + 2 = 8 pixels.
Text: Run-length encoding on text: **aaaabbbcc** can be stored as… 4a3b2c Each run is a count and the character: 4a 3b 2c, six characters instead of nine.
Bigger?: Can run-length encoding make data **bigger**? Yes, when there are few runs, as in abcd → 1a1b1c1d Each run costs a count and a value. Data that changes every step doubles in size.
draw from the codes: The codes on the right describe a 6 × 6 picture. Paint it.
A plus sign. 16 numbers rebuild 36 pixels exactly: lossless.
Solutions
One possible solution for each task. Other correct programs are fine.
Vary: one change at a time › A whole run
Open task: any program that does what the step asks.
Vary: one change at a time › No runs
Open task: any program that does what the step asks.
Vary: one change at a time › Fewest numbers
Open task: any program that does what the step asks.
Vary: one change at a time › Compression ratio
Open task: any program that does what the step asks.
Vary: one change at a time › When RLE works
Open task: any program that does what the step asks.
draw from the codes
Open task: any program that does what the step asks.
Stretch and support
Stretch: Design an 8 × 8 picture that compresses to 8 numbers or fewer. Design one that makes the code longer than 64.
Support: Have students say the colours aloud while counting: white 3, black 4, white 1.
Exit ticket
Encode the row black, black, black, white, white, white, white, white. Why is run-length encoding called lossless?
0, 3, 5. Decompressing gives back exactly the same data.
What each step is for
a shorter row: Committing to how to store a row in fewer numbers tests the new move before it is shown: count runs, in turn, instead of storing every pixel.
Try: paint a run: Painting pixels 4 to 7 black and reading the code settles the prediction: the row becomes 3, 4, 1.
Worked example: encode a picture: Encoding four rows, including one that starts black and one with no runs, models the new move and shows when it fails. Sam leaves out the leading 0, the misconception planted after the method; the why question covers what compression is for.
Vary: one change at a time: Each task changes one thing in the data: a whole run, then the worst case (no runs), then the best case (every row one run), then the ratio and when to use RLE.
codes: Encoding and decoding rows, a code longer than the data, run-length encoding on text, and choosing what compresses well.
draw from the codes: Drawing the picture from its codes reverses the process: students decompress by hand and check that the codes rebuild it exactly.
Where it leads
Next: Lossy or lossless.
Builds on: Data representation (pixels and bytes). Where it leads: file formats (PNG, GIF and ZIP use lossless methods; JPEG and MP3 lossy).