Sei w ein Wort über dem Alphabet {0, 1}.
Dann gibt es ein w', so das
w = 00w'
oder
w = 01w'
oder
w = 1w'
ist. w' ist eindeutig durch die Anzahl der führenden Nullen von w bestimmt. w kann also eindeutig dekodiert werden, falls w' eindeutig dekodiert werden kann.
Es ist |w'| < |w|. Nach endlich vielen Dekodierungsschritten kommt man entweder zu
w' = 00
oder
w' = 01
oder
w' = 11
oder
w' = 10.
In den ersten drei Fällen ist die Dekodierung eindeutig. Im letzten gibt es keine Dekodierung.