Gestutzte binäre Verschlüsselung ist ein Wärmegewicht, das normalerweise verwendet für den gleichförmigen Wahrscheinlichkeitsvertrieb mit einem begrenzten Alphabet verschlüsselt. Es wird durch ein Alphabet mit der Gesamtgröße der Nummer n parametrisiert. Es ist eine ein bisschen allgemeinere Form der binären Verschlüsselung, wenn n nicht eine Macht zwei ist.

Lassen Sie n = 2+b, für 0  b  2. Wenn n eine Macht 2 ist, können Sie zwei mögliche Werte von k wählen; beide erzeugen dieselben codierten Werte, die zu einem einfachen binären Code identisch sind.

Gestutzte binäre Verschlüsselung teilt das erste 2b Symbol-Kennwörter der Länge k zu und teilt dann das restliche 2b Symbole das letzte 2b Kennwörter der Länge k+1 zu. Weil alle Kennwörter der Länge k+1 aus einem unbestimmten Kennwort der Länge k mit "0" oder "1" angehangenes bestehen, ist der resultierende Code ein Präfix-Code.

Beispiel mit n

5 = =

Zum Beispiel, für das Alphabet {0, 1, 2, 3, 4}, n = 5 = 2 ² + 1. Gestutzte binäre Verschlüsselung teilt die ersten drei Symbole (2 ²  1) die Kennwörter 00, 01, und 10, die ganze Länge 2 zu, teilt dann die letzten zwei Symbole die Kennwörter 110 und 111, die letzten zwei Kennwörter der Länge 3 zu, von denen jeder das unbenutzte Zwei-Bit-Kennwort 11 mit einer angehangenen Extraziffer ist.

Zum Beispiel, wenn n 5 ist, teilen einfache binäre Verschlüsselung und gestutzte binäre Verschlüsselung die folgenden Kennwörter zu. Gezeigte Ziffern werden in der gestutzten Dualzahl nicht übersandt.

Die nächste Macht 2 danach n = 5 ist 2 ³ = 8, also gibt es u = 85 = 3 unbenutzte Codes in der aufrichtigen binären 3-Bit-Verschlüsselung.

In numerischen Begriffen, um einem Wert 0  x &lt zu senden; n, der einer von 2  n  2 Symbole ist, gibt es u = 2n unbenutzte Einträge, wenn die Alphabet-Größe zur nächsten Macht zwei zusammengetrieben wird. Der Prozess, um die Nummer x in der gestutzten Dualzahl zu verschlüsseln, ist: Wenn x weniger ist als u, verschlüsseln Sie es in k binären Bit. Wenn x größer oder gleich u ist, verschlüsseln Sie den Wert x+u in k+1 binären Bit.

Beispiel mit n

10 = =

Ein anderes Beispiel, ein Alphabet der Größe 10 (zwischen 0 und 9) verschlüsselnd, verlangt k=4 Bit, aber es gibt 210 = 6 unbenutzte Codes, so schätzt Eingang, ließen weniger als 6 das erste Bit verwerfen, während eingegebene Werte größer oder gleich 6 durch 6 zum Ende des binären Raums ausgeglichen werden. (Unbenutzte Muster werden in diesem Tisch nicht gezeigt.)

Um zu decodieren, lesen Sie die ersten k Bit. Wenn sie einen Wert weniger verschlüsseln als u, ist Entzifferung abgeschlossen. Fügen Sie sonst ein zusätzliches Bit hinzu und ziehen Sie u vom Ergebnis ab.

Beispiel mit n

7 = =

Hier ist ein mehr äußerster Fall: Mit n = 7 ist die folgende Macht 2 8 (wir werden dann 3 Bit oder 2 Bit verwenden, wenn das hohe Bit verworfen wird), und u = 1:

Dieses letzte Beispiel demonstriert, dass ein Hauptnullbit keinen kurzen Code immer anzeigt; wenn u < 2 werden einige lange Codes mit einem Nullbit beginnen.

Wenn n eine Macht zwei ist, dann kann die Verschlüsselung mit jedem von zwei verschiedenen Werten von k getan werden. Beide erzeugen gleichwertige Produktionen; man hat gerade u = 2 und verschlüsselt alle Werte, weil "kurzes" K-Bit codiert, während der andere u = 0 hat und alles mit "dem langen" verschlüsselt, k+1-bit codiert.

Siehe auch

• Das Gesetz von Benford