Rilevare gli errori con il CRC

Bit di controllo e parola di codice

Ogni metodo aggiunge ai $K$ bit di dati $N-K$ bit di controllo. La sequenza trasmessa, di $N=K+(N-K)$ bit, è la parola di codice. Chi riceve conosce il metodo, rifà il calcolo e dà un esito: errore o nessun errore e, con alcuni codici, anche in quale bit.

• Parità singola: un bit in coda, calcolato su tutta la stringa.
• Hamming: più bit di parità (tre nell'esempio), ciascuno su una combinazione diversa dei dati, in posizioni prestabilite.
• Parità su righe e colonne: la stringa è una matrice, con un bit per riga, uno per colonna e uno nell'angolo.
• Internet checksum: si sommano i blocchi (di 16 bit, per esempio, modulo $2^{16}-1$) e si aggiunge l'inverso della somma, lungo come un blocco.
• CRC: si aggiunge il resto di una divisione fra polinomi, lungo quanto il grado del generatore.

Il costo si conta in bit aggiunti. Per proteggere una stringa di 16 bit, un checksum a 8 bit ne aggiunge 8 e un CRC con $G(x)=x^3+1$ ne aggiunge 3.

Un errore è un polinomio

Un errore inverte dei bit, e invertire un bit vuol dire sommargli 1 modulo 2. L'errore è quindi una stringa con un 1 in ogni bit invertito, cioè un polinomio $E(x)$, e la parola ricevuta è

$$T'(x)=T(x)+E(x)$$

Chi riceve divide $T'(x)$ per $G(x)$ e chiama $R'(x)$ il resto. Siccome $T(x)$ è multiplo di $G(x)$, il resto dipende solo dall'errore:

$$R'(x)=E(x)\bmod G(x)$$

Se $R'(x)\ne0$ l'errore è rilevato. Se $R'(x)=0$ non si rileva niente. Sfuggono quindi tutti e soli gli errori $E(x)\ne0$ che sono multipli di $G(x)$.

Gli errori possono arrivare a raffiche. Una raffica (burst) di lunghezza $n$ comincia e finisce con un 1, con zeri e uni in mezzo, e la lunghezza si misura dal primo all'ultimo 1. Il suo polinomio ha $n$ coefficienti ed è $x^{n-1}+\dots+1$. Moltiplicarlo per $x^i$ lo sposta di $i$ posti a sinistra, e $i$ è la distanza dell'ultimo bit errato dall'estremo destro:

$$E(x)=x^i(x^{n-1}+\dots+1)$$

Dove cade una raffica

$x^0$$x^1$$x^2$$x^3$$x^4$$x^5$$x^6$$x^7$$x^8$$x^9$$n$$i$

• raffica

$i$

2

$n$

4

Quali errori rileva un generatore

$G(x)$ ha grado $z$ e termine noto 1. Ne seguono due garanzie.

• Ogni raffica con $n\le z$ è rilevata. Il fattore $x^{n-1}+\dots+1$ di $E(x)$ ha grado $n-1<z$ e non è nullo. Il termine noto 1 esclude $x$ come fattore di $G(x)$, quindi se $G(x)$ dividesse $E(x)$ dividerebbe quel fattore, che ha grado minore: impossibile.
• Ogni errore con un numero dispari di bit invertiti è rilevato, se $x+1$ divide $G(x)$. Un multiplo di $G(x)$ vale 0 in $x=1$, cioè ha un numero pari di termini. Un errore dispari vale 1, perché i coefficienti si sommano modulo 2.

Oltre $z$ la garanzia è probabilistica, con le raffiche di una stessa lunghezza ugualmente probabili. Con $n=z+1$ fra i due 1 restano $z-1$ bit liberi, quindi le raffiche sono $2^{z-1}$ e solo $G(x)$ stesso è un multiplo di $G(x)$. Con $n>z+1$ i multipli di $G(x)$ sono una frazione $2^{-z}$ delle raffiche. La probabilità che una raffica di lunghezza $n$ sfugga è quindi

$$\begin{cases} 0 & n\le z\\ 2^{-(z-1)} & n=z+1\\ 2^{-z} & n>z+1 \end{cases}$$

Una raffica più lunga di $z+1$ sfugge quindi meno spesso di una di lunghezza $z+1$.

Quali raffiche sfuggono

lunghezza $n$ della rafficaprobabilità, in unità di $2^{-z}$

• probabilità che la raffica sfugga

$z$

3

CRC-32 e overhead

CRC-32 indica un generatore di grado $z=32$: rileva ogni raffica fino a 32 bit. Con $n=33$ la probabilità di mancata rilevazione è $2^{-31}\approx4{,}66\cdot10^{-10}$, con $n>33$ è $2^{-32}\approx2{,}33\cdot10^{-10}$. È bassissima, ma non nulla.

Il prezzo sono i $z$ bit aggiunti. L'overhead, cioè la quota di bit aggiunti sul totale, è

$$\frac{z}{K+z}$$

Con $K=32$ e $z=32$ la parola è di 64 bit e metà è overhead. Per questo un CRC-32 si usa su stringhe lunghe, dove la quota è piccola.

Esercizio: parola trasmessa ed errori

Sono dati $P=1110$ e $G(x)=x^3+x+1$, cioè $1011$, con $z=3$. Si chiedono la parola $T$ trasmessa, una stringa di errore che non viene rilevata e una che viene rilevata. Le risposte sono stringhe di bit.

Parola trasmessa. Si aggiungono tre zeri, $x^3P(x)\to1110000$, e si divide per $1011$ con XOR e scorrimenti: si sottrae $1011$ quando la cifra di testa è 1 e si abbassa la cifra successiva. Restano tre cifre, che sono il resto:

$$\begin{array}{ccccccc} 1&1&1&0&0&0&0\\ 1&0&1&1&&&\\ \hline &1&0&1&0&&\\ &1&0&1&1&&\\ \hline &&&&1&0&0 \end{array}$$

Il resto è $100$, cioè $R(x)=x^2$, e la parola trasmessa è $T=1110100$. Si verifica che è un multiplo di $G(x)$:

$$T(x)=x^6+x^5+x^4+x^2=(x^3+x+1)(x^3+x^2)$$

Errore non rilevato e errore rilevato. Non serve dividere. Per non essere rilevato l'errore deve essere un multiplo di $G(x)$, e il più semplice è $G(x)$ stesso, che si può spostare nella parola. Spostato di un posto è $E_1(x)=xG(x)=x^4+x^2+x$, cioè $E_1=0010110$. Per essere rilevato basta un errore che non sia multiplo: si inverte anche l'ultimo bit, cioè $E_2(x)=E_1(x)+1=xG(x)+1$, e quindi $E_2=0010111$. La divisione serve solo come prova:

$$\begin{array}{lcc} & \text{con }E_1 & \text{con }E_2\\ \hline T & 1110100 & 1110100\\ E & 0010110 & 0010111\\ \hline T' & 1100010 & 1100011\\ R' & 000 & 001 \end{array}$$

Con $E_1$ tre bit invertiti passano inosservati. Con $E_2$ il resto è $001=E_2(x)\bmod G(x)$ e l'errore è rilevato.

Anche una raffica più lunga può sfuggire. Moltiplicando $G(x)$ per sé stesso modulo 2 i prodotti incrociati compaiono due volte e si annullano:

$$E_3(x)=(x^3+x+1)^2=x^6+x^2+1$$

Quindi $E_3=1000101$ è un multiplo di $G(x)$. Sommato a $T$ dà $0110001$, con resto $000$.

Oltre $z$ né la lunghezza né il numero di bit invertiti decidono: conta se $E(x)$ è multiplo di $G(x)$. $E_1$ è una raffica di lunghezza $z+1=4$, $E_3$ una di lunghezza 7. Entrambi invertono tre bit, un numero dispari, e sfuggono: $G(x)$ vale 1 in $x=1$, quindi $x+1$ non lo divide e la garanzia sugli errori dispari non vale.

Riempimento dei bit negli esercizi

Il flag contiene sei 1 consecutivi, $\text{FLAG}=01111110$. Perché i dati non lo imitino, il trasmettitore inserisce uno 0 dopo ogni cinque 1 consecutivi dei dati. Il ricevente, dopo cinque 1, elimina lo 0 che segue; se segue un 1 sono sei 1 di fila e quello è un flag.

• Inserire gli zeri. Si contano gli 1 consecutivi e lo 0 va dopo il quinto. Uno 0 messo dopo soli quattro 1 è un errore. Lo 0 inserito interrompe la serie, e il conteggio riparte.
• Ricostruire la trama. Si riconoscono i flag, sei 1 di fila, poi si elimina lo 0 dopo ogni cinque 1. Si controlla che non ci siano flag all'interno: se ce n'è uno, la sequenza è fatta di più trame di seguito. In una trasmissione continua un solo flag chiude una trama e apre la successiva.