(Run-length coding) Suppose X1, X2 . is a sequence of binary random symbols with pXa = 0
9 and pXb = 0.1. We encode this source by a variableto-variable-length encoding technique known as run-length coding. The source output is first mapped into intermediate digits by counting the number of occurrences of a between each
b. Thus an intermediate output occurs on each occurence of the symbol b. Since we do not want the intermediate digits to get too large, however, the intermediate digit 8 is used on the eighth consecutive a, and the counting restarts at this point. Thus, outputs appear on each b and on each eighth
a. For example, the first two lines below illustrate a string of source outputs and the corresponding intermediate outputs: ba
The final stage of encoding assigns the codeword 1 to the intermediate integer 8, and assigns a 4 bit codeword consisting of 0 followed by the 3 bit binary representation for each integer 0 to 7. This is illustrated in the third line above.
(a) Show why the overall code is uniquely decodable.
(b) Find the expected total number of output bits corresponding to each occurrence of the letter
b. This total number includes the 4 bit encoding of the letter b and the 1 bit encodings for each consecutive string of eight occurrences of a preceding that letter b.
(c) By considering a string of 1020 binary symbols into the encoder, show that the number of occurrences of b per input symbol is, with very high probability, very close to 0.1. (d) Combine parts (b) and (c) to find L, the expected number of output bits per input symbol.