Unterschied zwischen CRC und anderen Prüfmechanismen

[CyberCop]

Hallöchen!

Dachte mir, ich geben wieder mal etwas Senf zum großen Würstchen (Emule-Board, soll keine Beleidgung sein). Hoffe das der Klecks Senf ein paar Leuten hilft.

Diesmal geht es wie schon im Titel steht um CRC und andere Prüfmechanismen, wenn man Daten überträgt. Ich werde nur ein paar gängige Mechanismen (3) erklären.

Fangen wir nun also an. Ich beschreibe hier das Paritätsbit, die Kreuzparität und CRC.


1. Allgemeines:
===========

Wie sicher jeder (natürlich nicht jeder aber viele) wissen bestehen Daten am PC immer aus Einsen und Nullen (Bsp: binär 00101101 = dezimal 90).
Zur Erinnerung: Dies ist deshalb so, da der Computer nur 2 Zustände erkennt (Strom ein = 1, Strom aus = 0). Nun bei der Datenübertragung kann es passieren (aufgrund von Einstreuungen von Magnetfeldern, oder anderen Störimpulsen) das eines oder mehrere dieser Bits (ein Bit = entweder 1 oder 0) umfallen und aus einer 1 eine 0 wird oder umgekehrt.

Wenn man keine Fehlererkennung und Fehlerkorrektur hätte, würde man fast keine Daten zwischen PC-PC oder PC-Peripherie hin und herschieben können.
Um einzelne eventuelle "Umfaller" (sich verändertes Bit) zu erkennen und zu korrigieren wird das Paritätsbit verwendet.


2. Paritätsbit:
==========

Wenn eine Nachricht versendet wird, wird vom PC der sendet, an die Nachricht ein Paritätsbit angehängt. Ob dieses Paritätsbit 0 oder 1 ist hängt von der Nachricht ab. Der Computer zählt alle Einsen in der Nachricht zusammen. Wenn diese zusammengezählt eine ungerade Zahl ergeben, wird eine 1 an die nachricht angehängt. (dadurch wird die Gesamtzahl an Einsen Gerade). Wenn alle Einsen zusammengezählt schon ohne Paritätsbit Gerade sind wird eine Null angehängt. Die Nachricht wird mitsamt dem Paritätsbit versendet. Der Computer der die Nachricht erhält, schaut als erstes ob das Paritätsbit 0 oder 1 ist und rechnet die Einsen der Nachricht zusammen. Wenn das Ergebnis (Gerade oder Ungerade) mit dem Paritätsbit übereinstimmt, nimmt der Computer an das die Nachricht ohne Fehler übertragen wurde und sendet ein "OK"-Bit an den Sender zurück. Damit ist die Übertragung abgeschlossen. Sollte der Empfänger merken das die Zahl nicht mit dem Paritätsbit übereinstimmt, sendet er ein "Fehler"-Bit zurück an den Sender und dieser überträgt die Nachricht nochmal. Solange bis vom Empfänger ein "OK" kommt.

Man sieht also das Pritätsbit ist einfach und DUMM.

Beispiel: 10110110 + (Paritätsbit) 1
es wird gesendet... 2 Bits fallen um 10011110 + 1

Die Rechnung stimmt, aber die Nachricht ist fehlerhaft.

Man kann nicht erkennen WO das Bit umgefallen ist, oder wieviele.
Daher wurde die nächst bessere Stufe entwickelt. Nämlich die:


3. Kreuzparität (Blockparität):
====================

Bei der Blockparität werden 8x8 Bit in einem Block versendet... jedoch kommt bei dem Block noch eine extra Spalte und eine extra Zeile für die Paritäten hinzu, also werden im Endeffekt 9x9 Bits übertragen:

Skizze:
-------------------*
0 1 0 1 1 0 1 1|1
1 0 0 1 0 0 1 0|1
1 0 1 1 0 1 0 1|1
0 1 1 1 1 1 0 0|0
1 0 1 0 0 1 0 1|0
1 0 0 0 1 0 1 0|1
0 0 1 1 0 1 0 1|0
0 1 1 0 0 1 1 0|0
---------------------
0 1 1 0 1 1 0 0|0 **

* = Die Paritätsspalte, hier werden die Einzelnen Zeilen zusammengerechnet und mit 0 oder 1 ergänzt, wie beim Paritätsbit
**= Die Paritätszeile, hier werden die einzelnen Spalten zusammengerechnet und mit 0 oder 1 ergänzt, wie beim Paritätsbit

Wenn nun ein Bit umfällt (rotes Beispielbit), kann man durch die Kreuzparität rückrechnen wo es sich befindet und es einfach umdrehen.
Schon ist die Nachricht wieder in Ordnung.

Diese Version der Fehlererkennung und Fehlerbehebung funktioniert allerdings nur bei einzelnen Fehlern, wenn nur ein Bit umfällt, und nichtmehrere. Wenn es der Fall ist das mehrere umfallen, benötigt man einen etwas besseren Mechanismus. Kommen wir daher zum CRC:


4. CRC (cyclic redundancy check):
=======================

Diese Version der Fehlerbehebung setzt ein bisschen technisches Verständnis voraus:

Am Anfang steht eine Konstante (eine fixe Zahl) die dem Sender und Empfänger bekannt ist. Die zu sendende Nachricht wird zuerst in Einheiten gegliedert, zum Beispiel:
10011101011101100101010010011101 wird in Bytes aufgespaltet (1 Byte = 8 Bit) = 10011101 - 01110110 - 01010100 - 10011101
Jede dieser Einheiten (Bytes) wird nun durch die oben festgelegte Konstante ganzzahlig dividiert. Der Divisionsrest wird an die Einheit angehängt und mitgesendet.
Sobald die Einheit beim Empfänger angekommen ist, wird die GESAMTE Einheit (+angehängtem Divisionsrest) nochmals durch die gleiche Konstante dividiert. Wenn bei dieser zweiten Division kein Rest herauskommt (also 0) so ist die Übertragung erfolgreich gewesen. Man sieht, auch wenn 2 Bits umfallen (und dadurch ein Fehler kommt, welche dur das einfache Paritätsbit nicht erkennbar wäre) funktioniert diese Fehlererkennung.
Wenn die gewählte Dateneinheit "Byte" ist (8 Bit) so gibt es einige Vorschläge für Konstanten (fixe Zahlen) bei denen die CRC-Prüfung besonders effizient ist.


So, das wars auch schon von mir, ich hoffe ich konnte etwas Licht in die Dunkelheit der Datenübertragung bringen. Wenn jemand noch zusätzliche Fragen hat, so bitte per PN, ICQ oder Mail, oder einfach hier posten


mfg

CyberCop