Come correggere un messaggio utilizzando il Codice di Hamming

Question

Quindi voglio lavorare su questo progetto estivo per correggere errori di trasmissione di un messaggio utilizzando il Codice di Hamming, ma non riesco a capire come funziona davvero.Ho letto molti articoli on-line, ma non ho ben capito l'algoritmo.Qualcuno può spiegare in termini semplici?

Grazie.

Answer 1

E 'tutto su distanza di Hamming .

La distanza di Hamming tra due valori base-2 è il numero di bit in cui differiscono. Quindi, se si trasmettono una, ma ricevo B, quindi il numero di bit che deve essere stato commutato in trasmissione è la distanza di Hamming tra A e B.

codici di Hamming sono utili quando i bit di ogni parola di codice vengono trasmessi in qualche modo separatamente. Non ci interessa se sono seriale o parallelo, ma non sono ad esempio combinati in un valore analogico che rappresenta più bit, o compressa / cifrato dopo la codifica.

Così, ogni bit è indipendentemente (a caso con una certa probabilità fissa), sia ricevuto correttamente o capovolto. Supponendo che la trasmissione è abbastanza affidabile, la maggior parte dei bit vengono ricevuti correttamente. Così gli errori in un piccolo numero di bit sono più probabili, e gli errori simultanei in un gran numero di bit sono improbabili.

Quindi, un codice di Hamming di solito ha lo scopo di correggere gli errori 1-bit, e / o per rilevare errori di 2-bit (vedere l'articolo di Wikipedia per i dettagli dei due tipi principali). Codici che correggere gli errori più grandi / rilevare può essere costruito, ma per quanto ne so non sono usati tanto.

Il codice funziona uniformemente intervallando i punti di codice in "spazio Hamming", che in termini matematici è lo spazio metrico rappresentati da tutti i valori della dimensione della parola rilevante, con distanza di Hamming come metrica. Immaginare che ogni punto di codice è circondato da un piccolo "zona cuscinetto" dei valori validi. Se un valore viene ricevuto che non è un punto di codice, quindi un errore deve essersi verificato, perché solo codice punti validi vengono mai trasmessi.

Se un valore nella zona cuscinetto è ricevuto, allora sull'ipotesi che verificato un errore di 1 bit , il valore che è stato trasmesso deve essere distanza 1 dal valore ricevuto. Ma perché i punti di codice sono sparsi, c'è solo un punto di codice che chiudono. Quindi è "corretto" a quel punto il codice, per motivi che un errore di 1-bit è più probabile che la maggior errore che sarebbe necessario per qualsiasi altro punto di codice per produrre il valore ricevuto. In termini di probabilità, la probabilità condizionata che è stato inviato il punto di codice vicina è maggiore la probabilità condizionale di inviare qualsiasi altro punto del codice, dato che ho ricevuto il valore che ho fatto. Quindi credo che è stato inviato il vicino uno, con una certa fiducia sulla base della affidabilità della trasmissione e il numero di bit in ogni parola.

Se un valore non valido ricevuto, che è equidistante dai due punti di codice, quindi non posso dire che uno è più probabile che sia il valore vero rispetto agli altri. Così a rilevare l'errore, ma non riesco a correggerlo.

Ovviamente errori 3-bit non sono corrette da un codice di Hamming SECDED. Il valore ricevuto è ulteriormente dal valore che effettivamente inviato, che è di qualche altro punto di codice, e ho erroneamente "corretto" al valore errato. Così si sia bisogno di trasmissione sufficientemente affidabili che non si cura di loro, altrimenti è necessario il rilevamento degli errori di livello superiore, come pure (per esempio, un CRC su un intero messaggio).

Answer 2

In particolare da Wikipedia, l'algoritmo è il seguente:

1. Numero di bit a partire da 1:bit 1, 2, 3, 4, 5, ecc.
2. Scrivi la bit di numeri in binario.1, 10, 11, 100, 101, ecc.
3. Tutte le posizioni dei bit che sono potenze di due (hanno solo 1 po ' in forma binaria della loro posizione) sono i bit di parità.
4. Tutte le altre posizioni, con due o più bit a 1 in forma binaria della loro posizione, sono bit di dati.
5. Ogni bit di dati è incluso in un unico insieme di 2 o più bit di parità, come determinata dalla forma binaria della sua posizione bit.
   1. Bit di parità 1 copre tutte le posizioni di bit che hanno il bit meno significativo set:1 bit (il bit di parità stesso), 3, 5, 7, 9, ecc.
   2. Bit di parità 2 copre tutte le posizioni dei bit che sono il secondo bit meno significativo set:bit 2 (il bit di parità stesso), 3, 6, 7, 10, 11, ecc.
   3. Bit di parità 4 copre tutte le posizioni dei bit che sono il terzo bit meno significativo set:i bit da 4 a 7, 12-15, 20-23, etc.
   4. Bit di parità 8 copre tutte le posizioni di bit che è il quarto bit meno significativo set:bit 8-15, 24-31, 40-47, etc.
   5. In generale, ogni bit di parità copre tutti i bit dove il binario E di parità di posizione e la posizione del bit è diverso da zero.

Answer 3

Il wikipedia articolo spiega abbastanza bene.

Se non si capisce un aspetto specifico dell'algoritmo, allora si avrà bisogno di riformulare (o dettaglio) alla tua domanda, in modo che qualcuno possa affrontare la vostra parte specifica del problema.