Fondamenti di informatica - Laurea triennale Informatica/Errori di comunicazione

Quando i dati vengono trasmessi o memorizzati, possono verificarsi errori di comunicazione: sporco o difetti sui supporti magnetici, guasti dei circuiti, disturbi sulle linee di trasmissione o perfino la radiazione di fondo possono alterare i bit. Per rendere i sistemi affidabili si usano tecniche di codifica capaci di rilevare e talvolta correggere gli errori, spesso integrate nell’hardware e quindi invisibili all’utente.

Bit di parità (Parity bits)

Un metodo semplice di rilevazione è aggiungere a ogni parola di dati un bit extra (bit di parità) scelto in modo che il numero totale di “1” sia:

• dispari (odd parity) oppure
• pari (even parity)

Se, al controllo, la parità non corrisponde a quella attesa, si conclude che c’è stato un errore. In molte memorie, ciò significa che a dati “da 8 bit” in realtà si affianca un 9° bit di parità: in lettura la memoria verifica la parità e, se non torna, restituisce i dati con un avviso di possibile corruzione.

Limite importante: la parità semplice non rileva un numero pari di errori (es. due bit alterati possono “compensarsi” e lasciare invariata la parità). Per ridurre il problema, su sequenze lunghe si usano più bit di controllo (un checkbyte) associati a sottoinsiemi di bit sparsi nel messaggio. Da questo concetto derivano schemi come checksum e CRC (cyclic redundancy check).

Codici correttori di errore (Error-correcting codes)

Esistono anche algoritmi che permettono non solo di rilevare, ma anche di correggere errori. Il concetto chiave è la distanza di Hamming: il numero di posizioni in cui due sequenze di bit differiscono. In un esempio di codice, tutte le parole valide sono separate da una distanza di Hamming almeno 3. Questo comporta che:

• con 1 errore la parola ricevuta non coincide con nessuna parola valida → l’errore si rileva;
• inoltre si può correggere scegliendo la parola valida “più vicina” (distanza minima), perché la sequenza corrotta resta a distanza 1 dall’originale e più lontana dalle altre.

Con distanza minima 3 si riesce a correggere 1 errore e a rilevare fino a 2 errori per parola. Aumentando la distanza (es. almeno 5) si potrebbero correggere più errori, ma progettare codici efficienti diventa complesso ed è parte della teoria algebrica dei codici.

Esempio di correzione usando la distanza di Hamming

Sono rappresentate 4 “lettere” con distanza di Hamming pari a 4

• A = 00000000
• B = 11110000
• C = 11001100
• D = 10101010

Se Trasmetto C:

• Inviato: C = 11001100
• e si altera 1 bit (ultimo 0→1) → Ricevuto: 11001101

Controllo “è una parola valida?”

Non coincide con A/B/C/D ⇒ errore rilevato.

Correzione con “minima distanza” (conto quanti bit differiscono):

• 00000000 d= 5
• 11110000 d= 3
• 11001100 d=1 (minima)
• 10101010 d= 5

Decodifico come C e correggo l’errore (flip del bit sbagliato).

Applicazioni

Queste tecniche sono cruciali in molti ambiti: dischi magnetici ad alta capacità (per compensare difetti della superficie) e CD. I CD audio tollerano una certa probabilità d’errore perché piccoli difetti possono essere mascherati nell’ascolto; per i CD dati, invece, servono correzioni più robuste per rendere la probabilità di errore estremamente bassa.