The Art of Doing Science and Engineering: Learning to Learn

by Richard Hamming

The next topic is instantaneously decodable codes. To see what this is, consider the above code with the digits reversed end for end. Now consider receiving 011111…111. The only way you can decode this is to start at the final end and group by threes until you see how many 1s are left to go with the first 0. Only then can you decode the first symbol. Yes, it is uniquely decodable, but not instantaneously! You have to wait until you get to the end of the message before you can start the decoding process! It will turn out (McMillan’s theorem) that instantaneous decodability costs nothing in practice, hence we will stick to instantaneously uniquely decodable codes.