Codifica gamma

Template:Nota disambigua La codifica gamma di Elias è una codificazione entropica per la rappresentazione dei numeri interi.

Codifica

La codifica di un numero naturale $n$ si effettua nel seguente modo:

1. Sia $N=\lfloor lo{g}_{2}n\rfloor$ tale che $2^N\le n\le 2^{N+1}$.
2. Si pongono $N$ bit pari a 0;
3. Si concatena la codifica binaria del numero $n$.

Analogamente l'algoritmo può essere espresso come:

1. Effettua la codifica unaria di N;
2. Concatena il numero $x$ tale che $2^N+x=n$, espresso usando esattamente $N$ bit.

Tale rappresentazione richiede $2\lfloor logn\rfloor +1$ bit.

Numero	Codifica BCD	Codifica γ
1	1	1
2	10	010
3	11	011
4	100	00100
5	101	00101
6	110	00110
7	111	00111
8	1000	0001000
9	1001	0001001
10	1010	0001010

Decodifica

Il codice ottenuto è un codice prefisso. Ogni parola può essere decodificata nel seguente modo:

• Leggi $N$ 0 fintantoché non raggiungi 1. Salva il numero di 0 in una variabile N;
• Calcola $2^N$, leggi i restanti N bit e somma il numero binario al valore calcolato.

Bibliografia

• Template:Cita pubblicazione