Introduzione
Trilioni su trilioni di messaggi sfrecciano tra la Terra e le galassie vicine ogni millisecondo.
Ma trasmettere su distanze così lunghe è complicato.
Fastidiose eruzioni solari, distorsioni temporali, forze vaganti e persino il battito d'ali di una farfalla spaziale possono far cambiare un bit casuale durante la trasmissione.
Ora immagina le conseguenze:
- Far crollare il Mercato Azionario Intergalattico quando «compra basso» diventa «vendi subito».
- Perdere il contatto con il sistema Kepler Whirl quando «salva nuovo cunicolo» diventa «scava nuovo cunicolo».
- O precipitare l'universo in un orrore esistenziale sostituendo un'emoji di cowboy 🤠 con un'emoji di clown 🤡.
Rilevare i messaggi corrotti non è soltanto importante: è fondamentale.
Il ricevente deve sapere quando qualcosa è andato storto, prima che il disastro colpisca.
Ma come?
Scienziati e ingegneri di tutto l'universo combattono questo problema da eoni.
Interi supercluster di IA cosmiche macinano i dati.
E poi, un giorno, riemerge una leggenda: un metodo antico e potente, sussurrato nei forum di debug, mormorato da ingegneri che hanno visto troppo...
Il bit di parità!
Un metodo così semplice, così potente, che potrebbe davvero salvare la comunicazione interstellare.
Istruzioni
Il tuo compito è aiutare a implementare
- il trasmettitore, che calcola la sequenza di trasmissione, e
- il ricevitore, che la decodifica.
Un bit di parità è un modo semplice per rilevare gli errori di trasmissione.
Trasmettitori e ricevitori possono trasmettere e ricevere esattamente otto bit alla volta (bit di parità incluso).
Il bit di parità viene impostato in modo che ci sia un numero pari di bit 1 in ogni trasmissione, ed è sempre il primo bit da destra.
Quindi, se il ricevitore riceve 11000001, 01110101 o 01000000 (cioè una trasmissione con un numero dispari di bit 1), sa che c'è un errore.
Tuttavia, i messaggi sono raramente così brevi e, quando sono più lunghi, vanno trasmessi in una sequenza.
Per esempio, consideriamo il messaggio 11000000 00000001 11000000 11011110 (o C0 01 C0 DE in esadecimale).
Dato che ogni trasmissione contiene esattamente otto bit, può contenere solo sette bit di dati più il bit di parità.
Un bit di parità va quindi inserito dopo ogni sette bit di dati:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
La sequenza di trasmissione di questo messaggio è questa:
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
I dati della prima trasmissione della sequenza (1100000) contengono due bit 1 (un numero pari), quindi il bit di parità è 0.
La prima trasmissione diventa 11000000 (o C0 in esadecimale).
I dati della trasmissione successiva (0000000) contengono zero bit 1 (di nuovo un numero pari), quindi anche qui il bit di parità è 0.
La seconda trasmissione diventa così 00000000 (o 00 in esadecimale).
I dati delle due trasmissioni seguenti (0111000 e 0001101) contengono tre bit 1.
I loro bit di parità vengono impostati a 1, in modo che la trasmissione abbia un numero pari di bit 1.
Vengono trasmesse come 01110001 e 00011011 (o 71 e 1B in esadecimale).
L'ultima trasmissione (1110) contiene solo quattro bit di dati.
Dato che si trasmettono esattamente otto bit alla volta e il bit di parità è il bit più a destra, si aggiungono tre bit 0 e poi il bit di parità per arrivare a otto bit.
Ora appare così (dove _ è il bit di parità):
1110 000_
↑↑↑ (added 0 bits)
C'è di nuovo un numero dispari di bit 1, quindi il bit di parità è 1.
L'ultima trasmissione della sequenza diventa 11100001 (o E1 in esadecimale).
L'intera sequenza di trasmissione di questo messaggio è 11000000 00000000 01110001 00011011 11100001 (o C0 00 71 1B E1 in esadecimale).
