Explore BrainMass

Run length encoding of a bit sequence

(a) Encode the following bit sequence using run-length encoding with 4-bit codes

eighteen zeroes, 11, fifty-six zeroes, 1, fifteen zeroes, 11.

(b) Encode the same sequence using run-length encoding with 5-bit codes

(c) Compare the two codes. Comment on two choices.

Solution Preview

In run length encoding (RLE) we normally represent each subsequence of identical symbols by a pair (L,S), where L indicates the length of the subsequence and S indicates the recurring symbol in the sequence. So the encoded sequence will look like -

(L1,S1), (L2,S2), ......, (Ln,Sn)

where two consecutive symbols Si and Si+1 will not be same.

In case of binary sequence, only symbols are 0 and 1. Hence Si will alternate between 0 and 1, which simplifies our RLE sequence to

L1, L2, ...., Ln

However we can't use this simplified representation either in case (a) or ...

Solution Summary

Solution also discusses two representations for Run Length Encoded sequences and illustrates a scheme to generate the encoded bit sequence with the help of an example.