gigionismo CodeRilevamento e correzione degli errori con esempi

⚡ Riepilogo intelligente

Il codice di Hamming è un codice lineare di correzione degli errori che aggiunge bit di parità ridondanti in posizioni pari a potenze di due, consentendo a un ricevitore di rilevare errori fino a due bit e di correggere automaticamente qualsiasi errore a singolo bit durante la trasmissione dei dati.

🧭 Scopo: Il codice di Hamming rileva e corregge gli errori di trasmissione incorporando bit di parità che individuano con precisione la posizione di un bit corrotto.
🔢 Parti ridondanti: Il numero di bit di parità (p) soddisfa la regola 2^p ≥ n + p + 1, dove n è il numero di bit di dati.
📍 Placement: I bit di parità occupano le posizioni corrispondenti alle potenze di due (1, 2, 4 e 8), mentre i bit di dati occupano le posizioni rimanenti.
🧮 Hamming(7,4): Una forma comune codifica quattro bit di dati in un totale di sette bit utilizzando tre bit di parità.
🧯 Limitazione: Il codice Hamming standard corregge solo gli errori a singolo bit; un bit di parità complessivo aggiuntivo consente il rilevamento dei doppi errori (SECDED).
🤖 Assistenza AI: I decodificatori basati sull'apprendimento automatico aiutano a individuare canali rumorosi e schemi di errore che i codici fissi da soli potrebbero non rilevare.

Scopri di più

Cos'è un errore?

TransmitI dati trasmessi possono essere corrotti durante la comunicazione. È probabile che vengano influenzati da rumore esterno o altri guasti fisici. In una situazione del genere, i dati di input non possono essere uguali ai dati di output. Questa discrepanza è nota come "errore".

Gli errori nei dati possono causare la perdita di dati importanti o riservati. La maggior parte del trasferimento di dati nei sistemi digitali avviene tramite "trasferimento di bit", e anche una piccola modifica di un singolo bit può influenzare le prestazioni dell'intero sistema. In una sequenza di dati, se un 1 viene trasformato in uno 0, o uno 0 viene trasformato in un 1, si parla di "errore di bit".

Tipi di errori

Esistono principalmente tre tipi di errore di bit che si verificano quando i dati vengono transmitdal mittente al destinatario. Il diagramma seguente illustra come ogni tipo influisce su una sequenza di dati:

Errori a bit singolo
Errori multipli su bit
Errori scoppiati

Errori a bit singolo

Una modifica apportata a un singolo bit nell'intera sequenza di dati è nota come "errore a singolo bit". Il verificarsi di un errore a singolo bit non è molto comune. Si verifica principalmente nei sistemi di comunicazione parallela, perché i dati vengono trasferiti bit per bit su linee separate, quindi c'è una maggiore probabilità che una linea diventi disturbata mentre le altre rimangono pulite.

Errori multipli su bit

Quando due o più bit di una sequenza di dati cambiano tra transmite il ricevitore, è noto come "errore multi-bit".

Questo tipo di errore si verifica sia nelle reti di comunicazione dati seriali che in quelle parallele.

Errori di scoppio

Una modifica a un insieme di bit consecutivi in una sequenza di dati è nota come "errore a raffica". La lunghezza di un errore a raffica viene misurata dal primo bit modificato all'ultimo bit modificato.

Che cosa sono il rilevamento e la correzione degli errori?

Nei sistemi di comunicazione digitale, possono verificarsi errori durante il trasferimento dei dati da un dispositivo all'altro. Se questi errori non vengono rilevati e corretti, i dati vengono persi. Per una comunicazione efficace, i dati devono essere trasferiti con elevata precisione, obiettivo che si raggiunge innanzitutto identificando gli errori e successivamente correggendoli.

Rilevazione errori è un metodo per individuare gli errori presenti nei dati transmitted da un transmitda un ricevitore in un comunicazione dei dati .

I codici di ridondanza vengono utilizzati per trovare questi errori aggiungendo bit extra ai dati quando sono transmitderivati dalla sorgente. Questi bit aggiuntivi sono chiamati "codici di rilevamento degli errori". I tre tipi più comuni di codice di rilevamento degli errori sono:

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

Controllo di parità

È noto anche come controllo di parità.
Fornisce un meccanismo economicamente vantaggioso per il rilevamento degli errori.
In questa tecnica, il bit ridondante aggiunto a ogni unità di dati è noto come bit di parità. Viene impostato in modo che il numero totale di 1 nell'unità risulti pari (parità pari) o dispari (parità dispari).

Controllo di ridondanza longitudinale

In questa tecnica di rilevamento degli errori, un blocco di bit è organizzato in una tabella. Il metodo LRC calcola un bit di parità per ogni colonna e questo insieme di bit di parità viene inviato insieme ai dati originali. Il blocco di bit di parità aiuta il ricevitore a verificare la presenza di ridondanza e a rilevare gli errori.

Controllo di ridondanza ciclico

Il controllo di ridondanza ciclica aggiunge una sequenza di bit ridondanti alla fine dell'unità di dati in modo che l'unità di dati risultante sia esattamente divisibile per un secondo numero binario predeterminato.

A destinazione, i dati in arrivo vengono divisi per lo stesso numero. Se non si ottiene resto, l'unità di dati si considera corretta e viene accettata. In caso contrario, significa che l'unità di dati è stata danneggiata durante la trasmissione e deve essere rifiutata.

Cos'è un Hamming Code?

Il codice di Hamming è un codice lineare utile per rilevare fino a due errori di bit immediati e per correggere errori di singolo bit. La correzione degli errori di questo tipo opera tipicamente a livello di collegamento dati, incapsulando i dati e verificandone l'integrità tra nodi adiacenti.

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

Storia di Hamming Code

Il codice di Hamming è una tecnica sviluppata da RW Hamming per rilevare e correggere gli errori.
Può essere applicato a unità di dati di qualsiasi lunghezza e utilizza la relazione tra bit di dati e bit di ridondanza.
Hamming si dedicò al problema della correzione degli errori e sviluppò una serie di algoritmi sempre più potenti.
Nel 1950 pubblicò il codice di Hamming, tuttora ampiamente utilizzato in applicazioni come la memoria ECC.

Applicazioni di Hamming Code

Ecco alcune applicazioni comuni del codice di Hamming:

satelliti
Memoria del computer (ECC RAM)
Modem
PlasmaCAM
Connettori aperti
Filo schermato
Processori integrati

Vantaggi di Haming Code

Il codice di Hamming è efficace nelle reti in cui i flussi di dati sono esposti a errori di singolo bit.
Non solo rileva un errore di bit, ma aiuta anche a identificare il bit che contiene l'errore in modo che possa essere corretto.
La facilità d'uso dei codici di Hamming li rende particolarmente adatti alla memoria dei computer e alla correzione di singoli errori.

Svantaggi di Hamming Code

Si tratta di un codice di rilevamento e correzione degli errori a singolo bit. Se vengono rilevati errori in più bit, il risultato potrebbe invertire un altro bit che in realtà era corretto, corrompendo ulteriormente i dati.
L'algoritmo del codice di Hamming può risolvere solo problemi a singolo bit.

Come codificare un messaggio in Hamming Code

Il processo utilizzato dal mittente per codificare il messaggio prevede le seguenti tre fasi:

Calcola il numero totale di bit ridondanti.
Determinare la posizione dei bit ridondanti.
Calcola il valore di ciascun bit ridondante.

Quando i bit ridondanti sono incorporati nel messaggio, la parola codice completa viene inviata al destinatario.

Passaggio 1) Calcolare il numero totale di bit ridondanti.

Supponiamo che il messaggio contenga n bit di dati e p parti ridondanti, aggiunte in modo che 2^p può indicare almeno (n + p + 1) stati diversi.

Qui, (n + p) tiene conto della posizione di un errore in ciascuna delle (n + p) posizioni di bit e uno stato extra indica l'assenza di errore. Poiché p bit di parità possono indicare 2^p stati, 2^p deve essere almeno uguale a (n + p + 1).

Passaggio 2) Posizionare i componenti ridondanti nelle loro posizioni corrette.

I bit ridondanti p sono posizionati in posizioni di bit che sono potenze di 2, ad esempio 1, 2, 4, 8 e 16. Sono indicati come p₁ (nella posizione 1), pag₂ (nella posizione 2), pag₃ (in posizione 4), e così via.

Passaggio 3) Calcolare il valore di ciascun bit ridondante.

Ogni bit ridondante è un bit di parità che rende il numero di 1 nel suo gruppo pari o dispari. I due tipi di parità sono:

Parità paritaria: il numero totale di 1 nelle posizioni coperte è pari.
Parità dispari: il numero totale di 1 nelle posizioni coperte è dispari.

Ciascun bit di parità copre uno specifico insieme di posizioni, determinato dalla rappresentazione binaria dei numeri di posizione:

p₁ Controlla ogni posizione il cui valore binario ha un 1 nel bit meno significativo: posizioni 1, 3, 5, 7, 9, 11 e così via.
p₂ controlla ogni posizione il cui valore binario ha un 1 nel secondo bit da destra: posizioni 2, 3, 6, 7, 10, 11 e così via.
p₃ Controlla ogni posizione il cui valore binario ha un 1 nel terzo bit da destra: posizioni da 4 a 7, da 12 a 15 e così via.

Esempio svolto (7,4): Consideriamo i quattro bit di dati 1011. Sono necessari tre bit di parità (2³ = 8 ≥ 4 + 3 + 1), dando una parola codice a sette bit disposta come p₁ p₂ d₁ p₃ d₂ d₃ d₄. Posizionando i dati si ottengono le posizioni 3, 5, 6, 7 = 1, 0, 1, 1. Usando la parità pari: p₁ copre le posizioni 1, 3, 5, 7 (bit 1, 0, 1 → p₁ = 0); p₂ copre 2, 3, 6, 7 (bit 1, 1, 1 → p₂ = 1); p₃ copre 4, 5, 6, 7 (bit 0, 1, 1 → p₃ = 0). Il transmitLa parola in codice ted è quindi 0110011.

Come decodificare un messaggio in Hamming Code

Il ricevitore riceve il messaggio in arrivo ed esegue dei ricalcoli per individuare e correggere gli errori. Il processo di ricalcolo si articola nei seguenti passaggi:

Conta il numero di bit ridondanti.
Posizionare correttamente tutti i bit ridondanti.
Eseguire il controllo di parità.

Passaggio 1) Contare il numero di bit ridondanti. Utilizzare la stessa formula usata per la codifica: 2^p ≥ n + p + 1, dove n è il numero di bit di dati e p è il numero di bit ridondanti.

Passaggio 2) Posizionare correttamente tutti i bit ridondanti. Ogni bit ridondante si trova in una posizione che è una potenza di 2, ad esempio 1, 2, 4 e 8.

Passaggio 3) Eseguire il controllo di parità. I bit di parità vengono ricalcolati a partire dai bit di dati e dai bit ridondanti ricevuti:

p₁ = parità(1, 3, 5, 7, 9, 11, …)
p₂ = parità(2, 3, 6, 7, 10, 11, …)
p₃ = parità(4–7, 12–15, 20–23, …)

I bit di parità ricalcolati formano insieme un numero binario. Se questo numero è zero, non è presente alcun errore; altrimenti, il suo valore indica la posizione esatta del singolo bit corrotto, che viene quindi invertito per correggere il messaggio.

DOMANDE FREQUENTI

La distanza di Hamming è il numero di posizioni di bit in cui due stringhe binarie di uguale lunghezza differiscono. Nei codici di correzione degli errori, la distanza di Hamming minima tra parole codice valide determina quanti errori possono essere rilevati o corretti. Il codice di Hamming standard ha una distanza minima di tre.

Hamming(7,4) codifica quattro bit di dati in una parola codice di sette bit aggiungendo tre bit di parità. Corregge eventuali errori a singolo bit e rileva errori a due bit. La notazione (n, k) indica la lunghezza totale della parola codice n e il numero di bit di dati k.

Un singolo bit di parità rileva solo un numero dispari di errori di bit e non è in grado di localizzarli o correggerli. Il codice di Hamming utilizza più bit di parità in posizioni pari a potenze di due, individuando così con precisione il bit difettoso e correggendolo automaticamente.

Il codice Hamming di base corregge gli errori a un bit, ma può correggere erroneamente gli errori a due bit. L'aggiunta di un bit di parità complessivo che copre l'intera parola codice crea il codice SECDED (correzione di un singolo errore, rilevamento di un doppio errore), aumentando la distanza minima a quattro e rilevando in modo affidabile gli errori a due bit.

Il rilevamento e la correzione degli errori avvengono principalmente a livello del collegamento dati del Modello OSIche inquadra i dati e ne verifica l'integrità tra nodi adiacenti. I protocolli del livello di trasporto aggiungono controlli end-to-end, mentre il mezzo fisico introduce il rumore da cui questi codici proteggono.

Il codice di Hamming è un codice a blocchi lineare. Elabora un blocco di bit di dati di dimensioni fisse alla volta e aggiunge bit di parità, a differenza dei codici convoluzionali che codificano un flusso continuo di bit utilizzando la memoria dei bit precedenti. Questo rende il codice di Hamming semplice e veloce.

I modelli di apprendimento automatico apprendono i pattern di rumore di un canale e prevedono i probabili errori di bit, migliorando la precisione della decodifica rispetto agli schemi fissi. I decodificatori basati sull'intelligenza artificiale per i codici LDPC e polari supportano ora i moderni sistemi 5G e di archiviazione, dove il classico codice di Hamming da solo non è sufficiente.

Copilota GitHub può generare funzioni di codifica e decodifica, maschere di parità e bozze di test unitari da un breve commento. Verifica la matematica della posizione dei bit e il gruppo di paritàpings attentamente, perché l'indicizzazione con errore di uno è una frequente fonte di errori nel codice generato.