Lezione 10 · Canale 2 · giovedì 22 ottobre 2026
FCI · Reti
Una configurazione con errori
Esattamente errori
Parità singola: errori non rivelati
Distanza di un codice
Errori corretti
Errori rivelati, senza correggere
Hamming , ordine dei bit
Hamming , controlli
Checksum, blocchi
Controllo in ricezione
Un codice a parità singola aggiunge a una stringa di bit un solo bit di controllo, la somma modulo 2 dei bit della stringa. La parola di codice ha così bit e un numero pari di 1. Il codice rivela ogni errore che inverte un numero dispari di bit, ma non vede un numero pari di inversioni.
Il canale inverte alcuni bit della parola trasmessa . Il vettore d'errore , di bit, ha un 1 nelle posizioni invertite, e si riceve , con somma bit a bit modulo 2. Metà dei vettori possibili ha un numero pari di 1: la parità non cambia e l'errore passa inosservato. Non è però una probabilità, perché pochi errori sono molto più probabili di molti.
Sia la probabilità che un bit sia ricevuto errato (BER, bit error rate). Si assume che i bit si sbaglino in modo indipendente. Nella pratica gli errori arrivano a raffica, ma l'ipotesi rende il calcolo possibile.
Una configurazione precisa, con bit errati e corretti, ha probabilità
Il rapporto è molto minore di 1, perché è piccolo (valori tipici da a ). Elevato a diventa sempre più piccolo, quindi poche inversioni sono molto più probabili di molte.
Gli errori possono occupare posizioni diverse, perciò la probabilità di averne esattamente è
La parità singola non rivela l'errore quando è pari e almeno 2. È un falso negativo: l'errore non viene segnalato.
Per e si ottiene . È un valore alto se i messaggi sono milioni.
Errori non rivelati dalla parità singola
Due debolezze: un solo bit protegge una stringa lunga e la parola è costruita in modo poco robusto. Servono più bit di controllo e parole di codice scelte meglio.
Le stringhe di bit sono e solo alcune sono parole di codice. Con sono 16. Se tutte lo fossero, un solo errore porterebbe a un'altra parola senza lasciare traccia: manca la ridondanza. Con due bit di controllo e due di messaggio le parole di codice sono 4 su 16.
Conta anche quali 4 si scelgono. Se sono vicine, un piccolo errore porta da una all'altra. Se sono lontane, porta fuori dal codice e il ricevitore se ne accorge. Serve una distanza fra stringhe binarie.
La distanza di Hamming è il numero di posizioni in cui due stringhe della stessa lunghezza differiscono. Per e differiscono la seconda, la terza e la quinta posizione, quindi .
La distanza di un codice è la minima distanza fra due sue parole distinte:
Le stringhe di 3 bit stanno ai vertici di un cubo e la distanza di Hamming è il numero di spigoli da percorrere. Il codice con e ha . Se si trasmette e il canale inverte un bit, si riceve per esempio . Non è una parola di codice, quindi l'errore è rivelato. dista 1 da e 2 da , quindi la parola più vicina è e si corregge.
Il cubo delle stringhe di 3 bit
Nel cubo le croci sono le parole di codice e i cerchi le altre stringhe. Con due errori si arriva a , che dista 1 da e 2 da : la correzione sceglie e sbaglia. Con tre errori si arriva a stessa e non si rivela niente.
In un codice di distanza ogni bit errato sposta la stringa ricevuta a distanza 1 dalla precedente. Con meno di errori la stringa non può essere un'altra parola di codice, quindi l'errore si rivela. Se non si tenta di correggere, si rivelano fino a errori.
Per correggere si sceglie la parola di codice più vicina a quella ricevuta. La scelta è giusta finché la parola trasmessa resta la più vicina, cioè con al più errori.
Esempio con : e . Con uno o due errori la stringa ricevuta è ancora più vicina a , quindi si corregge. Con tre errori può essere più vicina a e la correzione sbaglia. Per si correggono 2 errori e si rivelano fino a 4.
Il codice migliore ha la distanza minima più grande possibile, e i codici di Hamming danno una regola per costruirlo. Il trasmette 4 bit informativi con 3 bit di controllo , in 7 bit. I bit di controllo non stanno in coda, ma nelle posizioni 1, 2 e 4:
Ogni bit di controllo impone parità pari su un gruppo di bit di informazione:
Con si ottiene , , e la parola . Questo schema ha distanza : corregge un errore, oppure rivela fino a due errori se non si corregge.
Un errore sul bit rompe i controlli di e , che lo contengono, e lascia a posto . Solo sta in e senza stare in , quindi i controlli indicano e basta invertirlo.
Quali controlli contengono un bit
Con due errori la stringa non è una parola di codice, ma i controlli puntano a un solo bit, diverso dai due sbagliati. Un decodificatore che corregge presume un errore solo, inverte quel bit e ottiene un'altra parola di codice, quindi sbaglia. Usato solo per rivelare, il codice riconosce invece anche i due errori.
Il messaggio si dispone in una matrice di righe della stessa lunghezza. Si aggiunge a ogni riga un bit che rende pari il numero di 1, e lo stesso a ogni colonna. Un bit nell'angolo completa la parità delle parità. In ricezione si ricostruisce la matrice e si ricontrollano righe e colonne.
Il checksum è un codice usato da IP (livello 3) e dal livello 4, con blocchi di 16 bit. Qui è la lunghezza di un blocco, non quella del messaggio. Il messaggio ha bit, con multiplo di , e si divide in blocchi . Si somma modulo .
Il checksum è un blocco , l'opposto della somma:
Così, sommando tutti i blocchi insieme al checksum, si ottiene 0. Il ricevitore divide ciò che riceve in blocchi di bit e li somma: con risultato 0 la stringa è una parola di codice, altrimenti c'è un errore.
Esempio con , quindi modulo , e due blocchi e :
Il checksum è . Si verifica che .