It is sometimes possible to reduce the size of the output file at the last stage of the encoding process. Consider encoding b followed by EOF, using the arrangements from Exercise 1.
(a) Show that the algorithm gives ‘1000001'.
(b) Let's try to save a few bits at the last stage. Assume that the decoder understands that any encoded string ends with an infinite number of zeros. In our problem, the final interval includes 0, and if there are no underflow bits pending, then two bits could be saved at the final stage. In every case (even if there are underflow bits), sending a single 1 suffices. (Why?)
Suppose the algorithm is modified so that the encoder never outputs until it has a maximum number of equal consecutive bits (and the decoder understands that the encoded string ends with all zeros). Show that these changes give ‘1' as the encoded string for this example. Are there any "problems" with these changes?