Es werden Methoden vorgestellt, die uns in unserem technischen Alltag eine Vielzahl von Sorgen nehmen. Dank der folgenden klugen Überlegungen ist es z. B. möglich, diesen Artikel fehlerfrei auf eure Bildschirme zu bringen - und alleine deswegen hat die Technik der fehlerkorrigierenden Codes bereits ihre Berechtigung, wie ihr nach dem Lesen des folgenden Textes von Jakob Kogler sicher auch denken werdet! ;-)
Einleitung
Vergangene Woche wurde von der NASA der Rekord für die schnellste Datenübertragung durch das Weltall gebrochen. Seit eh und je verwendet die NASA zur Kommunikation mit Satelliten, der Crew von der ISS, usw. sogenannte RF-Systeme, sprich Radiowellen. Mittlerweile gerät diese Technik aber an ihre Grenzen. Durch bessere Messgeräte, größere Auflösung bei Kameras,... entstehen immer mehr Daten, die zur Erde gesendet werden sollen. Doch die Geschwindigkeit bei Funkübertragungen ist begrenzt. Dadurch treffen wichtige Ergebnisse erst verspätet an bzw. HD-Videos können nicht live angesehen werden. Deshalb experimentiert die NASA seit einiger Zeit mit alternativen Techniken. Letzte Woche ist es ihnen bei der LLCD (Lunar Laser Communication Demonstration) gelungen, den alten Rekord zu brechen. Bei dieser neuen Technik werden pulsierende Laserstrahlen verwendet, die für eine deutlich schnellere Übertragung sorgen. Im vergangenen September wurde dazu der Satellit LADEE in den Orbit des Mondes geschossen. Über die große Distanz von 385.000 Kilometern wurde eine Downloadgeschwindigkeit (Mond → Erde) von 622 Mbps und Uploadgeschwindigkeit (Erde → Mond) von 20 Mbps gemessen, was ungefähr der 5-fachen alten Geschwindigkeit entspricht. |
| Satellit LADEE und die Kommunikation über Laserstrahlen (Credit: NASA) |
 |
| Ergebnis der Übertragung der Mona Lisa (Credit: Xiaoli Sun, NASA Goddard) |
Die wie wird man diese Fehler los? Die Physik kann keine hundertprozentig fehlerfreie Übertragung gewährleisten. Neben dem Interpolieren der fehlerhaften Daten gibt es ein anderes mathematisches Verfahren. Man greift schon vor dem Versenden mittels fehlerkorrigierenden Codes ein. Bei diesem Verfahren bringt man die Daten vor dem Senden auf eine spezielle Gestalt, sodass man, falls bei der Übertragung Fehler passieren, diese erkennen und korrekt ausbessern kann.
Wiederholungscodes
Dazu fangen wir allerdings einmal klein an. Machen wir ein Experiment. Wir haben einen Sender A und einen Empfänger B. Unsere Nachricht besteht, wie bei digitalen Datenübertragungen üblich, aus Einsen und Nullen, als Beispiel nehmen wir die Nachricht 10110. Zuerst schicken wir sie unkodiert. Durch irgendwelche äußere Einflüsse passiert ein Fehler an der dritten Stelle. Der Empfänger B bekommt nur die Nachricht 10010. Wie können wir einen solchen Fehler vermeiden? |
| Senden ohne Kodierung, Fehler werden nicht erkannt. |
Schicken wir die Nachricht zum Beispiel zwei Mal. Man nennt dies einen 2-fach Wiederholungscode. Unser Sendewort ist nun also 1011010110. Passiert wieder ein Fehler (zufällig wieder an der dritten Stelle), so bekommt der Empfänger B das Wort 1001010110. Nun kann der Empfänger die Stellen vergleichen. Die Stellen 1 und 6 sind jeweils "1", hier ist also kein Fehler passiert, die Stellen 2 und 7 sind "0", passt auch, aber an der dritten und der achten Stelle stehen unterschiedliche Werte, einmal eine 1 und einmal eine 0. Wir erkennen, dass ein Fehler passiert ist. Was ist aber jetzt die korrekte Version des Nachrichtenwortes, ist es 10110 oder 10010? Wir sind in einer eigenartigen Situation, wir wissen, dass ein Fehler auftrat, wir wissen sogar an welcher Stelle vom Nachrichtenwort, allerdings können wir ihn nicht ausbessern. Um das korrekte Nachrichtenwort zu bekommen, muss der Empfänger das Wort neu anfordern und hoffen, dass dieses Mal kein Fehler an der dritten Stelle passiert.
 |
| 3-fach Wiederholungscode, Fehler werden erkannt und korrigiert. |
Paritycheck
Versuchen wir, den 2-fach Wiederholungscode effektiver zu machen. Zur Erinnerung, die ursprüngliche Nachricht bestand aus 5 Bit, die kodierte Variante aus 10. Unsere Informationsrate liegt also bei 5/10 = 50%. Die Idee bei einem Paritycheck ist simpel. Man hängt an die Nachricht ein einzelnes Bit an, sodass in der Nachricht eine gerade Anzahl von Einsen vorliegt. Als Beispiel, in der Nachricht 10110 gibt es genau drei Einsen, deshalb hängen wir eine weitere Eins an, sodass wir insgesamt gerade viele (4) Einsen bekommen. Das kodierte Wort lautet nun 101101. Würde das Nachrichtenwort hingegen 01100 lauten, so würden wir eine Null anhängen, da wir schon eine gerade Anzahl (2) von Einsen haben, damit würden wir das Codewort 011000 bekommen. Was hat sich im Gegensatz zum 2-fach Wiederholungscode geändert? Wir müssen nur 6 Bit statt 10 schicken! Unsere Informationsrate liegt nun bei 5/6 ≈ 83,33 %. Trotzdem haben wir die Eigenschaft, Fehler zu erkennen, erhalten. Der Empfänger braucht nur die empfangenen Einsen zu zählen. Falls er eine gerade Anzahl bekommen hat, stimmt seine Nachricht und er kann die ersten 5 Bit ausgeben, wenn nicht, weiß er, dass sich ein Fehler eingeschlichen hat und fordert die Nachricht erneut an. |
| Paritycheck, Fehler wird erkannt, aber nicht korrigiert. |
 |
| 10€-Banknote |
Hammingcodes
Es geht also bergauf. Wir können nun schon effektiv Fehler erkennen, aber ausbessern können wir sie bis jetzt nur durch unseren uneffektiven (Informationsrate 5/15 ≈ 33,33 %) 3-fach Wiederholungscode. Die Lösung sind mehrere (bewusst gesetzte) Paritychecks. Der Mathematiker Richard Hamming hat sich darüber um 1950 Gedanken gemacht, und hat die Hamming-Codes entwickelt. Nehmen wir als Beispiel einen [7,4]-Hamming-Code. Dabei werden 4 Nachrichtenbits durch 3 Parity-Bits zu 7 Bits erweitert. Wir bekommen somit eine Informationsrate von 4/7 ≈ 57,14 %. In der folgenden Grafik sieht man die 4 Nachrichtenbits d1, d2, d3, d4 und die 3 Paritybits p1, p2, p3 in drei Kreisen. Die Anforderung an unseren Code ist, dass in jedem dieser Kreise die Anzahl der Einsen gerade ist..svg/350px-Hamming(7,4).svg.png) |
| [7,4]-Hamming-Code (Credit: Cburnett, Quelle: Wikimedia) |
2k = d1 + d2 + d4 + p1 = 1 + 0 + 1 + p1 = 2 + p1.
Somit muss p1 = 0 sein.Analog bestimmen wir p2 über den blauen (2k = d1 + d3 + d4 + p2 = 1 + 1 + 1 + p2 = 3 + p2) und p3 über den roten Kreis (2k = d2 + d3 + d4 + p3 = 0 + 1 + 1 + p3 = 2 + p3). Damit bekommen wir p2 = 1 und p3 = 0. Unser kodiertes Wort d1d2d3d4p1p2p3 lautet also 1011010. Angenommen, es passiert wieder ein Fehler an der dritten Stelle: 1001010. Wie finden wir hier den Fehler? Ganz einfach, wir berechnen die Paritybits neu und sehen uns die Unterschiede an. Wir bekommen p1=0, p2=0 und p3=1. Wir merken, dass die Paritybits p2 und p3 verschieden von den übertragenen Paritybits sind. Nun brauchen wir nur in der Grafik nachzuschauen, welches Bit genau vom blauen und vom roten Kreis eingenommen wird. Wir sehen, das ist genau das Nachrichtenbit d3, somit ist die dritte Stelle falsch und wir können das Nachrichtenwort rekonstruieren. Jedes der 7 Bits, die übertragen werden, kann einer bestimmten Paritybit-Kombination zugeordnet werden, so wird man merken, dass bei einem Fehler an der vierten Stelle sich alle berechneten Paritybits von den gesendeten unterscheiden oder bei einem Fehler an der sechsten Stelle nur das Paritybit p2 falsch ist.
Wie der Entdecker Hamming herausfand, kann man solche Verfahren allgemein für Nachrichtenwörter der Länge
2 r - r - 1
machen, indem man r Kreise zeichnet und somit r Paritybits anhängt. Die Informationsrate wird bei wachsendem r immer besser und geht asymptotisch gegen 100 %. |
| [7,4]-Hamming-Code, Fehler wird erkannt und korrigiert. |
Weiterführendes
Man kann mathematisch zeigen, dass der [7,4]-Hamming-Code perfekt ist. Das heißt, dass man für Nachrichtenwörter der Länge 4 keinen effizienteren Code (noch besser, Informationsrate) finden kann, der ebenso Einfachfehler (Fehleranzahl = 1) erkennt und verbessert. Analoges gilt für die anderen Hamming-Codes.Was kann man also noch verbessern? Nun, einerseits ist der Hamming-Code an die fixe Länge 2r - r - 1 gebunden. Oft möchte man aber Nachrichtenwörter einer anderen Länge kodieren. Und andererseits möchte man mehrere Fehler gleichzeitig korrigieren. Der Hammingcode kann immer nur einen einzigen Fehler ausbessern. Treten also bei der Übertragung eines kodierten Wortes zwei Fehler auf, so erkennt der Empfänger zwar die Fehler, korrigiert sie allerdings falsch. Durch algebraische Methoden kann man Codes generieren, die beliebig lang sind und mehrere Fehler im selben Wort korrekt ausbessern können. Bei solchen Codes wird selbstverständlich die Informationsrate wieder schlechter, allerdings überzeugen die neuen Eigenschaften deutlich.
Die Idee dahinter ist, dass man sich die Codewörter als Punkte in einem mehrdimensionalen Raum vorstellt. Bei einem [7,4]-Hamming-Code betrachtet man Punkte in einem 7-dimensionalen Raum, genauer gesagt, der Raum {0,1}7. Unser kodiertes Wort 1011010 ist nun ein Punkt in diesem Raum, ebenso das Wort (bzw. der Punkt) 1001010. Der Punkt 1011010 wird dabei als "guter Punkt" bezeichnet, da er fehlerfrei ist, der Punkt 1001010 ist ein "schlechter Punkt". Bei diesen algebraischen Methoden versucht man, gute Punkte so zu wählen, dass sie möglichst großen Abstand zu anderen guten Punkten besitzen.
Durch verschiedene Ansätze kommt man auf zyklische Codes, Reed-Solomon-Codes (wie sie die NASA bei der Mona Lisa-Übertragung benutzte), BCH-Codes und noch viele mehr. Diese Codes würden aber die Länge dieses Artikels endgültig sprengen.
Keine Kommentare:
Kommentar veröffentlichen