A prefix-free code is a set of codewords with the property that no codeword is a prefix of any other. This guarantees that as you read a bit‐stream from left to right, you can unambiguously determine where one codeword ends and the next begins.

 

Formal Definition

A code $C$ over an alphabet (e.g. $\lbrace 0,1 \rbrace$) is prefix-free if

$$ \forall x, y \in C, x \neq y \implies x \text{ is not a prefix of } y. $$

 

Examples

  • Valid prefix-free set: $\lbrace 0, 10, 11 \rbrace$
  • Valid prefix-free set: $\lbrace 00, 01, 10, 11 \rbrace$
  • Invalid set: $\lbrace 0, 01, 10 \rbrace$ , because $“0”$ is a prefix of $“01”$.

 

Why It Matters

  • Instantaneous Decoding: As soon as you hit a codeword you recognize, you know it’s complete — no need to read more bits.
  • Simplicity: Tree‐based (e.g., Huffman) encoders/decoders map directly to binary trees.

 

Prefix-Free Code Types

Here we introduce you to two types of prefix-free codes:

  • Fixed-Length Code - assign every symbol of a source alphabet the same binary codeword length.
  • Variable-Length Code - assign variable‐length binary codes to symbols based on their frequencies.

Last updated 09 May 2025, 23:43 +0500 . history