Fehlererkennung mittels CRCAn dieser Stelle soll in wenigen Worten ein Verfahren mit CRC (Cyclic Redundancy Check) besprochen werden. CRC basiert auf der Division vom Polynomen. Bei diesem Verfahren werden die n Bits eines Datenblocks als Koeffizienten eines Polynoms U(x) vom Grad n-1 interpretiert. Dann wird noch ein erzeugendes Polynom G(x) vom Grad k benötigt. Ein gängiges Gerneratorpolynom ist: CRC-CCITT: X16 + X12 + X5 + 1 (k = 16) Die Vorgehensweise ist folgende: -
An die Nutzinformation werden k Nullbits angehängt (oder bei Datex-P 1D0Fh). Die Nachricht einschließlich CRC-Feld ist dann n+k Bits lang und entspricht dem Polynom Xk * U(x).
-
Dieses Polynom wird nun durch das Generatorpolynom G(x) unter Verwendung der Dualarithmetik dividiert. Es entsteht ein Restpolynom R(x) vom Grad k-1 (also eine Folge von k Bits).
- Die Koeffizienten von R(x) werden in das CRC-Feld eingetragen. Da bei der Dualarithmetik 1-Bit-Addition/Subtraktion durch Exklusives Oder realisiert werden können, enthält die gesendete Nachricht einschließlich Prüfsumme das Polynom
B(x) ist durch G(x) ohne Rest teilbar. Auf Empfängerseite wird B(x) wieder durch G(x) geteilt. Das CRC-Feld muß dann lauter Nullen enthalten. Bei einem 16-Bit-CRC werden Burst-Fehler von nicht mehr als 16 Bit erkannt. Bei
längeren Burst ist die Wahrscheinlichkeit der Erkennung 99,997%. Bei einem
32-Bit-CRC werden 99,99999995% aller längeren Fehler-Bursts erkannt.
Die technische Realisierung kann durch ein rückgekoppeltes Schieberegister
der Länge k erfolgen. Das folgende Beispiel wird aus Gründen der Übersichtlichkeit
nur mit einem 5-Bit-Schieberegister realisiert. Wir wõhlen dazu das Generator-Polynom:
Die Nutzdaten werden um 5 Nullbits verlängert und dann seriell in das Schieberegister
gespeist. nach n Schiebeoperationen sind die Nutzdaten gesendet, nach weiteren
k Schiebeoperationen auch das CRC-Feld. Dazu ein Beispiel. Es soll der Datenblock
1010001101 (n = 10) gesendet werden. Der Inhalt des Schieberegisters kann anhand
der folgenden Tabelle verfolgt werden:
| | Flipflops des
Schieberegisters | Nutz-
daten |
| Urzustand | A | B | C | D | E | |
| 1.Schritt | 0 | 0 | 0 | 0 | 0 | |
| 2.Schritt | 1 | 0 | 1 | 0 | 0 | | 1 |
| 3.Schritt | 1 | 1 | 1 | 1 | 1 | | 0 |
| 4.Schritt | 1 | 1 | 1 | 1 | 0 | | 1 |
| 5.Schritt | 0 | 1 | 0 | 0 | 1 | | 0 |
| 6.Schritt | 1 | 0 | 0 | 1 | 0 | | 0 |
| 7.Schritt | 1 | 0 | 0 | 0 | 1 | | 0 |
| 8.Schritt | 0 | 0 | 0 | 1 | 0 | | 1 |
| 9.Schritt | 1 | 0 | 0 | 0 | 1 | | 1 |
| 10.Schritt | 1 | 0 | 1 | 1 | 1 | | 0 |
| 11.Schritt | 0 | 1 | 1 | 1 | 0 | | 1 |
Im Schieberegister steht nun R(x), das CRC-Feld. Da nun 5 Nullbits folgen, wird
dieses unverändert an die Daten angefügt.
| 
DIENSTE
