Codice di Hamming

Page 1

Il codice di Hamming Occasionalmente le memorie dei calcolatori possono commettere degli errori per via di picchi di tensioni sulle linee di alimentazione o per altre cause. Per proteggersi da questi errori alcune memorie utilizzano codici di rilevamenti e/o di correzione degli errori. Quando si applicano questi codici si aggiungono dei bit extra a ogni parola di memoria secondo una modalità particolare. Quando una parola viene letta in memoria si controllano questi bit consecutivi per vedere se si è verificato un errore. Supponiamo che una parola di memoria sia costituita da m bit di dati ai quali vengono aggiunti r bit ridondanti o di controllo. Quindi la lunghezza totale della parola sarà n=m+r . per determinare tra due parole il numero di bit diversi bisogna semplicemente calcolare l’or esclusivo tra i bit delle due parole e contare quanti valgono 1, questo valore viene chiamato distanza di Ha mming. Il suo significato principale è che se fra due parole esiste una distanza di Hamming pari a d, allora saranno necessari d errori singoli per trasformare una parola in un’altra. Con una parola di m bit tutte le 2 m combinazioni di bit sono legali, ma per via del modo in cui sono calcolati i bit di controllo, solo 2 m delle 2 n parole di codice sono valide . Se una lettura da memoria restituisce una parola non valida, il calcolatore sa che è avvenuto un errore. Conoscendo l’algoritmo che calcola i bit di controllo è possibile costruire una lista di parole di codice lecite e, da questa lista , trovare le due parole la cui distanza di Hamming è minima. Questa distanza è la distanza dell’intero codice. Le proprietà di rilevazione e di correzione degli errori di una parola di codice dipendono dalla distanza di Hamming. Per rilevare d errori singoli è necessaria una parola…