Compression: Run Length Encoding (AQA GCSE Computer Science)

What is run-length encoding?

• Run-length encoding (RLE) is a form of data compression that condenses identical elements into a single value with a count
• For a text file, "AAAABBBCCDAA" is compressed to "4A3B2C1D2A"
• The string has four 'A's, followed by three 'B's, two 'C's, one 'D', and two 'A's
• RLE is used in bitmap images to compress sequences of the same colour
• For example, a line in an image with 5 red pixels followed by 3 blue pixels could be represented as "5R3B"

How do you represent data in frequency/data pairs?

• Run-length encoding (RLE) uses frequency/data pairs to compress bitmap image data
• For example, the following bitmap image with a colour depth of 1 bit would have the following binary bit pattern

Bitmap	Bit pattern

• Using RLE we group pixel colours and can create frequency/data pairs as follows
  • 30, 11, 20, 11, 20, 11, 50, 11, 30, 11, 10, 11, 60, 11......

• • 3 x 0 = 3 x white, 1 x 1 = 1 x black
  • Data pairs can carry over on to the next line, e.g. end of first line and start of second line is 5 x 0 (5 x white)

How do you represent a bitmap image from frequency/data pairs?

• To recreate a simple bitmap from frequency/data pairs you need to know what binary code is assigned to what colour and reverse the process above
• If we assume 0 = white and 1 = black and have the following frequency/data pairs and the image size is 5x3 pixels
  • 20, 11, 30, 31, 10, 51
• The bitmap image would be