Name des Binärkodierungsschemes für Ganzzahlzahlen

Question

Ich habe einmal auf Wikipedia gefunden, eine schöne Technik zum Kodieren $ k \ in (2 ^ {n-1}, 2 ^ n) $ gleichmäßig verteilte Ganzzahlzahlen mitWeniger dann $ \ log_2n $ durchschnittliche Bits / Symbol, dank eines einfachen Code mit variabler Länge.Grundsätzlich verwendet es $ \ log_2n $ für einige Symbole und $ \ log_2n - 1 $ für einige andere.

Leider ist mein googel mich nicht gescheitert.Ich erinnere mich an etwas Ähnliches der "variablen Länge binär", aber ich ende immer wieder auf VLQ, das ein anderes Tier ist.Da kenne ich deine Erinnerung besser als meine, kannst du mir helfen?

Answer 1

Die Technikidee ist perfekt in der yuval filmus-Antwort beschrieben.Auch wenn etwas anders als etwas anders ist, heißt es Binärkodierung in Wikipedia.Ich konnte keine Originalquelle dafür finden, abgesehen von einer Erwähnung in einem Patent , in diesem Buch oder in diesem Google API

Answer 2

Angenommen, $ k= 2 ^ {n-1} + t $ , wobei $ 0 \ leq t <2 ^ {n-1} $ . Verwenden Sie das Folgende, um $ Z \ in \ {0, \ ldots, k-1 \} $ :

• Wenn $ Z <2 ^ {n-1} -t $ dann codiert $ Z $ Als eigener $ (n-1) $ -bit-codierung.
• ansonsten, schreibe $ z= 2 ^ {n-1} -t + 2 \ delta + \ epsilon $ , wo $ \ DELTA \ in \ {0, \ ldots, t-1 \} $ und $ \ epsilon \ in \ {0,1 \} $ . Codieren Sie $ Z $ in der $ (N-1) $ -bit-Kodierung von $ 2 ^ {n-1} -t + \ Delta $ Gefolgt von $ \ Epsilon $ .

Hier ist ein Beispiel. Lassen Sie $ k= 11= 2 ^ 3 + 3 $ . Die Kodierung ist wie folgt:

• $ 0 \ bis 000 $ .
• $ 1 \ bis 001 $ .
• $ 2 \ bis 010 $ .
• $ 3 \ bis 011 $ .
• $ 4 \ bis 100 $ .
• $ 5 \ bis 1010 $ .
• $ 6 \ bis 1011 $ .
• $ 7 \ bis 1100 $ .
• $ 8 \ bis 1101 $ .
• $ 9 \ bis 1110 $ .
• $ 10 \ bis 1111 $ .