Bit invertiti
Sindrome
Ricevuto
Bit di dati per bit inviato

Di più sui codici a correzione d'errore

Simulatore di codici a correzione d'errore

Ogni messaggio che viaggia lungo un filo, nell'aria o su un disco graffiato raccoglie errori: i bit passano da 0 a 1 e viceversa. Un codice a correzione d'errore aggiunge alcuni bit extra scelti con cura, così che il destinatario possa trovare e riparare il danno senza chiedere di nuovo. Digita quattro bit di dati, guarda il codice di Richard Hamming trasformarli in sette, inverti un bit qualsiasi e osserva tre cerchi sovrapposti puntare dritto all'errore. Poi invia un intero messaggio attraverso un canale rumoroso e confronta ciò che arriva con e senza il codice. Digita quattro bit di dati, per esempio 1011, e l'app aggiunge tre bit di parità per formare una parola di codice di Hamming a 7 bit. Fai clic su un bit qualsiasi, nei cerchi o nella riga, per invertirlo come farebbe il rumore; fai di nuovo clic per ripristinarlo. Ogni cerchio deve contenere un numero pari di 1: i cerchi il cui controllo fallisce indicano il bit sbagliato, e il decodificatore lo ripristina. Attiva il bit di parità extra per vedere due errori rilevati invece che corretti in modo sbagliato. Più in basso, invia un testo attraverso un canale rumoroso con e senza il codice.

Come funziona

  1. Digita quattro bit di dati e guarda la parola di codice a sette bit con i suoi tre bit di parità, nei cerchi e in una riga.
  2. Fai clic sui bit per invertirli e osserva quali cerchi falliscono, dove punta la sindrome e se il decodificatore ripara la parola.
  3. Attiva il bit di parità extra, poi invia un messaggio attraverso il canale rumoroso e confronta i risultati con e senza il codice.

Come il codice di Hamming trova un errore

I sette bit sono numerati da 1 a 7. I bit 1, 2 e 4 sono bit di parità, e i quattro bit di dati occupano le posizioni 3, 5, 6 e 7. Il bit di parità 1 rende pari il numero di 1 tra le posizioni 1, 3, 5 e 7, quelle il cui numero in binario finisce con 1; il bit 2 fa lo stesso per 2, 3, 6 e 7, e il bit 4 per 4, 5, 6 e 7. Disegnando i controlli come tre cerchi sovrapposti, ogni bit si trova esattamente nei cerchi che lo controllano. Quando un bit si inverte, i cerchi che lo contengono diventano dispari. Leggi i controlli falliti come un numero binario, la sindrome, e ottieni la posizione del bit sbagliato.

Che cosa offre un bit in più

Con due bit invertiti la sindrome indica un terzo bit, innocente, e il decodificatore peggiora le cose. Aggiungere un ottavo bit che rende pari l'intera parola risolve il problema: un errore cambia la parità complessiva, due errori la lasciano pari mentre alcuni cerchi falliscono. Il codice esteso, noto come SECDED (single error correction, double error detection: correzione di un errore, rilevamento di due), corregge un errore e ne rileva due in modo affidabile, così il destinatario può richiedere di nuovo quel blocco. È il codice usato nella memoria ECC dei server. Su un canale rumoroso, il codice trasforma molti errori sparsi in pochi, purché due inversioni cadano raramente nello stesso blocco.

Domande frequenti

Perché i bit di parità sono nelle posizioni 1, 2 e 4?

Perché sono le potenze di due, e ciascuna ha un solo 1 in binario. Il bit di parità 2ᵏ controlla ogni posizione il cui numero binario ha un 1 al posto k. Un bit invertito nella posizione 6 = 110 in binario fa fallire i controlli di 2 e 4 e lascia intatto quello di 1, e i controlli falliti compongono 110, la posizione stessa.

Quanto costa la protezione?

Il codice (7,4) invia 7 bit ogni 4 bit di dati, un tasso di 4/7: il 75% in più. Il codice esteso ne invia 8 per 4, il doppio. I codici di Hamming più lunghi costano meno: 15 bit trasportano 11 bit di dati, 31 ne trasportano 26. I codici moderni come i codici LDPC e i codici polari, usati nel Wi-Fi e nel 5G, si avvicinano molto al tasso migliore che Claude Shannon dimostrò possibile nel 1948.

Che cosa succede con tre errori?

Il codice di Hamming semplice può essere ingannato del tutto: due parole di codice qualsiasi differiscono in almeno tre bit, quindi tre inversioni possono trasformare una parola di codice valida in un'altra, e nessun controllo fallisce. L'app lo segnala come errore non rilevato. I sistemi reali rendono rari questi casi scegliendo un codice abbastanza forte per il livello di rumore.

Dove si usano i codici a correzione d'errore?

Quasi ovunque i dati digitali viaggino o vengano memorizzati: memoria ECC dei computer, dischi rigidi e SSD, CD, DVD e dischi Blu-ray, codici QR, che restano leggibili anche con un pezzo strappato, telefoni cellulari e Wi-Fi, televisione digitale e messaggi delle sonde spaziali come Voyager, che inviano ancora dati da oltre il Sistema solare.

Il mio messaggio viene inviato da qualche parte?

No. Il canale rumoroso è simulato nel tuo browser, e il tuo messaggio e le tue impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor