Controllo degli errori nello strato di collegamento

Dal framing al controllo degli errori

Su un collegamento lo strato 2 deve prima delimitare i frame, poi accorgersi dei bit che il canale ha alterato e, con certi codici, correggerli. Il framing è già noto e si richiama in breve; il resto è il controllo degli errori.

Ogni frame è chiuso fra due flag:

$$\text{FLAG}=01111110$$

Perché gli stessi bit nei dati non siano scambiati per un delimitatore, si usa una di due tecniche.

• Bit stuffing: il trasmettitore inserisce uno 0 dopo ogni cinque 1 consecutivi dei dati, qualunque sia il bit seguente. Il ricevente, dopo cinque 1, guarda il bit successivo: se è 0 lo elimina, se è 1 la sequenza è un flag.
• Control escape: si lavora byte per byte, con $\text{ESC}=01111101$. Il trasmettitore antepone un ESC a ogni byte dei dati uguale a FLAG o a ESC. Il ricevente elimina un ESC seguito da un altro ESC o da un FLAG; un FLAG senza ESC davanti è un delimitatore.

Errori e parole di codice

Un errore è un bit alterato dal canale: un 1 diventa 0 per l'attenuazione del segnale, uno 0 diventa 1 per un'interferenza. Spesso l'interferenza colpisce più bit vicini, un burst.

Il trasmettitore aggiunge ai $k$ bit informativi $n-k$ bit di controllo, la ridondanza (overhead). La sequenza trasmessa ha $n$ bit ed è una parola di codice (codeword). Il ricevente ricalcola i bit di controllo dai bit informativi ricevuti e li confronta con quelli ricevuti: se non coincidono, il blocco non è una parola di codice ed è in errore.

Se il canale trasforma una parola di codice in un'altra parola di codice, l'errore non è rivelato.

Parità semplice

Si aggiunge un solo bit, la somma modulo 2 dei bit informativi, cioè il resto della divisione per 2 (quindi $1+1\equiv 0$):

$$b_{k+1}=(b_1+b_2+\dots+b_k)\bmod 2$$

Il bit vale 1 se i bit informativi hanno un numero dispari di 1, 0 se pari. La parola $(b_1,\dots,b_k,b_{k+1})$ contiene quindi sempre un numero pari di 1. Per $1101$ la somma è $3$ e $3\bmod 2=1$: la parola è $11011$.

Il ricevente conta gli 1 dell'intera parola.

• Un numero dispari di bit invertiti rende dispari il numero di 1: l'errore è rivelato.
• Un numero pari di bit invertiti lascia pari il numero di 1: l'errore passa inosservato.

Fra le $2^{k+1}$ configurazioni di errore, metà ha un numero dispari di bit invertiti: solo quelle sono rivelate. La ridondanza è 1 bit su $k+1$ trasmessi, cioè $1/(k+1)$.

Distanza di Hamming

Dati due blocchi $X$ e $Y$ della stessa lunghezza, con $W(A)$ numero di 1 di $A$, la distanza di Hamming conta i bit in cui differiscono:

$$\mathrm{HD}(X,Y)=W(X\ \mathrm{xor}\ Y)$$

La $\mathrm{HD}$ del codice è la più piccola fra tutte le coppie di parole di codice. Se le parole sono vicine, pochi bit invertiti bastano per passare da una all'altra e la rivelazione fallisce. I buoni codici tengono le parole lontane, e l'unico modo è aggiungere bit di controllo.

Due capacità distinte, che non si sommano: o si rivelano gli errori, o si correggono.

$$\begin{aligned} \text{rivelati}&:\ \mathrm{HD}-1\\ \text{corretti}&:\ \left\lfloor\frac{\mathrm{HD}-1}{2}\right\rfloor \end{aligned}$$

Meno di $\mathrm{HD}$ inversioni non raggiungono un'altra parola di codice, quindi si rivelano. Entro il numero di errori corretti la parola ricevuta resta più vicina a quella trasmessa che a ogni altra, quindi si corregge.

Nella parità semplice due parole differiscono in un numero pari di bit, almeno 2, e invertendo un bit informativo e il bit di parità si passa da una all'altra: $\mathrm{HD}=2$. Si rivela 1 errore e se ne corregge 0.

Con 2 bit le parole sono i vertici di un quadrato, con 3 bit di un cubo; uno spigolo unisce due parole che differiscono in un bit. La parità dà $\{00,11\}$ su 1 bit informativo e $\{000,011,101,110\}$ su 2, entrambe con $\mathrm{HD}=2$; il codice $\{000,111\}$ ha $\mathrm{HD}=3$.

La distanza sul quadrato e sul cubo

codice

2 bit, HD 23 bit, HD 23 bit, HD 3

00110110

• cammino più corto fra due parole di codice

passo

0

Codice di Hamming (7,4)

Quattro bit informativi $d_1,d_2,d_3,d_4$ ricevono tre bit di parità pari $p_1,p_2,p_3$. La parola ha 7 bit, con i bit di parità nelle posizioni 1, 2 e 4:

$$p_1\,p_2\,d_1\,p_3\,d_2\,d_3\,d_4$$

Ogni bit di parità controlla un gruppo diverso di bit:

$$\begin{aligned} p_1&=(d_1+d_2+d_4)\bmod 2\\ p_2&=(d_1+d_3+d_4)\bmod 2\\ p_3&=(d_2+d_3+d_4)\bmod 2 \end{aligned}$$

Per $d_1d_2d_3d_4=1010$ risulta $p_1=1$, $p_2=0$, $p_3=1$, quindi la parola è 1011010. Trasmettitore e ricevente devono usare lo stesso schema, cioè sapere dove stanno i bit e quali bit entrano in ciascun controllo.

Il controllo $i$ verifica che il gruppo di $p_i$, con $p_i$ compreso, abbia un numero pari di 1. Se un solo bit è errato, ogni bit fa fallire un insieme diverso di controlli, che lo individua:

Bit errato	Controlli falliti
$p_1$	1
$p_2$	2
$d_1$	1, 2
$p_3$	3
$d_2$	1, 3
$d_3$	2, 3
$d_4$	1, 2, 3

Se di 1011010 si riceve 1011110, falliscono i controlli 1 e 3 e il 2 passa: l'errore è su $d_2$, e si corregge. Vale anche se l'errore colpisce un bit di parità.

Nelle slide i tre gruppi sono cerchi: ogni bit sta nei cerchi dei suoi controlli.

I tre controlli di Hamming (7,4)

bit errato

$p_1$$p_2$$d_1$$p_3$$d_2$$d_3$$d_4$

$p_1$$p_2$$d_1$$p_3$$d_2$$d_3$$d_4$

• controllo 1 fallito
• controllo 3 fallito

Con due errori, per esempio su $p_2$ e su $d_2$, si riceve 1111110 e falliscono tutti e tre i controlli: l'errore è rivelato ma non localizzato. Il codice ha $\mathrm{HD}=3$, quindi corregge 1 errore oppure ne rivela fino a 2.

Parità bidimensionale

I bit informativi si dispongono in una matrice, qui di 4 righe e 5 colonne. Si aggiunge un bit di parità per ogni riga (colonna finale), uno per ogni colonna (riga finale) e uno all'incrocio finale.

	1	2	3	4	5	Par.
1	1	0	0	1	0	0
2	0	1	0	0	0	1
3	1	0	0	1	0	0
4	1	1	0	1	1	0
Par.	1	0	0	1	1	1

I 20 bit informativi hanno 10 bit di controllo ($4+5+1$), quindi $n=30$. Il ricevente deve conoscere la disposizione per ricostruire la matrice.

• 1 errore (riga 2, colonna 2): falliscono la riga 2 e la colonna 2, e l'incrocio indica il bit da correggere.
• 2 errori nella stessa colonna (righe 2 e 4): falliscono due righe e nessuna colonna. L'errore è rivelato ma non localizzato.
• 3 errori (tre vertici di un rettangolo, senza l'incrocio $(4,4)$): sono rivelati, ma falliscono solo la riga 4 e la colonna 4, e l'incrocio indica un bit corretto.
• 4 errori ai vertici di un rettangolo (righe 2 e 4, colonne 2 e 4): ogni riga e ogni colonna cambia di due bit, quindi nessuna parità cambia e l'errore passa.

Nella figura i cerchi vuoti sono i bit di parità.

Errori nella parità bidimensionale

bit errati

1234

• riga 2 fallita
• colonna 2 fallita

La distanza è $\mathrm{HD}=4$: un solo bit informativo cambia 4 bit della parola, cioè sé stesso, la sua riga, la sua colonna e l'incrocio. Il codice corregge 1 errore oppure ne rivela fino a 3.

Correzione d'errore in avanti

Nella FEC (Forward Error Correction) il trasmettitore invia la parola di codice; il ricevente, che conosce il codice, esegue i controlli, rivela l'errore e, se la tecnica lo permette, lo corregge senza ritrasmissione. L'alternativa, l'ARQ (error detection and retransmission), fa ritrasmettere il frame.

Il costo sono i bit di controllo $n-k$ aggiunti ai $k$ informativi:

• parità semplice: $n-k=1$, $\mathrm{HD}=2$, rivela 1 errore e ne corregge 0;
• Hamming (7,4): $n-k=3$ su $k=4$, $\mathrm{HD}=3$, rivela 2 errori oppure ne corregge 1;
• parità bidimensionale: $n-k=10$ su $k=20$, $\mathrm{HD}=4$, rivela 3 errori oppure ne corregge 1.

Una distanza maggiore costa più bit di controllo.

Verso i codici CRC

I codici basati sulla parità richiedono molti bit di controllo oppure non sono abbastanza robusti. I codici polinomiali a ridondanza ciclica (CRC, Cyclic Redundancy Check) si calcolano in modo semplice, si realizzano facilmente in hardware e sono usati in Internet e in altri protocolli di strato 2 o superiore.