Errori nelle trasmissioni in rete.

Introduzione

Il segnale inviato attraverso un canale può essere soggetto interferenze, che possono causare errori alterando il messaggio rendendolo incomprensibile al ricevente o, peggio con un contenuto informativo differente da quello inviato. Immaginiamo di dover accendere e spegnere un faro a distanza, la cosa più semplice da fare è inviare:

1 per accendere
0 per spegnere

Ma durante la trasmissione si può verificare un errore ossia:


1 viene trasformato in 0	0 viene trasformato in 1

In questi casi il ricevitore non è in grado di accorgersi che si è verificato un errore, perché tutte e due le parole sono valide. È necessario introdurre un sistema che ci consenta di individuare la presenza di una situazione come quella descritta, in modo da accorgerci che l’informazione pervenuta è errata prima che possa provocare qualche “disastro”. Sono possibili due approcci per la risoluzione del problema:

l’errore viene corretto
l’errore viene solamente rilevato.

Per fare questo si aggiungono al contenuto dei dati trasmessi delle informazioni ridondanti per garantire la corretta informazione. Ad esempio nel caso precedente se indichiamo con :

11 accendere
00 spegnere

e si verifica un errore su singolo bit al destinatario può arrivare una delle seguenti parole:

le quali non sono parole valide.

In generale dati m bit di dati e r bit ridondanti (aggiunti per il controllo dell’errore), si ottiene un blocco complessivo di n bit (n = m + r), che corrisponde alla sequenza di bit trasmessa sul canale. l codici di controllo degli errori si basano sul seguente principio:

i bit di ridondanza fanno si che non vengano utilizzate tutte le possibili codeword
delle 2ⁿ possibili codeword:
- 2^m saranno valide
- le altre indicheranno la presenza di errori.

Meno sono le codeword valide, rispetto all’insieme di tutte le possibili, più è possibile riconoscere e/o correggere gli errori.

DISTANZA

Con distanza di due configurazioni binarie si intende il numero di bit per cui le due configurazioni differiscono. Vediamo alcuni esempi, dove indichiamo con D(A,B) la distanza tra due configurazioni binarie di 4 bit:

D(1000,1010) = 1

D(0110,0000) = 2

D(0100,1010) = 3

D(0100,0011) = 3

Essa prende il nome di distanza di Hamming, un codice per la rilevazione di modifiche su k bit deve avere almeno D_MIN = k + 1.

Bit di Parità

Prendiamo una sequenza di n = 2 bit: questa può assumere : 2ⁿ = 2² = 4 differenti configurazioni:

00, 01, 10, 11.

Se tutte e 4 queste configurazioni sono usate come dati validi, un errore trasformerà una parola valida in un’altra altrettanto valida, rendendo così impossibile rilevare l’errore. Aggiungendo alla sequenza originale un bit di ridondanza in modo da rendere pari il numero di 1, si ottengono 2³ = 8 configurazioni (codeword) di cui solo 4 valide. Nella tabeIla sono elencate, per ogni codeword valida, le codeword errate risultanti da un errore singolo.

Stati Validi	000	011	101	110
Stati di Errore	001	010	100	111
Stati di Errore	010	001	111	100
Stati di Errore	100	111	001	010

Se dobbiamo inviare la sequenza di bit 1010101111 il numero di bit “1” è 7, quindi dispari, allora il bit di parità (ridontande) da aggiungere sarà 1

101011111 rappresenta la sequenza che invieremo.

Se si inviano dei dati usando questa tecnica iI ricevitore provvederà a ricalcolare la parità sulla sequenza di bit ricevuta, escluso i bit di parità aggiunto, e confronterà il bit di parità ottenuto con quello ricevuto:

se sono diversi la trasmissione non è avvenuta correttamente
se sono uguali è probabile che la sequenza ricevuta sia quella originale

Questa tecnica rileva solo un numero dispari di errori. Per questo, l’utilizzo dei codici di parità è limitato solo ai collegamenti asincroni con bassi tassi d’errore. Il destinatario è in grado di individuare se la parola che arriva errata, ma non è in grado di correggerla in quanto gli è impossibile scoprire quale degli 8 bit si è sporcato e, quindi, riportarlo al valore originale. Una volta intercettato l’errore viene richiesta la ritrasmissione del messaggio.