Codifica gamma

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

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

Codifica

modifica

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

  1. Sia   tale che  .
  2. Si pongono   bit pari a 0;
  3. Si concatena la codifica binaria del numero  .

Analogamente l'algoritmo può essere espresso come:

  1. Effettua la codifica unaria di N;
  2. Concatena il numero   tale che  , espresso usando esattamente   bit.

Tale rappresentazione richiede   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

modifica

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

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

Bibliografia

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