= Solution
A binary code assigns a finite bit string to each source symbol. Use nonempty codewords for an unframed variable-length stream. The code is <uniquely decodable code>[uniquely decodable] if no two distinct finite sequences of source symbols produce the same concatenated bit string. It is a <prefix code>[prefix-free code] if no <codeword> is an initial segment of a different <codeword>.
To prove unique decoding of a <prefix code>, suppose two concatenations agree. Their first codewords both begin the same bit string, so the shorter is a prefix of the longer. The prefix condition forces the first codewords to be equal. Cancel them and repeat. Since the codewords are nonempty, this process ends with both symbol sequences exhausted at the same time; otherwise a nonempty remainder could not equal the empty string. Hence the source sequences agree.
The code $\{0,01\}$ is not a <prefix code>, since $0$ is a prefix of $01$. Nevertheless it is <uniquely decodable code>[uniquely decodable]: decode from the right. A final $1$ forces the last <codeword> to be $01$, whereas a final $0$ forces it to be $0$. Removing that final word recursively gives a unique parsing. Thus \b[the converse fails].
Back to article page
