Codifica gamma
# Codifica gamma

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:

* Sia $N=\lfloor log_{2}{n}\rfloor$ tale che $2^{N}\leq n\leq 2^{N+1}$.
* Si pongono $N$ bit pari a 0;
* Si concatena la codifica binaria del numero $n$.

Analogamente l'algoritmo può essere espresso come:

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

Tale rappresentazione richiede $2\lfloor log{n}\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.
