Präfixcode - Prefix code

Ein Präfixcode ist eine Art von Codesystem , das sich durch den Besitz der "Präfixeigenschaft" auszeichnet. Dies erfordert, dass das System kein ganzes Codewort enthält , das ein Präfix (Anfangssegment) eines anderen Codeworts im System ist. Dies gilt trivial für Code mit fester Länge, daher nur ein Gesichtspunkt für Code mit variabler Länge .

Beispielsweise hat ein Code mit den Codewörtern {9, 55} die Präfixeigenschaft. Ein Code, der aus {9, 5, 59, 55} besteht, tut dies nicht, da "5" ein Präfix von "59" und auch von "55" ist. Ein Präfixcode ist ein eindeutig decodierbarer Code : Bei einer vollständigen und genauen Sequenz kann ein Empfänger jedes Wort identifizieren, ohne dass eine spezielle Markierung zwischen den Wörtern erforderlich ist. Es gibt jedoch eindeutig decodierbare Codes, die keine Präfixcodes sind. Beispielsweise ist die Umkehrung eines Präfixcodes immer noch eindeutig decodierbar (es handelt sich um einen Suffixcode), es handelt sich jedoch nicht unbedingt um einen Präfixcode.

Präfixcodes werden auch als präfixfreie Codes , Präfixbedingungscodes und Sofortcodes bezeichnet . Obwohl die Huffman-Codierung nur einer von vielen Algorithmen zum Ableiten von Präfixcodes ist, werden Präfixcodes auch häufig als "Huffman-Codes" bezeichnet, selbst wenn der Code nicht von einem Huffman-Algorithmus erzeugt wurde. Der Begriff kommafreier Code wird manchmal auch als Synonym für präfixfreie Codes verwendet, aber in den meisten mathematischen Büchern und Artikeln (z. B.) wird ein kommafreier Code verwendet, um einen selbstsynchronisierenden Code , eine Unterklasse von Präfixcodes, zu bezeichnen.

Verwendung von Präfix - Codes kann eine Nachricht als eine Folge von verketteten Codeworten übertragen werden, ohne out-of-band - Marker oder (alternativ) spezieller Marker zwischen Worten umrahmen , die Worte in der Nachricht. Der Empfänger kann die Nachricht eindeutig dekodieren, indem er wiederholt Sequenzen findet und entfernt, die gültige Codewörter bilden. Dies ist im Allgemeinen nicht mit Codes möglich, denen die Präfix-Eigenschaft fehlt, z. B. {0, 1, 10, 11}: Ein Empfänger, der am Anfang eines Codeworts eine "1" liest, würde nicht wissen, ob dies das vollständige Codewort ist. " 1 "oder lediglich das Präfix des Codeworts" 10 "oder" 11 "; Die Zeichenfolge "10" könnte also entweder als einzelnes Codewort oder als Verkettung der Wörter "1" und dann "0" interpretiert werden.

Die Huffman-Codes variabler Länge , Länderanrufcodes , die Länder- und Herausgeberteile von ISBNs , die im UMTS W-CDMA 3G- Funkstandard verwendeten Sekundärsynchronisationscodes und die Befehlssätze (Maschinensprache) der meisten Computermikroarchitekturen sind Präfixcodes.

Präfixcodes sind keine fehlerkorrigierenden Codes . In der Praxis kann eine Nachricht zuerst mit einem Präfixcode komprimiert und dann vor der Übertragung erneut mit Kanalcodierung (einschließlich Fehlerkorrektur) codiert werden .

Für jeden eindeutig decodierbaren Code gibt es einen Präfixcode mit denselben Codewortlängen. Krafts Ungleichung charakterisiert die Sätze von Codewortlängen, die in einem eindeutig decodierbaren Code möglich sind.

Techniken

Wenn jedes Wort im Code dieselbe Länge hat, wird der Code als Code mit fester Länge oder als Blockcode bezeichnet (obwohl der Begriff Blockcode auch für Fehlerkorrekturcodes mit fester Größe bei der Kanalcodierung verwendet wird ). Beispielsweise sind ISO 8859-15- Buchstaben immer 8 Bit lang. UTF-32 / UCS-4- Buchstaben sind immer 32 Bit lang. ATM-Zellen sind immer 424 Bit (53 Byte) lang. Ein Code fester Länge mit k Bits fester Länge kann bis zu Quellensymbolen codieren . ${\ displaystyle 2 ^ {k}}$

Ein Code mit fester Länge ist notwendigerweise ein Präfixcode. Es ist möglich, jeden Code in einen Code mit fester Länge umzuwandeln, indem feste Symbole an die kürzeren Präfixe aufgefüllt werden, um die Länge der längsten Präfixe zu erreichen. Alternativ können solche Füllcodes verwendet werden, um Redundanz einzuführen, die Autokorrektur und / oder Synchronisation ermöglicht. Codierungen mit fester Länge sind jedoch in Situationen ineffizient, in denen einige Wörter viel wahrscheinlicher übertragen werden als andere.

Die abgeschnittene Binärcodierung ist eine einfache Verallgemeinerung von Codes fester Länge, um Fälle zu behandeln, in denen die Anzahl der Symbole n keine Zweierpotenz ist. Source - Symbole werden Codewörter mit der Länge zugewiesen k und k + 1, wobei k so gewählt ist, daß 2 ^k <n ≤ 2 ^{k + 1} .

Die Huffman-Codierung ist eine ausgefeiltere Technik zum Erstellen von Präfixcodes variabler Länge. Der Huffman-Codierungsalgorithmus verwendet als Eingabe die Frequenzen, die die Codewörter haben sollten, und erstellt einen Präfixcode, der den gewichteten Durchschnitt der Codewortlängen minimiert. (Dies hängt eng mit der Minimierung der Entropie zusammen.) Dies ist eine Form der verlustfreien Datenkomprimierung basierend auf der Entropiecodierung .

Einige Codes markieren das Ende eines Codeworts mit einem speziellen "Komma" -Symbol, das sich von normalen Daten unterscheidet. Dies ist etwas analog zu den Leerzeichen zwischen Wörtern in einem Satz; Sie markieren, wo ein Wort endet und ein anderes beginnt. Wenn jedes Codewort mit einem Komma endet und das Komma an keiner anderen Stelle in einem Codewort erscheint, ist der Code automatisch ohne Präfix. Moderne Kommunikationssysteme senden jedoch alles als Folgen von "1" und "0" - das Hinzufügen eines dritten Symbols wäre teuer, und die Verwendung nur am Ende von Wörtern wäre ineffizient. Morsecode ist ein alltägliches Beispiel für einen Code variabler Länge mit einem Komma. Die langen Pausen zwischen den Buchstaben und die noch längeren Pausen zwischen den Wörtern helfen den Menschen zu erkennen, wo ein Buchstabe (oder ein Wort) endet und der nächste beginnt. In ähnlicher Weise verwendet die Fibonacci-Codierung eine "11", um das Ende jedes Codeworts zu markieren.

Selbstsynchronisierende Codes sind Präfixcodes, die eine Rahmensynchronisation ermöglichen .

Verwandte konzepte

Ein Suffix-Code ist eine Reihe von Wörtern, von denen keines ein Suffix eines anderen ist. äquivalent eine Reihe von Wörtern, die die Umkehrung eines Präfixcodes sind. Wie bei einem Präfixcode ist die Darstellung einer Zeichenfolge als Verkettung solcher Wörter eindeutig. Ein Bifix-Code ist eine Reihe von Wörtern, die sowohl ein Präfix- als auch ein Suffix-Code sind. Ein optimaler Präfixcode ist ein Präfixcode mit minimaler durchschnittlicher Länge. Das heißt, es wird ein Alphabet mit n Symbolen mit Wahrscheinlichkeiten für einen Präfixcode C angenommen . Wenn C ' ein anderer Präfixcode ist und die Länge der Codewörter von C' ist , dann . ${\ displaystyle p (A_ {i})}$${\ displaystyle \ lambda '_ {i}}$${\ displaystyle \ sum _ {i = 1} ^ {n} {\ lambda _ {i} p (A_ {i})} \ leq \ sum _ {i = 1} ^ {n} {\ lambda '_ { i} p (A_ {i})} \!}$

Heute verwendete Präfixcodes

Beispiele für Präfixcodes sind:

• Huffman-Codes variabler Länge
• Länderanrufcodes
• Chen-Ho-Codierung
• das Land und Herausgeber Teile von ISBNs
• die im UMTS W-CDMA 3G Wireless Standard verwendeten sekundären Synchronisationscodes
• VCR Plus + Codes
• Unicode-Transformationsformat , insbesondere das UTF-8- System zum Codieren von Unicode- Zeichen, das sowohl ein präfixfreier Code als auch ein selbstsynchronisierender Code ist
• Menge variabler Länge

Techniken

Zu den häufig verwendeten Techniken zum Erstellen von Präfixcodes gehören Huffman-Codes und die früheren Shannon-Fano-Codes sowie universelle Codes wie:

• Elias-Delta-Codierung
• Elias Gammakodierung
• Elias Omega-Codierung
• Fibonacci-Codierung
• Levenshtein-Codierung
• Unäre Codierung
• Golomb Rice Code
• Überbrückendes Schachbrett (einfache Kryptografietechnik, die Präfixcodes erzeugt)
• Vbinary Codierung

Anmerkungen

Verweise

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes und Automaten . Enzyklopädie der Mathematik und ihrer Anwendungen. 129 . Cambridge: Cambridge University Press . ISBN   978-0-521-88831-8 . Zbl   1187.94001 .
• Elias, Peter (1975). "Universelle Codewortsätze und Darstellungen der ganzen Zahlen". IEEE Trans. Inf. Theorie . 21 (2): 194–203. doi : 10.1109 / tit.1975.1055349 . ISSN   0018-9448 . Zbl   0298.94011 .
• DA Huffman, "Eine Methode zur Konstruktion von Codes mit minimaler Redundanz", Proceedings of the IRE, Sept. 1952, S. 1098–1102 (Huffmans Originalartikel)
• Profil: David A. Huffman , Scientific American , Sept. 1991, S. 54–58 (Hintergrundgeschichte)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest und Clifford Stein . Einführung in Algorithmen , 2. Auflage. MIT Press und McGraw-Hill, 2001. ISBN   0-262-03293-7 . Abschnitt 16.3, S. 385–392.
•  Dieser Artikel enthält  gemeinfreies Material aus dem Dokument der General Services Administration : "Federal Standard 1037C" .

Externe Links

• Codes, Bäume und die Präfix-Eigenschaft von Kona Macphee