Präfixcode oder präfixfreier Code ist ein Begriff aus der Kodierungstheorie. Als Präfixcode wird ein Code bezeichnet, der die Präfix-Eigenschaft erfüllt: Kein Codewort des Codes ist Präfix eines anderen Codewortes. Anders ausgedrückt darf kein Codewort den Beginn eines anderen Codewortes darstellen. Ein Code zum Beispiel mit den Codewörtern {0, 10, 11} erfüllt die Präfix-Eigenschaft, während hingegen der Code mit den Codewörtern {0, 01, 10} sie nicht erfüllt, da „0“ Präfix von „01“ ist.
Eigenschaften
- Bei einem Präfixcode ist eine Nachricht eindeutig in ihre Codewörter zerlegbar
- Codewörter können unterschiedlich lang sein
- Jeder Präfixcode erfüllt die Kraft-Ungleichung
Beispiele
Die Objekte A, B, C und D werden mit binären Ziffern dargestellt.
Eine unzulässige Codierung wäre die folgende.
Die Codierung von A kollidiert jeweils mit der von B und von C. Da hierbei beispielsweise CB zu 101100 und ADB zu 1011100 kodiert wird, wird klar, dass ohne die Präfixeigenschaft die Dekodierung eines Codewortes erst einige Ziffern später (oder möglicherweise gar nicht) möglich ist.
Huffman-Code
Innerhalb des Huffman-Codes werden Eingabesymbole (beispielsweise die Buchstaben eines Textes) mit unterschiedlich langen binären Ziffernfolgen codiert, deren Länge von der Häufigkeit des zugehörigen Eingabesymbols abhängt. So wird der Speicherverbrauch entsprechend diesen Häufigkeiten optimiert. Der Huffman-Code ist ein Präfix-Code.
Morse-Code
Der Morse-Code ist von Haus aus kein Präfixcode, da beispielsweise A (kurz-lang) ein Präfix von L (kurz-lang-kurz-kurz) ist. Erst durch das Einfügen von Pausen (im Prinzip ein drittes Symbol neben kurz und lang) zwischen Buchstaben wird die Nachricht eindeutig dekodierbar, z. B. kurz-lang-Pause-kurz-kurz = AI, kurz-lang-kurz-Pause-kurz = RE.
Literatur
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. 2. Auflage. M.I.T. Press u. a., Cambridge MA [u. a.] 2001, ISBN 0-262-03293-7.
- Ralph-Hardo Schulz: Codierungstheorie. Eine Einführung. 2. aktualisierte und erweiterte Auflage. Vieweg+Teubner Verlag, Wiesbaden 2003, ISBN 3-528-16419-0.
- Herbert Klimant, Rudi Piotraschke, Dagmar Schönfeld: Informations- und Kodierungstheorie. 3. überarbeitete und erweiterte Auflage. Vieweg+Teubner Verlag, Wiesbaden 2006, ISBN 3-8351-0042-4 (Lehrbuch Informatik).