What is the definition of a prefix-free code?

Conditions

• Defined relative to concatenation of binary strings.
• For every pair of distinct codewords $c_a$, $c_b$, neither $c_a$ is a prefix of $c_b$ nor $c_b$ is a prefix of $c_a$.

Reasoning, step by step

1. List all codewords assigned to the source symbols under the code.
2. For each pair of distinct codewords, check if one is a prefix of the other.
3. Verify that no such prefix relation exists.
4. Conclude that the code is prefix-free.

Example

In the displayed table, Codes 1, 2, and 4 are prefix-free. Code 3 is not prefix-free because the codeword 0 for $x_1$ is a prefix of 00 for $x_3$, and the codeword 1 for $x_2$ is a prefix of 11 for $x_4$.

Common misconceptions

• Assuming that prefix-free codes must be fixed-length.
• Confusing prefix-free codes with distinct codes; a code can be distinct but not prefix-free.

Watch the explanation

Explore next

• Why does Code 3 fail the prefix-free condition?
• What is the relationship between instantaneous codes and prefix-free codes in this lesson?