Nome dello schema di codifica binaria per numeri interi

Question

Una volta trovato su Wikipedia una bella tecnica per la codifica $ k \ in (2 ^ {n-1}, 2 ^ n) $ numeri interi distribuiti uniformemente conmeno quindi $ \ log_2n $ bit / simbolo medio, grazie ad un codice di lunghezza variabile semplice da calcolare.Fondamentalmente ha usato $ \ log_2n $ per alcuni simboli e $ \ log_2n - 1 $ per alcuni altri.

Sfortunatamente tutto il mio googling mi ha capito.Ricordo qualcosa di simile a "Binary a lunghezza variabile", ma continuo a finire su VLQ che sono una bestia diversa.Dal momento che conosco la tua memoria meglio del mio, puoi aiutarmi?

Answer 1

L'idea tecnica è perfettamente descritta nella risposta Yuval Filmus.Anche se leggermente diverso, si chiama troncated binary codifica in Wikipedia.Non sono riuscito a trovare una fonte originale per questo, a parte una menzione in un brevetto , in questo Prenota o in questo Google API

Answer 2

Supponiamo $ k= 2 ^ {n-1} + t $ , dove $ 0 \ Leq T <2 ^ {n-1} $ . Utilizzare quanto segue per codificare $ z \ in \ {0, \ Ldots, k-1 \} $ :

.
• se $ z <2 ^ {n-1} -t $ quindi codifica $ z $ come il suo $ (n-1) $ -bit codifica.
• Altrimenti, scrivi $ z= 2 ^ {n-1} -t + 2 \ delta + \ epsilon $ , dove $ \ delta \ in \ {0, \ ldots, t-1 \ ldots, T-1 \} $ e $ \ epsilon \ in \ {0,1 \} $ . Codifica $ Z $ alla $ (n-1) $ --bit codifica di $ 2 ^ {n-1} -t + \ delta $ seguito da $ \ epsilon $ .

Ecco un esempio. Let $ k= 11= 2 ^ 3 + 3 $ . La codifica è la seguente:

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