How does a non-prefix-free code cause ambiguity when decoding 00 or 11?

Conditions

• Occurs when at least one codeword is a prefix of another codeword.
• Illustrated here for concatenated received strings under Code 3.

Reasoning, step by step

1. Consider the received bit string 00 under Code 3.
2. Identify that 0 is a valid codeword for $x_1$ and 00 is a valid codeword for $x_3$.
3. Segment 00 as 0 followed by 0, resulting in $x_1x_1$.
4. Segment 00 as the single codeword 00, resulting in $x_3$.
5. Conclude that the receiver cannot uniquely determine the original symbol sequence.

Example

The lower table in the video shows 'x1x1 OR x3 --- confusion while decoding' for the received string 00, and 'x2x2 OR x4 --- confusion while decoding' for the received string 11.

Common misconceptions

• Assuming that the receiver can always choose the longest matching codeword greedily without error.
• Thinking that distinctness of codewords prevents decoding ambiguity.

Watch the explanation

Explore next

• What is the definition of a uniquely decodable code?
• Why does the video say prefix-freeness is sufficient but not necessary for unique decodability?