Einführung
Billionen über Billionen von Nachrichten schießen jede Millisekunde zwischen der Erde und benachbarten Galaxien hin und her.
Doch die Übertragung über solche Entfernungen ist knifflig.
Lästige Sonneneruptionen, zeitliche Verzerrungen, verirrte Kräfte und sogar der Flügelschlag eines Weltraum-Schmetterlings können dazu führen, dass sich während der Übertragung ein zufälliges Bit ändert.
Stell dir jetzt die Folgen vor:
- Den intergalaktischen Aktienmarkt zum Absturz bringen, wenn aus „billig kaufen" „jetzt verkaufen" wird.
- Den Kontakt zum Kepler-Whirl-System verlieren, wenn aus „neues Wurmloch sichern" „neues Wurmloch sickern" wird.
- Oder das Universum in existenziellen Horror stürzen, indem ein Cowboy-Emoji 🤠 durch ein Clown-Emoji 🤡 ersetzt wird.
Beschädigte Nachrichten zu erkennen, ist nicht nur wichtig, sondern entscheidend.
Der Empfänger muss wissen, wann etwas schiefgelaufen ist, bevor die Katastrophe zuschlägt.
Doch wie?
Wissenschaftler und Ingenieure aus dem ganzen Universum kämpfen seit Äonen mit diesem Problem.
Ganze kosmische KI-Supercluster arbeiten sich durch die Daten.
Und dann, eines Tages, taucht eine Legende wieder auf: eine uralte, mächtige Methode, geflüstert in Debugging-Foren, gemurmelt von Ingenieuren, die zu viel gesehen haben ...
Das Paritätsbit!
Eine Methode, so einfach und so mächtig, dass sie die interstellare Kommunikation retten könnte.
Anleitung
Deine Aufgabe ist es, bei der Implementierung
- des Senders, der die Übertragungssequenz berechnet, und
- des Empfängers, der sie dekodiert,
zu helfen.
Ein Paritätsbit ist eine einfache Möglichkeit, Übertragungsfehler zu erkennen.
Sender und Empfänger können immer nur genau acht Bits auf einmal senden und empfangen (einschließlich des Paritätsbits).
Das Paritätsbit wird so gesetzt, dass jede Übertragung eine gerade Anzahl von 1-Bits enthält, und das Paritätsbit ist immer das erste Bit von rechts.
Wenn der Empfänger also 11000001, 01110101 oder 01000000 empfängt (d. h. eine Übertragung mit einer ungeraden Anzahl von 1-Bits), weiß er, dass ein Fehler vorliegt.
Nachrichten sind jedoch selten so kurz und müssen, wenn sie länger sind, in einer Sequenz übertragen werden.
Betrachte zum Beispiel die Nachricht 11000000 00000001 11000000 11011110 (oder C0 01 C0 DE in Hexadezimal).
Da jede Übertragung genau acht Bits enthält, kann sie nur sieben Datenbits und das Paritätsbit enthalten.
Nach jeweils sieben Datenbits muss also ein Paritätsbit eingefügt werden:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
Die Übertragungssequenz für diese Nachricht sieht so aus:
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
Die Daten in der ersten Übertragung der Sequenz (1100000) haben zwei 1-Bits (eine gerade Anzahl), also ist das Paritätsbit 0.
Die erste Übertragung wird zu 11000000 (oder C0 in Hexadezimal).
Die Daten in der nächsten Übertragung (0000000) haben null 1-Bits (wieder eine gerade Anzahl), also ist das Paritätsbit wieder 0.
Die zweite Übertragung wird damit zu 00000000 (oder 00 in Hexadezimal).
Die Daten für die nächsten beiden Übertragungen (0111000 und 0001101) haben drei 1-Bits.
Ihre Paritätsbits werden auf 1 gesetzt, damit sie eine gerade Anzahl von 1-Bits in der Übertragung haben.
Sie werden als 01110001 und 00011011 übertragen (oder 71 und 1B in Hexadezimal).
Die letzte Übertragung (1110) hat nur vier Datenbits.
Da immer genau acht Bits übertragen werden und das Paritätsbit das rechteste Bit ist, werden drei 0-Bits und danach das Paritätsbit ergänzt, um auf acht Bits zu kommen.
Jetzt sieht sie so aus (wobei _ das Paritätsbit ist):
1110 000_
↑↑↑ (added 0 bits)
Es gibt wieder eine ungerade Anzahl von 1-Bits, also ist das Paritätsbit 1.
Die letzte Übertragung der Sequenz wird zu 11100001 (oder E1 in Hexadezimal).
Die gesamte Übertragungssequenz für diese Nachricht ist 11000000 00000000 01110001 00011011 11100001 (oder C0 00 71 1B E1 in Hexadezimal).
