CRC

Cyclic Redundancy Check -
Prüfsummen und Prüfpolynome für den Datenaustausch

Franz Fiala

Prüfsummenbildung ist eine Aufgabe der Sicherungsschicht im OSI-Schichtenmodell (Schicht 2). Die für die Prüfsummenbildung erforderlichen Schieberegister und Vergleichsoperationen werden im allgemeinen in der Hardware implementiert. Zum Beispiel übernehmen die Chips für die serielle asynchrone Übertragung (UART, im PC: 8250) die Bildung und Prüfung des Paritätsbits und die Chips für die synchrone Übertragung  (USART, meist gekoppelt mit einer asynchronen Funktionalität) die Bildung und Prüfung des CRC-Prüfwortes.

Wenn bei asynchronen Übertragungsstrecken ein eigenständiges Übertragungsprotokoll verwendet wird, welches zusätzliche Prüsummenbildung verlangt, kann die Prüfsummenbildung auch in der Software implementiert werden. Dafür ist die Kenntnis des genauen Ablaufs entscheidend.

Prinzip

CRC-Prüfsummen gewinnt man, indem die Daten in ein 16-Bit-Schieberegister geschoben werden. Das Schieberegister repräsentiert das Prüfpolynom und enthält an bestimmten Bitpositionen XOR-Rückkopplungen. Sind alle Bits eingeschoben, enthält das Schieberegister die Prüfsumme. Diese wird den Daten angehängt. Auf Empfängerseite werden die Daten inklusive Prüfsumme in ein äquivalentes Schieberegister eingeschoben. Bei fehlerfreier Übertragung enthält das Schieberegister den Wert 0. Netzwerke verwenden 32 Bit.

CRC-16-Schieberegister

Schiebt man in das Schieberegister z.B. das Byte 31H (MSB zuerst), so entsteht nach dem 8ten Schiebeschritt die Prüfsumme 80A5H (siehe Kasten).

Gängige CRC-Prüfpolynome

Parity-Bit:  X+1 (even Parity)

LRC-8:       X8+1

CRC-16:      X16+X15+X21

CRC-16 X.25: X16+X12+X5+1

CRC-12:      X12+X11+X3X2X1+1

Protokoll

Die korrekte Funktion einer Prüfsumme beruht auf einer Übereinkunft zwischen Sender und Empfänger über die Länge des zu sichernden Datenpakets.

Es muß Klarheit herrschen, wo das zu sichernde Datenpaket beginnt (Startbit, Flag, SYNC-Zeichen) und wie lang es ist (festgelegte Länge, Längenfeld). Weiters muß festgelegt werden, ob diese Information bei der Sicherung mitberücksichtigt wird.

Die Summe dieser Vereinbarungen nennt man Protokoll.

Quelle

Dieses Beispiel ist dem Tabellenbuch Friedrich entnommen (Kapitel 6.6.3) und wurde für Unterrichtszwecke etwas erweitert.

Friedrich

Tabellenbuch Information- und Kommunikationstechnik, Dümmler-Verlag, Bonn, 8. Auflage, 536 Seiten, ISBN 3-427-53101-5. Als Schulbuch zur Approbation vorgelegt.

Kapitel

Mathematische Grundlagen l Physikalische Grundlagen l Grundlagen der Elektrotechnik l Baulemente und Grundschaltungen de Elektrotechnik l Digitaltecnik l Computertechnik l Signalübertragung l Vermittlungstechnik und Endgeräte l Netzwerke l Audiotechnik l Fernsehtechnik l Satellitenempfangstechnik l Videospeichertechnik l Regelungstechnik l Arbeits- und Umweltschutz l Datenschutz l Schaltzeichen und Symbole l Normen und Vorschriften

Dieses Tabellenbuch kann für einen weiten Bereich von Anwendern der Informationstechnologie ein ständiger Begleiter werden, da hier Informationen gemeinsam präsentiert sind, die sonst mühsam aus Datenblättern, Normen und anderen Quellen zusammengetragen werden müßten.

Sowohl für die einschlägig orientierten HTLs, HAKs aber auch für AHS mit Informatikschwerpunkt ist dieses Werk eine wertvolle Informationsquelle.

Beispielsweise sind im Abschnitt Computertechnik alle Peripheriebausteine des PC so detailliert beschrieben, daß nach den Tabellen unmittelbar Programme formuliert werden können. Es wurde auch nicht darauf vergessen, die jeweiligen Adressen im PC genau anzugeben. Selbstverständlich findet man auch die Pinbelegungen der betreffenden Stecker, sodaß auch praktische Experimente ausführbar sind.

Beispiel für eine Prüfsummenbildungbild3.GIF