ScholaFly

CS03-07 Computer Science Watch

Run length encoding

Watch on YouTube

In this lesson

Run length encoding for GCSE Computer Science. AQA 8525 GCSE. Images and sound 7 of 7. Full Images and sound playlist: {{playlist:CS03-07}} More at https://scholafly.com

By the end: Explain how run length encoding compresses data by replacing runs of repeated values with frequency and data pairs, produce the pairs for a given bit pattern or bitmap row, read the pairs back to reconstruct the original, and say what kind of data RLE suits and what kind it makes worse.

What it covers

  1. 0:00 Intro: run length encoding
  2. 0:49 Run length encoding: runs and pairs
  3. 2:55 A bitmap row, and back
  4. 4:25 When it suits the data
  5. 6:56 When it backfires

Key words

About this video

Run length encoding | GCSE Computer Science

Run length encoding for GCSE Computer Science.
AQA 8525 GCSE. Images and sound 7 of 7.
Full Images and sound playlist: {{playlist:CS03-07}}
More at https://scholafly.com

Watch first: CS03-02 From binary to bitmap and back, CS03-05 Why we compress data
Video code: CS03-07 (search "ScholaFly CS03-07")

Videos in this chapter:
CS03-00 Images, sound and compression - Intro: {{link:CS03-00}}
CS03-01 How an image is stored: {{link:CS03-01}}
CS03-02 From binary to bitmap and back: {{link:CS03-02}}
CS03-03 How sound is stored: {{link:CS03-03}}
CS03-04 Working out image and sound file sizes: {{link:CS03-04}}
CS03-05 Why we compress data: {{link:CS03-05}}
CS03-06 Huffman coding: {{link:CS03-06}}
CS03-07 Run length encoding: {{link:CS03-07}}

#GCSEComputerScience #ImagesAndSound #RunLengthEncoding

For teachers
This GCSE Computer Science lesson teaches run length encoding. By the end, students should be able to explain how run length encoding compresses data by replacing runs of repeated values with frequency and data pairs, produce the pairs for a given bit pattern or bitmap row, read the pairs back to reconstruct the original, and say what kind of data RLE suits and what kind it makes worse. It works through four worked examples and the mistakes examiners report, and suits Foundation and Higher tier students.

Exam board specification references:
AQA GCSE Computer Science (8525)
- 3.3.8 Data compression

Read the transcript

Can compressing a file ever make it bigger? It sounds impossible, because squashing should only ever shrink things. Run length encoding, which stores repeats as a count and a value, can do it: a photograph can come out bigger than the original. Whether a file shrinks or grows comes down to one word, and that word is runs. It starts with a row of ones and zeros, counted one run at a time. Keep that photograph in mind; the word runs will explain it before the recap.

A run is a stretch of the same value repeated, one after another. Run length encoding replaces each run with a pair of numbers: how many, then what. This method is on one exam board's course only, and the other courses rule it out or never set it, so for them it is background. That course calls each pair a frequency and data pair, with the frequency first. Its own specification gives an example. Zero zero zero zero zero, one one one, zero zero zero zero zero zero, one one becomes five zero, three one, six zero, two one. The first number of each pair is a count. Five zero means five zeros, never a zero followed by a five. The method has three steps. Cut the string wherever the value changes, count each run, then write each run as its count followed by its value. Here is a string to try: zero zero zero zero, one one one one, zero zero zero zero zero, one one. The first cut comes where zero turns to one. The first run is four zeros, so four zero, and the second is four ones, so four one. Following the same steps, what are the last two pairs? Five zero, and then two one, for the last two runs. So the full string becomes four zero, four one, five zero, two one: eight numbers in place of fifteen.

A bitmap grid like the ones in From binary to bitmap and back can be compressed one row at a time, in the same way. Take a row that reads one one one, zero zero zero zero, one one. Cut it where it changes: three ones, then four zeros, then two ones. So the pairs are three one, four zero, two one. Six numbers stand in for nine. Reading pairs back runs the same steps in reverse. For each pair, write the value as many times as the count says. Here are the pairs for another row: two zero, five one, one zero. Rebuild the row from those pairs, before I show you. Zero zero, one one one one one, zero. Eight values, the original row back as it was, because nothing was thrown away. That is why run length encoding loses nothing. If you met the word lossless in Why we compress data, this is a lossless method.

Run length encoding only shrinks data that has long runs of the same value. Flat backgrounds, simple line drawings and big blocks of one colour all have long runs. Two answers to why it suits a company logo. The first says it suits the logo because the compressed file comes out smaller. The second says it suits the logo because the logo has long runs of the same colour. Which of those two answers explains why the logo suits run length encoding? The answer about runs. Suitability is a fact about the data going in, and runs are that fact; a smaller result is only what follows from it. One examiner's report gives the target in its own words. The majority of explanations concerning the suitability of R L E for compressing the data given in the question focused on the size of the resulting data. Very few talked about the need for a high frequency of consecutive repeating characters in the original data. The fix: every suitability answer contains the word runs, and says the data has long runs of the same value. An older report, on the previous version of this course from November twenty twenty, goes further. There appeared to be much confusion of compression and encryption in responses to this question. A lot of students failed to convey that there need to be runs of repeated data to allow effective compression using R L E. It continues. Many students described aspects of R L E without being specific about how it works. For example, they wrote about runs of data but did not then describe how those runs are counted or are stored as count and data value pairs. So a full description has both halves: the runs are counted, and each is stored as a count and data value pair. And compression is not encryption: one changes how much room the data takes, the other changes who can read it.

Now the failure case. Here is a row with no repeats at all: zero one zero one zero one. Write its pairs and count how many numbers you end up with, before I show you. One zero, one one, one zero, one one, one zero, one one: twelve numbers where the row had six. Every run is one long, so every value needs a count stuck in front of it. The pairs end up twice the size of the data they replaced. A photograph is like this. Neighbouring pixels are rarely the same colour, so the runs are short, and the pairs can take more space than the original. That is the photograph from the start. Run length encoding is a bet on the data. With long runs it wins, and with few runs it loses.

Four questions to finish, with the photograph from the start saved for last. In a frequency and data pair, which number comes first? The frequency, which is the count, comes first. How many, then what. Try a row you have not seen: six ones, then two zeros. What are its pairs? Six one, two zero. Four numbers in place of eight values. Now the other way. From the pairs three zero, one one, two zero, rebuild the row. Zero zero zero, one, zero zero. Six values, back as they were. One more, back to the photograph. Why can run length encoding make it bigger? A photograph has few runs, because neighbouring pixels rarely match. Each short run still needs a count, so the pairs can outgrow the original.

This one's yours if you could compress a row, rebuild it from its pairs, and say when the method suits the data, and the thumb under the video can say so. If any of it is still hazy, save it, and come back to it later in the week.

That completes our chapter on Images, sound and compression. Next chapter: Inside the computer.

For more, visit scholafly.com, or watch the next video.

Related terms

For: AQA GCSE 8525

On the specification

BoardSpecStatement
AQA GCSE 85253.3.8Data compression
For teachers

This GCSE Computer Science lesson teaches run length encoding. By the end, students should be able to explain how run length encoding compresses data by replacing runs of repeated values with frequency and data pairs, produce the pairs for a given bit pattern or bitmap row, read the pairs back to reconstruct the original, and say what kind of data RLE suits and what kind it makes worse. It works through four worked examples and the mistakes examiners report, and suits Foundation and Higher tier students.