9.5: Wie kann man sichergehen, dass Daten richtig übertragen wurden?
| Autoren: | |
| Publikation: | 4.10.2016 |
| Lernstufe: | 3 |
| Übersicht: | Fehler, die beim Abspeichern oder bei der Übertragung einer Datei aufgetreten sind, lassen sich finden und korrigieren. Dazu muss man allerdings Information hinzufügen und diese geschickt wählen. |
| Angestrebte Kenntnisse: |
|
| Wortschatz: | Paritätsbit, Prüfsumme |
| Dauer: | 1 Stunde |
| Material: |
Für jede Gruppe:
|
| Herkunft: | La main à la pâte, Paris |
Vorbemerkung
Die Schüler werden mit Sicherheit nicht von selbst auf eine Fehlerkontrolle durch das sogenannte Paritätsbit kommen. Wir beschreiben deshalb im Folgenden zwei Varianten der Unterrichtsstunde. In der ersten Variante werden die Schüler Schritt für Schritt an die Methode der Fehlerkontrolle mit Paritätsbits herangeführt. In der zweiten Variante zeigt die Lehrerin den Schülern einen "Zaubertrick", den die Schüler versuchen zu verstehen.
Ausgangssituation
Die Lehrerin zeigt ein Bild, das entfernt an die Früchtebilder der Unterrichtsstunde 9.1 (Bilder versenden und empfangen) erinnert. In den Abbildungen auf dieser Seite werden in den Textdateien die Kopfdaten weggelassen. Diese sind "P1" (es handelt sich um ein Schwarz-Weiß-Bild) und "5 5" (das Bild besteht aus 5 x 5 Pixeln).
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
Abb. 1: Muster und dazugehörige Kodierung
Die Lehrerin fragt die Schüler, was passieren würde, wenn sich während der Übertragung des Bildes Fehler einschleichen würden. Man könnte sich zum Beispiel vorstellen, dass der Wert eines oder mehrerer Pixel verändert wurde. Die Lehrerin ändert jetzt einen Wert in den Bilddaten der Datei und bittet einen Schüler an der Tafel das veränderte Bild zu zeichnen. Hier ein Beispiel (aus der "1" in Spalte 4 / Reihe 2 wurde eine "0"):
0 0 1 0 0
0 1 0 0 0
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
Abb. 2: Veränderte Kodierung und dazugehöriges Muster
Pädagogische Anmerkung
Hier wird absichtlich ein sehr einfaches Beispiel gewählt, sodass die Schüler das, was sie in der Unterrichtsstunde 9.1 (Bilder versenden und empfangen) gelernt haben, erneut einbringen und festigen können.
Recherchearbeit: Wie kann man einen Fehler finden?
Die Lehrerin fragt die Schüler, wie man sichergehen könnte, dass das empfangene Bild mit dem gesendeten Bild übereinstimmt. Es geht hier nicht darum, mögliche Fehler zu korrigieren, sondern darum, (übertragene) Daten auf Fehler zu prüfen: Man möchte die Integrität (Vollständigkeit + Richtigkeit) der Daten sicherstellen.
Das geht nicht ohne zusätzliche Information. Man könnte die Summe aller Werte in einer Zeile zusammenaddieren, Zeile für Zeile, und die entsprechenden Werte rechts in eine weitere Spalte schreiben. Oder man zählt ab, ob die Anzahl der Einsen in einer Zeile gerade oder ungerade ist – das ist einfacher und praktischer. Auch in diesem Fall wird diese zusätzliche Information rechts in eine weitere Spalte geschrieben. Dieses Verfahren ist äquivalent zu dem folgenden: Man schreibt in die rechte Spalte jeweils eine "1" oder eine "0", sodass die Anzahl der Einsen in jeder Zeile gerade ist.
- Ist die Anzahl der Einsen in einer Zeile eine gerade Zahl, schreibt man in die rechte Spalte eine "0". Das heißt, dass auch mit der zusätzlichen Spalte, die Anzahl der Einsen gerade ist.
- Ist die Anzahl der Einsen in einer Zeile eine ungerade Zahl, schreibt man in die rechte Spalte eine "1". Mit der zusätzlichen Spalte ist die Anzahl der Einsen nun gerade.
Wendet man dieses Verfahren auf die erste Datei an (Abb. 1), erhält man:
0 0 1 0 0
0 0 1 0 0 1
0 1 0 1 0
0 1 0 1 0 0
1 0 0 0 1
1 0 0 0 1 0
0 1 0 1 0
0 1 0 1 0 0
0 0 1 0 0
0 0 1 0 0 1
Abb. 3: Muster, dazugehörige Kodierung mit zusätzlicher Information
Es wurde also eine weitere Spalte hinzugefügt, sodass in jeder Reihe die Anzahl der Einsen gerade ist. Die Lehrerin schließt die Augen und bittet einen Schüler, irgendeinen Wert zu ändern. Um den Fehler zu finden, muss die Lehrerin jetzt nur Zeile für Zeile alle Einsen zusammenzählen.
Wissenschaftliche Anmerkungen
- Diese Methode wird in der Informatik sehr oft zur Fehlerkontrolle beim Kopieren oder bei der Übertragung einer Datei eingesetzt. Wie der Fehler dann auch gefunden werden kann, wird weiter unten beschrieben.
- Das am Ende der Zeile hinzugefügte Bit nennt man Paritätsbit.
Recherchearbeit: Wie kann man den Fehler korrigieren?
Die Klasse bemerkt: Auf diese Weise erfährt man zwar, dass ein Fehler vorliegt, man kann ihn aber nicht korrigieren. Man weiß nicht, welches Pixel fehlerhaft ist, sondern lediglich, in welcher Reihe sich das fehlerhafte Pixel befindet. Um die genaue Position des fehlerhaften Pixels zu bestimmen, müsste man zusätzlich wissen, in welcher Spalte es sich befindet.
Die Lehrerin fragt die Klasse, wie das funktionieren könnte. Die Schüler kommen dieses Mal von allein auf die Antwort: Man macht einfach mit den Spalten das, was vorhin schon mit den Zeilen gemacht wurde. Man zählt die Anzahl der Einsen in jeder Spalte. Ist die Anzahl gerade, schreibt man unter die Spalte eine "0", ist sie ungerade, schreibt man unter die Spalte eine "1". In dieser erweiterten Datei ist die Anzahl der Einsen in jeder Spalte immer gerade.
Die Datei sieht nun folgendermaßen aus:
0 0 1 0 0
0 0 1 0 0 1
0 1 0 1 0
0 1 0 1 0 0
1 0 0 0 1
1 0 0 0 1 0
0 1 0 1 0
0 1 0 1 0 0
0 0 1 0 0
0 0 1 0 0 1
1 0 0 0 1 0
Abb. 4: Paritätsbits am Ende der Zeilen und Spalten
Ein Schüler verändert erneut einen Wert in der Datei. Diesmal wird die Lehrerin ihm genau sagen können, welchen Wert er verändert hat (nämlich den Wert am Kreuzungspunkt der Spalte und der Zeile mit ungeraden Paritätsbits). Sie kann den Fehler auch sofort korrigieren.
Wissenschaftliche Anmerkung
Ein auf "1" gesetztes Paritätsbit unten rechts in der Ecke weist darauf hin, dass der Fehler nicht in den Bilddaten, sondern in den Paritätsbits selbst zu suchen ist.
Aufgabe (Gruppenarbeit)
Diese Aufgabe basiert auf einer Übung aus dem Buch "Computer Science Unplugged" [1].
Sobald die Schüler das Prinzip mit den Paritätsbits verstanden haben, teilt die Lehrerin sie in Zweiergruppen auf und gibt jeder Gruppe einen Satz Karten (am besten eignen sich Memory-Karten oder quadratische Pappstücke, die auf der einen Seite schwarz, auf der anderen weiß angemalt sind; aber normale Spielkarten tun es auch). Die Schüler üben damit, Fehler in der Bilddatei zu erkennen und zu korrigieren.
- Ein Schüler spielt den Detektiv: Er dreht sich um oder lässt sich die Augen verbinden. Der andere "zeichnet" mit den Karten ein Muster (jede aufgedeckte Karte stellt eine "1" dar, jede umgedrehte Karte eine "0").
- Der Detektiv-Schüler schaut sich das Bild an und setzt die Paritätsbits (zusätzliche Karten).
- Der Detektiv-Schüler schaut erneut weg, während der andere Schüler eine Karte umdreht.
- Nun sucht und korrigiert der Detektiv-Schüler den Fehler, indem er die Parität der Zeilen und Spalten überprüft.
Pädagogische Anmerkung
Wenn ein Schüler der Meinung ist, dass sein Partner den Fehler nicht anhand der Paritätsbits erkennt, sondern weil er sich das Muster gemerkt hat, kann er versuchen, die Anzahl der Karten zu erhöhen und ein Muster zu legen, das sich der Detektiv-Schüler weniger leicht merken kann.
Gemeinsame Erörterung
Die Lehrerin vergewissert sich, dass alle Schüler das Prinzip mit den Paritätsbits verstanden haben, und fragt sie nun: "Was passiert, wenn zwei Fehler auftreten, zum Beispiel in der gleichen Reihe?". Die Klasse stellt fest, dass man in solch einem Fall trotzdem sagen kann, dass die Datei Fehler enthält, weil sich durch die beiden Fehler die Paritätsbits zweier Spalten ändern. Aber man kann nicht herausbekommen, welche Reihe fehlerhaft ist.
Die Klasse diskutiert darüber, wie man verhindern könnte, dass man Fehler nicht lokalisieren kann. Man könnte zum Beispiel die Anzahl der Paritätsbits erhöhen (anstatt nach 5 Bits ein Paritätsbit zu setzen, könnte man schon nach 3 Bits eins setzen). Je mehr Paritätsbits man setzt, desto wahrscheinlicher ist es, dass man einen Fehler entdeckt. Der Nachteil ist, dass die Datei entsprechend größer wird – sie braucht mehr Speicherplatz und es dauert länger, bis man sie übertragen hat.
Fügt man alle 5 Bits ein Paritätsbit hinzu, erhöht man den Informationsgehalt und damit die Größe der Datei um 20%. Je nachdem wie wichtig die Daten sind und wie sicher/verlässlich das Abspeichern/Übertragen einer Datei ist, kann man auch nur alle 10 Bits bzw. alle 100 Bits ein Paritätsbit setzen. Man muss einen vernünftigen Kompromiss finden.
Zusammenfassung
Die Schüler fassen zusammen, was sie in dieser Unterrichtsstunde gelernt haben.
- Ein Computer stellt jede Information im Binärcode dar.
- Es können beim Verarbeiten und/oder der Übertragung von Daten Fehler auftreten.
- Es gibt Methoden, um solche Fehler zu entdecken und zu korrigieren (Paritätsbit, Prüfsumme). Allerdings muss dann mehr Information gespeichert und übertragen werden.
Die Lehrerin vervollständigt den Abschnitt "Information" des Plakats "Was ist Informatik?".
Variante
Man kann diese Unterrichtsstunde auch anders aufziehen, losgelöst von den bisherigen Unterrichtsstunden, eher als eine Art Spiel. Diese Variante beruht auf einer Übung aus dem Buch "Computer Science Unplugged" [1].
- Die Lehrerin erklärt, dass sie ein kleines Zauberkunststück vorführen wird.
- Die Klasse ist in vier Gruppen aufgeteilt. Jede Gruppe hat 25 Karten, aus denen sie ein Muster mit 5 Spalten und 5 Reihen legen kann.
- Die Lehrerin geht von Gruppe zu Gruppe und legt ans Ende der Reihen und unter die Spalten zusätzliche Karten. Sie setzt Paritätsbits, ohne den Schülern zu erklären, was sie tut.
- Sie bittet anschließend jede Gruppe heimlich eine einzige Karte umzudrehen. Sie geht dann erneut von Gruppe zu Gruppe und deutet auf die Karte, die umgedreht wurde.
- Der weitere Ablauf der Unterrichtsstunde erfolgt dann ähnlich wie weiter oben beschrieben. Das Ziel ist, dass sich die Schüler die Methode aneignen, die die Lehrerin ihnen gerade gezeigt hat.
Die Schüler können diesen "Zaubertrick" ihrer Familie vorführen. Das kann Spaß machen!
Mögliche Erweiterung für die Sekundarstufe I
Die Schüler können recherchieren, in welchen Bereichen die Methode mit den Paritätsbits eingesetzt wird.
- Der ASCII-Code, mit dem u. a. die Buchstaben des Alphabets kodiert werden, verwendet 7 Bits pro Zeichen. Computer arbeiten aber meistens mit Paketen von 8 Bits (= 1 Byte). Das achte Bit wurde früher oft als Paritätsbit verwendet. Heutzutage wird es jedoch meistens verwendet, um die Anzahl der darstellbaren Zeichen zu erhöhen (mit 7 Bits kann man "nur" 128 Zeichen darstellen).
- Die Netzkommunikation im Internet geschieht mittels Netzwerkprotokollen (zum Beispiel TCP/IP). Diese Netzwerkprotokolle verwenden Paritätsbits, um die Integrität (Vollständigkeit + Richtigkeit) der übertragenen Daten zu überprüfen.
- Zur Fehlerkontrolle wird anstatt des Paritätsbits oft eine sogenannte Prüfziffer verwendet. Diese wird je nach Anwendung auf unterschiedliche Weise berechnet. Beispiele: die ISBN-Nummer eines Buches, die IBAN-Kontonummer (Internationale Bankkonto-Nummer), die Personalausweisnummer.
Fußnote
1:
Computer Science Unplugged: Error detection – Card Flip Magic
(CC BY-NC-SA 4.0).
Diese Aktivität gibt es auch auf Deutsch:
Der
Zaubertrick (S. 33).
Letzte Aktualisierung: 14.10.2024
