Übungsblatt 4 - Fehlererkennung

Aufgabe 1

1. Erklären Sie die unterschiedlichen Aufgaben Fehlererkennung und Fehlerkorrektur.
2. Überlegen Sie sich ein ganz einfaches Verfahren, um bei der Übertragung eines Frames die fehlerhafte Übertragung von genau einem Bit zu erkennen.

Aufgabe 2

Die Banken möchten durch Vergabe geeigneter Kontonummern Überweisungen sicherer machen.
Dazu wird folgender Algorithmus verwendet: Man vergibt nur Kontonummern x, die durch 97 teilbar sind.

1. Weisen Sie nach, dass man mit diesem Algorithmus bei falscher Eingabe genau einer Ziffer erkennt, dass ein Fehler aufgetreten ist.
2. Wird bei falscher Eingabe zweier Ziffern zuverlässig erkannt, dass ein Fehler aufgetreten ist? Begründung!
3. Ist die Kontonummer 3429403 gültig?
4. Geben Sie einen Algorithmus an, mit dem sich eine beliebige Ziffernfolge durch Anfügen zweier Prüfziffern zu einer gültigen Kontonummer ergänzen lässt.
5. Ergänzen Sie die Kontonummer 43564523  durch Anfügen von zwei Prüfziffern zu einer gültigen Kontonummer.

Hinweis: Dieses hier vorgestellte - sehr einfache - Verfahren beruht auf der üblichen Division natürlicher Zahlen. Bei der Fehlerüberprüfung von Ethernet-Frames werden diese nicht als Binärzahlen, sondern als Polynome über dem Körper {0,1} aufgefasst. Zur Überprüfung wird dann ein Divisionsverfahren benutzt, das auf der Polynom-Division basiert. Damit beschäftigen sich die nun folgenden Aufgaben.

Aufgabe 3

Die Menge {0,1} ist der kleinste Körper mit genau zwei Elementen. Ein Rahmen mit k Bits kann als Koeffizientenliste für ein Polynom mit k Termen x^k-1 bis x⁰ über diesem Körper aufgefasst werden.

1. Für welches Polynom steht die Bitfolge 010011101 ?
2. Berechnen Sie (x³+x)  +  (x³ +x²+1)
3. Berechnen Sie 0111 1001 + 1010 1101
4. Berechnen Sie 0111 1001 - 1010 1101
5. Berechnen Sie  - (1101 1101)
6. Berechnen Sie 1001 :0011
7. Berechnen Sie 1 1001 0111 : 1011

Aufgabe 4 (Hausaufgabe)

Die Übertragung von Frames soll dadurch gesichert werden, dass nur Frames übertragen werden, die durch das Polynom x⁸+x⁵+1 (Generatorpolynom) geteilt werden können.

Anmerkung: Das Verfahren heißt zyklische Redundanzprüfung oder CRC (Cyclic Redundancy Check). Es wird beim Ethernetprotokoll zur Fehlererkennung verwendet.

1. Prüfen Sie nach, ob das aus 4 Hexziffern bestehende Frame EA74 korrekt übertragen wurde. Gehen Sie hierbei davon aus, dass die letzten beide Hexziffern die CRC-Prüfsumme bezüglich des Generatorpolynoms x⁸+x⁵+1 darstellen.
2. Es sollen die beiden Hexziffern 1C übertragen werden. Hierzu wird ein aus 4 Hexziffern bestehendes Frame 1Cxy gebildet, wobei die letzten beiden Hexziffern x und y die CRC-Prüfsumme bezüglich des Generatorpolynoms x⁸+x⁵+1 darstellen. Bestimmen Sie die Hexziffern x und y .
3. Welche Arten von Übertragungsfehler werden durch ein gut geeignetes Generatorpolynom 32-ten Grades entdeckt? (Lesen Sie hierzu Tanenbaum Andrew S.: Computernetzwerke, Prentice Hall, 2003, 3.2.2 Fehlererkennungscodes)
4. Welches Generatorpolynom wird bei Ethernet/IEEE802.3 verwendet?

Hinweis

Ein hervorragende, animierte Einführung in das Thema CRC finden Sie auf der Seite von Marek Gonet: How does CRC work? Vielen Dank an den Autor!