Codifica gamma

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

Codifica

La codifica di un numero naturale ${\displaystyle n}$ si effettua nel seguente modo:

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

Analogamente l'algoritmo può essere espresso come:

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

Tale rappresentazione richiede ${\displaystyle 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 ${\displaystyle N}$ 0 fintantoché non raggiungi 1. Salva il numero di 0 in una variabile N;
• Calcola ${\displaystyle 2^{N}}$, leggi i restanti N bit e somma il numero binario al valore calcolato.

Bibliografia

• (EN) Peter Elias, Universal codeword sets and representations of the integers, in IEEE Transactions on Information Theory, vol. 21, n. 2, marzo 1975, pp. 194-203, DOI:10.1109/TIT.1975.1055349. URL consultato il 28 marzo 2015.