Fehlererkennung

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.

Fehlererkennung mit Paritätsbit

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

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.

Fehlererkennung - CRC

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 3

(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.

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 4

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?

X

Fehler melden

X

Suche