Präfix-Codes

Eine Menge von Wörtern {w₁, w₂,...} heißt präfix-frei, wenn es keine verschiedenen i, j gibt, so daß w_i ein Präfix (Anfangsstück) von w_j ist.

Satz: Jede präfixfreie Menge ist eine Code.

Beispiele:

• A$\to$00, B$\to$01, C$\to$10, D$\to$11 ist ein Präfix-Code.
• A$\to$0, B$\to$10, C$\to$110, D$\to$111 ist ein Präfix-Code.
• A$\to$00, B$\to$0011, C$\to$10, D$\to$01 ist kein Präfix-Code, aber ein Code!