Tecniche di controllo degli errori

Concetti principali

Le tecniche di controllo degli errori permettono di rilevare o correggere alterazioni introdotte durante la trasmissione.

• differenza tra rilevazione e correzione;
• principio del bit di parità;
• funzione di checksum e CRC;
• codici di Hamming e FEC;
• complessità ed efficacia delle diverse tecniche.

Rilevare e correggere non sono la stessa cosa

Una tecnica di rilevazione permette di capire che qualcosa è andato storto. Una tecnica di correzione permette invece di ricostruire il dato corretto.

• rilevare = accorgersi dell'errore;
• correggere = sapere anche come rimediare.

Bit di parità

È la tecnica più semplice. Si aggiunge un bit in più per far sì che il numero totale di bit a 1 sia pari oppure dispari.

Esempio

Dato: 1011001
Parità pari: 10110010

Esempio passo passo - bit di parità

La dataword 1011001 viene completata usando la parità pari.

Formula utile

p = b1 xor b2 xor b3 xor ... xor bn

Dove p è il bit di parità e xor vale 1 quando i due bit confrontati sono diversi.

Calcolo

1 xor 0 = 1
1 xor 1 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 0 = 1
1 xor 1 = 0

Il risultato finale è 0, quindi il bit di parità da aggiungere è 0.

Dataword: 1011001
Bit di parità: 0
Codeword: 10110010

Controllo al destinatario

Il ricevitore rifà lo xor su tutti i bit della codeword. Se il risultato finale non è coerente con la parità scelta, sa che si è verificato un errore. Questo metodo però non dice quale bit è sbagliato.

Checksum

Il checksum si basa su un valore calcolato a partire dai dati e inviato insieme al messaggio.

Il destinatario ripete il calcolo:

• se il risultato coincide, il dato è probabilmente corretto;
• se non coincide, si rileva la presenza di un errore.

Qui viene usata una versione semplificata; nei protocolli reali esistono varianti più precise, come il checksum basato su somme in complemento a 1.

Esempio passo passo - checksum

Un esempio semplificato con parole da 4 bit permette di dividere il messaggio in due blocchi:

Blocco 1 = 1011
Blocco 2 = 0110

Formula utile

checksum = somma dei blocchi

In questo esempio la somma binaria rappresenta il modello di base del meccanismo.

Calcolo al mittente

  1011
+ 0110
------
1 0001

La somma produce 10001. Se manteniamo 4 bit di risultato, il valore di controllo trasmesso è:

Checksum = 0001

Controllo al destinatario

Il ricevitore rifà la stessa somma sui blocchi ricevuti.

• se ottiene ancora 0001, il messaggio è probabilmente corretto;
• se ottiene un valore diverso, rileva un errore.

Nelle reti reali esistono versioni più precise del checksum, ma l'idea fondamentale è sempre questa: calcolare un valore di controllo a partire dai dati e confrontarlo alla ricezione.

CRC - Cyclic Redundancy Check

Il CRC è molto più robusto della sola parità. I dati vengono trattati come sequenza binaria e controllati con un polinomio generatore.

• si calcola un resto;
• quel resto viene aggiunto ai dati;
• il destinatario ripete il controllo;
• se il controllo non torna, il dato viene scartato.

Nelle reti Ethernet il campo FCS del frame è basato proprio su un CRC.

Esempio passo passo - CRC

Esempio classico e semplice:

• dati: 1101
• polinomio generatore: 1011

Il generatore ha 4 bit, quindi il mittente aggiunge 3 zeri ai dati.

Messaggio esteso = 1101000

Idea matematica

CRC = resto della divisione modulo 2

messaggio esteso ÷ generatore

Nella divisione modulo 2 non ci sono riporti: si usa di fatto l'operazione xor.

Divisione modulo 2

1101 xor 1011 = 0110
porto giù il bit successivo -> 1100
1100 xor 1011 = 0111
porto giù il bit successivo -> 1110
1110 xor 1011 = 0101
porto giù il bit successivo -> 1010
1010 xor 1011 = 0001

Il resto finale è formato dagli ultimi 3 bit:

Resto = 001

Questo è il valore CRC che viene aggiunto ai dati originali.

Dati originali = 1101
CRC = 001
Messaggio trasmesso = 1101001

Il destinatario divide di nuovo 1101001 per 1011. Se il resto è 000, il messaggio è coerente; se il resto è diverso da zero, l'errore viene rilevato.

Codici di Hamming

I codici di Hamming aggiungono bit di controllo in posizioni precise. In questo modo il ricevitore non si limita a capire che esiste un errore, ma può anche individuarne la posizione in molti casi.

• rilevano errori;
• correggono errori singoli;
• sono più sofisticati dei metodi precedenti.

FEC - Forward Error Correction

La FEC aggiunge abbastanza ridondanza da consentire al destinatario di correggere direttamente alcuni errori, senza dover richiedere una nuova trasmissione.

È particolarmente utile in collegamenti dove ritrasmettere è costoso o scomodo, come radio, satelliti e collegamenti ad alta velocità.