Netzwerk-Grundlagen, Teil 2

Im Allgemeinen ist die Übertragung über einen Kanal nicht fehlerfrei. Ein Rahmen kann daher fehlerhafte Daten enthalten. Wie oben beschrieben, können Fehler im Extremfall sogar dazu führen, dass das Rahmenende nicht richtig erkannt und damit auch der Empfang der nachfolgenden Rahmen gestört wird. Deshalb ist es wichtig, dass der Empfänger durch Analyse des Rahmens feststellen kann, ob Übertragungsfehler auftraten.

Bei optimaler Ausnutzung der Übertragungskapazität entspricht jedem Bitmuster ein gültiges Zeichen. Durch Übertragungsfehler werden dann aus gültigen Zeichen auch wieder „gültige“ Zeichen. Der Empfänger kann dann nicht erkennen, ob Übertragungsfehler vorliegen. Um eine Fehlererkennung zu ermöglichen, muss die Übertragung so erweitert werden, dass Fehler zu ungültigen Zeichen (oder Rahmen) führen. Dazu fügt der Sender zusätzliche Informationen (Redundanz) in den Rahmen ein.

Diesen und weitere Artikel zum Thema finden Sie im tecCHANNEL-Compact "Netzwerk-Know-How". Sie können die Ausgabe versandkostenfrei in unserem Online-Shop bestellen.

Redundanz

Eine Anwendung dieses Prinzips sind die Prüfzeichen bei wichtigen oder leicht zu verwechselnden Informationen wie Konto- und Kreditkartennummern oder die Internationale Standard Buchnummer (ISBN). Diese Nummern enthalten ein zusätzliches Zeichen, das nach einem vorgegebenen Algorithmus aus den anderen Stellen berechnet wird.

Auch in der sprachlichen Kommunikation setzen wir in schwierigen Fällen Redundanz ein. Ein Beispiel ist das Buchstabieren bei der Übermittlung von Namen. Noch mehr Redundanz kann man durch die Verwendung von Buchstabieralphabeten wie A wie Anton, B wie Berta ... erreichen. Die Eigennamen sind als längere Einheiten besser zu erkennen als die einzelnen Buchstaben.

Oft lassen sich nicht erkannte Fehler in der unteren Schicht auf einer höheren Schicht noch feststellen. Bei der Übermittlung einer Textdatei führen Übertragungsfehler mit einiger Wahrscheinlichkeit dazu, dass erkennbar falsche Wörter daraus resultieren. Diese Fehlererkennung ist aber nur auf Grund der Redundanz der Sprache möglich. Nicht jede Buchstabenfolge ergibt ein Wort in der jeweiligen Sprache, so dass Sprache auch ein Maß an Redundanz enthält.

Die Zusatzinformation als Sicherung gegen Fehler verringert die Nettoübertragungsrate. Daraus ergibt sich die Herausforderung, mit möglichst wenig Zusatzinformation eine zuverlässige Fehlererkennung zu ermöglichen.

Man unterscheidet dabei:

• Fehlererkennung: Der Empfänger kann erkennen, dass ein Rahmen fehlerhaft übertragen wurde.

• Fehlerkorrektur: Der Empfänger kann bis zu einem gewissen Grad erkannte Übertragungsfehler auch korrigieren.

Kommt nur eine Fehlererkennung zum Einsatz, muss der Empfänger im Fehlerfall den Sender auffordern, den Rahmen erneut zu schicken. Will man eine Fehlerkorrektur realisieren, muss mehr Sicherheitsinformation in den Rahmen eingebaut werden. Trotzdem ist auch damit nur ein Teil der Fehler zu reparieren. Enthält ein Rahmen zu viele Fehler, dann lässt sich die ursprüngliche Information nicht wieder herstellen.

Welches Verfahren effizienter in Hinblick auf die Sicherheit und die insgesamt erreichbare Nettodatenrate ist, hängt von dem Übertragungskanal ab. Dabei spielen sowohl die Auftrittswahrscheinlichkeit für einen Bitfehler als auch die statistische Verteilung der Fehler eine Rolle. Bei vielen Kanälen treten Fehler nicht gleichmäßig verteilt auf, sondern in Gruppen (Bursts). Wenn der Kanal in einem schlechten Zustand ist – zum Beispiel bei einer Funkverbindung in einem „Schatten“ hinter einem Hochhaus – kommt es zu sehr viel mehr Fehlern als im Normalzustand. Dann scheitert die Fehlerkorrektur, und die entsprechenden Rahmen müssen verworfen werden.

Insgesamt ist die Fehlererkennung eine komplexe Aufgabe. Die eingesetzten Methoden erfordern ein tiefes Verständnis von Statistik und Informationstheorie. Letztere erlaubt auch Aussagen zu den theoretischen Grenzen für die Nachrichtenübertragung über einen gegebenen Kanal.

Im Folgenden werden ohne Anspruch auf mathematische Tiefe anhand von zwei wichtigen Beispielen einige grundsätzliche Prinzipien der Fehlererkennung dargestellt. Bei diesen beiden Verfahren bleiben die Daten unverändert und werden um zusätzliche Sicherungsdaten ergänzt.

Parität

Eine weit verbreitete Methode zur Fehlererkennung ist das Einfügen von Paritätsbits. Dazu zählt man die Bits mit Wert 1 in dem Datenwort und fügt dann ein weiteres Bit hinzu, so dass bei der so genannten geraden Parität (even parity) insgesamt eine gerade Anzahl von Einsen entsteht. Bei ungerader Parität (odd parity) ist die Anzahl der gesetzten Bits ungerade. Das folgende Beispiel zeigt, was man für das ASCII-Zeichen C bei gerader Parität erhält.

Das zusätzliche Paritätsbit eignet sich sehr gut für ASCII-Zeichen. Wenn man sich auf den 7-Bit-Zeichensatz beschränkt, dann kann das achte Bit als Paritätsbit verwendet werden. Die Parität hat weiterhin den Vorteil, dass sich die Prüfung auch in Hardware ohne großen Aufwand mit hintereinander geschalteten XOR-Elementen realisieren lässt.

Von den mit acht Bit möglichen 256 Zeichen bleiben nach der Paritätsprüfung nur noch 128 gültige Zeichen übrig. Dabei gilt, dass sich zwei gültige Zeichen in mindestens zwei Bitpositionen unterscheiden. Ändert man nur ein Bit, so resultiert daraus ein ungültiges Zeichen. Man sagt, der Hamming2 -Abstand beträgt 2. Allgemein bedeutet ein Hamming-Abstand n, dass sich zwei Zeichen in mindestens n Positionen voneinander unterscheiden.

Zweidimensionale Parität

Mit einem Paritätsbit wird ein Fehler (oder allgemein eine ungerade Anzahl von Fehlern) innerhalb eines Bytes erkannt. Zwei Fehler kompensieren sich aber gegenseitig und führen wieder zu einem korrekten Paritätsbit. Betrachtet man einen Block – das heißt eine Anzahl aufeinander folgender Zeichen – gemeinsam, lässt sich die Sicherheit deutlich erhöhen. Dazu wird zu der beschriebenen Parität pro Zeichen eine zweite Parität pro Position in Zeitrichtung eingeführt. Zur Unterscheidung zur einfachen (eindimensionalen) Parität spricht man auch von zweidimensionaler Parität. Die Tabelle zeigt die zweidimensionale Parität am Beispiel der Zeichenfolge HALLO. Die Parität in Zeilen- und Spaltenrichtung heißt Quer- und Längsparität.

Ein einzelner Fehler macht sich sowohl in einer Zeile als auch Spalte bemerkbar und ist damit korrigierbar. Zwei Fehler – selbst in unterschiedlichen Zeilen und Spalten – sind aber nicht mehr auszubessern. Allerdings lassen sich die Fehler relativ gut lokalisieren, und es gibt nur zwei Möglichkeiten, wo sie sich befinden können. Liegen die beiden Fehler zusätzlich in einer Zeile, stimmen alle Querparitäten. Die Fehler werden zwar durch die Längsparität detektiert, können aber nicht mehr korrigiert werden. Allgemein lassen sich alle 3-Bit-Fehler und auch die meisten 4-Bit-Fehler erkennen. Nur wenn die vier Fehler genau an den passenden Kreuzungspunkten liegen, stimmen wieder alle Quer- und Längsparitäten.

Die Paritätsprüfung zählt die vorkommenden Einsen und prüft, ob sich in Summe eine gerade Anzahl ergibt. Die Übertragung umfasst einen Block Daten und eine Anzahl von Paritätsinformationen:

[Datenbits] [Paritätsbits]

Der Empfänger kann dann durch die Prüfoperation auf dem Gesamtblock die Integrität testen. Dieses allgemeine Schema „Daten – Prüfinformation – Prüfoperation“ lässt sich leicht verallgemeinern, indem man andere Prüfoperationen nutzt. In Internet-Protokollen wird ein Verfahren mit einer Prüfsumme angewandt. Die Prüfoperation ist dabei eine Addition im Einerkomplement. Als Prüfinformation wird das Ergebnis dieser Addition an die Daten angehängt. Der Empfänger führt dann ebenfalls die Addition aus und vergleicht das Ergebnis mit der Prüfsumme. Dieses Verfahren ist einfach zu realisieren, bietet aber nicht sehr viel Schutz. Wesentlich mächtiger ist das Verfahren der zyklischen Redundanzprüfung.

Zyklische Redundanzprüfung

Bei dem Verfahren der zyklischen Redundanzprüfung (Cyclic Redundancy Check CRC) ist die Prüfoperation im Prinzip eine Division. Betrachten wir zunächst ein Beispiel mit Dezimalzahlen. Übertragen werden soll eine große Dezimalzahl wie etwa 35628828297292. Weiterhin wählt man einen Divisor D aus. Nimmt man dafür beispielsweise den Wert 17 und führt die Division aus, so erhält man bei ganzzahliger Division (Modulo-Operator % in C) einen Rest von 8. Der Sender kann damit zu der großen Zahl als Prüfwert die 8 senden. Der Empfänger rechnet dann zur Kontrolle (35628828297292-8)%17. Bleibt bei der Division ein Rest übrig, so liegt ein Übertragungsfehler vor.

Schon an diesem einfachen Beispiel werden einige Grundeigenschaften deutlich. Zunächst einmal sind nicht alle Divisoren gleich gut geeignet für diesen Zweck. Beispielsweise wäre 10 ein schlechter Divisor, da sich dann nur Fehler an der letzten Stelle auswirken würden.

Weiterhin wird ein größerer Divisor einen besseren Schutz bieten. Allerdings muss dann entsprechend mehr Platz für den Rest vorgehalten werden. Der Rest kann maximal den Wert D-1 annehmen. Der Divisor selbst hat sinnvollerweise einen festen Wert und braucht dann nicht mehr übertragen zu werden.

Die Übertragung dieses Ansatzes auf Binärdaten beruht auf der Interpretation von Bitfolgen als Polynomen. Für eine Bitfolge abcdef schreibt man:

Dabei genügt es, die Terme mit Einsen anzugeben. Für die Bitfolge 100101 erhält man dann zum Beispiel:

Die Prüfbits werden durch eine Division von solchen Polynomen bestimmt. CRC benutzt eine polynomiale Modulo-2-Arithmetik. In dieser Arithmetik reduziert sich die Subtraktion auf eine XOR-Operation. Die Division lässt sich – wie bei der üblichen Division – durch fortgesetzte Subtraktion ausführen.

Beispiel für die zyklische Redundanzprüfung

Es sei als Beispiel x^3+x+1 das Divisorpolynom und damit 1011 das zugehörige Bitmuster. Die Nachricht 110101101 ist zu übertragen. Zunächst wird sie entsprechend der höchsten Potenz im Divisor um drei Bits erweitert: 110101101000. Genau in diese zusätzlichen Bits kommen später die Prüfbits.

Der erste Schritt in der Division ist dann:

Das Ergebnis der Division wird nicht benötigt und daher nicht notiert. Dann wird die nächste Stelle von oben übernommen und der Divisor erneut subtrahiert:

Insgesamt ergibt sich

Bei der Division bleibt ein Rest von 110. Zieht man diesen von der erweiterten Zahl ab, so ist die neue Zahl ohne Rest durch den Divisor teilbar. Da Subtraktion einer XOR-Operation entspricht, erhält man 110101101110. Diese um die drei Prüfbits erweiterte Bitfolge wird gesendet. Der Empfänger führt ebenfalls die Division durch. Falls dabei ein Rest übrig bleibt, liegt ein Übertragungsfehler vor.

Generatorpolynome

Wie bei dem Beispiel mit den Dezimalzahlen gibt es auch für die Polynomdivision mehr oder weniger gut geeignete Divisorpolynome. In der Fachliteratur – beziehungsweise in den entsprechenden Spezifikationen – findet man jedoch schnell geeignete Polynome.

Man bezeichnet die Polynome in diesem Zusammenhang oft auch als Generator-polynome. Einige davon sind unten in der Tabelle aufgelistet. Die Zahl nach dem Namen gibt an, wie viele Prüfbits jeweils genutzt werden. Details der Implementierung zusammen mit einer Realisierung in der Programmiersprache C findet man beispielsweise in [1].

Die Prüfverfahren schützen in allen Fällen, in denen die Anzahl der Bitfehler kleiner ist als die Anzahl der Prüfbits. Darüber hinaus werden auch die „meisten“ anderen Fehler erkannt.

Ausblick

Im nächsten Teil der Serie widmen wir uns der sicheren Übertragung der Daten. Dazu sehen wir uns dem Stop-and-Wait- sowie den Sliding-Windows-Algorithmus genauer an.

Diesen und weitere Artikel zum Thema finden Sie im tecCHANNEL-Compact "Netzwerk-Know-How". Sie können die Ausgabe versandkostenfrei in unserem Online-Shop bestellen.

Literatur

[1] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical recipes in C. Cambridge University Press, 1992