Compression - Run Length Encoding (AQA GCSE Computer Science)

Run Length Encoding

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"

Represent Data in Frequency / Data Pairs

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