Wikipedia · einfach zusammengefasst · Stand
Präfixcode
Als Präfixcode wird ein Code bezeichnet, der die Fano-Bedingung erfüllt: Kein Codewort des Codes ist Präfix eines anderen Codewortes. Anders ausgedrückt darf …
Inhalt4 Abschnitte
Grundprinzip und Definition
Ein Präfixcode, auch präfixfreier Code genannt, ist ein Begriff aus der Kodierungstheorie. Er erfüllt die sogenannte Fano-Bedingung: Kein Codewort darf Präfix eines anderen Codeworts sein. Ein Präfix ist dabei ein Codewort, das den Beginn eines anderen Codeworts bildet.
Diese Bedingung ermöglicht eine eindeutige Zerlegung einer Nachricht in ihre einzelnen Codewörter. Beim Lesen kann jedes Codewort erkannt werden, sobald es vollständig vorliegt. Die Codewörter müssen nicht gleich lang sein. Außerdem erfüllt jeder Präfixcode die Kraft-Ungleichung.
Binäre Beispiele und Folgen fehlender Präfixfreiheit
Die Objekte A, B, C und D können beispielsweise so mit binären Ziffern dargestellt werden:
A → 0, B → 100, C → 101, D → 11
Diese Codierung ist ein Präfixcode, weil keines der Codewörter den Anfang eines anderen Codeworts bildet.
Eine unzulässige Codierung lautet:
A → 10, B → 100, C → 101, D → 11
Hier kollidiert die Codierung von A jeweils mit der von B und C, weil „10“ ein Präfix von „100“ und „101“ ist. Dadurch kann eine Folge von Ziffern nicht immer sofort eindeutig dekodiert werden. Beispielsweise werden CB und ADB zu 101100 beziehungsweise 1011100 codiert. Ohne Präfixeigenschaft ist möglicherweise erst einige Ziffern später oder sogar gar nicht erkennbar, wie die Nachricht in Codewörter zerlegt werden muss.
Anwendungen und wichtige Codearten
Bei Telefonnummern muss jeder Anschluss eindeutig identifizierbar sein. Während des Wählens darf daher nicht zwischenzeitlich bei einem anderen Teilnehmer geklingelt werden. In Deutschland beginnt außer dem Notruf keine andere Telefonnummer mit 112. Ebenso beginnt in keinem Ortsnetz eine Nummer mit 0, damit keine Kollision mit Ortsvorwahlen oder Sondernummern wie 0800 entsteht. Ähnliche Überlegungen gelten für internationale Vorwahlen.
Der Huffman-Code ordnet Eingabesymbolen, beispielsweise den Buchstaben eines Textes, unterschiedlich lange binäre Ziffernfolgen zu. Die Länge hängt von der Häufigkeit des jeweiligen Symbols ab. Dadurch wird der Speicherverbrauch an diese Häufigkeiten angepasst und optimiert. Der Huffman-Code ist ein Präfixcode.
Der Fibonacci-Code ist ein universeller Präfixcode für die natürlichen Zahlen.
Morse-Code als Gegenbeispiel
Der Morse-Code ist von sich aus kein Präfixcode. Beispielsweise ist A, dargestellt als kurz-lang, ein Präfix von L, dargestellt als kurz-lang-kurz-kurz. Erst durch Pausen zwischen den Buchstaben wird die Nachricht eindeutig dekodierbar. Die Pause wirkt dabei im Prinzip als drittes Symbol neben kurz und lang.
Beispiele sind kurz-lang-Pause-kurz-kurz = AI sowie kurz-lang-kurz-Pause-kurz = RE.