Codice Hamming(7,4).html

Raffigurazione grafica dei 4 bit di dati e dei 3 bit di parità e quali bit si applicano a quali bit

Il codice Hamming(7,4) è un codice di Hamming che codifica 4 bit di data in 7 bit, aggiungendo 3 bit di parità.

Oggi, per codice Hamming ci si riferisce a uno specifico codice (7,4) creato da Richard W. Hamming nel 1950 mentre lavorava come teorico ai laboratori Bell Telephone negli anni 40. Hamming inventò il codice nel 1950 per consentire un correzione degli errori durante le trasmissioni e ridurre il rapporto risorse computazionali / tempo sprecato^[1].

Il codice di Hamming aggiunge tre bit di controllo addizionali ad ogni quattro bit di messaggio. L'algoritmo di Hamming (7,4) può correggere ogni errore di singolo bit, oppure rivelatore tutti gli errori di singolo bit e gli errori su due bit. Questo significa che in situazioni in cui il canale di trasmissione in cui gli errori non sono in burst (gruppi vicini), il codice Hamming (7,4) è efficace (poiché il canale deve essere molto disturbato per avere un rumore che cambi 2 bit su 7). In altre parole, la distanza di Hamming tra le parole trasmesse e ricevute non deve essere maggiore di uno per essere correggibili.

modifica Scopo

Lo scopo del codice di Hamming è di creare un insieme di bit di parità che si intersechino in modo tale che un errore su un singolo bit di dati o su un singolo bit di parità possa essere rivelato e corretto.

Bit #	1	2	3	4	5	6	7
Bit trasmesso	$p 1$	$p 2$	$d 1$	$p 3$	$d 2$	$d 3$	$d 4$
$p 1$	(SI)	(NO)	(SI)	(NO)	(SI)	(NO)	(SI)
$p 2$	(NO)	(SI)	(SI)	(NO)	(NO)	(SI)	(SI)
$p 3$	(NO)	(NO)	(NO)	(SI)	(SI)	(SI)	(SI)

Questa tabella descrive quali bit di parità coprono quali bit trasmessi nel messaggio codificato. Per esempio $p 2$ protegge i bit 2, 3, 6, e 7. È anche illustrato da quale bit di parità è coperto un bit trasmesso. Per esempio $d 1$ è protetto da $p 1$ e $p 2$ ma non $p 3$ . Questa tabella è molto simile alla matrice di controllo di parità ( $\mathbf{H}$ ) nella prossima sezione.

Inoltre, se le colonne dei bit di parità sono rimosse nella tabella sopra

	$d 1$	$d 2$	$d 3$	$d 4$
$p 1$	(SI)	(SI)	(NO)	(SI)
$p 2$	(SI)	(NO)	(SI)	(SI)
$p 3$	(NO)	(SI)	(SI)	(SI)

se si considerano solo le righe 1, 2 e 4 della matrice generatrice del codice ( $\mathbf{G}$ ) sotto è ancora evidente la somiglianza.

Quindi, proteggendo opportunamente i bit, tutti gli errori con distanza di Hamming 1 possono essere rivelati e corretti, che è lo scopo del codice di Hamming.

modifica Matrici di Hamming

I codici di Hamming possono essere calcolati in termini di algebra lineare attraverso matrici poiché i codici di Hamming sono codici lineari. Per i codici di Hamming vengono definite due matrici di Hamming: la matrice generatrice del codice $\mathbf{G}$ e la matrice di controllo di parità $\mathbf{H}$ :

$\mathbf{G} := \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$

$\mathbf{H} := \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix}.$

Posizione dei bit dei dati e dei bit di parità

Come menzionato prima le righe 1, 2, e 4 della matrice $\mathbf{G}$ sono familiari in quanto mappano i bit di dati nei loro bit di parità:

$p 1$ protegge $d 1$ , $d 2$ , $d 4$
$p 2$ protegge $d 1$ , $d 3$ , $d 4$
$p 3$ protegge $d 2$ , $d 3$ , $d 4$

Le righe rimanenti (3, 5, 6, 7) mappano i dati nelle loro posizioni nel messaggio codificato e altro non sono che la matrice identità. In realtà, queste quattro righe sono linearmente indipendenti e formano la matrice identità (per costruzione).

Anche altre tre righe di $\mathbf{H}$ sono famigliari. Queste righe sono usate per calcolare il vettore sindrome alla ricezione e se il vettore sindrome è il vettore nullo (tutti zero) allora la parola ricevuta è senza errori; se invece è diversa da zero allora il suo valore indica quale bit è stato invertito.

I 4 bit di dati — ordinati in un vettore $\mathbf{p}$ — sono moltiplicati da $\mathbf{G}$ (i.e., $\mathbf{Gp}$ ) ed è preso il modulo 2. I quattro bit originali di dati sono quindi convertiti in 7 bit (da qui il nome "Hamming(7,4)") con l'aggiunta di 3 bit di parità.

La prima tabla sopra mostra la corrispondenza tra ogni bit di dati e di parità e le loro posizioni finali, ma questo può essere rappresentato con un diagramma di Venn. Il primo diagramma mostra tre cerchi (uno per ogni bit di parità) che racchiudono i bit di dati e la protezione di ogni bit di parità. Il secondo diagramma (qui a destra) è identico, ma è segnata la posizione dei bit. Per il resto dell'articolo si useranno i bit di esempio:

$\mathbf{p} = \begin{pmatrix} d_1 \\ d_2 \\ d_3 \\ d_4 \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}$

modifica Codifica

Codifica di esempio. La parità dei cerchi rosso, verde e blu è pari.

Si supponga che si vogliano trasmettere questi dati su un un canale rumoroso. Supponiamo che la probabilità che un bit 0 cambi in 1 sia la stessa che un bit 1 cambi in 0 (rumore simmetrico). Prendiamo il prodotto di G e p e ne facciamo il modulo 2, per determinare il messaggio da trasmettere x:

$\mathbf{x} = \mathbf{G} \mathbf{p} = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2 \\ 3 \\ 1 \\ 2 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix}$

Quindi trasmetteremo 0110011 prodotto dal messaggio originale 1011.

Nel diagramma a destra, i 7 bit della parola codificata sono inseriti nelle loro rispettive posizioni; dall'osservazione è chiaro che la parità dei cerchi rosso, verde e blu è pari:

il cerchio rosso ha due 1
il cerchio verde ha due 1
il cerchio blu ha quattro 1

Se durante la trasmissione un bit viene invertito allora la parità di 2 dei 3 cerchi sarà scorretta e il bit errato può essere determinato (anche se si tratta di un bit di parità) usando il fatto che la parità di tutti i tre i cerchi deve essere pari.

modifica Controllo di parità

Se non avvengono errori durante la trasmissione, la parola codificata ricevuta $r$ è identica a quella trasmessa $x$ :

$\mathbf{r} = \mathbf{x}$

Il ricevitore moltiplica $H$ e $r$ per ottenere il vettore sindrome $\mathbf{z}$ , che indica se è avvenuto un errore, e nel caso lo sia per quale bit. Facendo questa moltiplicazione per il nostro esempio e prendendo il modulo 2:

$\mathbf{z} = \mathbf{H}\mathbf{r} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2 \\ 4 \\ 2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}$

Poiché la sindrome $z$ è il vettore nullo, il ricevitore può concludere che non sono avvenuti errori. Questa affermazione è basata sull'osservazione che quando un vettore di dati è moltiplicato per $\mathbf{G}$ , avviene un cambiamento della base che porta il messaggio codificato ad appartenere al kernel di $\mathbf{H}$ . Se non avviene niente durante la trasmissione, allora $\mathbf{r}$ rimarrà nel kernel di $\mathbf{H}$ e la moltiplicazione darà il vettore nullo.

modifica Correzione degli errori

Supponiamo invece che sia avvenuto un errore su un singolo bit . Matematicamente, si può scrivere

$\mathbf{r} = \mathbf{x} +\mathbf{e}_i$

modulo 2, dove $e i$ è il i-esimo vettore unitario, cioè un vettore nullo con un 1 nella posizione i-esima, contando da 1.

$e_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$

Quindi l'espressione precedente significa che è avvenuto un singolo errore nella posizione i.

Se moltiplichiamo questo vettore per $H$ :

$\mathbf{Hr} = \mathbf{H} \left( \mathbf{x}+\mathbf{e}_i \right) = \mathbf{Hx} + \mathbf{He}_i$

Poiché $x$ è il dato trasmesso, esso è senza errore, e quindi il risultato del prodotto di $H$ e $x$ è zero. Quindi

$\mathbf{Hx} + \mathbf{He}_i = \mathbf{0} + \mathbf{He}_i = \mathbf{He}_i$

Il prodotto di $H$ con l'i-esimo vettore della base estrae la colonna i-esemi di $H$ . Per esempio, supponiamo di aver introdotto un errore sul bit numero 5

$\mathbf{r} = \left( \mathbf{x}+\mathbf{e}_5 \right) = \left( \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \right) = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix}$

Un errore sul bit numero 5 causa una parità sbagliata nei cerchi rosso e verde

Il diagramma a destra mostra come il bit sbagliato (mostrato in blu) causa una parità sbagliata (mostrata in rosso) nei cerchi rosso e verde. Il bit sbagliato può essere riconosciuto calcolando la parità dei cerchi rosso, verde e blue. Se viene trovato una parità sbagliata allora il bit che si sovrappone ai cerchi dell'unico bit di parità sbagliato è il bit con l'errore. Nell'esempio, i cerchi rosso e verde hanno parità sbagliata, quindi il bit corrispondete all'intersezione del cerchio rosso e verde, ma non blu, indica il bit sbagliato.

Ora,

$\mathbf{z} = \mathbf{Hr} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}$

che corrisponde alla quinta colonna di $\mathbf{H}$ . Inoltre, grazie alla costruzione dell'algoritmo la sindrome 101, che corrisponde al valore 5, indica la posizione dove si è verificato l'errore. Quindi l'errore può essere corretto (negando il valore del bit):

$\mathbf{r}_{corretto} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ \overline{1} \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix}$

Questo valore ricevuto adesso è uguale a quello trasmesso $\mathbf{x}$ .

modifica Decodifica

Una volta che dal vettore ricevuto è stato eliminato l'eventuale errore il messaggio ricevuto va decodificato nei 4 bit originali.

Si definisce la matrice $\mathbf{R}$ :

$\mathbf{R} = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}$

Il valore ricevuto $p r$ è

$\mathbf{p_r} = \mathbf{R} \mathbf{r}$

e usando l'esempio sopra

$\mathbf{p_r} = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}$

modifica Errori multipli

È stato introdotto un errore sui bit 4 e 5 (mostrati in blu) a cui corrisponde una parità sbagliata nel cerchio verde (mostrato in rosso)

Non è difficile mostrare che solo gli errori di singolo bit possono essere corretti usando questo schema. Alternativamente, il codice può essere usato per rivelare un errore singolo o doppio, semplicemente notando che il prodotto di H è non nullo quando questi errori avvengono. Nel diagramma a destra i bit 4 e 5 sono invertiti. Questo provoca un solo errore di parità nel cerchio verde, ma l'errore non è correggibile.

Inoltre, il codice Hamming (7,4) non può distinguere tra errori di singolo bit e errori su due bit.

modifica Tutti i codici

Poiché la sorgente è formata da solo 4 bit ci sono solo 2⁴ = 16 possibili parole trasmissibili. Si può includere anche un ottavo bit per un controllo di parità extra che consente in aggiunta di rivelare gli errori doppi, ma non di correggerli. (I bit di dati sono in blu; i bit di parità sono in rosso; il bit extra di parità in verde.)

Data $({\color{blue}d_1}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})$	Hamming(7,4)		Hamming(7,4) con bit di parità extra (Hamming(8,4))
	Trasmesso $({\color{red}p_1}, {\color{red}p_2}, {\color{blue}d_1}, {\color{red}p_3}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})$	Diagramma	Trasmesso $({\color{red}p_1}, {\color{red}p_2}, {\color{blue}d_1}, {\color{red}p_3}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4}, {\color{green}p_4})$	Diagramma
0000	0000000		00000000
1000	1110000		11100001
0100	1001100		10011001
1100	0111100		01111000
0010	0101010		01010101
1010	1011010		10110100
0110	1100110		11001100
1110	0010110		00101101
0001	1101001		11010010
1001	0011001		00110011
0101	0100101		01001011
1101	1010101		10101010
0011	1000011		10000111
1011	0110011		01100110
0111	0001111		00011110
1111	1111111		11111111

modifica Note

^ History of Hamming Codes. URL consultato il 03-04-2008.