Fehlerkorrektur

Alice und Bob haben einen erstaunlichen Trick herausgefunden. Sie tauschen Nachrichten aus, indem sie einen Draht entweder hart oder weich zupfen, um eine Null oder eine Eins zu übertragen. Aufgrund von Windböen können jedoch während der Übertragung falsche Nullen oder Einsen auftreten, was zu Fehlern führt. Sie haben jedoch einen Weg gefunden, fehlerfrei zu kommunizieren, selbst in Gegenwart von Störgeräuschen. Wie könnten sie das tun? In den 1940er Jahren stand Richard Hamming vor einem ähnlichen Problem, während er in den Bell Laboratories arbeitete. In den Bell Telephone Laboratories führen wir etwa 10% der Experimente auf einem Computer durch und etwa 90% im Labor. Ich erwarte, dass wir mit der Zeit 90% auf dem Computer und 10% im Labor machen werden. Geschwindigkeit, Kosten und Aufwand sprechen für den Computer gegenüber dem Laboransatz. Zu dieser Zeit speicherten die Computer Informationen auf Lochkarten, wobei eine Eins oder eine Null durch ein Loch respektive kein Loch dargestellt wurde. Dieses System war fehleranfällig, weil es üblich war, dass Karten verbogen wurden oder von Anfang an falsch gelocht wurden. So konnten Löcher übersehen oder keine Löcher versehentlich durchstochen werden, was zu vertauschten Bits führte. Diese Fehler führten dazu, dass das gesamte System zum Stillstand kam, bis die Fehlerstelle manuell gefunden und korrigiert werden konnte. Hamming machte es sich zur Aufgabe, eine Methode zu entwickeln, die einzelne Bitfehler automatisch erkennen und korrigieren konnte, ohne die Berechnungen zu unterbrechen. Seine Lösung beruhte auf der intuitiven Idee der Wiederholung. Etwas, das wir alle tun, wenn wir mit Störungen konfrontiert sind oder die Möglichkeit besteht, dass ein Teil unserer Nachricht verfälscht wird. Seine fehlerkorrigierenden Codes basierten auf dem einfachen Konzept des Paritätsbits. Ein Paritätsbit ist ein einzelnes Bit, das am Ende einer Nachricht hinzugefügt wird und angibt, ob die Anzahl der Einsen in der Nachricht gerade oder ungerade ist. Wenn ein einzelner Fehler auftritt, kann der Empfänger diesen dann erkennen, weil das Paritätsbit nicht mehr übereinstimmt. Um jedoch einzelne Fehler erkennen und korrigieren zu können, musste Hamming mehr Paritätsbits hinzufügen, um den Fehlerort zu identifizieren. Dies führt zu seinem Sieben-Vier-Code, der jedem Block von vier Datenbits wie folgt drei Paritätsbits hinzufügt. Zuerst beginnen wir mit den drei Paritätsbits, die durch einen Kreis dargestellt werden können. Diese Kreise überschneiden sich, um vier Bereiche zu erzeugen. Die vier Datenbits werden in einer bestimmten Reihenfolge in diese Bereiche gelegt. Um die Paritätsbits zu berechnen, betrachten wir einen Kreis nach dem anderen. Jeder enthält drei Datenbits. Wir bestimmen das Paritätsbit wie zuvor. Wir addieren die Datenbits, und wenn wir Null oder Zwei bekommen, ist das Paritätsbit Null für gerade, und wenn wir Eins oder Drei bekommen, ist das Paritätsbit Eins, für ungerade. Wir machen das für alle Kreise und erhalten am Ende drei Paritätsbits, die zu den vier Datenbits passen. Diese werden dann wie folgt in einer Standardsequenz platziert. Erkenne nun, dass dieses System einzelne Fehler mit einer einfachen Regel automatisch korrigieren kann. Wenn ein einzelner Fehler auftritt, werden zwei oder mehr der Paritätsbits falsch sein. Wo auch immer sie sich überschneiden, ist der Fehlerort. Dieses sich überschneidende Datenbit wird dann automatisch umgekehrt, so dass alle Paritätsbits wieder gültig sind. Dies ist der Trick von Alice und Bob. Die zusätzlichen Paritätsbits werden als redundante Bits bezeichnet, weil sie keine neuen Informationen enthalten. Alle Fehlerkorrekturcodes arbeiten auf diese Weise. Sie erhöhen alle die Größe der Quellnachrichten geringfügig, auf Kosten der automatischen Fehlerkorrektur. Wir verwenden auch Fehlerkorrekturcodes für die Speicherung. Zum Beispiel auf einer physischen CD. Die Informationen werden mit speziellen Codes codiert, um Fehlerblöcke zu korrigieren, die durch Kratzer oder Staub verursacht werden, welche längere Sequenzen von Nullen und Einsen auf der Oberfläche verfälschen. Deshalb kannst du eine CD zerkratzen und oft wird sie immer noch perfekt abspielen. Claude Shannon nutzte diese Idee der Redundanz, um die Kapazität eines Kommunikationskanals neu zu definieren. Denn wenn das Rauschen auf deinem Kanal zunimmt, müssen wir die Menge an Redundanz erhöhen, um fehlerfrei zu kommunizieren. Dies muss dann die effektive Menge an Informationen verringern, die du pro Zeiteinheit senden kannst.