Data compression: eg 0000011100000011

The idea

This row gives a worked bit pattern, 0000011100000011, used to illustrate run-length encoding within data compression. Learners should read the pattern as a sequence of runs: five 0s, then three 1s, then six 0s, then two 1s. Run-length encoding stores each run as a count paired with the bit value, so this pattern becomes (5,0)(3,1)(6,0)(2,1). The technique suits data with long repeated runs and saves space when runs are long, but can enlarge data when values alternate frequently. Learners should be able to encode and decode such a pattern and judge when run-length encoding is worthwhile.

What earns the marks

• Reading the pattern as runs: five 0s, three 1s, six 0s, two 1s, in that order.
• Encoding each run as a count paired with its bit value, giving (5,0)(3,1)(6,0)(2,1).
• Decoding a run-length encoded list back to the original bit pattern by repeating each value its stated count of times.
• Judging that run-length encoding saves space when runs are long but can increase size when bits alternate frequently.

Common mistakes and how to put them right

• Miscounting a run, for example reading the opening zeros as four rather than five.

  Put it right by counting each bit carefully from left to right.

• Recording only the counts and omitting the bit values.

  Put it right by pairing every count with the value it repeats.

• Assuming run-length encoding always reduces size.

  Put it right by noting it can enlarge data when runs are short or values alternate.

Exam tips

• Count runs from left to right and write each count next to its bit value before combining them.
• Check your encoding by decoding it back and comparing with the original pattern.
• State the condition under which run-length encoding is beneficial: long repeated runs.