home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 10 / readme.doc < prev   
Encoding:
Text File  |  1988-11-18  |  7.9 KB  |  184 lines
  1. CRC-Sicherung (cyclic-redundancy-check) per Software
  2.  
  3. Beim Einsatz von Rechnern werden binäre Daten zwischen den Verarbei-
  4. tungskomponenten ausgetauscht. Insbesondere bei der seriellen Über-
  5. tragung verfälschen Störungen auf der Leitung die gesendeten Infor-
  6. mationen. Um das Problem zu beheben, existieren verschiedene Ver-
  7. fahren zur Fehlererkennung und -korrektur. Ist die Übertragung im
  8. Fehlerfall leicht wiederholbar, beschränkt man sich aus Aufwands-
  9. gründen meist auf die Fehlererkennung. Zu diesem Zweck wird, neben
  10. Verfahren wie Paritäts-, Längs- und Quersummerprüfung, die CRC -
  11. Sicherung eingesetzt. Die CRC-Prüfung (z.B. in Floppy Controllern)
  12. erfolgt dabei in der Regel mittels spezieller Bausteine. In der
  13. täglichen Praxis treten jedoch immer wieder Fälle auf (z.B. bei
  14. Übertragungsprotokollen auf V24 Leitungen), wo entsprechende Hard-
  15. warekomponenten aus den  unterschiedlichsten Gründen nicht einsetz-
  16. bar sind. Hier kann eine softwaremäßige CRC-Berechnung gute Dienste
  17. leisten. Die verfügbare Literatur behandelt das Thema CRC-Sicherung
  18. teilweise recht stiefmütterlich, insbesondere was konkrete Software-
  19. algorithmen angeht. Die vorliegende Toolbox enthält deshalb konkrete
  20. Programmlösungen in Turbo Pascal 4.0 / 5.0 und Assembler. Die Module
  21. lassen sich sowohl in Turbo Pascal, Assembler und Quick Basic 4.x
  22. einbinden. Eine Portierung für weitere Sprachen ist möglich, da alle
  23. Module im Quellcode vorliegen.
  24.  
  25.  
  26. Einleitung
  27.  
  28. Datenübertragung zwischen Rechnern, oder zu Datenendgeräten, erfolgt
  29. häufig mittels serieller Verbindungen. Als Problem erweisen sich
  30. Störungen während der Übertragung, die im Empfänger zu fehlerhaften
  31. Ergebnissen führen. Eine Hauptaufgabe der Datenkommunikation besteht
  32. deshalb in der Fehlererkennung und -korrektur. Da Fehlerkorrekturen
  33. recht aufwendig sind, wird diese Methode nur dort angewandt, wo die
  34. Daten nicht oder nur mit großem Aufwand, wiederbeschaffbar sind (z.B.
  35. Satellitenübertragung). In allen anderen Fällen reicht eine sichere
  36. Fehlererkennung, da der Sender die Daten gegebenenfalls neu übertragen
  37. kann. Bei einfachen Anwendungen erfolgt die Sicherung mittels Paritäts-
  38. bits (z.B. Terminal- und Druckerverbindungen). Verbesserte Übertra-
  39. gungsverfahren verwenden Längs- und Querparitätsprüfungen zur Erhöhung
  40. der Sicherheit. Gemeinsam ist allen Varianten die leichte Realisier-
  41. barkeit, aber auch das Problem, daß Mehrfachfehler nicht immer sicher
  42. erkannt werden können. Aufbauend auf dieser Erkenntnis benutzen
  43. höherwertigere Übertragungsverfahren die CRC-Methode zur Codesicherung
  44. (z.B. HDLC / SDLC, Floppy- / Plattenaufzeichnung, etc.). Durch Auswahl
  45. geeigneter Sicherungspolynome kann die geforderte Fehlerzahl pro Nach-
  46. richt sicher erkannt werden. Da die Aufgabe aufwendiger als eine reine
  47. Paritätsprüfung ist, verwendet man in der Regel spezielle Bausteine.
  48. In der Praxis kommt es jedoch immer wieder vor, daß eine CRC-Sicherung
  49. erforderlich wird, ohne daß entsprechende Hardware eingesetzt
  50. werden kann. Ein Beispiel ist die Implementierung von zeichenorien-
  51. tierten Übertragungsprozeduren mit einer Fehlererkennung per cyclic -
  52. redundancy - check. Hier kommt dann nur eine Softwarelösung in Frage.
  53. Da nicht alle Prozessoren mit entsprechenden Befehlen ausgestattet
  54. sind, werden nachfolgend entsprechende Programme vorgestellt.
  55.  
  56.  
  57. Grundlagen der CRC-Berechnung
  58.  
  59. Die Grundlagen der CRC - Berechnung wurden in
  60.  
  61.   Born G. : CRC - Sicherung (cyclic redundancy check) per
  62.   Software. Zeitschrift Toolbox, 1989, DMV Verlag Eschwege
  63.  
  64. diskutiert. Die Codesicherung beruht auf der Tatsache, daß sich eine
  65. Folge von Binärzeichen durch ein Polynom dividieren läßt. Die Binär-
  66. zeichen, sowie der Divisionsrest werden anschließend übertragen. Im
  67. Empfänger wird dann die komplette Zeichenfolge (Nutzdaten und Divi-
  68. sionsrest) durch das gleiche Polynom dividiert. Bei fehlerfreier
  69. Übertragung ist dann der Divisionsrest = 0. Andernfalls liegt ein
  70. Übertragungsfehler vor. Im Gegensatz zu Paritätsprüfungen erlaubt
  71. das CRC-Verfahren auch die zuverlässige Erkennung von Mehrfachfehlern.
  72.  
  73.  
  74. Der Inhalt der Toolbox Diskette.
  75.  
  76. Auf der Diskette befinden sich nachfolgend aufgeführte Dateien:
  77.  
  78.  
  79.  README.DOC     Die Datei mit der vorliegenden Dokumentation
  80.  
  81.  CRC.ASM        Assembler Quellprogramm zur CRC - Berechnung
  82.  
  83.  CRCA.ASM       Assembler Quellprogramm zur CRC - Berechnung
  84.  CRCA.OBJ       Objectdatei zur Einbindung in Hochspracheprogramme
  85.  
  86.  DEMO.BAS       Demonstrationsprogramme mit Hinweisen zur 
  87.  DEMO1.PAS      Anwendung der CRC - Routinen
  88.  DEMO2.PAS
  89.  DEMO3.PAS
  90.  
  91.  
  92.  
  93. Das Programm CRC.ASM
  94.  
  95. Dieses Programm enthält einen Algorithmus zur Berechnung der
  96. CRC - Checksumme und ist in Assembler (8086) formuliert. Die
  97. Parameterübergabe erfolgt in den Registern. Das Programm eignet
  98. sich im wesentlichen zur Einbindung in Assemblerroutinen und
  99. als Rumpf zur Portierung für verschiedene Sprachen.
  100.  
  101.  
  102. Die Module CRCA.ASM und CRCA.OBJ
  103.  
  104. Bei diesen Modulen handelt es sich um die Anpassung des Programmes
  105. CRC.ASM für verschiedene Hochsprachen. Das Quellprogramm liegt als
  106. Assemblerdatei (CRCA.ASM) vor. Die Datei CRCA.OBJ wurde bereits
  107. durch einen Assembler übersetzt und läßt sich direkt in Hoch-
  108. spracheprogramme einbinden. Dabei gelten folgende Aufrufkon-
  109. ventionen:
  110.  
  111.  * Die Parameterübergabe erfolgt über den Stack, wobei
  112.    Adressen als FAR Pointer übergeben werden.
  113.  
  114.  * Der Aufruf muß folgendem Format entsprechen:
  115.  
  116.      CALL CRC (CRC_Register, Buffer, Zeichenzahl)
  117.  
  118.    CRC_Register : 16 Bit (Word) Variable in der der Startwert
  119.                   zur CRC - Berechnung übergeben wird (z.B. 0).
  120.                   Nach dem Aufruf enthält die Variable das
  121.                   Ergebnis der CRC - Berechnung
  122.  
  123.     Buffer      : Zeichenpuffer mit n Bytes, über die die
  124.                   CRC - Berechnung durchzuführen ist.
  125.  
  126.     Zeichenzahl : Zahl der Zeichen im Buffer, die in die Be-
  127.                   rechnung eingehen.
  128.  
  129.     Die zwei Parameter CRC_Register und Buffer sind als Adressen
  130.     (Call by reference) zu übergeben, während die Zeichenzahl
  131.     als Wert (Call by value) gesetzt wird.
  132.  
  133.   * Die Procedur CRC ist als FAR - CALL aufzurufen, da die
  134.     Procedur über eine RETF Instruktion verlassen wird.
  135.  
  136. Die Einbindung der Procedur in ein Turbo Pascal 4.0 und 5.0
  137. Programm wird mit dem Programm DEMO3.PAS demonstriert. Die
  138. Objectdatei wird über den Schalter {$L CRCA.OBJ} eingebunden.
  139. Wichtig ist dabei, daß der Schalter {$F+} für das FAR Modell
  140. gesetzt wird. Nähere Einzelheiten sind dem Modul DEMO3.PAS
  141. zu entnehmen.
  142.  
  143. Bei Einsatz in Quick Basic wird das Microsoft Mixed Language
  144. Interface benutzt (Medium Modell). Die Datei DEMO.BAS ent-
  145. hält ein Beispiel zur Benutzung des Moduls CRCA.OBJ. Ein
  146. Einsatz ist nur mit dem Basic Compiler (BC) möglich. Die
  147. Linkanweisung für die Einbindung der Objectdatei erfolgt
  148. gemäß folgender Notation:
  149.  
  150.  LINK  xxx.obj+....obj+CRCA.OBJ
  151.  
  152. Die Anweisungen für das Programm DEMO.EXE lauten dann:
  153.  
  154.   BC DEMO.BAS
  155.  
  156.   LINK DEMO.OBJ+CRCA.OBJ
  157.  
  158. Wichtig ist in Quick Basic, daß als Puffer keine Stringadresse
  159. übergeben wird, da der Compiler in der Regel die Adresse des
  160. Stringdescriptors einsetzt. Die eigentliche Stringadresse steht
  161. dann an anderer Stelle im Speicher.
  162.  
  163.  
  164. Die Dateien DEMO1.PAS und CRC.PAS
  165.  
  166. In der Datei CRC.PAS ist die Implementierung des CRC - Verfahrens
  167. mittels Polynomdivision gespeichert. Das Programm DEMO1.PAS zeigt
  168. die Einbindung in eigene Programme. Es gelten im Prinzip die
  169. gleichen Übergabekonventionen für CRCA.ASM. Nähere Einzelheiten
  170. sind dem jeweiligen Quelltext zu entnehmen.
  171.  
  172.  
  173. Die Dateien DEMO2.PAS und CRCF.PAS
  174.  
  175. Neben der Polynomdivison existiert ein wesentlich effizienteres
  176. Verfahren zur CRC - Berechnung über Lock Up Tabellen, welches
  177. von Stuard Wecker publiziert wurde. Damit läßt sich eine erheb-
  178. liche Geschwindigkeitssteigerung erreichen. Das Turbo Pascal
  179. Programm CRCF.PAS enthält eine Implementierung dieses Verfahrens.
  180. Das Programm DEMO2.PAS zeigt die Einbindung in eigene Routinen.
  181.  
  182.  
  183.  
  184.