IGCSE Computer Science 0478: Encoding a Pixel Row with RLE

A fax machine scans a single row of a black-and-white document as 60 individual pixels, each of which is either black or white. Before any compression, each pixel is stored using 1 bit (0 for white, 1 for black).

The scanned row consists of four runs of pixels, in this order:

15 white pixels
20 black pixels
10 white pixels
15 black pixels

The fax machine then applies run-length encoding (RLE) to compress the row. Each run is stored as one code made up of: 1 bit for the colour, followed by 8 bits for the count of pixels in that run (an 8-bit count can record run lengths from 0 up to 255).

(a) Calculate the uncompressed file size of the pixel row, in bits. [1]

(b) Calculate the file size of the RLE-encoded row, in bits, showing your working for one run code. [3]

(d) State how many pixels are described in total by the four RLE run codes, and explain how this confirms that no image data has been lost by the compression. [2]

Part (a): Uncompressed file size

Before compression, every one of the 60 pixels in the row is stored individually using 1 bit each:

uncompressed size = number of pixels x bits per pixel = 60 x 1 = 60 bits

So the uncompressed file size is 60 bits.

Part (b): File size after RLE encoding

Instead of storing every pixel separately, RLE stores one code per run. Each code uses:

1 bit (colour) + 8 bits (count) = 9 bits per run

For example, the first run (15 white pixels) is stored as a single 9-bit code: 1 bit recording the colour “white”, followed by the 8-bit binary count for 15, one code instead of 15 separate pixel bits.

There are 4 runs in total, so:

compressed size = number of runs x bits per run code = 4 x 9 = 36 bits

So the RLE-encoded row is 36 bits.

Part (c): Percentage reduction in file size

The reduction in size is the uncompressed size minus the compressed size:

60 - 36 = 24 bits

This reduction is then expressed as a percentage of the original (uncompressed) file size:

(24 / 60) x 100 = 40

So RLE achieves a 40% reduction in file size for this row.

Part (d): Confirming no data is lost

Adding up the pixel counts recorded by the four RLE run codes:

15 + 20 + 10 + 15 = 60 pixels

This total of 60 pixels exactly matches the number of pixels in the original row. Because each code records both the correct colour and the correct count for its run, the original sequence of 60 individual pixels can be rebuilt exactly, one run at a time, from the four codes. This confirms that RLE has compressed the row without permanently discarding any of the original image data. It is a lossless compression method.

Final answers

(a) Uncompressed file size = 60 bits
(b) RLE-encoded file size = 36 bits
(c) Percentage reduction = 40%
(d) The four run codes describe 60 pixels in total, matching the original row exactly, confirming no data was lost.