Unique decoding, binary

Question

Suppose I have the following coding scheme,

• $a \rightarrow 0$
• $b \rightarrow 110$
• $c \rightarrow 10$
• $d \rightarrow 111$

Assuming I combine these into an arbitrary long binary sequence (for instance aaabcdccb). How do I know that I can decode the message in a unique way, thus recovering the message? Is there a way to prove this?

Answer 1

Here is an FSM that will recognize the tokens:

Answer 2

Yes, what you do when you decode it is to start at the beginning of the sequence and look at the first three bits and decide what letter it is:

$$\begin{matrix} 0?? & a & \text{and skip one bit}\\ 10? & b & \text{and skip two bits} \\ 110 & c & \text{and skip three bits}\\ 111 & d & \text{and skip three bits}\\ \end{matrix}$$

As you see the possibilities in the first column does not overlap, and it covers all posibilities (that is you always know what to do).

(Also one can realize that if you start in the middle of the sequence you will eventually get in sync an decode the correct letters.)

(Note however that in some applications the input is in fact an infinite sequence. In this case the encoding would need a code showing when you've reached the end of the message)