Ein Präfix-Code ist ein Typ des Codesystems (normalerweise ein Code der variablen Länge) bemerkenswert durch seinen Besitz des "Präfix-Eigentums"; der feststellt, dass es kein gültiges Codewort im System gibt, das ein Präfix (Anfang) jedes anderen gültigen Codewortes im Satz ist. Zum Beispiel hat ein Code mit Codewörtern {9, 59, 55} das Präfix-Eigentum; ein Code, der aus {9, 5, 59, 55} besteht, tut nicht, weil "5" ein Präfix sowohl "59" als auch "55" ist. Mit einem Präfix-Code kann ein Empfänger jedes Wort identifizieren, ohne einen speziellen Anschreiber zwischen Wörtern zu verlangen.

Präfix-Codes sind auch bekannt als Codes ohne Präfixe, Präfix-Bedingungscodes und sofortige Codes. Obwohl Huffman, der codiert, gerade einer von vielen Algorithmen ist, um Präfix-Codes abzuleiten, werden Präfix-Codes auch weit "Codes von Huffman" genannt, selbst wenn der Code durch einen Algorithmus von Huffman nicht erzeugt wurde. Code ohne Kommas des Begriffes wird manchmal auch als ein Synonym für Codes ohne Präfixe angewandt, aber in den meisten mathematischen Büchern und Artikeln (zum Beispiel) wird er verwendet, um zu bedeuten, Codes, eine Unterklasse von Präfix-Codes zu selbstsynchronisieren.

Mit Präfix-Codes kann eine Nachricht als eine Folge von verketteten Codewörtern ohne irgendwelche Anschreiber aus dem Band übersandt werden, um die Wörter in der Nachricht einzurahmen. Der Empfänger kann die Nachricht eindeutig decodieren, indem er wiederholt findet und Präfixe entfernt, die gültige Codewörter bilden. Das ist mit Codes nicht möglich, die am Präfix-Eigentum, zum Beispiel {0, 1, 10, 11} Mangel haben: Ein Empfänger, "1" am Anfang eines Codewortes lesend, würde nicht wissen, ob das das ganze Codewort "1", oder bloß das Präfix des Codewortes "10" oder "11" war.

Die variable Länge Codes von Huffman, Landbenennen-Codes, das Land und die Herausgeber-Teile von ISBNs, die Sekundären Synchronisationscodes, die im UMTS W-CDMA 3G Radiostandard und die Befehlssätze (Maschinensprache) der meisten Computermikroarchitekturen verwendet sind, ist Präfix-Codes.

Präfix-Codes sind nicht Fehlerkorrekturcodes. In der Praxis könnte eine Nachricht zuerst mit einem Präfix-Code zusammengepresst, und dann wieder mit dem Kanalcodieren (einschließlich der Fehlerkorrektur) vor der Übertragung verschlüsselt werden.

Die Ungleichheit von Kraft charakterisiert die Sätze von Codewortlängen, die in einem Präfix-Code möglich sind.

Techniken

Wenn jedes Wort im Code dieselbe Länge hat, wird der Code einen Code der festen Länge oder einen Block-Code genannt (obwohl der Begriff-Block-Code auch für Fehlerkorrekturcodes der festen Größe im Kanalcodieren verwendet wird). Zum Beispiel sind ISO 8859-15 Briefe immer 8 Bit lang. UTF-32/UCS-4 sind Briefe immer 32 Bit lang. ATM Pakete sind immer 424 Bit lang. Ein Block-Code der festen Länge k Bit kann bis zu Quellsymbolen verschlüsseln.

Präfixe können in einem Code der festen Länge nicht bestehen, ohne befestigte Codes zu den kürzeren Präfixen auszupolstern, um die Länge der längsten Präfixe zu entsprechen (jedoch, können solche Polstern-Codes ausgewählt werden, um Überfülle einzuführen, die Selbstkorrektur und/oder Synchronisation erlaubt). Jedoch ist feste Länge encodings in Situationen ineffizient, wo einige Wörter viel mit größerer Wahrscheinlichkeit übersandt werden als andere (in welchem Fall einige oder die ganze Überfülle für die Datenkompression beseitigt werden können).

Gestutzte binäre Verschlüsselung ist eine aufrichtige Generalisation von Block-Codes, um sich mit Fällen zu befassen, wo die Zahl von Symbolen n nicht eine Macht zwei ist. Quellsymbole sind zugeteilte Kennwörter der Länge k und des k+1. wo

Huffman, der codiert, ist eine hoch entwickeltere Technik, um Präfix-Codes der variablen Länge zu bauen. Der Huffman, der Algorithmus codiert, nimmt als Eingang die Frequenzen, die die Codewörter haben sollten, und einen Präfix-Code bauen, der den gewogenen Mittelwert der Codewortlängen minimiert. Das ist eine Form der lossless auf der Wärmegewicht-Verschlüsselung gestützten Datenkompression.

Einige Codes kennzeichnen das Ende eines Codewortes mit einem speziellen "Komma"-Symbol, das von normalen Daten verschieden ist. Das ist den Räumen zwischen Wörtern in einem Satz etwas analog; sie kennzeichnen, wo Wortenden und ein anderer beginnen. Wenn jedes Codewort Enden in einem Komma und dem Komma erscheinen anderswohin in einem Codewort, der Code nicht, ohne Präfixe ist. Jedoch senden moderne Nachrichtensysteme alles als Folgen "1" und "0" - das Hinzufügen, dass ein drittes Symbol teuer sein würde, und das Verwenden davon nur an den Enden von Wörtern ineffizient sein würde. Morsezeichen-Code ist ein tägliches Beispiel eines Codes der variablen Länge mit einem Komma. Die langen Pausen zwischen Briefen und die noch längeren Pausen zwischen Wörtern, helfen Leuten anzuerkennen, wo ein Brief (oder Wort) Enden und das folgende beginnt. Ähnlich Fibonacci codierender Gebrauch "11", um das Ende jedes Codewortes zu kennzeichnen.

Gleichzeitig selbstseiende Codes sind Präfix-Codes, die Rahmensynchronisation erlauben.

Präfix codiert im Gebrauch heute

Beispiele von Präfix-Codes schließen ein:

• variable Länge Huffman codiert
• das Landbenennen codiert
• das Land und die Herausgeber-Teile von ISBNs
• die Sekundären Synchronisationscodes, die im UMTS W-CDMA 3G Radiostandard verwendet sind
• Videorecorder Plus + codiert
• das UTF-8 System, für Charaktere von Unicode zu verschlüsseln
• die Befehlssätze (Maschinensprache) der meisten Computermikroarchitekturen

Techniken

Allgemein verwendete Techniken, um Präfix-Codes zu bauen, schließen Codes von Huffman und die früheren Codes von Shannon-Fano und universalen Codes ein wie:

• Delta von Elias, das codiert
• Gamma von Elias, das codiert
• Omega von Elias, das codiert
• Fibonacci, der codiert
• Levenshtein, der codiert
• Das unäre Codieren
• Code von Golomb Rice

• Damebrett (einfache Geheimschrift-Technik rittlings sitzend, die Präfix-Codes erzeugt)

Referenzen

• P. Elias, Universale Kennwort-Sätze und Darstellungen von ganzen Zahlen, IEEE Trans. Anzeigen. Theorie 21 (2) (1975) 194-203.
• D.A. Huffman, "Eine Methode für den Aufbau von Codes der minimalen Überfülle", Verhandlungen des I.R.E. September 1952, Seiten 1098-1102 (der ursprüngliche Artikel von Huffman)
• Profil: David A. Huffman, Wissenschaftlicher Amerikaner, September 1991, Seiten 54-58 (Schilderung der Zusammenhänge)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 16.3, pp.385-392.

Links

• Codes, Bäume und das Präfix-Eigentum durch Kona Macphee