Wie hängt das Stapeln von Orangen in 24 Dimensionen mit dem Empfang und der Dekodierung von Signalen der Voyager zusammen?

All die unterschiedlichen Datenworte, die ein Sender senden und ein Empfänger erkennen kann, kann man sich als Punkte vorstellen, die in einem großen Raum angeordnet sind.

Bei der Auswahl einer Datencodierung zur Fehlererkennung und -korrektur geht es darum, gültige Codewörter in einem bestimmten Abstand voneinander zu halten. Infolgedessen lässt eine geringfügige Änderung ("Bewegung") eines gültigen Worts es nicht wie ein anderes gültiges Wort aussehen.

Da ich keine Zeichnungen von 24-dimensionalen Kugeln und Hyperwürfeln machen werde, werde ich diese Antwort auf drei Dimensionen beschränken.

3-Bit-Beispiel

Stellen Sie sich ein Datenwort vor, das aus drei Binärziffern besteht. Wir können sie in Form eines Würfels anordnen, indem wir jede Ziffer als Koordinate in einer Dimension behandeln:

Jeder Übertragungsfehler, also ein Bit, das eine '0' mit einer '1' verwechselt oder umgekehrt, entspricht einer Bewegung um einen Schritt entlang einer der Kanten dieses Würfels.

Bei normaler, alltäglicher Kommunikation mit ausreichend niedrigen Fehlerraten können wir alle Codepunkte als valide behandeln:

Aber jedes umgedrehte Bit führt zu einem anderen gültigen Wort. Wenn wir also jedes zweite gültige Wort entfernen, erhalten wir Folgendes:

Jetzt sind alle gültigen Wörter zwei Kanten voneinander entfernt. Ein umgedrehtes Bit bringt uns zu einem ungültigen Wort und wir wissen, dass ein Fehler aufgetreten ist, aber wir können ihn nicht korrigieren, weil es drei mögliche Bits gibt, die umgedreht sein könnten. Dies wird als Code "0 Fehler korrigierend, 1 Fehler erkennend" bezeichnet.

Um die Robustheit zu verbessern, entfernen Sie zwei weitere gültige Codewörter:

Jetzt sind alle gültigen Wörter drei Kanten voneinander entfernt. Wenn ein Bit umkippt, gelangen wir zu einem ungültigen Wort, aber wir können immer noch sagen, woher wir kamen. Wenn zwei Bits vertauscht sind, können wir das Wort nicht korrigieren, da ein anderes gültiges Wort näher am falschen Code liegt als das richtige Wort. Daher wird dieser Code "1 Fehlerkorrektur, 2 Bit-Erkennung" [*] genannt. Das ist das Beste, was wir mit unseren einfachen 3-Bit-Codewörtern erreichen können.

4-Bit-Code-Erweiterung

Wenn Sie ein weiteres Bit hinzufügen, um 4-Bit-Codewörter zu haben, können Sie den Abstand zwischen gültigen Punkten auf drei Kanten des dann 4-dimensionalen Würfels erhöhen. Dies ergibt eine weitere Ebene der Fehlerminderung: Wenn zwei Bits vertauscht werden, erreicht man ein ungültiges Wort genau „in der Mitte“ mehrerer gültiger Wörter. Sie können sich nicht entscheiden, welches das richtige sein könnte, aber zumindest wissen Sie, dass zwei Bits umgedreht sind. Diese Art von Code wird "1 Fehlerkorrektur, 3 Fehlererkennung" genannt.

Reisender

Im Fall von Voyager würde dies nicht ausreichen, also entschied man sich für ein 24 Bit langes Codewort. Von den insgesamt 16 Millionen Codewörtern haben sie nur 4096 als gültig definiert. Dh 12 Bits tragen eigentliche Informationen und weitere 12 werden zur Fehlerkorrektur verwendet. Dies führte zu einem Code "3 Fehler korrigieren, 7 Fehler erkennen". Dh wenn in irgendeinem Wort 3 Bit falsch empfangen wurden, könnte es noch richtig korrigiert werden und wenn bis zu 7 Bit gekippt werden; Zumindest wäre bekannt, dass etwas nicht stimmt. Dieser Code könnte auf die gleiche Weise dargestellt werden, wie ich es oben als die Ecken eines 24-dimensionalen Hyperwürfels getan habe.

Wie hängt das nun mit dem Packen von Kugeln zusammen? Tatsächlich zeigen die drei Bilder die dichteste Packung von Kugeln mit Durchmessern von$\sqrt 1$,$\sqrt 2$Und$\sqrt 3$unter der Bedingung, dass ihre Mittelpunkte an den Ecken des Würfels liegen müssen.[**]

Das sieht natürlich nicht besonders spektakulär aus, wird aber deutlich anspruchsvoller, wenn wir nicht auf digitale, binäre Daten schauen, sondern einen Sender verwenden, der auch Werte dazwischen unterstützt, zB indem er kein einfaches Ein/Aus verwendet Modulation, aber fügen Sie noch eine Amplitudenmodulation hinzu. Indem wir in unserem Beispiel für jede der drei Ziffern einen weiteren Schritt (z. B. Ausschalten/Niedrig/Hoch) hinzufügen, haben wir nicht acht gültige Codewörter, sondern tatsächlich$3^3 = 27$- Beginnen Sie, Ihre Kugeln auf dieses Gitter zu packen!

---

[*] Beachten Sie, dass "Erkennen" nicht bedeutet, dass Sie genau sagen können, wie viele Bitfehler es gibt. Es bezieht sich auf die Anzahl von Bitfehlern, die auftreten können, bevor Sie mit einem anderen gültigen Codewort enden.

[**] Streng genommen haben wir es hier nicht mit Kugeln in einem regulären euklidischen Raum zu tun, sondern mit Hamming-Kugeln - diese werden durch die Menge der Ecken definiert, die eine bestimmte Anzahl von Kanten von ihrem Zentrum entfernt sind. Dies erklärt die Tatsache, dass in einer binären Welt nur die Ecken des Würfels gültige Punkte darstellen, während jeder andere Punkt Bruchkoordinaten hätte und einfach nicht existiert. In den hier angegebenen Beispielen gibt es praktisch keinen Unterschied zwischen den beiden.