Run length encoding

In this lesson

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

• THE IDEA: a run of identical values is replaced by a PAIR - how many, and what - which AQA calls a frequency/data pair
• AQA'S OWN WORKED EXAMPLE, which the specification prints: 0000011100000011 becomes 5 0 3 1 6 0 2 1
• Producing the pairs for a given bit pattern, counting each run before writing anything down
• Doing it on a bitmap ROW BY ROW - the same grid CS03-02 read off, now compressed
• READING THE PAIRS BACK to reconstruct the original exactly - nothing has been thrown away
• WHEN IT WORKS: data with long runs of consecutive repeating values - flat backgrounds, simple line drawings, large blocks of one colour
• WHEN IT FAILS: data with few or no repeats, such as a photograph, where the pairs can take MORE space than the original did
• Being specific about HOW, not just that runs exist: count the run, then store the count and the value, then move to the next run

Key words

On the specification