Freitag, 1. November 2013

Ein Raumanzug für Mona Lisa - Fehlerkorrigierende Codes (Gastbeitrag)

Heute gibt's etwas Besonderes, etwas Erstmaliges: einen Gastartikel.
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)
Bereits im Januar dieses Jahres ist diese neue Technik in die Medien gerückt, als ein ähnliches Experiment stattfand. Damals wurde allerdings nicht die Geschwindigkeit untersucht, sondern die Fehleranfälligkeit. Wie man sich denken kann, ist so eine Übertragung nicht perfekt, schließlich liegt die Erdatmosphäre zwischen Sender und Empfänger. Bei diesem Experiment wurde eine digitale Version der Mona Lisa mit einer Auflösung von 152x200 Pixel zu einem mondnahen Satelliten geschickt. Zum Testen der Fehleranfälligkeit schickten sie das Bild einmal in Rohform und einmal veränderten sie die Daten vorher mit einem bestimmten mathematischen Verfahren, das ich in diesem Artikel vorstellen möchte. Das Ergebnis sieht man in der folgenden Grafik. Links ist das Ergebnis der normalen Übertragung, bei welcher große Teile des Bildes nicht richtig angekommen sind, wobei weiße Pixel fehlende und schwarze Pixel falsche Daten indizieren. Rechts hingegen kann man keine Fehler beobachten.
Ergebnis der Übertragung der Mona Lisa
(Credit: Xiaoli Sun, NASA Goddard)
Dieses mathematische Verfahren nennt sich "fehlerkorrigierende Codes"; in diesem Fall verwendete die NASA einen speziellen Reed-Solomon-Code. Diese Codes sind alltäglicher als man glaubt. Jeder von uns verwendet tägliche diese Technik. Schließlich übertragen wir ständig Daten, sei es übers Handy (Anrufe, SMS, Internet), am PC, wo Daten von der Festplatte oder von der RAM gelesen werden, wenn wir uns eine CD anhören, ... An all diese Übertragungen stellen wir eine wichtige Anforderung. Die Daten sollen genauso ankommen, wie sie ursprünglich waren. Eine CD bekommt nach kurzer Zeit Kratzer, doch wir möchten die Musik rauschfrei genießen, bei Funkübertragungen stören kosmische oder elektromagnetische Strahlen, trotzdem möchten wir keine SMS der Art "Tref/*n um 1%:00" entziffern müssen, und wir wollen keine wichtigen Daten verlieren, nur weil irgendwo beim Speichern ein kleiner Fehler passiert ist.

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.
Eine einfache Lösung ist, die Nachricht mehrfach zu versenden.
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.
Paritychecks werden übrigens sehr oft bei wichtigen Identifizierungsnummern verwendet. Davon kannst du dich mit einem kleinen Experiment sofort selber überzeugen. Nimm irgendeine Euro-Banknote aus deiner Geldbörse, egal ob 5€ oder 500€. Auf der Rückseite findet man die Seriennummer, angeführt von einem oder zwei Buchstaben. Bei meinem 10€-Schein ist es N43217754501. Ersetze zuerst den/die Buchstaben durch den dazupassenden Index aus dem Alphabet (A=1, ..., Z=26). Ich bekomme somit 1443217754501. Nun zähle alle Ziffern zusammen: 1+4+4+3+2+1+7+7+5+4+5+0+1=44. Bilde von diesem Ergebnis erneut die Ziffernsumme und wiederhole diesen Vorgang, bis das Ergebnis eine einzige (einstellige) Ziffer ist, bei mir also 4+4=8. Mein Ergebnis ist 8. Und sollte dein Geldschein nicht eine Fälschung sein, wird ebenfalls 8 herauskommen. Denn jede einzelne Seriennummer einer gültigen Euro-Banknote ergibt bei wiederholtem Bilden der Ziffernsumme das Ergebnis 8. Das liegt an einer Art Paritycode, den das Europäische Währungsinstitut eingeführt hat. Durch das wiederholte Berechnen der Ziffernsumme berechnet man im Grunde nur de Rest, der bei einer Division mit 9 übrigbleibt. 53/9 = 5+(8 Rest). Mathematisch ausgedrückt, die Summe der Ziffern ist kongruent 8 modulo 9. Jetzt sieht man den Zusammenhang, denn bei dem Paritycheck oben haben wir folgende Eigenschaft: Die Summe der Ziffern ist 0 kongruent 2, also die Summe der Ziffern ist durch zwei ohne Rest teilbar. Damit sich wirklich bei jeder Seriennummer ein 8er ergibt, wurde eine einzige Ziffer angehängt. Die letzte Ziffer der Seriennummer (bei mir 1) gehört nicht mehr zur eigentlichen Seriennummer, sondern wurde lediglich so gewählt, dass die wiederholte Ziffernsumme 8 ergibt. Sehr ähnliche Verfahren gibt es bei EAN-Codes (das sind die Strichcodes auf Lebensmittel), den ISBN-Codes bei Büchern, bei Kreditkartennummern, usw.
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.
[7,4]-Hamming-Code
(Credit: Cburnett, Quelle: Wikimedia)
Nehmen wir zum Beispiel das Nachrichtenwort 1011. Zuerst sehen wir uns den grünen Kreis an. Es muss folgende Gleichung gelten:
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
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 posten