Codice di Hamming

Da Wikipedia, l'enciclopedia libera.

Il codice di Hamming è un codice per la correzione di errori chiamato come il suo inventore, Richard Hamming. Serve dunque per la ricerca e la Correzione degli errori nella comunicazione numerica. Permette la rilevazione e la correzione di errori semplici (1 bit), e la sola rilevazione per errori doppi (2 bit).

Il codice di Hamming fa parte dei codici lineari, ed i suoi parametri sono $\left[\frac{q^m-1}{q-1},q^m-m,3\right]$ , dove q è la grandezza dell'alfabeto utilizzato (ad esempio 2 se è binario) e m è il numero di bit usati.

Il codice di parità consente la rivelazione dell'errore ma non la sua correzione. Aumentando la ridondanza nel messaggio (aggiunta di bit per la rivelazione e la correzione degli errori) è possibile conoscere anche la posizione del bit errato e quindi correggerlo. Il codice di Hamming fornisce questa possibilità.

Se un codice contiene N informazioni distinte, la rappresentazione in forma binaria di ciascuna di esse avviene utilizzando una parola di n bit in modo che si verifichi: $2^n \ge \ N$ .

Se, $2 n = N$ , un errore in uno o più bit porta ad una configurazione binaria diversa che corrisponde, però, sempre ad un dato appartenente allo stesso codice: in pratica non si riesce a comprendere se vi è stato un errore o meno.

Ad esempio, supponiamo di voler codificare le cifre decimali da 0 a 9 utilizzando 5 bit. Con 5 bit sono possibili $25 = 32$ configurazioni differenti di cui solo 10 saranno utilizzate. Se vi è un errore il dato potrebbe assumere una delle altre 22 configurazioni e sarà, quindi, possibile rivelare un errore. Si noti che per la codifica delle 10 cifre decimali sarebbero necessari solo 4 bit. Il quinto bit è ridondante. Resta da definire la modalità di codifica. Un buon criterio è quello che associa ad ogni cifra decimale una configurazione binaria in cui sono presenti sempre due 1 e tre 0 (o viceversa) come nella seguente tabella.

Decimale	Codifica
0	11000
1	10100
2	10010
3	10001
4	01100
5	01010
6	01001
7	00110
8	00101
9	00011

Si noti che se si verifica un errore il numero 1 presente nel codice si altera. Anche questo tipo di codifica individua la presenza ma non la posizione dell'errore.