I principali metodi di rilevazioni di errori sono 3: CRC, CHECKSUM ed il codice di HAMMING ma ci siamo mai chiesti in che modo nascono questi errori?
DOVE NASCONO GLI ERRORI?
Quando avviene uno scambio di informazioni tra l’elaboratore e la memoria attraverso i fili paralleli (BUS), il segnale trasmesso può essere soggetto a rumori e quindi si può sovrapporre creando un bit errato. In caso vi sia la presenza di ERRORE questo può esser trattato in 4 modi diversi:
- Il messaggio viene scartato.
- Viene richiesta la trasmissione del messaggio.
- Viene migliorata la qualità del canale.
- L’errore viene cercato di correggerlo
HAMMING
Nel 1950 Hamming propone il sistema di codifica a correzione d’errore che porta oggi il suo nome: il codice di Hamming.
- L’idea di base del codice di Hamming è quella di codificare la posizione dell’eventuale errore
- Si aggiungono alcuni bit di controllo, tanti quanti sono necessari per codificare la posizione del bit errato
Poiché anche i bit di controllo sono soggetti a errore, occorre includere anche le posizioni di questi bit nel conteggio totale.
- Data una stringa di 8 bit, si aggiungono 4 bit di controllo, per un totale di 12 bit di codework
- 4 bit di posizione bastano per codificare le 12 posizioni, dato che 24 = 16 ci permette di codificare 16 posizioni (4 configurazioni non utilizzate).
Codework è il risultato della somma dei bit di dati + i bit di controllo
BIT DI CONTROLLO del codice di Hamming
Costruiamo il singolo codework “mischiando” bit di informazione e bit di controllo. Innanzitutto numeriamo i bit della parola da trasmettere a partire da sinistra verso destra, inserendo a ogni posizione avente per indice una potenza del 2 il posto per un bit di controllo.
- Ogni bit di controllo è un bit di parità che esprime la parità di un sottoinsieme opportuno dei bit della stringa
- il bit di controllo in posizione 2j controlla la parità di tutti i bit la cui posizione, in binario, ha il j-esimo bit a 1
- Il primo bit di controllo si ottiene come parità di tutti i bit che sono in posizione tale per cui la loro codifica binaria ha 1 nel bit meno significativo (sono tutte le posizioni dispari).
- Il secondo bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 2° bit = 1, e cioè 2 3 6 7 10 11..
- Il terzo bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 3° bit=1, cioè 4 5 6 7 12 …
- Il quarto bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 4° bit = 1 cioè 8 9 10 11 12 …
ESERCIZIO: codice di Hamming
