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

Text files

• For a text file containing the string "AAAABBBCCDAA", the plain RLE encoding would be "4A3B2C1D2A"

• The string has:

  • four 'A's (4A)

  • three 'B's (3B)

  • two 'C's (2C)

  • one 'D' (1D)

  • two 'A's (2A)

• To represent this in binary, the count is stored in a fixed size binary format (e.g. 7 or 8 bits)

• The character is stored using its ASCII value (7 bits)

• The binary RLE representation of 4A would be 0000100 1000001

  • 0000100 - binary for the count (4)

  • 1000001 - binary for 'A' (65)

Images

• In bitmap images, RLE is used 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"

• The image has:

  • 5 red pixels (5R)

  • 3 blue pixels (3B)

• To represent this in binary, the pixel count is stored in a fixed size binary format (e.g. 1, 4, 8 or 16 bits)

• The colour is stored based on the required colour depth of the image

• For this example we will assume a colour depth of 2 bits

  • 00 - Black

  • 01 - Red

  • 10 - Green

  • 11 - Blue

• The binary representation of 5R3B would be 1001 01 0011 11

  • 1001 - pixel count (5), 01 - red

  • 0011 - pixel count (3), 11 - blue

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