Codice di Hamming

Il codice Hamming è un insieme di codici di correzione degli errori che possono essere utilizzati per rilevare e correggere gli errori di bit che possono verificarsi quando i dati del computer vengono spostati o archiviati. Il codice di Hamming prende il nome da RW Hamming dei Bell Labs.

Come altri codici di correzione degli errori, il codice Hamming fa uso del concetto di parità e bit di parità, che sono bit che vengono aggiunti ai dati in modo che la validità dei dati possa essere verificata quando vengono letti o dopo che sono stati ricevuti in una trasmissione di dati. Utilizzando più di un bit di parità, un codice di correzione degli errori può non solo identificare un singolo errore di bit nell'unità dati, ma anche la sua posizione nell'unità dati.

Nella trasmissione dei dati, la capacità di una stazione ricevente di correggere gli errori nei dati ricevuti è chiamata correzione degli errori in avanti (FEC) e può aumentare il throughput su un collegamento dati quando è presente molto rumore. Per abilitarlo, una stazione trasmittente deve aggiungere dati extra (chiamati bit di correzione degli errori ) alla trasmissione. Tuttavia, la correzione potrebbe non rappresentare sempre un risparmio sui costi rispetto al semplice reinvio delle informazioni. I codici di Hamming rendono FEC meno costoso da implementare attraverso l'uso di un file parità di blocco meccanismo.

Il calcolo della parità implica il conteggio del numero di unità in un'unità di dati e l'aggiunta di uno zero o uno (chiamato bit di parità ) per rendere il conteggio dispari (per parità dispari) o pari (per parità pari). Ad esempio, 1001 è un'unità dati a 4 bit contenente due bit uno; poiché si tratta di un numero pari, verrebbe aggiunto uno zero per mantenere la parità pari o, se viene mantenuta la parità dispari, ne verrà aggiunto un altro. Per calcolare la parità pari, viene utilizzato l'operatore XOR; per calcolare la parità dispari, viene utilizzato l'operatore XNOR. Gli errori di bit singolo vengono rilevati quando il conteggio di parità indica che il numero di uno non è corretto, indicando che un bit di dati è stato capovolto a causa del rumore nella linea. I codici di Hamming rilevano due errori di bit utilizzando più di un bit di parità, ciascuno dei quali viene calcolato su diverse combinazioni di bit nei dati. Il numero di bit di parità richiesto dipende dal numero di bit nella trasmissione dei dati ed è calcolato dalla regola di Hamming:

p
d + p + 1 <= 2 (1)

Dove d è il numero di bit di dati e p è il numero di bit di parità. Il totale dei due è chiamato parola in codice di Hamming, che viene generata moltiplicando i bit di dati per una matrice generatore.