Question

Q7: Compress the bit string below using run length compression. Show the runs as decimal numbers as well as the final compressed form with nibbles. You do not need to calculate the compression percentage. Ignore the spaces in the bit string, they've just been added to make it easier to read. What percent compression is this?

0000 0000 0000 0000 0011 0001 0000 0000 0010 0000 0000 0000 1100 0001

Answer 1

Run length compression or run length encoding is a form of lossless data compression in which a sequence of data are stored as a single data value and count, rather than as the original sequence. It is mainly useful when there are repeative data (bits of information) in the actual file. For example, typical graphics images, animations, graphical games transition etc.

The given sequence is 0000 0000 0000 0000 0011 0001 0000 0000 0010 0000 0000 0000 1100 0001

If we do the run length calculations for above sequence, we get,
18(0s) 2(1s) 3(0s) 1(1) 10(0s) 1(1) 13(0s) 2(1s) 5(0s) 1(1)

So it can be represented as,
0:18, 1:2, 0:3, 1:1, 0:10, 1:1, 0:13, 1:2, 0:5, 1;1

Converting the above information to binary we get,
(0 10010) (1 00010) (0 00001) (0 01010) (1 00001) (0 01101) (1 00010) (0 00101) (1 00001)
It is advisable to use the number of bits for encoding equal to the number of bits required to represent highest frequency (18 here requires 5 bits). First bit represents the actual bit value (either 0 or 1).

Now to represent them in the form of nibbles we get,
0100 1010 0010 0000 0100 1010 1000 0100 1101 1000 1000 0101 1000 01

Now, Number of bits required to represent actual data (without compression), Na = 54 bits
And Number of bits required to represent compressed data, Nc = 52 bits

Therefore, Compression ratio = (Na - Nc) / Na
And Compression percent = (Na - Nc) * 100 / Na

=> Compression percent = (54 - 52) * 100 / 54 = 3.7037 %