Bei der Übertragung von Daten erhält man auf Grund von fehlerbehafteten Übertragungs-Kanälen (Rauschen auf der Leitung etc.) häufig verfälschte Daten. Das stört bei Anwendungen wie zum Beispiel einem CD-Player oder der Übertragung von Daten zwischen Computern. Neben elektrischer Spannung oder Strom können auch Licht (z.B. Infrarot- oder Laserlicht in Luft oder in Glasfaserkabeln), elektromagnetische Wellen oder akustische Signale verwendet werden. Solche Systeme besitzen eine mehr oder minder hohe Anfälligkeit für Verfälschung der Signale, d.h. dass ein Empfänger ein Signal anders interpretiert als der Sender es gemeint hat.
Die Darstellung einer Nachricht wird auch als Kodierung der Nachricht bezeichnet. Die Form, in der wir eine Nachricht schreiben, wird daher auch als Codewort bezeichnet.
Ein Code kann ausser der Nachricht, welche die Information repräsentiert, auch noch weitere Information tragen. Diese Information wird als Redundanz bezeichnet. Wir nennen im folgenden die zusätzliche Information, die zur Fehlererkennung dient, Prüfdaten. Da die Prüfdaten stets über den gleichen Kanal geschickt werden müssen wie die Nutzdaten, können natürlich auch diese verfälscht beim Empfänger ankommen.
# Fehlerarten
Einzelbitfehler sind Fehler, die unabhängig von anderen auftreten.
Bündelfehler (auch Blockfehler, oder engl. Error Bursts genannt) sind Fehler, die abhängig von anderen auftreten. Diese Art von Fehlern tritt häufig durch Störeinflüsse wie zum Beispiel Blitze auf. Ein typischer Bündelfehler ist auch ein Kratzer auf einer CD.
Synchronisationsfehler sind (meist längere) Bündelfehler, die neben einem Datenverlust auch zu einem Verlust der Information führen, die man gerade empfängt. Das führt dazu, dass auch nachfolgende korrekte Bits nicht mehr verwendet werden können.
Um dem Problem der fehlerbehafteten Übertragung vorzubeugen, werden fehlererkennende und fehlerkorrigierende Codes verwendet.
# Fehlererkennende Codes
Allen fehlererkennenden Codes liegt ein Prinzip zugrunde, nämlich, zu einer gegebenen Nachricht weitere Information hinzuzufügen, die ausreicht um einen Übertragungsfehler zu erkennen. Ist dieser Fehler dann erkannt, so kann man die Übertragung einfach wiederholen.
# Einfache Paritätskontrollen
Paritätskontrollen sind die einfachste Art, Fehler in binären Nachrichten zu erkennen.
Das Prinzip ist recht simpel: Man zählt die Anzahl der Einsen in einer (z.B. 8 Bit langen) binären Nachricht. Ist die Anzahl der Einsen ungerade, so hängt man eine Eins an die Nachricht an. Ist die Anzahl der Einsen gerade, so hängt man eine Null an die Nachricht an. Will man dann die Korrektheit dieser Nachricht prüfen, muss man lediglich testen, ob die Anzahl der Einsen gerade ist.
Der Nachteil der einfachen Paritätskontrollen besteht darin, dass sich nur Einzelfehler erkennen lassen. Tritt zum Beispiel eine gerade Anzahl an Fehlern auf, stimmt die Parität wieder und die Nachricht wird als korrekt behandelt. (Natürlich könnte man genauso gut ungerade Parität verwenden, jedoch lässt sich die gerade Parität in der Theorie besser handhaben.)
Beispiel
Die zu codierende Information sei das binäre Wort 1111 0001. Man zähle also zuerst die Werte aller Binärstellen zusammen (1111 0001 1.
# ISBN-Nummern
Ein weiteres Beispiel für einen einfachen fehlererkennenden Code ist die ISBN-Nummer.
Die Prüfziffer (zehnte Ziffer) der ISBN-Nummer berechnet sich wie folgt:
Man multipliziere die erste Ziffer mit eins, die zweite mit zwei, die dritte mit drei und so fort bis zur neunten Ziffer, die mit neun multipliziert wird.
Man addiert nun die Produkte und teilt die Summe ganzzahlig mit Rest durch 11. Der Divisionsrest ist die Prüfziffer. Falls der Rest 10 beträgt, ist die Prüfziffer ein «X».
Beispiel
ISBN 3-499-13599-? (Fräulein Smillas Gespür für Schnee)
ISBN 3-446-19313-? (Fermats letzter Satz)
Aufgaben
Berechne die Prüfziffer der folgenden beiden ISBN-Nummern
- ISBN 0-7475-5100-?
- ISBN 1-57231-422-?
# Fehlerkorrigierende Codes
Ebenso, wie bei den fehlererkennenden Codes, wird auch bei den fehlerkorrigierenden Codes zu einer gegebenen Nachricht zusätzliche Information hinzugefügt. Diese zugefügte Information muss aber nicht nur dazu ausreichen, Fehler zu erkennen, sie muss auch dazu ausreichen, den erkannten Fehler zu lokalisieren, um ihn korrigieren zu können. Besonders bei Fehlern die nicht vorübergehender Natur sind, ist ein fehlerkorrigierender Code wünschenswert, da das Fehlererkennen und anschliessende Wiederholen der Übertragung in diesem Fall nie zum Erfolg führt.
Der einfachste fehlerkorrigierende Code ist der Verdreifacher-Code. Die zu übertragende Information wird dreifach übertragen und am Empfangsende einem Mehrheitsvergleich unterzogen. Stimmen mindestens zwei der drei Nachrichtenfragmente überein, so wird angenommen, dass diese korrekt sind. Der grosse Nachteil bei diesem Code ist jedoch, dass er eine Vervielfachung der Datenmenge verursacht und somit recht ineffizient ist.
Fehlerkorrigierende Codes helfen bei der Übertragung von Daten, indem sie dabei entstandene Fehler korrigieren können. Dies geschieht mit Hilfe von Redundanz. Eine wichtige Grösse bei fehlerkorrigierenden Codes ist die minimale Distanz zwischen zwei Codewörtern. Diese gibt an, wieviel Fehler erkannt und korrigiert werden können und sollte deshalb möglichst maximiert werden.
Beispiel
Nehmen wir an, dass du einen Code für die vier mathematischen Operationen
Über deine Signalleitung übermittelst du 00. Allerdings findet ein Übertragungsfehler statt, der ein Bit verändert, so dass die Zielperson die Serie 10 empfängt. Diese wird als Multiplikation interpretiert!
Wenn du hingegen längere Serien definierst, wie z.B.:
dann wird ein Übertragungsfehler erkannt. Nehmen wir an, dass du 0000 sendest und an der Empfangsstation erhalten sie 0010. Nun wissen die Empfänger, dass ein Übertragungsfehler stattgefunden hat. Sie können aber noch nicht auf die gesendete Serie schliessen:
Wo liegt der Fehler?
Wir sehen: Je länger der Code ist, desto mehr Korrektur-Möglichkeiten.
Als nächste Schritt definieren wir:
Jetzt kann ein Fehler entdeckt werden: du sendest 00000 und die Empfänger erhalten z.B. 00010. Sie wissen, dass mit einem Fehler 00010 nur als 00000 interpretiert werden kann.
Ziel ist es eine Beziehung zwischen der Länge des Codes und der maximalen Anzahl von korrigierbaren Fehlern zu finden:
# Hamming-Distanz Beziehung (ohne Beweis)
Betrachten wir folgende Codierung als Beispiel:
Die Codes unterscheiden sich paarweise an genau zwei Stellen. Das bedeutet, dass zwei Übertragungsfehler einen Code in einen anderen verwandeln können. Eine 1111 Folge könnte als 1100 empfangen werden. Dagegen wird ein einzelner Fehler entdeckt: eine empfangene 1000 Folge wird als fehlerhafte erkannt. Es bleibt das Problem, dass der Fehler noch nicht korrigiert werden kann (war 1000 eine 1010 Folge, eine 1001 oder eine 1100?).
Definition
Der minimale Unterschied zwischen zwei Code-Zeilen heisst Hamming Distance (HD).
Im Beispiel ist HD
Theorem
Ein Code mit einer HD
Im Beispiel HD
Aufgabe
Finde einen minimalen Code für die vier Grundrechenarten
# Verfahren in Rechnernetzen
Heutige Rechnernetzprotokolle zur gesicherten Datenübertragung verwenden vorwiegend Fehlererkennungsverfahren, um beim Auftreten eines Fehlers durch geeignete Massnahmen, wie erneute Datenübertragung oder Abbruch der Übertragung und Meldung an den Auftraggeber, eine unverfälschte Datenübertragung zu garantieren.
Aufgabe
Auf einer Ethernet-Übertragungsleitung sei ohne Fehlerkorrektur ca. jedes 100‘000 Bit fehlerhaft. Wie viele Fehler würden bei einer Übertragungsrate von 10MBit/s in einer Sekunde auftreten?