Rilevazione degli errori: parità, checksum e CRC

di
// obiettivi di apprendimento
✓Spiegare il principio del bit di parità (EVEN e ODD), applicarlo su una sequenza di bit e indicarne il limite rispetto agli errori pari
✓Descrivere il funzionamento del checksum: somma modulo 256, complemento bit a bit lato mittente, verifica lato ricevitore
✓Descrivere il CRC: polinomio generatore, divisione XOR, calcolo del resto lato mittente e verifica lato ricevitore, con esempio numerico completo
✓Confrontare le tre tecniche per potere di rilevazione, overhead e contesti di utilizzo tipici
📄
Slides
Rilevazione errori — parità, checksum e CRC

Perché i bit si corrompono durante la trasmissione

Ogni mezzo trasmissivo introduce disturbi: il rumore elettromagnetico, le attenuazioni, le interferenze tra cavi vicini (crosstalk) o le variazioni di tensione possono alterare il valore di uno o più bit durante il loro percorso dal trasmettitore al ricevitore. Un bit 1 diventa 0, un 0 diventa 1 — e il ricevitore non ha modo di saperlo, a meno che non utilizzi una tecnica di rilevazione degli errori.

La soluzione adottata a livello Data Link è aggiungere al trailer del frame dei bit ridondanti — bit calcolati in funzione dei dati trasmessi. Il ricevitore ripete il calcolo sui dati ricevuti e confronta il risultato con i bit ridondanti nel trailer: se non coincidono, si è verificato un errore.

Esistono tre grandi famiglie di tecniche, ordinate per potenza crescente:

1️⃣
BIT DI PARITÀ
1 bit ridondante. Rileva solo errori singoli (numero dispari di errori).
2️⃣
CHECKSUM
8 o 16 bit ridondanti. Rileva molti errori comuni ma non tutti.
3️⃣
CRC
16 o 32 bit ridondanti. Potere di rilevazione elevatissimo — standard nei protocolli di rete.

Bit di parità

Il bit di parità è la tecnica più semplice. Si aggiunge un solo bit ridondante al termine di una sequenza di bit di dati. Il valore di questo bit è scelto in modo che il numero totale di bit a 1 nell’intera sequenza (dati + bit di parità) sia pari o dispari, a seconda della convenzione scelta.

PARITÀ PARI — EVEN

Il bit di parità è scelto in modo che il numero totale di 1 (dati + parità) sia pari. Se i dati hanno un numero dispari di 1, il bit di parità vale 1; altrimenti vale 0.

PARITÀ DISPARI — ODD

Il bit di parità è scelto in modo che il numero totale di 1 sia dispari. Funziona in modo speculare rispetto alla parità pari.

Esempio con parità pari (EVEN)

Esempio — trasmissione e ricezione con parità EVEN
// mittente — calcola il bit di parità
Dati: 1 0 1 1 0 1 0    →    numero di 1 nei dati = 4 (pari)    →    bit di parità EVEN = 0
Sequenza trasmessa: 1 0 1 1 0 1 0 0    →    totale 1 = 4 (pari ✓)
// scenario A — nessun errore
Ricevuto: 1 0 1 1 0 1 0 0  →  conta 1 = 4 (pari) = atteso ✓  →  nessun errore
// scenario B — un errore (bit 3 da 1 a 0)
Ricevuto: 1 0 0 1 0 1 0 0  →  conta 1 = 3 (dispari) ≠ atteso  →  errore rilevato!
// scenario C — due errori (bit 3 e bit 5 alterati)
Ricevuto: 1 0 0 1 1 1 0 0  →  conta 1 = 4 (pari) = atteso  →  errore NON rilevato!
⚠️ Il limite fondamentale del bit di parità

Il bit di parità rileva solo gli errori su un numero dispari di bit (1, 3, 5…). Se si alterano esattamente 2, 4, 6… bit, la parità rimane invariata e l’errore passa inosservato. Nonostante questo limite, la parità è ancora usata in hardware con alta velocità di operazione (bus SCSI, PCI, cache CPU) dove la semplicità vale più della perfezione.

Checksum

Il checksum migliora il bit di parità usando più bit ridondanti — tipicamente 8 o 16. L’algoritmo somma tutti i byte (o parole a 16 bit) del frame e invia il complemento in uno della somma come campo di controllo nel trailer.

Algoritmo lato mittente

1
Somma tutti i byte del frame (header + payload) in aritmetica binaria modulo 256 (per checksum a 8 bit) o modulo 65536 (per checksum a 16 bit)
2
Se c’è un riporto finale oltre il limite (overflow), lo somma al bit meno significativo del risultato (end-around carry)
3
Prende il complemento bit a bit (NOT) della somma — inverte tutti i bit. Il risultato è il checksum che viene inserito nel trailer del frame.

Verifica lato ricevitore

Il ricevitore somma tutti i byte ricevuti (dati + checksum). Se non ci sono errori, la somma dovrebbe dare tutti 1 (0xFF per 8 bit, 0xFFFF per 16 bit) — oppure fare 0 se si considera anche il complemento. Qualsiasi deviazione da questo valore atteso segnala un errore.

// dove viene usato il checksum

Il checksum è usato nei protocolli di livello superiore come IP (header checksum a 16 bit), TCP e UDP (checksum a 16 bit sull’intero segmento). Non viene usato come meccanismo primario a livello Data Link dove il CRC offre protezione superiore.

CRC — Cyclic Redundancy Check

Il CRC è la tecnica più robusta tra le tre ed è quella adottata in quasi tutti i protocolli di rete moderni: Ethernet usa CRC-32 (4 byte nel campo FCS), Wi-Fi usa CRC-32, HDLC e PPP usano CRC-16. La sua forza deriva dall’uso dell’aritmetica modulare e dalla teoria dei polinomi.

Il polinomio generatore

Ogni implementazione di CRC è definita da un polinomio generatore scelto in modo da massimizzare il rilevamento degli errori. Un polinomio di grado r produce un CRC di r bit. Ad esempio il CRC-16-CCITT è definito da:

x¹⁶ + x¹² + x⁵ + 1
I coefficienti non nulli del polinomio corrispondono ai bit 1 nella rappresentazione binaria
1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1
bit 16, bit 12, bit 5, bit 0 (costante 1) sono a 1 — tutti gli altri a 0

Algoritmo del CRC — passo per passo

Algoritmo CRC — Lato Mittente
①
Converti il polinomio generatore in sequenza di bit (i bit a 1 sono le posizioni in cui il coefficiente è ≠ 0)
②
Aggiungi in coda al messaggio originale tanti zeri quant’è il grado r del polinomio generatore (il numero di bit di CRC che verranno prodotti)
③
Esegui la divisione XOR del messaggio esteso (con gli zeri aggiunti) per la sequenza del polinomio. La divisione XOR è simile a una divisione lunga binaria, ma invece della sottrazione si usa XOR
④
Il resto della divisione è il CRC. Va accodato al messaggio originale (senza gli zeri aggiunti). Questo frame completo viene trasmesso.

Esempio numerico completo

Esempio CRC — messaggio 10011010, polinomio x³+x+1 → 1011
// dati di partenza
Messaggio originale (m):     1 0 0 1 1 0 1 0
Polinomio generatore (g):  1 0 1 1  → grado r=3
// passo 1 — aggiunta di r=3 zeri al messaggio
Messaggio esteso:  1 0 0 1 1 0 1 00 0 0
// passo 2 — divisione XOR (simulazione)
1 0 0 1 1 0 1 0 0 0 0
1 0 1 1                   ← XOR con generatore
0 0 1 0 1 0 1 0 0 0 0    → sposta a sinistra al prossimo 1
    … (divisione prosegue fino al termine dei bit) …
// il resto finale (ultimi r=3 bit) è il CRC
// passo 3 — frame trasmesso
Frame = messaggio + CRC:  1 0 0 1 1 0 1 0 + CRC
Il ricevitore divide il frame ricevuto per il polinomio → resto = 0 se nessun errore

Verifica lato ricevitore

Il ricevitore ha due metodi equivalenti per verificare l’integrità:

// metodo A

Divide l’intero frame ricevuto (dati + CRC) per il polinomio generatore. Se il resto è 0, il frame è corretto. Se è diverso da 0, c’è un errore.

// metodo B

Estrae il CRC dal frame, ricalcola il CRC sui soli dati e confronta: se il CRC ricalcolato coincide con quello ricevuto, il frame è integro.

// perché il CRC è così potente

CRC-32 (usato in Ethernet) rileva: tutti gli errori a singolo bit, tutti gli errori a doppio bit, tutti gli errori su un numero dispari di bit, tutti i burst di errori di lunghezza ≤ 32 bit, e la grande maggioranza dei burst più lunghi. La probabilità di un errore non rilevato con CRC-32 è dell’ordine di 2⁻³² ≈ 1 su 4 miliardi.

Confronto tra le tre tecniche

TecnicaOverheadPotere di rilevazioneUtilizzo tipico
Parità1 bitSolo errori su numero dispari di bitBus SCSI/PCI, cache CPU
Checksum8 o 16 bitBuono ma non garantito su tutti i patternHeader IP, TCP, UDP
CRC16 o 32 bitElevatissimo — standard industrialeEthernet, Wi-Fi, HDLC, PPP
📌 Riepilogo — Punti chiave
  • Le tecniche di rilevazione errori aggiungono bit ridondanti nel trailer calcolati in funzione dei dati. Il ricevitore ripete il calcolo e confronta: disaccordo → errore.
  • Bit di parità (EVEN/ODD): 1 bit ridondante. Rileva solo errori su numero dispari di bit. Fallisce con errori su numero pari di bit. Usato in hardware per semplicità.
  • Checksum: somma modulo 256/65536 + complemento bit a bit. Più robusto della parità. Usato in IP, TCP, UDP.
  • CRC: divisione XOR del messaggio esteso (con r zeri aggiunti) per il polinomio generatore. Il resto è il CRC. Il ricevitore verifica che la divisione del frame ricevuto per il polinomio dia resto 0. Potere di rilevazione elevatissimo: standard in Ethernet (CRC-32), HDLC (CRC-16).
  • Tutte e tre rilevano gli errori ma non li correggono — per la correzione servono tecniche diverse (VRC+LRC o Hamming, che vedremo nella lezione 4).

Lascia un commento