Sistemi e Reti - Anno 4 - Modulo 1 - Lezione 03 - Rilevazione Errori: Parita, Checksum, CRC

Sistemi e Reti · Anno 4 · Modulo 1 · Lezione 03

✍ Autore: profgiagnotti · Materia: Sistemi e Reti

Rilevazione degli errori: parità, checksum e CRC

Come il livello Data Link aggiunge bit ridondanti nel trailer per accorgersi di una corruzione e perché parità, checksum e CRC hanno poteri di rilevazione così diversi.

🧪 Simulatore online parità 🧪 Simulatore online checksum 🧪 Simulatore online CRC

// 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

✓Collegare rilevazione e correzione: capire perché parità/checksum/CRC rilevano ma non correggono e preparare lo studio di VRC/LRC e Hamming

// Indice della lezione

1. Perché i bit si corrompono durante la trasmissione 2. Bit di parità: EVEN e ODD 3. Checksum: somma e complemento 4. CRC: polinomio generatore e divisione XOR 5. Confronto tra le tre tecniche 6. Verifica / Esercizio guidato 7. Riepilogo e concetti chiave

1. 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.

📌 Definizione da ricordare

Ridondanza = bit extra che non aggiungono informazione utile ma permettono di verificare l'integrità. Tutto il gioco è: quanta ridondanza aggiungere per ottenere quale probabilità di rilevazione.

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

01 · 1 BIT

Bit di parità

1 bit ridondante. Rileva solo errori singoli (numero dispari di errori).

02 · 8/16 BIT

Checksum

8 o 16 bit ridondanti. Rileva molti errori comuni ma non tutti i pattern.

03 · 16/32 BIT

CRC

16 o 32 bit ridondanti. Potere di rilevazione elevatissimo — standard nei protocolli di rete.

2. 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.

EVEN · PARI

Parità pari

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 vale 1; altrimenti 0.

ODD · DISPARI

Parità dispari

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 · calcolo parità

Dati: 1 0 1 1 0 1 0  → numero di 1 nei dati = 4 (pari) → bit 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) → nessun errore

Scenario B — 1 errore (bit3 1→0): Ricevuto 1 0 0 1 0 1 0 0 → conta 1 = 3 (dispari) ≠ atteso → errore rilevato!

Scenario C — 2 errori: Ricevuto 1 0 0 1 1 1 0 0 → conta 1 = 4 (pari) = atteso → errore NON rilevato!

⚠️ Limite fondamentale della parità

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

💬 Tip del docente

In verifica chiedi sempre: "Quanti 1 ha il dato? La parità è pari o dispari? Quindi il bit di parità vale...?" Fai due contaggi separati: prima dei dati, poi del totale. Se capita la domanda trabocchetto su 2 errori, rispondi: parità non lo vede.

3. 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.

STEP 01

Somma modulo

Somma tutti i byte header+payload modulo 256 (8 bit) o 65536 (16 bit).

STEP 02

End-around carry

Se c'è riporto oltre il limite, lo sommi al bit meno significativo.

STEP 03

Complemento NOT

Inverti tutti i bit. Il risultato è il checksum da inserire nel trailer.

🎯 Esempio in classe — Algoritmo lato mittente

Immagina un frame con byte: 0x44 0x61 0x74 0x69. Sommiamo in binario. Otteniamo somma parziale. Se superiamo 0xFF (per checksum 8 bit) riportiamo l'overflow. Alla fine calcoliamo NOT(somma) → questo è il checksum. Il ricevitore somma dati+checksum: deve ottenere 0xFF (o 0xFFFF).

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 segnala errore.

📌 Dove viene usato il checksum

Checksum a 16 bit in header IP, TCP, UDP. Non è usato come meccanismo primario a livello Data Link: lì il CRC offre protezione superiore e costo accettabile in hardware dedicato.

PSEUDOCODICE · CHECKSUM 8 BIT

mittente:
sum = 0
for each byte b in frame:
sum = (sum + b) mod 256
if overflow: sum = (sum + 1) mod 256  // end-around carry
checksum = NOT(sum)   // complemento bit a bit
trasmetti frame + checksumricevitore:
total = 0
for each byte b in frame_ricevuto + checksum_ricevuto:
total = (total + b) mod 256
if total == 0xFF (oppure 0 con altra convenzione):
OK
else:
ERRORE

4. 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. Grado r → CRC di r bit. Esempio CRC-16-CCITT:

x¹⁶ + x¹² + x⁵ + 1

Coefficienti non nulli → bit 1 nella rappresentazione binaria

1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1

bit 16,12,5,0 a 1 — altri a 0

Algoritmo CRC — passo per passo lato mittente

① CONVERTI

Polinomio → bit

Converti il generatore in sequenza binaria (1 dove coefficiente ≠0).

② ESTENDI

Aggiungi r zeri

Aggiungi in coda al messaggio originale r zeri (r = grado polinomio).

③ DIVIDI XOR

Divisione modulo 2

Esegui divisione XOR del messaggio esteso per la sequenza generatore.

④ RESTO = CRC

Accoda CRC

Il resto è il CRC. Accodalo al messaggio originale (senza zeri) e trasmetti.

Esempio numerico completo

ESEMPIO CRC · m=10011010, g=1011 (x³+x+1, r=3)

// dati di partenza
Messaggio m:         1 0 0 1 1 0 1 0
Generatore g:        1 0 1 1  → grado r=3// passo 1 — aggiunta r=3 zeri
Messaggio esteso:    1 0 0 1 1 0 1 0 0 0 0// passo 2 — divisione XOR (long division modulo 2)
10011010000
1011          ← XOR
----
00101010000  → sposta al prossimo 1
1011
----
... (prosegue fino a fine bit)
resto finale (ultimi 3 bit) = CRC// passo 3 — frame trasmesso
Frame = messaggio + CRC: 1 0 0 1 1 0 1 0 + CRC
Ricevitore verifica: divide frame per g → resto 0 = nessun errore

Verifica lato ricevitore

Metodo A · Resto zero

Divide l'intero frame ricevuto (dati+CRC) per il polinomio generatore. Se resto è 0 → frame corretto, altrimenti errore.

Metodo B · Confronto CRC

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

📌 Perché il CRC è così potente

CRC-32 (Ethernet) rileva: tutti gli errori a singolo bit, tutti i doppi, tutti i dispari, tutti i burst ≤32 bit e la maggioranza dei burst più lunghi. Probabilità errore non rilevato ≈ 2⁻³² ≈ 1 su 4 miliardi.

5. Confronto tra le tre tecniche

Tecnica	Overhead	Potere di rilevazione	Utilizzo tipico
Parità	1 bit	Solo errori su numero dispari di bit	Bus SCSI/PCI, cache CPU
Checksum	8 o 16 bit	Buono ma non garantito su tutti i pattern	Header IP, TCP, UDP
CRC	16 o 32 bit	Elevatissimo — standard industriale	Ethernet, Wi-Fi, HDLC, PPP

⚠️ Errore comune in verifica

Dire che checksum e CRC sono identici. Il checksum fa somma + complemento, il CRC fa divisione XOR con polinomio. Overhead diverso, robustezza diversa, uso diverso. Ricorda: Data Link = CRC, Trasporto/Rete = checksum.

6. Verifica / Esercizio guidato

🔬 Attività in classe

Applica le tre tecniche e verifica cosa succede con errori singoli e doppi.

Dato 1011001, calcola bit parità EVEN e ODD. Simula 1 errore e 2 errori: cosa rilevi?
Frame 2 byte: 0x41 0x42. Calcola checksum 8 bit (somma mod256 + NOT). Verifica ricevitore.
Con m=10011010 e g=1011 calcola il CRC (resto 3 bit) usando divisione XOR. Costruisci frame finale e verifica che diviso per g dia resto 0.
Su https://crccalc.com verifica un CRC-16-CCITT di "Hello" e confronta con calcolo manuale troncato.

✅ Soluzione ragionata — parità

1011001 ha tre 1 → dispari. EVEN: serve aggiungere 1 per rendere pari → trasmesso 10110011 (tot 4 pari). Con 1 errore il conteggio diventa dispari → errore rilevato. Con 2 errori il conteggio torna pari → non rilevato, limite intrinseco.

7. Riepilogo e concetti chiave

✓Rilevazione errori = bit ridondanti nel trailer calcolati sui dati; ricevitore ricalcola e confronta: disaccordo → errore.

✓Parità EVEN/ODD: 1 bit. Rileva solo dispari. Fallisce su pari. Usata in hardware per semplicità.

✓Checksum: somma mod256/65536 + complemento. Più robusto, usato in IP/TCP/UDP.

✓CRC: divisione XOR del messaggio esteso (m + r zeri) per polinomio generatore; resto = CRC; verifica resto 0. Standard Ethernet CRC-32, HDLC CRC-16.

✓Tutte rilevano ma non correggono. Correzione → VRC+LRC o codici di Hamming (Lezione 04).

📚 Prossimo passo — Correzione degli errori: VRC, LRC e Hamming

Ora che sai rilevare, imparerai a correggere: come due parità incrociate (VRC+LRC) localizzano l'errore e come Hamming aggiunge bit di controllo in posizioni potenza di 2 per correggere un bit singolo.

← Lezione precedenteFraming: delimitare le trame nel flusso di bit Prossima lezione →Correzione degli errori: VRC, LRC e codici di Hamming