Codifica gamma

Disambiguazione – Se stai cercando altri significati, vedi Correzione di gamma.

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

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

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

Analogamente l'algoritmo può essere espresso come:

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

Tale rappresentazione richiede 2 ⌊ l o g n ⌋ + 1 {\displaystyle 2\lfloor log{n}\rfloor +1} bit.

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

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

• (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.

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica