Variable-Length Binary Codes

Definition link

Let $\Sigma$ be a finite source alphabet. A variable‐length binary code is an injective mapping

$$ f\colon \Sigma \longrightarrow \lbrace 0,1 \rbrace ^ * $$

such that different source symbols $\sigma \in \Sigma$ may be assigned codewords of different lengths. Equivalently, one often identifies the code with its set of codewords

$$ C = \lbrace f(\sigma)\mid \sigma \in \Sigma \rbrace \subseteq \lbrace 0,1 \rbrace^*, $$

where the lengths $l(c) \text{ for } c \in C$ need not all be equal.

• To ensure unique decodability, $C$ must satisfy that any concatenation of codewords can be parsed in exactly one way.
• A common sufficient condition is prefix‐freeness:

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

In that case, decoding is instantaneous: read bits until you reach a leaf in the corresponding binary tree.