Supponiamo di avere a disposizione un canale di comunicazione digitale (ossia attraverso il quale è possibile trasmettere esclusivamente codice binario, 0 o 1). In pratica, nel mondo reale, il canale non risulterà ideale ma presenterà del rumore, il quale può comportare degli errori nella trasmissione dei dati (uno zero può diventare un uno o viceversa). Per semplicità assumiamo che il rumore sia stocastico (casuale) e che ci sia una certa probabilità p, costante nel tempo e uguale per ciascun bit, che avvenga effettivamente un errore di trasmissione.

Questo comporta che la probabilità di trasmettere correttamente un messaggio di lunghezza n bit risulta essere: (1 - p)ⁿ.

Si può vedere, dunque, che per quanto p sia piccola, basta avere dei messaggi abbastanza lunghi affinché la probabilità che ci sia almeno un errore diventi alta.

Come fare, allora?

Una prima forma di controllo: il bit di parità

Un possibile metodo consiste nell'aggiungere un bit di controllo, detto di parità, il quale ci avverte della presenza di un errore. Dal punto di vista pratico, ecco una possibile implementazione…

Supponiamo di dover trasmettere del semplice codice ASCII, limitandoci però a considerare la prima metà della tabella (situazione tipica nella lingua inglese) codificando, dunque, il messaggio in sequenze di 7 bit e supponiamo che la probabilità p di errore per bit della trasmissione sia molto minore di 1/7. Ad ogni sequenza di 7 bit aggiungiamo un bit, detto di parità, il cui valore è zero se il numero di bit uguali a uno nella sequenza è dispari e, ovviamente, uno in caso contrario.

Questo metodo rende possibile l'individuazione di un errore (la probabilità di avere due errori in una sequenza di 7 bit, cosa che inficerebbe il metodo, è assunta essere trascurabile), ma non ci dà alcun aiuto per correggere l'errore, una volta individuato. L'unica soluzione resta ritrasmettere la porzione del messaggio in questione (sempre che sia possibile farlo).

E se potessimo anche correggere gli errori?

Supponiamo, invece, di utilizzare il seguente metodo di trasmissione…

Ogni bit viene ripetuto tre volte: 0 diventa 000 mentre 1 diventa 111.

Cosa succede se riceviamo, ad esempio, la terna 010? Il messaggio originale doveva essere necessariamente o 000 (quindi con un singolo errore, nel secondo bit) o 111 (ma, in questo caso, con un doppio errore di trasmissione!). Ovviamente, se la probabilità di errore per singolo bit è piccola, è molto più probabile che l'errore sia stato solo uno.

Ecco, dunque, come dovremmo tradurre le eventuali terne ricevute (supponendo, ovviamente che non ci sia più di un errore ogni tre bit).

terna	bit
000	0
001	0
010	0
011	1
100	0
101	1
110	1
111	1

P.S.: non si è obbligati a scegliere come chiavi le terne 000 e 111; si potrebbe scegliere, ad esempio, 010 e 101. L'importante è che tutte le altre combinazioni, siano più "vicine" all'una o all'altra chiave.

Con questa definizione, è possibile descrivere il metodo in maniera più rigorosa. Le stringhe "000" e "111" hanno distanza di Hamming 3. Qualsiasi altra combinazione ha distanza di Hamming pari a 1 da una di queste due.

Chiavi con numero di bit maggiore

Osservato come funziona il metodo con chiavi a tre bit, ci si rende conto che è possibile ampliarlo a casi con un numero di bit maggiore. Tuttavia, il metodo non funziona ugualmente bene per un numero qualsiasi di bit. Ad esempio con 4 bit, ci si rende subito conto che 0011 è equidistante da 0000 e da 1111. E, anche se non si è obbligati a scegliere entrambe come chiavi, scegliendone altre si trova che comunque alcune combinazioni vanno sprecate, in quanto equidistanti dalle chiavi.

Supponiamo di considerare messaggi con stringhe a k bit che, una volta codificate con l'analogo del metodo descritto prima, salgono a n bit (con n > k, ovviamente). Si hanno 2^k chiavi diverse, su un totale di 2ⁿ stringhe possibili. Ogni chiave corrisponderà a 2^n-k combinazioni, che coincidono con quelle che hanno distanza di Hamming 0 o 1 dalla chiave. Ma queste ultime devono essere esattamente n + 1 (tutte quelle con un singolo bit variato, più se stessa). Uguagliando si trova n = 2^n-k - 1.

Alcuni esempi:

• 3 bit (1 del messaggio e 2 per i codici di correzione)
• 7 bit (4 del messaggio e 3 per i codici di correzione)
• 15 bit ...

Una possibile disposizione delle chiavi nel caso di 7 bit:

La tabella che segue mostra come varia il numero di bit di correzione rispetto al totale del messaggio.

Ricordando che k = n - l = log₂ (2ⁿ/(n+1)) = n - log₂ (n + 1).

A prima vista, sembrerebbe conveniente scegliere stringhe e chiavi con un numero di bit molto alto, per minimizzare il numero di bit di correzione rispetto al totale. Tuttavia bisogna ricordarsi che con questo metodo si può correggere solo un singolo errore per stringa e all'aumentare del numero di bit, con un rumore casuale, la possibilità di un doppio errore aumenta.

Venendo alle formule, la probabilità di fallimento nella trasmissione per ogni segmento del messaggio lungo n bit (come la chiave), data p come la probabilità di errore per un singolo bit è dunque pari a 1 - "probabilità nessun errore" - "probabilità di un errore", ossia:

P_err = 1 - (1 - p)ⁿ - n p (1 - p)^{n - 1} = 1 - (1 - p)^{n - 1} (1+p(n-1))

Per p << 1/n, si ha, approssimando al primo ordine, che la probabilità di errore nella trasmissione di una singola sequenza è all'incirca:

P_err ~= p²(n-1)(n+4)/2 + O(p³)