Codice Hamming(7,4)

Da Wikipedia, l'enciclopedia libera.

1leftarrow.pngVoce principale: Codice di Hamming.

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 dati 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 una 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 rivelare tutti gli errori di singolo bit e gli errori su due bit, ma senza poterli correggere. 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.

Scopo[modifica | modifica wikitesto]

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 SiY X mark.svgNo SiY X mark.svgNo SiY X mark.svgNo SiY
p_2 X mark.svgNo SiY SiY X mark.svgNo X mark.svgNo SiY SiY
p_3 X mark.svgNo X mark.svgNo X mark.svgNo SiY SiY SiY SiY

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 SiY SiY X mark.svgNo SiY
p_2 SiY X mark.svgNo SiY SiY
p_3 X mark.svgNo SiY SiY SiY

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.

Matrici di Hamming[modifica | modifica wikitesto]

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}

e

\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 familiari. 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 tabella 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}

Codifica[modifica | modifica wikitesto]

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

Si supponga che si vogliano trasmettere questi dati su 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.

Controllo di parità[modifica | modifica wikitesto]

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.

Correzione degli errori[modifica | modifica wikitesto]

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-esimi 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 corrispondente 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}.

Decodifica[modifica | modifica wikitesto]

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}

Errori multipli[modifica | modifica wikitesto]

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


Tutti i codici[modifica | modifica wikitesto]

Poiché la sorgente è formata da solo 4 bit ci sono solo 24 = 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 Il codice Hamming per 0000 diventa 0000000 00000000 Il codice Hamming per 0000 diventa 0000000 con il bit di parità extra 0
1000 1110000 Il codice Hamming per 1000 diventa 1000011 11100001 Il codice Hamming per 1000 diventa 1000011 con il bit di parità extra 1
0100 1001100 Il codice Hamming per 0100 diventa 0100101 10011001 Il codice Hamming per 0100 diventa 0100101 con il bit di parità extra 1
1100 0111100 Il codice Hamming per 1100 diventa 1100110 01111000 Il codice Hamming per 1100 diventa 1100110 con il bit di parità extra 0
0010 0101010 Il codice Hamming per 0010 diventa 0010110 01010101 Il codice Hamming per 0010 diventa 0010110 con il bit di parità extra 1
1010 1011010 Il codice Hamming per 1010 diventa 1010101 10110100 Il codice Hamming per 1010 diventa 1010101 con il bit di parità extra 0
0110 1100110 Il codice Hamming per 0110 diventa 0110011 11001100 Il codice Hamming per 0110 diventa 0110011 con il bit di parità extra 0
1110 0010110 Il codice Hamming per 1110 diventa 1110000 00101101 Il codice Hamming per 1110 diventa 1110000 con il bit di parità extra 1
0001 1101001 Il codice Hamming per 0001 diventa 0001111 11010010 Il codice Hamming per 0001 diventa 0001111 con il bit di parità extra 0
1001 0011001 Il codice Hamming per 1001 diventa 1001100 00110011 Il codice Hamming per 1001 diventa 1001100 con il bit di parità extra 1
0101 0100101 Il codice Hamming per 0101 diventa 0101010 01001011 Il codice Hamming per 0101 diventa 0101010 con il bit di parità extra 1
1101 1010101 Il codice Hamming per 1101 diventa 1101001 10101010 Il codice Hamming per 1101 diventa 1101001 con il bit di parità extra 0
0011 1000011 Il codice Hamming per 0011 diventa 0011001 10000111 Il codice Hamming per 0011 diventa 0011001 con il bit di parità extra 1
1011 0110011 Il codice Hamming per 1011 diventa 1011010 01100110 Il codice Hamming per 1011 diventa 1011010 con il bit di parità extra 0
0111 0001111 Il codice Hamming per 0111 diventa 0111100 00011110 Il codice Hamming per 0111 diventa 0111100 con il bit di parità extra 0
1111 1111111 Il codice Hamming per 1111 diventa 1111111 11111111 Il codice Hamming per 1111 diventa 1111111 con il bit di parità extra 1

Note[modifica | modifica wikitesto]

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