Come funziona il codice di Hamming lavoro?

Question

Durante la trasmissione dei dati, il codice di Hamming permette evidentemente di ricreare i dati che è stato danneggiato oltre il filo (un errore codice di correzione).

Come funziona e quali sono i suoi limiti, se del caso?

Ci sono soluzioni migliori per la correzione degli errori (al contrario di ritrasmissione)? Ci sono circostanze in cui la ritrasmissione è meglio?

Answer 1

Proviamo a spiegarlo un po ':

Abbiamo un certo numero 3 bit. Le possibilità possono essere presentate come un cubo in cui ogni bit rappresenta un asse. Gli otto possibilità sono sugli angoli.

000 --------001
 | \         | \
 | 100---------101
 |  |        |  |
 |  |        |  |
010-|-------011 |
   \|          \|
   110---------111

Ogni difetti (per esempio 101 viene letto come 100) determina uno spostamento su una linea sul cubo.

Se si utilizzano due bit per i dati e il terzo per un controllo di parità (ad esempio per esempio parità pari). Perdiamo 4 datapoints. Ma ha il vantaggio che siamo in grado di rilevare un singolo guasto bit (che trasforma un ancora conteggio di 1 di in un conteggio dispari di quelli). I numeri dispari sono contrassegnati con *. E vediamo che ogni parola dispari (erroneamente trasmessa) è alle strette da anche le parole (giustamente trasmesse). Quindi, se riceviamo 100, possiamo essere sicuri che sia sbagliato.

Ma (con un singolo guasto bit) la rappresentazione corretta avrebbe potuto essere 000, 101 o 110. Così possiamo rilevare qualcosa è stato sbagliato, ma non siamo in grado di rilevare cosa non andava:

 000 -------*001
  | \         | \
  |*100---------101
  |  |        |  |
  |  |        |  |
*010-|-------011 |
    \|          \|
    110--------*111

Questo è chiamato un errore di un bit di codice di rilevamento.

Se si usa un altro po 'per il controllo e quindi rimuovere uno per i dati. Siamo lasciati con 1 databit e 2 "bit di controllo". In questo caso, lascia supporre 000 e 111 sono rappresentazioni di dati validi e gli altri sei non lo sono. Ora abbiamo una situazione interessante, se un bit è storpiato durante il trasporto. Se mandiamo 000 e riceviamo 010, si vede che 010 ha un vicino valido (000) e due quelli non validi (110 e 011). Così ora sappiamo che abbiamo intenzione di inviare 000 e sono in grado di correggere che:

 000 -------*001
  | \         | \
  |*100--------*101
  |  |        |  |
  |  |        |  |
*010-|------*011 |
    \|          \|
   *110---------111

Questo si chiama un errore di un bit di codice di correzione.

Si prega di notare che un codice di correzione di errore di un bit è anche un codice di rilevamento di errore a due bit.

E per dirla più in generale.

Se avete n controllare bit, si dispone di un errore di n po 'la rilevazione di codici. Se si dispone di bit di controllo 2n, si dispone di un codice di errore n po 'di correzione.

Ovviamente si deve ordinare i codici "valido", in modo che non confinano tra loro.

Answer 2

Ecco la panoramica davvero di alto livello.

Suppose that every time I send a message, I send thrie copies of the text.
Suppose that every time I send z message, I send three copies of the teyt.
Suppose that every tyme I send a message, I send three copies if the tezt.

Confrontando personaggi e prendendo un semplice voto di maggioranza in ogni posizione, è possibile correggere i caratteri errati singoli. Tuttavia, il costo di questo schema (quantità di dati che devono essere inviati) è elevata, e non cattura caso improbabile-but-possibilità di due errori in posizioni corrispondenti delle diverse copie (come in l'ultima parola del campione sopra).

codici di Hamming (e altri tipi di codici di correzione degli errori, come Reed-Solomon) si basano su formule che calcolano i dati aggiuntivi (piuttosto che semplice duplicazione). I bit aggiunti dipendono combinazioni dei bit di dati in modo che gli errori di trascrizione rendono pattern rilevabili di modifiche quando il calcolo viene ripetuto alla fine di ricezione.

A fini di illustrazione, iniziamo con semplice parità dispari, aggiungendo un singolo bit per garantire che il numero totale di bit in un messaggio è dispari. Così il 10110110 messaggio diventa 101101100 (cinque 1s, senza supplemento 1 necessario) e il 10010110 messaggio diventa 100101101 (quattro 1s, in più 1 necessario). Se si riceve un messaggio di 101101101 e vedere che ci sono sei 1s, si sa che c'è un errore, ma non si sa dove. Supponiamo di aggiungere più bit di parità, ciascuno su base solo su un parte del messaggio, come illustrato di seguito copiando i bit considerati e usando '-' per i bit ignorati:

10110110
1-1-0-1- => 0
-0-1-1-0 =>  1
10--01-- =>   1
--11--10 =>    0
1011---- =>     0
----0110 =>      1

in modo che il messaggio completo è 10110110011001. Ora supponiamo che un errore di trasmissione cambia il terzo bit nel messaggio, in modo che legga 10010110011001. Quando il ricevitore ri-corre il calcolo di controllo degli errori, non riesce a corrispondere:

10010110
1-0-0-1- => 1*
-0-1-1-0 =>  1
10--01-- =>   1
--01--10 =>    1*
1001---- =>     1*
----0110 =>      1

ed i bit di controllo che non riescono a corrispondere sono esattamente quelle colpite dal terzo bit di dati. Questo è non un vero e proprio, robusto sistema di correzione degli errori; è solo uno schizzo per illustrare come edificio di ridondanza può aiutare a identificare l'esatta natura di un errore.

Answer 3

Troverete i dettagli sul modo in cui funziona qui

ulteriori informazioni generali su codici di errore Corecting è disponibile qui

Answer 4

Informazioni sulla codice di Hamming è disponibile qui e qui .

Per quanto riguarda l'idoneità, questo spiega perché:

1. I codici di errore-correzione come Hamming sono adatti per canali simplex dove nessun ritrasmissione può essere richiesto.

2. di rilevamento degli errori più ritrasmissione è spesso preferito perché è più efficiente.

Per confronto, si consideri un canale con tasso di errore per bit. Lasciate dimensione del blocco sia 1000 bit.

Per correggere un singolo errore (da codice di Hamming) occorrono 10 bit di controllo per blocco. Per trasmettere 1000 blocchi, sono necessari 10.000 bit di controllo (overhead). Per rilevare un errore singolo, un singolo bit di parità per ciascun blocco sarà sufficiente. Per trasmettere 1000 blocchi, un solo blocco exter (a causa del tasso di errore per bit) dovrà essere ritrasmesso, dando l'overhead di soli 2001 (= 1000 + 1001) bit.

Answer 5

codice di Hamming è un trucco matematico per correggere fino a 4 perso bit in una trasmissione seriale. E 'utilizzato anche a favore della "bit di parità" nei moderni chip di memoria.

Le limitazioni sono nel numero di bit che possono essere ripristinati, che non è più di 4. Se più di 4 bit vengono persi, è necessaria la ritrasmissione.

situazioni diversi richiedono tecniche di correzione di errore. Alcune di queste tecniche sono elencati negli altri posti qui.

Answer 6

@GameCat e che dire di errore 2-bit di codice di rilevamento.

In questo caso consente di dire 111 è cambiato a 100. Poi possiamo essere sicuri che ci sono 2 bit errati e sappiamo perché la distanza tra 111 e 100 è 2 bit, e la distanza di 000 e 100 è 1 bit . Quindi, se sappiamo che non c'è errore di 2-bit possiamo essere sicuri di cosa sia il giusto valore.