Che cos'è un codice Hamming?
Un codice Hamming è un metodo per rilevare e correggere errori in una trasmissione binaria. Lo fa attraverso l'inclusione di ulteriori cifre binarie nella sequenza utilizzate per il controllo, nonché un algoritmo che fornisce la logica di rilevamento. Tale codice è in grado di trovare due errori in qualsiasi sequenza di bit e di riparare un bit che potrebbe non essere corretto. Il codice Hamming più comunemente indicato è noto come Hamming (7,4), dove i quattro indicano il numero originale di bit di partenza e il sette rappresenta il numero totale di bit nella sequenza dopo che sono stati inclusi i bit di controllo aggiuntivi.
La tecnica prese il nome dal suo creatore, Richard Hamming, che pubblicò il metodo nel 1950. Il modo in cui funziona il codice Hamming è quello di prendere una stringa di bit e inserire ulteriori bit di controllo, chiamati bit di parità, nella sequenza. I bit di controllo vengono sempre iniettati in una posizione che è una potenza di due, quindi è possibile verificare qualsiasi numero di bit includendo bit di parità aggiuntivi. Questo può continuare fino a quando l'ultimo bit di parità aggiunto nella sequenza non si trova in una posizione che è una potenza di due che è inferiore o uguale alla posizione finale nella sequenza.
Con tutti i bit di parità attivi, le posizioni rimanenti sono i bit di dati effettivi. Dato l'esempio a quattro bit, quindi, le posizioni di bit uno, due e quattro sarebbero i bit di parità, mentre le posizioni tre, cinque, sei e sette sono i dati. Una volta stabilita questa sequenza, la logica del codice di Hamming diventa operativa.
In un codice di Hamming, ciascuno dei bit di parità che sono stati aggiunti alla sequenza vengono utilizzati per verificare alcune delle posizioni di bit a cui sono vicini, incluso se stessi. Il bit di parità in posizione uno controlla ogni altra posizione del bit, che è essenzialmente ogni posizione dispari nella sequenza. Il secondo bit di parità, nella posizione due, controlla le posizioni due e tre, quindi salta due posizioni, controlla altre due posizioni, salta altre due e così via. Se nella posizione quattro è presente un bit di parità, agisce in modo analogo in quanto controlla le posizioni da quattro a sette, quindi salta quattro posizioni, ne controlla altre quattro e continua. Ogni bit di parità nella sequenza continua in questo modo per l'intera sequenza.
Il processo mediante il quale un codice di Hamming rileva e corregge un errore consiste nell'aggiungere i bit nella sequenza di controllo per ciascun controllo di parità, ognuno dei quali deve essere visualizzato un numero pari. Dato l'esempio a sette bit, per il primo controllo di parità, vengono aggiunti i bit uno, tre, cinque e sette. Se il totale è un numero pari, la parità viene verificata, ma se il totale è dispari, si verifica un errore. Poiché i controlli di parità si sovrappongono, verranno visualizzati due di questi errori. Quando le posizioni dei bit a due parità che non riescono a ottenere i totali pari vengono sommate, rivelerà il bit che deve essere corretto.
Nell'esempio del codice Hamming a sette bit, considerare che il bit nella posizione numero cinque non è corretto. La somma dei bit nelle posizioni uno, tre, cinque e sette verrà fuori come un numero dispari, così come la somma dei bit nelle posizioni da quattro a sette. Ciò indica che i controlli di parità per i bit di controllo nelle posizioni 1 e 4 non sono riusciti. Quando uno e quattro vengono sommati, il totale è cinque, che è la posizione per il bit errato nella trasmissione che deve essere corretto.