Fehlererkennung

Grenzen des Übertragungsmediums

Die Übertragung von Daten ist nie ganz perfekt. Durch Grenzen technischer Systeme und äußere Einflüsse kann es immer vorkommen, dass Daten während des Transports verändert werden.

Ein Grundproblem der Datensicherung besteht darin, Fehler bei der Datenübertragung zwischen zwei Rechnern zu erkennen und geeignete Maßnahmen zur Behandlung von Fehlern zu ergreifen.

Fehlererkennung mit einem Zusatzbit

Sandy will Emmy eine Bitfolge senden. Felice, die für die Übertragung zuständig ist, ändert ab und zu ein Bit ab. Sandy und Emmy haben sich ein Verfahren ausgedacht, mit dem sie die Veränderung von Bits überprüfen wollen. Sandy zählt hierzu die Einsen in der zu übertragenen Bitfolge. Ist die Anzahl ungerade, so fügt Sandy der Bitfolge eine 1 hinzu, ansonsten eine 0.

Aufgabe 1

(a) Wie kann Emmy überprüfen, ob Felice ein Bit abgeändert hat? Funktioniert das auch, wenn Felice das Zusatzbit abändert?

(b) Kann Emmy feststellen, welches Bit abgeändert wurde?

(c) Felice ändert mehrere Bits ab. Welche Möglichkeiten ergeben sich für Emmy, solche Veränderungen zu erkennen?

(d) Du kannst das beschriebene Szenario auch mit dem Programm fehlererkennungParitaet.py erkunden. Führe das Programm mehrfach aus und interpretiere die ausgegebenen Ergebnisse.

Aufgabe 2 - Erweiterter Sender und Empfänger

Passe den Sender und Empfänger so an, dass mit Hilfe eines Paritätsbits Fehler erkannt werden. Im Fehlerfall soll eine entsprechende Meldung ausgegeben werden. Implementiere zuerst den Sender und teste ihn mit dem Universaltransceiver. Implemeniere dann den Empfänger und teste das System. Tipp: Du kannst die Implementierung schlank halten, indem Du die Paritätsbit-Funktion in eine Datei paritaetsbit.py auslagerst und mit from paritaetsbit import * importierst.

Aufgabe 3

Das Prüfverfahren wird jetzt verbessert. Diskutiere jeweils die möglichen Fehlerfälle und beurteile die Güte des Verfahrens.

(a) Prüfsummenverfahren: Gegeben ist eine Folge von Bytes (hier dezimal dargestellt) wie z.B. 72, 65, 78, 76, 79. Aus dieser Folge wird die Summe berechnet: 72 + 65 + 78 + 76 + 79 = 370. Damit das Ergebnis wieder ein Byte darstellt, bildet man anschließend den Rest bei der Division durch 256: 370 % 256 = 114. Versendet wird jetzt die erweiterte Nachricht 72, 65, 78, 76, 79, 114.

(b) Prüfrestverfahren: Gegeben ist eine Folge von 3 Bytes (hier dezimal dargestellt) wie z.B. 72, 65, 78. Aus dieser Folge von Zahlen wird eine 9-stellige Zahl gebildet: 072065078. Diese Zahl wird durch einen festen "geeigneten" Divisor geteilt: 72065078 % 171 = 35. Der Rest 35 wird jetzt als "Prüfzahl" benutzt und zusammen mit den Ausgangszahlen übertragen: 72, 65, 78, 35.

Fehlererkennung mit einem verbesserten Verfahren

Sandy und Emmy benutzen jetzt ein verbessertes Verfahren, um Fehler bei der Übertragung der Bitfolgen zu erkennen.

Sie haben sich eine Funktion crc besorgt, mit der sie aus einer gegebenen Bitfolge eine Folge von Zusatzbits bestimmen können. Wie diese Funktion die Zusatzbits berechnet, haben sie nicht verstanden. Verwenden können sie die Funktion dennoch.

Aufgabe 4

(a) Teste erst einmal die Funktion crc.py. Benutze hierzu Dialoge wie den folgenden:

>>> crc('01011101')
'0110'

(b) Benutze anschließend das Testprogramm fehlererkennungCRC.py zur Fehlererkennung mit der crc-Funktion. Führe das Programm mehrfach durch. Ändere auch die voreingestellte Fehlerwahrscheinlichkeit.

(c) Wie gut ist das Fehlererkennungsverfahren mit der crc-Funktion? Kann es alle möglichen Veränderungen der vorgegebenen Bitfolge erkennen?

(d) Wenn du genauer wissen willst, was die crc-Funktion macht, dann benutze das Programm crc_demo.py und rufe es z.B. folgendermaßen auf:

>>> crc('1001101100')
10011011000000
10011
=====
 00000
 00000
 =====
  00001
  00000
  =====
   00011
   00000
   =====
    00110
    00000
    =====
     01100
     00000
     =====
      11000
      10011
      =====
       10110
       10011
       =====
        01010
        00000
        =====
         10100
         10011
         =====
         00111
'0111'

Erläuterungen zu diesen Rechnungen findest du z.B. auf der Seite Fehlererkennung.

Aufgabe 5 - Sender und Empfänger mit CRC

Ändere Dein Sender-Empfänger-System so ab, dass beide CRC zur Fehlererkennung benutzen. Im Fehlerfall soll eine entsprechende Meldung angezeigt werden.

Fehlerbehandlung

Wurde ein Fehler erkannt, gibt es prinzipiell zwei Möglichkeiten wie man darauf reagieren kann: Man kann den Fehler ignorieren oder man kann versuchen ihn zu korrigieren. Tatsächlich gibt es beide Varianten in der Praxis.

Aufgabe 6

Bei Ethernet - einem der verbreitetsten Protokolle in der Praxis - werden fehlerhafte Pakete verworfen. Welche Vorteile hat das (Tipp: Schichten)? Wie könnte ein Verfahren aussehen, bei dem fehlerhafte Daten noch einmal gesendet werden?

Fehlerkorrektur

Die bisher benutzten Verfahren erlauben nur, das Vorhandensein von Fehlern zu erkennen. Man ist jedoch nicht in der Lage, Fehler genau lokalisieren und dann korrigieren zu können. In der folgenden Aufgabe soll ein einfaches Verfahren zur Fehlerkorrektur untersucht werden.

Aufgabe 7

Gehe im Folgenden davon aus, dass nur 1 Bit abgeändert wird.

Eine Bitfolge wie z.B. '010111000' lässt sich auch folgendermaßen mit Zusatzbits anreichern:

010|1
111|1
000|0
---
101

Man schreibt die Bitfolge als zweidimensionales Muster in mehreren Zeilen auf. Dann bestimmt man für jede Zeile und jede Spalte ein Zusatzbit (z.B. mit dem Verfahren ganz oben). Aus dem erweiterten zweidimensionalen Bitmuster wird jetzt wieder nach einer vereinbarten Systematik eine Bitfolge erzeugt: '010111000110101'.

(a) Probiere das selbst aus und überlege dir, wie man eine Veränderung eines Bits jetzt genau lokalisieren kann.

(b) Worin liegen die Nachteile dieses Verfahrens?