RILEVAZIONI ERRORI: Codice di Hamming

I principali metodi di rilevazioni di errori sono 3: CRC, CHECKSUM ed 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 2⁴ = 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

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 2^j 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 …

Per approfondire ti consigliamo la lettura di questi articoli:

ESERCIZIO