Codici di Hamming e CRC

Questa nota mette in pratica la teoria dei codici lineari (Codici a blocco lineari e sindromeUn codice a blocco è lineare se la somma (XOR) di due parole di codice è una parola di codice: allora le parole formano un sottospazio di $\mathbb Z_2^n$. Si descrive con la matrice generatrice $G$ ($n\times k$, $\mathbf c=G\mathbf b$; in forma sistematica $G=\binom{I_k}{A}$) e con la matrice di controllo $H$ ($(n-k)\times n$, $H\mathbf c=\mathbf 0$ se e solo se $\mathbf c\in\mathcal C$; per $G$ sistematica $H=[A\mid I_{n-k}]$). La distanza minima è il peso minimo delle parole non nulle e vale $d_{min}\le n-k+1$ (Singleton). La sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ dipende solo dall'errore; la decodifica a distanza minima è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, dove $\varepsilon(\boldsymbol\sigma)$ è il coset leader (vettore di peso minimo con quella sindrome).Codici a blocco lineari e sindrome →) su due codici di uso reale: il codice di Hamming, il più semplice codice correttore, e il CRC (Cyclic Redundancy Check), il codice rivelatore che chiude quasi ogni pacchetto del livello di collegamento (Ethernet, Wi-Fi, ...) e che permette l'ARQ (Tecniche ARQ e loro prestazioniARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore risponde a ogni pacchetto con ACK (corretto) o NACK (errato), e il trasmettitore ritrasmette. Con probabilità di pacchetto errato $p$, $t_{RTT}=t_P+t_A+2\tau_P$ e coda sempre piena, il throughput massimo (frazione di tempo d'aria) è: Stop-and-Wait $S=\frac{t_P(1-p)}{t_{RTT}}$; Go-Back-N con $N=t_{RTT}/t_P$ $S=\frac{1-p}{(N-1)p+1}$; Selective Repeat $S=1-p$. Il ritardo medio è $m_{delay}=t_P+\tau_P+\frac p{1-p}t_{RTT}$ (a coda vuota). Sono solo valori massimi: la coda ARQ è stabile solo se $\lambda$ è minore della velocità di servizio, $\lambda<1/m_y$; altrimenti il throughput è $\min(\lambda,\mu)$. L'efficienza (payload) è $\eta=S,L_D/L$.Tecniche ARQ e loro prestazioni →).

Vedi anche Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di HammingUn codice a blocco è lineare se la somma (bit a bit, modulo 2) di due parole di codice è una parola di codice. Si descrive con la matrice generatrice $G$ ($k\times n$, $\mathbf c=\mathbf mG$) e con la matrice di controllo di parità $H$ ($(n-k)\times n$, $G H^T=0$); in forma sistematica $G=[I_k\mid P]$ e $H=[P^T\mid I_{n-k}]$. La distanza minima è il peso minimo delle parole non nulle. La sindrome $\mathbf s=\mathbf rH^T$ dipende solo dall'errore: se è nulla la parola è valida, altrimenti identifica l'errore (un solo errore ha per sindrome la colonna di $H$ corrispondente). I codici di Hamming $(2^m-1,,2^m-1-m)$ hanno $d_{min}=3$.Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di Hamming → e, per il CRC nel livello di collegamento, Livello di collegamento e framingIl livello di collegamento (DLL) consegna un frame da un nodo a un nodo adiacente su un collegamento. Servizi: framing, accesso al mezzo (MAC) con indirizzi MAC a 48 bit, controllo di flusso, rilevazione e correzione degli errori. Si divide in DLC (framing, controllo di errore e di flusso) e MAC (accesso al mezzo condiviso). Il framing delimita i frame con un flag: nei protocolli a byte (flag di 8 bit, ESC) si usa il byte stuffing, in quelli a bit (flag 01111110) il bit stuffing, che inserisce uno 0 dopo ogni cinque 1 consecutivi.Livello di collegamento e framing →.

Il codice di Hamming

Idea. Per correggere $1$ errore con la decodifica a sindrome basta che ogni errore singolo abbia una sindrome diversa e non nulla: la sindrome di un errore sulla posizione $j$ è la colonna $j$ di $H$ ($H\mathbf e_j=\mathbf h_j$). Quindi $H$ deve avere colonne non nulle e tutte distinte. Con $n-k=h$ righe ci sono al più $2^h-1$ colonne non nulle distinte: il codice di Hamming le usa tutte.

Definizione (codice di Hamming). Per ogni $h\ge2$ è il codice lineare con $H$ di tipo $h\times n$ che ha per colonne tutte le $2^h-1$ sequenze binarie non nulle di $h$ bit: $n=2^h-1$, $k=n-h=2^h-h-1$.

Il tasso tende a $1$ al crescere di $h$: più la parola è lunga, meno pesa la ridondanza ($h=\log_2(n+1)$ bit di parità). (Le slide del corso citano i codici della famiglia come esistenti per $h$ dispari, con $n=2^h-1$ e $k=2^h-h-1$; la costruzione funziona per ogni $h\ge2$, come mostra la tabella.)

Teorema (proprietà del codice di Hamming). (1) $d_{min}=3$. (2) Corregge ogni errore singolo. (3) Per qualunque pattern di $2$ errori la decodifica a sindrome sbaglia. (4) È un codice perfetto: le regioni di decisione sono tutte le sfere di raggio $1$ attorno alle parole e coprono esattamente tutto lo spazio. Dimostrazione. (1) Colonne non nulle: nessuna parola di peso $1$; colonne distinte: nessuna parola di peso $2$ (la somma di due colonne distinte non è nulla). Tra tre colonne ce ne sono sempre dipendenti: prese due colonne distinte $\mathbf h_a,\mathbf h_b$, la loro somma è un'altra colonna non nulla $\mathbf h_c$ (perché le colonne sono tutte le sequenze non nulle), e $\mathbf h_a+\mathbf h_b+\mathbf h_c=\mathbf0$. Dunque esiste una parola di peso $3$: $d_{min}=3$ (si ricordi che $d_{min}$ è il numero minimo di colonne di $H$ linearmente dipendenti). (2) Un errore singolo in $j$ ha sindrome $\mathbf h_j$, diversa da ogni altra colonna e non nulla: il coset leader è $\mathbf e_j$. (3) Con due errori in $a$ e $b$ la sindrome è $\mathbf h_a+\mathbf h_b=\mathbf h_c$: il decodificatore "corregge" la posizione $c$ introducendo un terzo errore. (4) Le sfere di raggio $1$ hanno ciascuna $1+n$ elementi e sono $2^k$: $2^k(1+n)=2^k\cdot2^h=2^n$, uguaglianza nel limite di Hamming (Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione →). $\square$

In termini di rivelazione e correzione: rivela fino a $2$ errori oppure ne corregge $1$ ($d_{min}=3$).

L'esempio $(7,4)$

Con $G=\binom{I_4}{A}$, $A=\begin{pmatrix}1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}$ e $H=[A\mid I_3]$ (Codici a blocco lineari e sindromeUn codice a blocco è lineare se la somma (XOR) di due parole di codice è una parola di codice: allora le parole formano un sottospazio di $\mathbb Z_2^n$. Si descrive con la matrice generatrice $G$ ($n\times k$, $\mathbf c=G\mathbf b$; in forma sistematica $G=\binom{I_k}{A}$) e con la matrice di controllo $H$ ($(n-k)\times n$, $H\mathbf c=\mathbf 0$ se e solo se $\mathbf c\in\mathcal C$; per $G$ sistematica $H=[A\mid I_{n-k}]$). La distanza minima è il peso minimo delle parole non nulle e vale $d_{min}\le n-k+1$ (Singleton). La sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ dipende solo dall'errore; la decodifica a distanza minima è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, dove $\varepsilon(\boldsymbol\sigma)$ è il coset leader (vettore di peso minimo con quella sindrome).Codici a blocco lineari e sindrome →): le colonne di $H$ sono $110,101,011,111,100,010,001$, cioè tutte le $7$ sequenze non nulle. La sindrome è un indirizzo: dice quale bit invertire. Le $16$ parole hanno pesi $0,3,4,7$ con $1,7,7,1$ parole: ogni parola ha sette vicine a distanza $3$, sette a distanza $4$ e una (la complementare) a distanza $7$ (l'insieme delle distanze è lo stesso da ogni parola, come in ogni codice lineare).

Esempio (correzione). $\mathbf b=1011$, $\mathbf c=G\mathbf b=1011010$. Il canale inverte il bit $6$: $\tilde{\mathbf c}=1011000$. $\boldsymbol\sigma=H\tilde{\mathbf c}$: riga $1$ (bit $1,2,4,5$): $1+0+1+0=0$; riga $2$ (bit $1,3,4,6$): $1+1+1+0=1$; riga $3$ (bit $2,3,4,7$): $0+1+1+0=0$; $\boldsymbol\sigma=(0,1,0)$, che è la colonna $6$ di $H$: si inverte il bit $6$ e si ottiene $\hat{\mathbf c}=\mathbf c$.

Esempio (due errori). Si invertono i bit $1$ e $2$: $\tilde{\mathbf c}=0111010$, $\boldsymbol\sigma=\mathbf h_1+\mathbf h_2=110+101=011=\mathbf h_3$: il decodificatore inverte il bit $3$ e produce $\hat{\mathbf c}=0101010$, che è una parola di codice, ma quella sbagliata (ha $3$ bit di differenza da $\mathbf c$).

Prestazioni su un BSC

Sia $P=P_{bit}$ la probabilità d'errore del canale (BSC senza memoria), $n=7$. Il corso confronta due modi di usare il $(7,4)$ (Esercizio - Test del DNA con 4, 5 e 7 provette):

a) Rivelazione. Si sbaglia (errore non rivelato) solo se il pattern d'errore è esso stesso una parola di codice non nulla: peso $3$ (7 pattern), peso $4$ (7), peso $7$ (1): $$P_{undetected}=7P^3(1-P)^4+7P^4(1-P)^3+P^7\ \simeq\ 7P^3(1-P)^4.$$ Una stima più rozza conta tutti i $\binom73=35$ pattern a $3$ errori: $35P^3(1-P)^4$ è una sovrastima di un fattore $5$, perché solo $7$ pattern su $35$ finiscono su una parola di codice. Esempio. $P=0{,}05$: stima rozza $0{,}36\,\%$, stima corretta $7P^3(1-P)^4=0{,}071\,\%$, valore esatto (con tutti e tre i termini) $0{,}075\,\%$.

b) Correzione. La decodifica sbaglia quando ci sono almeno $2$ errori: $P[\hat{\mathbf c}\ne\mathbf c]=1-(1-P)^7-7P(1-P)^6$, e con la stima del corso (si trascurano $\ge3$ errori) $\simeq\binom72P^2(1-P)^5$. Esempio. $P=0{,}05$: esatto $4{,}44\,\%$, stima $4{,}06\,\%$ ($21\cdot0{,}0025\cdot0{,}7738$). Sul bit di informazione, con $d_{min}=3$ ($\frac{3}{7}$ dei bit di una parola sbagliata), $P[b_\ell\ne\hat b_\ell]\simeq\frac37\binom72P^2(1-P)^5=9P^2(1-P)^5$.

Si noti l'enorme differenza: la correzione, per $P=5\%$, sbaglia nel $4\,\%$ dei casi, la rivelazione lascia passare solo lo $0{,}075\,\%$ degli errori. Rivelare è molto più sicuro che correggere, con la stessa ridondanza; il prezzo è dover chiedere la ritrasmissione (ARQ). Per questo i sistemi reali ricorrono all'Hybrid ARQ.

Il codice esteso. Aggiungendo un bit di parità complessiva a un Hamming $(2^h-1,\cdot)$ si ottiene il codice $(2^h,2^h-h-1)$ con $d_{min}=4$: corregge $1$ errore e rivela $2$ (usato nelle memorie ECC).

Il CRC

Dalla parità al polinomio

Un singolo bit di parità non basta: rivela solo un numero dispari di errori. Il CRC (Cyclic Redundancy Check) aggiunge $r$ bit di controllo che dipendono da tutto il messaggio in modo che quasi ogni tipo di errore, in particolare quelli a burst (più bit consecutivi sbagliati, tipici dei canali reali), venga rivelato. È un codice lineare $(n,k)$ con $n=k+r$ e si descrive con i polinomi su $\mathbb Z_2$.

Una sequenza di bit $(a_{n-1},\dots,a_1,a_0)$ si identifica con il polinomio $a(x)=a_{n-1}x^{n-1}+\dots+a_1x+a_0$ a coefficienti in $\mathbb Z_2$; somma e sottrazione sono XOR, il prodotto per $x^i$ è uno scorrimento di $i$ posizioni a sinistra. La divisione tra polinomi si fa come la divisione lunga, con sottrazioni = XOR.

Definizione (codice CRC). Si fissa un polinomio generatore $g(x)$ di grado $r$, con termine noto $1$ (per esempio $g(x)=x^4+x+1\leftrightarrow10011$). Dato il messaggio $m(x)$ di $k$ bit, si calcola il resto $$\rho(x)=\big(m(x)\,x^r\big)\ \mathrm{mod}\ g(x)\qquad(\deg\rho<r)$$ e si trasmette la parola $c(x)=m(x)\,x^r+\rho(x)$, cioè il messaggio seguito dagli $r$ bit del resto (codice sistematico).

Perché funziona: $m(x)x^r$ dà il messaggio seguito da $r$ zeri; sommando il resto $\rho(x)$ (che occupa proprio quei $r$ posti) si ottiene un polinomio divisibile per $g(x)$, perché $m(x)x^r=q(x)g(x)+\rho(x)$ e in $\mathbb Z_2$ $\rho+\rho=0$, quindi $c(x)=q(x)g(x)$. Le parole di codice sono tutti e soli i multipli di $g(x)$ di grado $<n$. La verifica è la stessa operazione: il ricevitore divide la parola ricevuta per $g(x)$; resto nullo $\Rightarrow$ nessun errore rivelato.

Esempio numerico

Messaggio $\mathbf m=1101011011$ ($k=10$) e $g=10011$ ($x^4+x+1$, $r=4$). Si divide $1101011011\,0000$ per $10011$ (a ogni passo, dove il bit di testa è $1$, si fa lo XOR con $g$ e si prosegue):

11010110110000
11010            xor 10011 = 01001
 10011           xor 10011 = 00000
      10110      xor 10011 = 00101
        10100    xor 10011 = 00111
resto = 1110

(i passi sono quelli in cui il bit di testa è $1$; gli altri si saltano scorrendo). Il resto è $\rho=1110$, quindi la parola trasmessa è $\mathbf c=1101011011\,1110$. Verifica del ricevitore: $11010110111110\ \mathrm{mod}\ 10011=0000$ ✓ (nessun errore). Se il canale inverte il terzo bit, $\tilde{\mathbf c}=11110110111110$, il resto è $1110\ne0$: errore rivelato. (I calcoli sono verificati al calcolatore.) La sindrome $\mathbf e(x)\ \mathrm{mod}\ g(x)$ dipende solo dall'errore, come per ogni codice lineare.

Che errori rivela

Con $\tilde c(x)=c(x)+e(x)$ ($e(x)$ = polinomio d'errore), il resto è $e(x)\ \mathrm{mod}\ g(x)$: un errore non è rivelato se e solo se $g(x)$ divide $e(x)$. Ne seguono:

• errore singolo $e(x)=x^i$: rivelato sempre se $g(x)$ ha almeno due termini (un monomio non è multiplo di $g$);
• errori doppi $e(x)=x^i(1+x^j)$: rivelati se $g$ non divide $1+x^j$ per nessun $j$ minore della lunghezza della parola: succede se $g$ è un polinomio primitivo di periodo $\ge n$ (per $g=x^3+x+1$ e $n=7$ lo è);
• numero dispari di errori: sempre rivelato se $(x+1)$ divide $g(x)$ (cioè $g$ ha un numero pari di termini, perché $g(1)=0$);
• burst di lunghezza $\le r$ (cioè $e(x)=x^i\,b(x)$ con $\deg b<r$ e $b(0)=1$): sempre rivelati, perché $\deg b<\deg g$ e quindi $g\nmid b$;
• un burst di lunghezza esattamente $r+1$ sfugge con probabilità $2^{-(r-1)}$ (solo se $b(x)=g(x)$), e un burst più lungo sfugge con probabilità $2^{-r}$.

Verifica numerica con $g=10011$ ($r=4$), parole di $14$ bit: tutti i burst di lunghezza $1$–$4$ sono rivelati ($0$ su $14$, $13$, $24$, $44$ casi non rivelati); dei $80$ burst di lunghezza $5$ ne sfuggono $10=80/8$; dei $144$ di lunghezza $6$, $9=144/16$.

Esempi pratici. CRC-16 (CCITT) $g=x^{16}+x^{12}+x^5+1$ e CRC-32 (Ethernet, Wi-Fi) $g$ di grado $32$: con $r=32$ la probabilità che un errore lungo sfugga è circa $2^{-32}\simeq2{,}3\cdot10^{-10}$. Il calcolo in hardware si fa con un registro a scorrimento di $r$ celle e qualche XOR.

Legame con Hamming

Il codice di Hamming $(7,4)$ è anche ciclico: le sue parole sono i multipli di $g(x)=x^3+x+1\ (1011)$ di grado $<7$, e ogni scorrimento ciclico di una parola è ancora una parola. Con la codifica sistematica del CRC le $16$ parole sono $0000000,\,0001011,\,0010110,\dots,1111111$, hanno peso minimo $3$ e sono un codice equivalente a quello della matrice $G$ delle note precedenti (stesse proprietà, bit di parità disposti in altro ordine). Quindi il CRC con $g=x^3+x+1$ è un Hamming $(7,4)$ se il messaggio è lungo $4$ bit. Se la parola è più lunga di $7$ bit, invece, il polinomio $x^7+1$ è multiplo di $g$ (si fattorizza come $(x+1)(x^3+x+1)(x^3+x^2+1)$): l'errore doppio $e(x)=1+x^7$ non viene più rivelato e $d_{min}$ scende a $2$. Per messaggi lunghi servono quindi polinomi di grado alto, il cui "periodo" supera la lunghezza della parola.

Errori comuni

• Dire che l'Hamming "corregge 2 errori": con due errori sbaglia sempre, non soltanto a volte.
• Dimenticare che l'errore non rivelato dell'Hamming usato come rivelatore richiede un pattern uguale a una parola di codice ($7$ casi a peso $3$), non uno qualsiasi di $\binom73=35$.
• Nel CRC: lo scorrimento $m(x)x^r$ va fatto prima della divisione; sottrazioni = XOR, senza riporti.
• Credere che il CRC corregga: serve solo a rivelare (il bit di parità e il CRC hanno la stessa funzione; il CRC è molto più forte).