Codici di rilevamento e correzione degli errori
Sappiamo che i bit 0 e 1 corrispondono a due diversi range di tensioni analogiche. Quindi, durante la trasmissione di dati binari da un sistema all'altro, il rumore può anche essere aggiunto. A causa di ciò, potrebbero esserci errori nei dati ricevuti su un altro sistema.
Ciò significa che un bit 0 può cambiare in 1 o un bit 1 può cambiare in 0. Non possiamo evitare l'interferenza del rumore. Tuttavia, possiamo prima recuperare i dati originali rilevando se sono presenti errori e quindi correggendoli. A tale scopo, possiamo utilizzare i seguenti codici.
- Codici di rilevamento degli errori
- Codici di correzione degli errori
Error detection codes- sono utilizzati per rilevare gli errori presenti nei dati ricevuti (flusso di bit). Questi codici contengono alcuni bit, che sono inclusi (aggiunti) al flusso di bit originale. Questi codici rilevano l'errore, se si è verificato durante la trasmissione dei dati originali (flusso di bit).Example - Codice di parità, codice di Hamming.
Error correction codes- vengono utilizzati per correggere gli errori presenti nei dati ricevuti (flusso di bit) in modo da ottenere i dati originali. I codici di correzione degli errori utilizzano anche la strategia simile dei codici di rilevamento degli errori.Example - Codice di Hamming.
Pertanto, per rilevare e correggere gli errori, bit aggiuntivi vengono aggiunti ai bit di dati al momento della trasmissione.
Codice di parità
È facile includere (aggiungere) un bit di parità a sinistra di MSB oa destra di LSB del flusso di bit originale. Esistono due tipi di codici di parità, vale a dire codice di parità pari e codice di parità dispari in base al tipo di parità scelto.
Even Parity Code
Il valore del bit di parità pari dovrebbe essere zero, se pari numero di quelli presenti nel codice binario. Altrimenti, dovrebbe essere uno. Quindi, il numero pari di quelli presenti ineven parity code. Anche il codice di parità contiene i bit di dati e anche il bit di parità.
La tabella seguente mostra il file even parity codescorrispondente a ciascun codice binario a 3 bit. Qui, il bit di parità pari è incluso a destra dell'LSB del codice binario.
| Codice binario | Even Parity bit | Even Parity Code |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Qui, il numero di bit presenti nei codici di parità pari è 4. Quindi, il numero possibile pari di uno in questi codici di parità pari è 0, 2 e 4.
Se l'altro sistema riceve uno di questi codici di parità pari, non ci sono errori nei dati ricevuti. I bit diversi dal bit di parità pari sono gli stessi del codice binario.
Se l'altro sistema riceve codici di parità diversi da quelli pari, si verificherà uno o più errori nei dati ricevuti. In questo caso, non possiamo prevedere il codice binario originale perché non conosciamo le posizioni dei bit di errore.
Pertanto, anche il bit di parità è utile solo per il rilevamento di errori nel codice di parità ricevuto. Tuttavia, non è sufficiente correggere l'errore.
Codice di parità dispari
Il valore del bit di parità dispari dovrebbe essere zero, se il numero di quelli dispari è presente nel codice binario. Altrimenti, dovrebbe essere uno. Quindi, numero dispari di quelli presenti inodd parity code. Il codice di parità dispari contiene i bit di dati e il bit di parità dispari.
La tabella seguente mostra il file odd parity codescorrispondente a ciascun codice binario a 3 bit. Qui, il bit di parità dispari è incluso a destra dell'LSB del codice binario.
| Codice binario | Bit di parità dispari | Codice di parità dispari |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Qui, il numero di bit presenti nei codici di parità dispari è 4. Quindi, il numero possibile di bit presenti in questi codici di parità dispari è 1 e 3.
Se l'altro sistema riceve uno di questi codici di parità dispari, non ci sono errori nei dati ricevuti. I bit diversi dal bit di parità dispari sono gli stessi del codice binario.
Se l'altro sistema riceve codici di parità diversi da quelli dispari, si verifica uno o più errori nei dati ricevuti. In questo caso, non possiamo prevedere il codice binario originale perché non conosciamo le posizioni dei bit di errore.
Pertanto, il bit di parità dispari è utile solo per il rilevamento di errori nel codice di parità ricevuto. Tuttavia, non è sufficiente correggere l'errore.
Codice di Hamming
Il codice Hamming è utile sia per il rilevamento che per la correzione degli errori presenti nei dati ricevuti. Questo codice utilizza più bit di parità e dobbiamo posizionare questi bit di parità nelle posizioni delle potenze di 2.
Il minimum value of 'k' per cui la seguente relazione è corretta (valida) non è altro che il numero richiesto di bit di parità.
$$ 2 ^ k \ geq n + k + 1 $$
Dove,
'n' è il numero di bit nel codice binario (informazioni)
'k' è il numero di bit di parità
Pertanto, il numero di bit nel codice di Hamming è uguale a n + k.
Lascia il Hamming codeè $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ e bit di parità $ p_ {k}, p_ {k-1}, .... p_ {1} $. Possiamo posizionare i bit di parità "k" solo in potenze di 2 posizioni. Nelle restanti posizioni di bit, possiamo posizionare gli "n" bit di codice binario.
In base ai requisiti, possiamo utilizzare la parità pari o dispari durante la formazione di un codice Hamming. Tuttavia, la stessa tecnica di parità dovrebbe essere utilizzata per scoprire se sono presenti errori nei dati ricevuti.
Segui questa procedura per la ricerca parity bits.
Trova il valore di p1, in base al numero di quelli presenti nelle posizioni dei bit b 3 , b 5 , b 7 e così via. Tutte queste posizioni di bit (suffissi) nel loro binario equivalente hanno "1" al posto di 2 0 .
Trova il valore di p2, in base al numero di quelli presenti nelle posizioni dei bit b 3 , b 6 , b 7 e così via. Tutte queste posizioni di bit (suffissi) nel loro binario equivalente hanno "1" al posto di 2 1 .
Trova il valore di p3, in base al numero di quelli presenti nelle posizioni dei bit b 5 , b 6 , b 7 e così via. Tutte queste posizioni di bit (suffissi) nel loro binario equivalente hanno "1" al posto di 2 2 .
Allo stesso modo, trova altri valori di bit di parità.
Segui questa procedura per la ricerca check bits.
Trova il valore di c 1 , in base al numero di quelli presenti nelle posizioni dei bit b 1 , b 3 , b 5 , b 7 e così via. Tutte queste posizioni di bit (suffissi) nel loro binario equivalente hanno "1" al posto di 2 0 .
Trova il valore di c 2 , in base al numero di quelli presenti nelle posizioni dei bit b 2 , b 3 , b 6 , b 7 e così via. Tutte queste posizioni di bit (suffissi) nel loro binario equivalente hanno "1" al posto di 2 1 .
Trova il valore di c 3 , in base al numero di quelli presenti nelle posizioni dei bit b 4 , b 5 , b 6 , b 7 e così via. Tutte queste posizioni di bit (suffissi) nel loro binario equivalente hanno "1" al posto di 2 2 .
Allo stesso modo, trova altri valori dei bit di controllo.
L'equivalente decimale dei bit di controllo nei dati ricevuti fornisce il valore della posizione del bit, dove è presente l'errore. Basta completare il valore presente in quella posizione del bit. Pertanto, otterremo il codice binario originale dopo aver rimosso i bit di parità.
Esempio 1
Cerchiamo di trovare il codice di Hamming per il codice binario, d 4 d 3 d 2 d 1 = 1000. Consideriamo i bit di parità pari.
Il numero di bit nel codice binario dato è n = 4.
Possiamo trovare il numero richiesto di bit di parità utilizzando la seguente relazione matematica.
$$ 2 ^ k \ geq n + k + 1 $$
Sostituisci, n = 4 nella relazione matematica sopra.
$$ \ Rightarrow 2 ^ k \ geq 4 + k + 1 $$
$$ \ Rightarrow 2 ^ k \ geq 5 + k $$
Il valore minimo di k che ha soddisfatto la relazione di cui sopra è 3. Quindi, abbiamo bisogno di 3 bit di parità p 1 , p 2 e p 3 . Pertanto, il numero di bit nel codice di Hamming sarà 7, poiché ci sono 4 bit nel codice binario e 3 bit di parità. Dobbiamo inserire i bit di parità e i bit di codice binario nel codice di Hamming come mostrato di seguito.
Il 7-bit Hamming code è $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1 } p_ {2} bp_ {1} $
Sostituendo i bit del codice binario, il codice Hamming sarà $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1} $. Ora, troviamo i bit di parità.
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
Sostituendo questi bit di parità, il Hamming code sarà $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $.
Esempio 2
Nell'esempio precedente, abbiamo ottenuto il codice Hamming come $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $. Ora, cerchiamo di trovare la posizione dell'errore quando il codice ricevuto è $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $.
Ora, cerchiamo di trovare i bit di controllo.
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
Il valore decimale dei bit di controllo fornisce la posizione dell'errore nel codice Hamming ricevuto.
$$ c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10} $$
Pertanto, l'errore presente nel terzo bit (b 3 ) del codice di Hamming. Basta completare il valore presente in quel bit e rimuovere i bit di parità per ottenere il codice binario originale.