La tecnica più semplice per il rilevamento degli errori è quella che utilizza un unico bit di parità. Supponiamo che le informazioni da inviare D (considerando la figura sopra) siano costituite da d bit. In uno schema di parità pari, il mittente include un bit aggiuntivo e sceglie il suo valore in modo da rendere pari il numero totale di bit con valore 1 nei d + 1 bi trasmessi (l'informazione originale + il bit di parità). Nel schema di parità dispari il valore del bit di parità è scelto in modo che ci sia un numero dispari di bit 1. Noi consideriamo un sistema che sfrutta il controllo di parità.
Dati in bit di D | Bit di partità |
---|---|
0111000110101011 | 1 |
Nel messaggio D ci sono 9 bit (evidenziati), allora, in un campo separato, si aggiunge un altro bit 1, per far sì che ci sia un numero pari di 1. Il ricevente, aperto il messaggio D', non deve fare altro che contare il numero di bit 1, se è dispari si è verificato almeno un errore (tale sistema, più precisamente consente di rilevare un numero dispari di errori nei bit). Potrebbe però, verificarsi il caso in cui si verifica un numero pari di errori, in questo caso, se la probabilità di errori nei bit è bassa e si può assumere che gli errori siano indipendenti, l'eventualità di errori multipli in un pacchetto è estremamente ridotta e un solo bit di parità potrebbe risultare sufficiente. Tuttavia statisticamente è stato verificato che gli errori si verificano a raffiche (burst), piuttosto che in modo indipendente.
Per cui risulta evidente che è necessario adottare una soluzione più efficiente.
Prima di analizzare gli schemi adottati nella realtà, consideriamo una semplice generalizzazione del bit di parità che ci fornirà un approccio alla tecnica di correzione dell'errore.
Definizione tabella:
Questa è una tabella di parità bidimensionale.
I bit del dato D sono suddivise in colonne i e righe j.
Per ogni riga e per ogni colonna è stato calcolato il bit di parità.
Ci sono i bit di parità che sono praticamente equivalenti al numero di colonne i.
Ci sono j bit di parità che sono praticamente equivalenti al numero di righe j.
I bit risultanti (nella colonna più a destra e quella più in basso) sono i bit di parità.
Il mittente, calcolata la parità spedisce i dati prendendo i bit per riga:
riga1, riga2, ... ,rigaN
Ora, supponiamo che si verifichi un errore nei bit di D originale. Con questo schema, non solo si riesce a rilevare un errore, ma si riesce ad individuare anche in quale punto del dato si è verificato:
Infatti, la colonna evidenziata, ha un solo valore 1, per esserci un numero pari di bit, il bit di parità sarebbe dovuto essere 1, ma è 0, quindi in quella colonna si è verificato un errore. Analizzando tutte le righe, risulta che la seconda, ha un errore di parità per lo stesso ragionamento di prima: ci sono 3 valori 1, il bit di parità sarebbe dovuto essere 1, invece è zero. Incrociando le due linee si riesce a capire in quale punto si è verificato l'errore. Nonostante l'esempio si centrato su i bit del dato (d), con questa tecnica sarebbero rilevabili anche errori su singoli bit in quelli di parità. Questo schema può rilevare, ma non correggere qualsiasi combinazione di due errori in un pacchetto.