Introduction
Des milliards de milliards de messages filent entre la Terre et les galaxies voisines à chaque milliseconde.
Mais transmettre sur d'aussi longues distances est délicat.
Des éruptions solaires agaçantes, des distorsions temporelles, des forces parasites et même le battement d'aile d'un papillon de l'espace peuvent faire changer un bit aléatoire pendant la transmission.
Imagine maintenant les conséquences :
- Faire s'effondrer le marché boursier intergalactique quand « acheter bas » devient « vendre maintenant ».
- Perdre le contact avec le système Kepler Whirl quand « save new worm hole » devient « cave new worm hole ».
- Ou plonger l'univers dans une horreur existentielle en remplaçant un emoji cowboy 🤠 par un emoji clown 🤡.
Détecter les messages corrompus n'est pas seulement important, c'est crucial.
Le récepteur doit savoir que quelque chose a mal tourné avant que le désastre ne frappe.
Mais comment ?
Les scientifiques et les ingénieurs de tout l'univers se battent contre ce problème depuis des éons.
Des grappes entières de supercalculateurs cosmiques d'IA passent les données au crible.
Et puis, un jour, une légende refait surface : une méthode ancienne et puissante, murmurée sur les forums de débogage, marmonnée par des ingénieurs qui en ont trop vu...
Le bit de parité !
Une méthode si simple, si puissante, qu'elle pourrait bien sauver la communication interstellaire.
Instructions
Ton travail consiste à contribuer à l'implémentation
- de l'émetteur, qui calcule la séquence de transmission, et
- du récepteur, qui la décode.
Un bit de parité est un moyen simple de détecter les erreurs de transmission.
Les émetteurs et les récepteurs ne peuvent transmettre et recevoir qu'exactement huit bits à la fois (bit de parité compris).
Le bit de parité est défini de sorte que chaque transmission contienne un nombre pair de bits à 1, et il occupe toujours la première place en partant de la droite.
Ainsi, si le récepteur reçoit 11000001, 01110101 ou 01000000 (c'est-à-dire une transmission avec un nombre impair de bits à 1), il sait qu'il y a une erreur.
Cependant, les messages sont rarement aussi courts et, lorsqu'ils sont plus longs, ils doivent être transmis sous forme de séquence.
Par exemple, prenons le message 11000000 00000001 11000000 11011110 (soit C0 01 C0 DE en hexadécimal).
Chaque transmission contenant exactement huit bits, elle ne peut contenir que sept bits de données, plus le bit de parité.
Il faut donc insérer un bit de parité tous les sept bits de données :
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
Voici à quoi ressemble la séquence de transmission de ce message :
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
Les données de la première transmission de la séquence (1100000) contiennent deux bits à 1 (un nombre pair), donc le bit de parité vaut 0.
La première transmission devient 11000000 (soit C0 en hexadécimal).
Les données de la transmission suivante (0000000) contiennent zéro bit à 1 (un nombre pair, là encore), donc le bit de parité vaut de nouveau 0.
La deuxième transmission devient donc 00000000 (soit 00 en hexadécimal).
Les données des deux transmissions suivantes (0111000 et 0001101) contiennent trois bits à 1.
Leur bit de parité est mis à 1 pour que la transmission contienne un nombre pair de bits à 1.
Elles sont transmises sous la forme 01110001 et 00011011 (soit 71 et 1B en hexadécimal).
La dernière transmission (1110) ne contient que quatre bits de données.
Comme on transmet exactement huit bits à la fois et que le bit de parité est le bit le plus à droite, on ajoute trois bits à 0, puis le bit de parité, pour compléter les huit bits.
Voici ce que cela donne (où _ représente le bit de parité) :
1110 000_
↑↑↑ (added 0 bits)
Il y a de nouveau un nombre impair de bits à 1, donc le bit de parité vaut 1.
La dernière transmission de la séquence devient 11100001 (soit E1 en hexadécimal).
La séquence de transmission complète de ce message est 11000000 00000000 01110001 00011011 11100001 (soit C0 00 71 1B E1 en hexadécimal).
