Turbo Toolbox/Turbo_Toolbox.iso/spezial/10/crc.dok

Text File | 1989-04-24 | 13.8 KB | 372 lines

CRC-Sicherung per Software


von Günter Born


Wenn binäre Daten zwischen Verarbeitungskomponenten ausgetauscht
werden, ist damit zu rechnen, daß Störungen die Informationen verfäl-
schen. Um das Problem zu beheben, existieren verschiedenartige Ver-
fahren, unter anderem auch der "cyclic-redundancy-check".

Da das Thema CRC-Sicherung teilweise recht stiefmütterlich behandelt
wird, insbesondere was konkrete Softwarealgorithmen angeht, zeigt der
folgende Beitrag die Grundlagen des CRC-Verfahrens. Implementierungen
für verschiedene Sprachen sind auf einer TOOLBOX Spezial-Diskette
ausgearbeitet und erhältlich.

Die CRC-Prüfung, zum Beispiel in Floppy Controllern, erfolgt in der
Regel mittels spezieller Bausteine. In der täglichen Praxis treten
jedoch immer wieder Fälle auf, wo entsprechende Hardwarekomponenten
aus den unterschiedlichsten Gründen nicht einsetzbar sind. Hier kann
eine softwaremäßige CRC-Berechnung gute Dienste leisten.

Eine Hauptaufgabe der Datenkommunikation besteht in der Fehlerer-
kennung und -korrektur. Da Fehlerkorrekturen recht aufwendig sind,
wird diese Methode nur dort angewandt, wo die Daten nicht, oder nur
mit großem Aufwand, wiederbeschaffbar sind (z.B. Satellitenüber-
tragung). In allen anderen Fällen reicht eine sichere
Fehlererkennung, da der Sender die Daten gegebenenfalls neu
übertragen kann.

Bei einfachen Anwendungen erfolgt die Sicherung mittels Paritätsbits
(z.B. Terminal- und Druckerverbindungen). Verbesserte Über-
tragungsverfahren verwenden Längs- und Querparitätsprüfungen zur Er-
höhung der Sicherheit. Gemeinsam ist allen Varianten die leichte Rea-
lisierbarkeit, aber auch das Problem, daß Mehrfachfehler nicht immer
sicher erkannt werden können. Aufbauend auf dieser Erkenntnis
benutzen höherwertigere Übertragungsverfahren die CRC-Methode zur
Codesicherung (z.B. HDLC / SDLC, Floppy- / Plattenaufzeichnung,
etc.). Durch Auswahl geeigneter Sicherungspolynome kann die ge-
forderte Fehlerzahl pro Nachricht sicher erkannt werden.

Da diese Aufgabe aufwendiger als eine reine Paritätsprüfung ist,
verwendet man in der Regel spezielle Bausteine. In der Praxis kommt
es jedoch immer wieder vor, daß eine CRC-Sicherung erforderlich wird,
ohne daß entsprechende Hardware eingesetzt werden kann. Ein Beispiel
ist die Implementierung von zeichenorientierten Übertragungsproze-
duren mit einer Fehlererkennung per cyclic-redundancy-check. Hier
kommt dann nur eine Softwarelösung in Frage. Da nicht alle
Prozessoren mit entsprechenden Befehlen ausgestattet sind, wird nach-
folgend gezeigt, wie man zu einer Lösung gelangt.


Grundlagen der CRC-Berechnung


Bevor wir uns mit konkreten Algorithmen zur CRC-Berechnung beschäf-
tigen, soll noch kurz auf die Grundlagen eingegangen werden.

Eine Folge von n Binärzeichen (Bsp. 1001 0000) werde mit:

Repro1 (75 x 15)

bezeichnet. Diese Folge läßt sich dann als binäres Polynom vom Grade
n darstellen,

Repro2 (75 x 15)

mit dem Koeffizienten a,,tn. I(x) wird im folgenden als
Informationspolynom bezeichnet, da es die Folge von Binärzeichen
(Information) beinhaltet. Der Grad des Polynoms wird durch die Länge
der Folge B bestimmt.

Es existiert nun ein weiteres Polynom G(x) vom Grad k < n, d.h. der
Grad ist kleiner als der des Informationspolynoms, welches nicht
durch andere binäre Polynome darstellbar (irreduzibel) ist.

Repro 3 (75 x 15)

Das Informationspolynom wird nun mit x,,hk (k = Grad G(x))
multipliziert und dann durch das Generatorpolynom G(x) dividiert.



Repro 4 (75 x 30)


Das Restpolynom R(x) mit dem Grad k wird nun an das Informationspoly-
nom angehängt. Das Ergebnis wird als Codepolynom C(x) bezeichnet.

Repro 5 (75 x 15)

An Stelle der ursprünglichen Binärzeichenfolge B finden wir nun eine
Codefolge, in der B um die Koeffizienten von R(x) ergänzt wurde. Das
zugehörige Codepolynom C(x) besitzt die Eigenschaft, daß es durch
G(x) ohne Rest teilbar ist /1/.


Repro 6 (75 x 30)




Diese Eigenschaft wird nun zur Informationssicherung ausgenutzt: Eine
Folge von Binärzeichen (Koeffizienten des Informationspolynoms I(x))
wird durch ein Generatorpolynom G(x) dividiert. Die Koeffizienten des
entstehenden Restpolynoms (CRC-Code) werden an die Nachricht
angehängt. Auf der Empfängerseite wird die eintreffende Zeichenfolge,
einschließlich des Divisionsrestes, durch das vereinbarte
Generatorpolynom dividiert. Ist der Divisionsrest Null, dann wurde
die Zeichenfolge korrekt empfangen. Andernfalls sind Fehler während
der Übertragung aufgetreten. Der Grad des Generatorpolynoms bestimmt
dabei die Zahl der Mehrfachfehler, die sicher erkannt werden können.


Ein Beispiel


Das Verfahren soll nun an Hand eines kleinen Beispiels überprüft
werden. Es soll die Binärzeichenfolge 1001100101 übertragen werden.
Als Generatorpolynom wird:

   G(x) = x,,h3 + x + 1 (Grad k = 3)

gewählt. Aus der Binärzeichenfolge ergibt sich das
Informationspolynom zu:


Repro 7 (75 x 23)


Die Division von I(x) * x,,h3 durch G(x) liefert folgendes Ergebnis:




Repro 8 (75 x 40)







Damit ergibt sich das Codepolynom zu:

Repro 9 (75 x 15)

An die ursprüngliche Zeichenfolge wird der Divisionsrest 101
angehängt.



Repro 10 (75 x 30)


Das Ergebnis wird nun übertragen und auf der Empfängerseite durch das
gleiche Polynom G(x) dividiert. Bei korrekter Übertragung ergibt
sich:




Repro 11 (75 x 40)





Eine Division des Codepolynoms C(x) durch x,,h3 führt auf das
ursprüngliche Informationspolynom I(x) und damit auf die Binärfolge
1001100101 zurück. Tritt nun während der Übertragung eine Störung
auf, muß sich dies bei der CRC-Berechnung im Empfänger bemerkbar
machen. Unter der Annahme, daß die empfangene Nachricht:

        1011100001101

zwei Fehler enthält, ergibt sich folgende Rechnung:




Repro 12 (75 x 40)





Übertragungsfehler können also leicht durch
R(x) <> 0 erkannt werden.

Die CRC-Sicherung beruht also darauf, eine Zeichenfolge bitweise
durch ein Generatorpolynom zu dividieren. Die Bitfolge, sowie der
Divisionsrest, sind dann zu übertragen. Im Empfänger wird der
eintreffende Bitstrom (Nutzzeichen und Divisionsrest) durch das glei-
che Polynom dividiert. Falls ein Divisionsrest <> 0 auftritt, liegt
ein Übertragungsfehler vor.

In der Praxis werden häufig Generatorpolynome mit dem Grad 8,12,16,32
eingesetzt, um bei byteorientierter Bearbeitung Abspeicherung und
Handhabung zu vereinfachen.


Die Umsetzung in ein numerisches Verfahren.


Nun soll aber die trockene Theorie verlassen werden. Es stellt sich
die Frage, wie obige Erkenntnis in die Praxis umsetzbar ist. Die ge-
zeigte Polynomdivision ist sicherlich nicht sehr effektiv auf dem
Rechner zu realisieren. Glücklicherweise läßt sich eine binäre Divi-
sion jedoch auf Verknüpfungen von Schiebeoperationen mit Additionen
(mittels Exclusiv ODER) zurückführen. Damit ist die CRC-Berechnung
nach einem Schema gemäß Bild 1 darstellbar.

Hierbei wurde das häufig verwendete Generatorpolynom:

Repro 13 (75 x 15)


gewählt. Eine binäre Zeichenfolge, z.B. ein Text, wird nun Bit für
Bit in den Generator eingespeist. Dieser berechnet die CRC-Summe
durch fortlaufende XOR und Schiebeoperationen. Am Ende des Vorganges
liegt die 16 Bit CRC-Summe zur weiteren Auswertung vor. In Bild 2
wird der Ablauf während der CRC-Berechnung der Zeichen 55H, 88H, CCH
gezeigt.

Die Realisierung eines solchen Generators per Hardware ist durch zu-
sammenschalten einzelner Digitalbausteine leicht möglich. Interessant
wird dieser Ansatz bei Verwendung von PLA (Programmable Logic Array)
oder ASIC (Application Spezific Integrated Circuit) Komponenten. Hier
kann der gesamte Generator unter Umständen auf einem Chip
untergebracht werden.


Realisierung eines CRC-Generators per Software


Nun haben wir bereits einige Anhaltspunkte zur Realisierung eines
CRC-Generators. Durch Übertragung des oben aufgezeigten Prinzips in
einen geeigneten Algorithmus, kann die CRC-Berechnung aber auch soft-
waremäßig erfolgen. Es gibt z.B. Prozessoren, die bereits
entsprechende Befehle vorsehen. Bei Mikroprozessoren ist dies jedoch
im allgemeinen nicht der Fall. Hier muß ein entsprechendes Programm
erstellt werden.

Vor der Erstellung muß ein geeigneter Algorithmus formuliert werden,
der als erstes ein 16 Bit CRC-Register reserviert. Dies kann entweder
in Form einer Variablen, oder als Register des Prozessors, erfolgen.
Dann ist die zu übertragende Zeichenkette in einzelne Bytes zu
unterteilen. ASCII-Zeichen liegen in der Regel bereits als Bytes vor.
Für die Berechnung wird nun jedes Byte Bit für Bit über die XOR-
Funktion mit dem CRC-Register verknüpft. Der Ablauf schematisch:
,,l
  clear CRC.Reg
  LOOP über alle Zeichen
   lese Zeichen
   LOOP über alle 8 Bits des Zeichens
    carry := CRC.Reg XOR Zeichen
    shift right (Zeichen)
    shift right (CRC.Reg)
    IF carry = 1 THEN
     CRC.Reg := CRC.Reg OR 8000H {* shift MSB *}
     CRC.Reg := CRC.Reg XOR Polynom {* xor Bits *}
    ELSE
     CRC.Reg := CRC.Reg AND 7FFFH {* clear MSB *}
    ENDIF
   END {* LOOP über 8 Bit *}
  END {* LOOP über alle Zeichen *}

Dieser Algorithmus läßt sich nun recht einfach in Form eines
Programmes implementieren. Wie dies zum Beispiel für den Intel 8086
Prozessor aussieht, wird im Listing (Bild 3) gezeigt.

Ein Großteil der Anwender setzt nun aber Hochsprachen zur
Softwareentwicklung ein und obiges Programm läßt sich wegen der
Parameterübergabe per Register nur in Assemblerroutinen einbinden.
Geeignete Algorithmen für verschiedene Hochsprachen finden Sie auf
der "TOOLBOX-Spezial X: CRC-Softwaresicherung", die solche Routinen
für die Intel 80x86 Prozessoren in Assembler und Turbo Pascal 4/5
enthält. Die CRC-Berechnung reduziert sich dann auf den Aufruf der
Prozedur (z.B. in Turbo Pascal):

 CRC (CRCregister, Zeichenpuffer, Zeichenzahl)

und die Einbindung der entsprechenden Bibliotheksroutine.
Beispielprogramme in Turbo Pascal 4/5 und Quick Basic 4.x
demonstrieren den Umgang mit den Bibliotheksmodulen.


Weitere Optimierungen


Die Implementierung des Algorithmus in Assembler bringt bereits eine
erhebliche Effizienzsteigerung gegenüber Lösungen in Hochsprachen.
Trotzdem bleibt die Frage, ob sich das Verfahren im Hinblick auf die
Verarbeitungsgeschwindigkeit noch steigern läßt. Eine Analyse des Al-
gorithmus zeigt, wo Optimierungen Sinn machen: Das Auslesen der
Zeichen aus dem Puffer kostet zwar Zeit, ist aber unvermeidbar. Da
jeweils nur ein Zugriff pro Zeichen erfolgt, bringt eine Optimierung
nur wenige Vorteile. Anders sieht es aber bei der Bearbeitung des
Zeichens aus, da für jedes Zeichen die innere Schleife 8 mal
durchlaufen wird. Jede noch so kleine Optimierung wirkt sich deshalb
drastisch auf das Laufzeitverhalten aus. Aber wie kann der
Algorithmus noch verbessert werden?

Im Assembler hilft es, wenn alle Zwischendaten nicht im Speicher,
sondern in den Registern des Prozessors gehalten werden können. Aber
ganz befriedigend ist dieses Verfahren immer noch nicht. Schön wäre
es, wenn die Zahl der Schleifendurchläufe verringert werden kann:
Hier hat uns die Betrachtung der Hardwarelösung unbewußt in eine
Sackgasse geführt. Per Hardware läßt sich die XOR-Verknüpfung und die
Schiebeoperation sehr elegant verwirklichen. Bei hohen Taktraten
erreicht der CRC-Generator dann einen recht hohen Durchsatz.

Anders sieht es aber bei den Mikroprozessoren aus. Einmal sind diese
für eine Bitverarbeitung nicht optimiert, sollen sie doch gewöhnlich
Bytes und Worte bearbeiten. Zusätzlich ist die Taktfrequenz des
Prozessors in der Regel fest vorgegeben, so daß die
Verarbeitungsleistung begrenzt wird. Diese obige Einschränkung ist
einerseits bedauerlich, birgt aber anderseits auch den Schlüssel zur
Lösung unseres Problems. Wenn ein Mikroprozessor besser zur Bearbei-
tung von Bytes oder Worten geeignet ist, dann sollte der CRC-
Algorithmus dies berücksichtigen. Während die hardwareorientierte
Lösung sich nicht zuletzt aus Aufwandsgründen auf die bitorientierte
Verarbeitung beschränkt, gilt diese Einschränkung beim Mikrprozessor
nicht. Was hindert uns also daran, eine parallele Verarbeitung anzu-
streben?

Überlegen wir uns einmal die Konsequenzen: In einem 8 Bit Zeichen
lassen sich maximal 255 verschiedene Bitkombinationen speichern. Dies
bedeutet andererseits, daß bei der CRC-Berechnung im Grunde auch nur
255 verschiedene Ergebnisse auftreten können. Die Daten im CRC-
Register werden ja zyklisch verschoben. Also müßte es doch möglich
sein, ausgehend vom Wert im CRC-Register und vom gerade eingelesenen
Zeichen das Ergebnis vorauszuberechnen.

Das Ergebnis ist ein Algorithmus, der die bitweise Bearbeitung der
einzelen Zeichen vermeidet. Vielmehr werden Tabellen mit vorher
ermittelten Ergebnissen zur CRC-Berechnung benutzt. Bei jedem Zeichen
ist dann nur noch eine Verknüpfung des CRC-Registers mit dem
Tabelleneintrag erforderlich. Die vormals existierende innere
Schleife mit 8 maligem Durchlauf reduziert sich dann auf einen
Zugriff auf die Tabelle. Es ist einsichtig, daß dieser Algorithmus
eine erhebliche Effizienzsteigerung bringt.

Auf der ist "TOOLBOX-Spezial-Diskette" ist dieser Algorithmus in Form
einer Turbo Pascal Procedur enthalten. Damit lassen sich eigene
Lösungen zur Berechnung von CRC-Summen recht schnell erzielen. Gerade
bei der seriellen Übertragung von Daten über V24 Leitungen sollte das
Übertragungsprotokoll nicht auf ein solches Sicherungsverfahren
verzichten.


Literatur

/1/ Unger, C.: Datenfernverarbeitung und Rechnernetze. Kursunter-
lagen der Fernuniversität - Gesamthochschule - Hagen, KE 2, S. 43 -
45.


Achtung:

Die Implementationen für die vorgestellten Algorithmen in Turbo
Pascal 4/5 und Assembler für die Intel 80x86-Prozessoren, sowie
Beispielprogramme zum Umgang mit den Bibliotheksmodulen in Turbo Pas-
cal 4/5 und Quick-Basic 4.x bietet die

TOOLBOX-Spezial X: CRC-Softwaresicherung

Beachten Sie die Werbung am Ende der Sonderbeilage.