Codice Hamming: rilevamento e correzione degli errori con esempi

Cos'è un errore?

I dati trasmessi possono essere danneggiati durante la comunicazione. È probabile che venga influenzato dal rumore esterno o da altri guasti fisici. In una situazione del genere, i dati di input non possono essere uguali ai dati di output. Questa mancata corrispondenza è nota come "Errore".

Gli errori nei dati possono comportare la perdita di dati importanti o protetti. La maggior parte del trasferimento di dati nei sistemi digitali avverrà sotto forma di "trasferimento bit". Anche un piccolo cambiamento può influenzare le prestazioni dell’intero sistema. In una sequenza di dati, se 1 viene modificato in 0 o 0 viene modificato in 1, si parla di "errore bit".

Tipi di errori

Esistono principalmente tre tipi di errori di bit che si verificano nella trasmissione dei dati dal mittente al destinatario.

• Errori a bit singolo
• Errori multipli su bit
• Errori scoppiati

Errori a bit singolo

La modifica apportata a un bit nell'intera sequenza di dati è nota come "errore di singolo bit". Tuttavia, il verificarsi di un errore di singolo bit non è così comune. Inoltre, questo errore si verifica solo in un sistema di comunicazione parallelo perché i dati vengono trasferiti bit a bit in una singola riga. Pertanto, ci sono più possibilità che una singola riga possa essere rumorosa.

Errori multipli su bit

Nella sequenza di dati, se si verifica una modifica in due o più bit di una sequenza di dati da un trasmettitore a un ricevitore, si parla di "errori multipli di bit".

Questo tipo di errore si verifica principalmente nelle reti di comunicazione dati sia di tipo seriale che parallelo.

Errori di scoppio

La modifica del set di bit nella sequenza dei dati è nota come “errore burst”. Questo tipo di errore di dati viene calcolato dalla modifica del primo bit all'ultima modifica del bit.

Cos'è il rilevamento e la correzione degli errori?

Nel sistema di comunicazione digitale l'errore verrà trasferito da un sistema di comunicazione all'altro. Se questi errori non vengono rilevati e corretti, i dati andranno persi. Per una comunicazione efficace, i dati di sistema dovrebbero essere trasferiti con elevata precisione. Ciò verrà fatto identificando innanzitutto gli errori e correggendoli.

Il rilevamento degli errori è un metodo per rilevare gli errori presenti nei dati trasmessi da un trasmettitore a un ricevitore in un sistema di comunicazione dati.

Qui è possibile utilizzare i codici di ridondanza per trovare questi errori, aggiungendoli ai dati quando vengono trasmessi dalla sorgente. Questi codici sono chiamati “Codici di rilevamento errori”.

Tre tipi di codici di rilevamento errori sono:

• Controllo di parità
• Cyclic Redundancy Check (CRC)
• Controllo di ridondanza longitudinale (LRC)

Controllo di parità

• È noto anche come controllo di parità.
• Dispone di un meccanismo economicamente vantaggioso per il rilevamento degli errori.
• In questa tecnica, il bit ridondante è noto come bit di parità. Viene aggiunto per ogni unità di dati. Il numero totale di 1 nell'unità dovrebbe diventare pari, fenomeno noto come bit di parità.

Controllo di ridondanza longitudinale

In questa tecnica di rilevamento degli errori, un blocco di bit è organizzato in formato tabellare. Il metodo LRC ti aiuta a calcolare il bit di parità per ogni colonna. Insieme ai dati originali viene inviato anche l'insieme di questa parità. Il blocco di parità aiuta a verificare la ridondanza.

Controllo di ridondanza ciclico

Il controllo di ridondanza ciclico è una sequenza ridondante che deve essere aggiunta alla fine dell'unità. Ecco perché l'unità di dati risultante dovrebbe diventare divisibile per un secondo numero binario predeterminato.

A destinazione, i dati in arrivo devono essere divisi per lo stesso numero. Nel caso in cui non ci sia resto, allora l'unità dati si presume corretta e viene accettata. Altrimenti, indica che l'unità dati è danneggiata durante la trasmissione e quindi deve essere rifiutata.

Nel codice Hamming, la sorgente codifica il messaggio aggiungendo bit ridondanti nel messaggio. Questi bit ridondanti vengono per lo più inseriti e generati in determinate posizioni nel messaggio per eseguire il processo di rilevamento e correzione degli errori.

Storia del codice di Hamming

• Il codice Hamming è una tecnica creata da RWHamming per rilevare errori.
• Il codice Hamming dovrebbe essere applicato a unità di dati di qualsiasi lunghezza e utilizza la relazione tra dati e bit di ridondanza.
• Lavorò sul problema del metodo di correzione degli errori e sviluppò una serie sempre più potente di algoritmi chiamati codice Hamming.
• Nel 1950 pubblicò il codice Hamming, oggi ampiamente utilizzato in applicazioni come la memoria ECC.

Applicazione del codice di Hamming

Ecco alcune applicazioni comuni dell'utilizzo del codice Hamming:

• satelliti
• Memoria del computer
• Modem
• PlasmaCAM
• Connettori aperti
• Filo schermante
• Processore incorporato

Vantaggi del codice di Hamming

• Il metodo del codice Hamming è efficace sulle reti in cui i flussi di dati vengono forniti per errori a bit singolo.
• Il codice Hamming non solo fornisce il rilevamento di un errore di bit, ma aiuta anche a rientrare il bit contenente l'errore in modo che possa essere corretto.
• La facilità d'uso dei codici di hamming li rende particolarmente adatti all'uso nella memoria del computer e alla correzione di singoli errori.

Svantaggi del codice di Hamming

• Codice di rilevamento e correzione degli errori a bit singolo. Tuttavia, se viene rilevato un errore su più bit, il risultato potrebbe risultare in un altro bit che dovrebbe essere corretto per essere modificato. Ciò può causare ulteriori errori nei dati.
• L'algoritmo del codice Hamming può risolvere solo problemi relativi a bit singoli.

Come codificare un messaggio nel codice Hamming

Il processo utilizzato dal mittente per codificare il messaggio comprende i tre passaggi seguenti:

• Calcolo del numero totale di bit ridondanti.
• Controllo della posizione dei bit ridondanti.
• Infine, calcolando i valori di questi bit ridondanti.

Quando i bit ridondanti di cui sopra sono incorporati nel messaggio, questo viene inviato all'utente.

Passo 1) Calcolo del numero totale di bit ridondanti.

Supponiamo che il messaggio contenga:

• n– numero di bit di dati
• p – numero di bit ridondanti che vengono aggiunti ad esso affinché np possa indicare almeno (n + p + 1) stati diversi.

Qui, (n + p) rappresenta la posizione di un errore in ciascuna delle (n + p) posizioni di bit e uno stato aggiuntivo non indica alcun errore. Poiché i bit p possono indicare 2^p stati, 2^p deve essere almeno uguale a (n + p + 1).

Passo 2) Posizionamento dei bit ridondanti nella posizione corretta.

I bit ridondanti dovrebbero essere posizionati nelle posizioni di bit di potenze di 2. Ad esempio, 1, 2, 4, 8, 16, ecc. Sono indicati come p₁ (nella posizione 1), pag₂ (nella posizione 2), pag₃ (nella posizione 4), ecc.

Passo 3) Calcolo dei valori del bit ridondante.

I bit ridondanti dovrebbero essere bit di parità che rendono il numero di 1 pari o dispari.

I due tipi di parità sono ?

• Il numero totale di bit nel messaggio viene reso pari e viene chiamato parità pari.
• Il numero totale di bit nel messaggio reso dispari viene chiamato parità dispari.

Qui, tutto il bit ridondante, p1, deve essere calcolato come parità. Dovrebbe coprire tutte le posizioni di bit la cui rappresentazione binaria dovrebbe includere un 1 nella prima posizione esclusa la posizione di p1.

P1 è il bit di parità per ogni bit di dati nelle posizioni la cui rappresentazione binaria include un 1 nella posizione meno importante escluso 1 Like (3, 5, 7, 9, ….)

P2 è il bit di parità per ogni bit di dati nelle posizioni la cui rappresentazione binaria include 1 nella posizione 2 da destra, esclusi 2 Like (3, 6, 7, 10, 11,…)

P3 è il bit di parità per ogni bit nelle posizioni la cui rappresentazione binaria include un 1 nella posizione 3 da destra, esclusi 4 Like (5-7, 12-15,…)

Decifrare un messaggio in codice Hamming

Il destinatario riceve messaggi in arrivo che richiedono di eseguire ricalcoli per trovare e correggere gli errori.

Il processo di ricalcolo avviene nei seguenti passaggi:

• Conteggio del numero di bit ridondanti.
• Posizionamento corretto di tutti i bit ridondanti.
• Controllo di parità

Passo 1) Conteggio del numero di bit ridondanti

È possibile utilizzare la stessa formula per la codifica, il numero di bit ridondanti

2^p ? n+p+1

Qui, il numero di bit di dati e p è il numero di bit ridondanti.

Passo 2) Posizionamento corretto di tutti i bit ridondanti

Qui, p è un bit ridondante che si trova nelle posizioni bit di potenze di 2, ad esempio 1, 2, 4, 8, ecc.

Passo 3) Controllo di parità

I bit di parità devono essere calcolati in base ai bit di dati e ai bit ridondanti.

p1 = parità(1, 3, 5, 7, 9, 11…)

p2 = parità(2, 3, 6, 7, 10, 11… )

p3 = parità(4-7, 12-15, 20-23… )

Sintesi

• I dati trasmessi possono essere danneggiati durante la comunicazione
• Tre tipi di errori bit sono 1) Errori bit singoli 2) Errori bit multipli 3) Errori bit burst
• La modifica apportata in un bit nell'intera sequenza di dati è nota come "errore a bit singolo".
• Nella sequenza di dati, se si verifica una modifica in due o più bit di una sequenza di dati da un trasmettitore a un ricevitore, si parla di "errori multipli di bit".
• La modifica del set di bit nella sequenza dei dati è nota come “errore burst”.
• Il rilevamento degli errori è un metodo per rilevare gli errori presenti nei dati trasmessi da un trasmettitore a un ricevitore in un sistema di comunicazione dati
• Tre tipi di codici di rilevamento degli errori sono 1) Controllo di parità 2) Controllo di ridondanza ciclico (CRC) 3) Controllo di ridondanza longitudinale (LRC)
• Il codice Hamming è un codice di linea utile per il rilevamento di errori fino a due errori di bit immediati. È capace di errori a bit singolo.
• Il codice Hamming è una tecnica creata da RWHamming per rilevare errori.
• Le applicazioni comuni dell'utilizzo del codice Hamming sono la memoria del computer satellitare, i modem, il processore incorporato, ecc.
• Il vantaggio più grande del metodo del codice di hamming è efficace sulle reti in cui i flussi di dati vengono forniti per errori a bit singolo.
• Il più grande svantaggio del metodo del codice hamming è che può risolvere solo problemi relativi a bit singoli.
• Possiamo eseguire il processo di crittografia e decodifica del messaggio con l'aiuto del codice hamming.