CRC, bit stuffing e Internet checksum

CRC: la parola trasmessa

Il CRC tratta una stringa di bit come un polinomio $P(x)$ a coefficienti binari, con l'aritmetica modulo 2: somma e sottrazione coincidono e sono uno XOR. Dato un polinomio generatore $G(x)$ di grado $z$, si calcola il resto $R(x)$ della divisione di $x^zP(x)$ per $G(x)$ e si trasmette

$$T(x)=x^zP(x)+R(x)$$

Poiché $x^zP(x)=Q(x)G(x)+R(x)$ e somma e sottrazione sono uguali, $T(x)=Q(x)G(x)$: ogni parola di codice è divisibile per $G(x)$. Il resto ha grado minore di $z$, quindi sta in $z$ bit.

Esercizio. $P=1110$ e $G(x)=x^3+x+1$. Allora $P(x)=x^3+x^2+x$ e $z=3$:

$$\begin{aligned} x^3P(x)&=x^6+x^5+x^4\\ &=(x^3+x^2)\,G(x)+x^2 \end{aligned}$$

La divisione procede eliminando il termine di grado massimo: $x^6$ con $x^3G(x)$, poi $x^5$ con $x^2G(x)$. Resta $x^2$, di grado minore di 3, quindi $R(x)=x^2$, cioè $100$ su tre bit. La parola trasmessa è $T=1110\,100$, cioè $T(x)=x^6+x^5+x^4+x^2$.

Con le stringhe di bit la stessa divisione è una serie di XOR. Si accodano a $P$ tre zeri e si scrive $G=1011$ sotto il primo 1; poi sotto il primo 1 che resta, e così via, finché restano tre bit: sono il resto.

$$\begin{array}{r} \mathtt{1110000}\\ \oplus\ \mathtt{1011000}\\ \hline \mathtt{0101000}\\ \oplus\ \mathtt{0101100}\\ \hline \mathtt{0000100} \end{array}$$

Errori non rivelati

Il canale può alterare dei bit. Il vettore d'errore $E(x)$ ha un 1 in ogni posizione alterata, quindi il ricevitore riceve $T(x)+E(x)$ e lo divide per $G(x)$. Con resto nullo non rivela errori, altrimenti li rivela. Poiché $T(x)$ è divisibile per $G(x)$:

$$(T(x)+E(x))\bmod G(x)=E(x)\bmod G(x)$$

Un errore non è rivelato se e solo se $E(x)$ è multiplo di $G(x)$.

Errore non rivelato. Si cerca $E_1(x)=H(x)G(x)$ diverso da $G(x)$ stesso, quindi con $H(x)\neq1$. Il vettore d'errore ha la lunghezza della parola trasmessa, quindi il grado di $E_1(x)$ non supera quello di $T(x)$, che è 6. Con $H(x)=x+1$:

$$E_1(x)=(x+1)(x^3+x+1)=x^4+x^3+x^2+1$$

cioè $E_1=0011101$. La parola ricevuta è

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

cioè $1101001$. È divisibile per $G(x)$, quindi il resto è nullo e l'errore non è rivelato. La divisione lo conferma:

$$x^6+x^5+x^3+1=(x^3+x^2+x+1)\,G(x)$$

Errore rivelato. Basta cambiare un solo bit di $E_1$. Il nuovo $E_2(x)=E_1(x)+x^i$ ha lo stesso resto di $x^i$, che non è nullo perché $G(x)$ non divide $x^i$.

Framing e bit stuffing

Il framing delimita il frame con un flag all'inizio e uno alla fine, per esempio $01111110$. Il ricevitore deve riconoscere i flag senza ambiguità, quindi il contenuto del frame non deve mai avere sei 1 di fila. Lo garantisce il bit stuffing:

• in trasmissione si inserisce uno 0 dopo ogni cinque 1 consecutivi, qualunque sia il bit successivo;
• in ricezione, dopo cinque 1 si guarda il bit successivo. Se è uno 0 è di stuffing e si toglie; se è un 1 la sequenza è un flag.

Esercizio, stuffing. La sequenza di 43 bit contiene sequenze di 1 lunghe 3, 6, 3, 3, 1, 8, 4 e 6. Si inserisce uno 0 dopo il quinto 1 delle tre sequenze lunghe 6, 8 e 6. Sequenza originale:

$$\begin{aligned} &\mathtt{0111011111100111011101}\\ &\mathtt{011111111011110111111} \end{aligned}$$

Sequenza trasmessa, di 46 bit, con gli 0 inseriti sottolineati:

$$\begin{aligned} &\mathtt{0111011111}\underline{\mathtt{0}}\mathtt{100111011101}\\ &\mathtt{011111}\underline{\mathtt{0}}\mathtt{11101111011111}\underline{\mathtt{0}}\mathtt{1} \end{aligned}$$

Esercizio, destuffing. La sequenza ricevuta comincia e finisce con un flag. Fra i due flag il contenuto è lungo 44 bit, e si toglie lo 0 che segue ogni gruppo di cinque 1. Sono quattro, sottolineati:

$$\begin{aligned} &\mathtt{111011111}\underline{\mathtt{0}}\mathtt{11111}\underline{\mathtt{0}}\mathtt{11111}\underline{\mathtt{0}}\\ &\mathtt{111101100011111}\underline{\mathtt{0}}\mathtt{101000} \end{aligned}$$

Lo 0 dopo i quattro 1 all'inizio della seconda riga non è di stuffing e resta. Il frame originale, di 40 bit, è:

$$\begin{aligned} &\mathtt{1110111111111111111}\\ &\mathtt{111101100011111101000} \end{aligned}$$

Internet checksum

L'Internet checksum rivela gli errori, non li corregge. Il messaggio si divide in parole di $w$ bit $b_0,\dots,b_{L-1}$, lette come interi con l'aritmetica modulo $2^w-1$. Il checksum è l'opposto della loro somma:

$$b_L=-(b_0+\dots+b_{L-1})\bmod(2^w-1)$$

Così la somma di tutte le parole, checksum compreso, vale zero, e il ricevitore accetta se la trova nulla. La lunghezza $w$ del checksum fissa sia il modulo $2^w-1$ sia la lunghezza delle parole, quindi il messaggio si può dividere in parole solo se la sua lunghezza è un multiplo di $w$. In aritmetica modulo $m$ l'opposto di $a$ è $m-a$, come tornare indietro di $a$ posizioni su un orologio di $m$ posizioni.

Esercizio, 8 bit. Il messaggio è $M=1011000101101010$ e il modulo è $2^8-1=255$. Le parole sono due, $b_0=10110001=177$ e $b_1=01101010=106$:

$$\begin{gathered} 177+106=283\equiv28\pmod{255}\\ b_2=-28\equiv227=11100011_2 \end{gathered}$$

Controllo: $177+106+227=510=2\cdot255\equiv0$.

Esercizio, 4 bit. Le parole sono $b_0=1001$, $b_1=1100$, $b_2=1010$, $b_3=0011$, cioè 9, 12, 10 e 3, con modulo $2^4-1=15$:

$$\begin{gathered} 9+12+10+3=34\equiv4\pmod{15}\\ b_4=-4\equiv11=1011_2 \end{gathered}$$

Controllo: $34+11=45=3\cdot15\equiv0$.

CRC sullo stesso messaggio

Per lo stesso $M$ si usa il CRC con $G(x)=x^3+1$, cioè $G=1001$ e $z=3$. Con il metodo delle stringhe si accodano a $M$ tre zeri e si divide per $G$ con XOR, ripetendo sul primo 1 che resta finché restano tre bit.

Qui il resto è $000$. Il messaggio è già divisibile per $G(x)$, quindi la parola trasmessa è $M$ seguito da tre zeri:

$$1011000101101010\,000$$

Lo stesso messaggio è quindi protetto in due modi. Il checksum a 8 bit aggiunge 8 bit di controllo, il CRC con $x^3+1$ ne aggiunge 3. Entrambi servono solo a rivelare gli errori.