AX25 @KS de:DC4OX 13.08.89 13:19 5 3642 Bytes
ERKLAERUNG CRC 1/10
*** Bulletin-ID: 315803DK0MAV ***
de DB8AS @ DB8AS
CRC Teil 1 von 10
CRC Cyclic Redundancy Check / FCS Frame Check Sequence
"Vorwort"
Ich will mich bemuehen, da anscheinend doch das Interesse besteht, einiges
ueber den benutzten CRC bei Packet-Radio zu schreiben. Ich will aber nicht
nur mal eben einen schnellen Algorithmus angeben, wie man das Ding denn
nun berechnen kann, ich moechte vielmehr versuchen die Sache so darzustellen,
dass wenigstens der Weg zu den verschiedenen Algorithmen begreifbar und
nachvollziehbar wird. Was den Rahmen der Box weit sprengen wuerde, das waere
die mathematische Herleitung der Eigenschaften zyklischer Codes, da um
dies verstehen zu koennen tiefergehende mathematische Kenntnisse erforderlich
sind, tiefergehende als zum Beispiel Grundvorlesungen fuer Ingenieure in
Mathematik. Wer dennoch soooo tief in die Materie eindringen will, dem kann
ich bei Bedarf einige Literaturstellen (zur Abschreckung, hi) angeben.
Natuerlich ist das, was ich ueber CRC-Berechnung so von mir geben will, nicht
alles auf meinem Mist gewachsen, sondern ein Resultat des Lesens einiger
Literatur. Diese Literatur sollte man in normalen UNI-Bibliotheken leicht
finden koennen.
Ich gebe diese Literatur hier erst einmal an, erstens koennen sich dann
ganz Wissbegierige darauf stuerzen ohne meine Erguesse abwarten zu muessen,
zweitens bin ich gar nicht sicher, ob meine Erguesse zu diesem Thema
ueberhaupt fertig werden, hi.
Liste (sicher nicht vollstaendig, dafuer aber bei mir vorhanden ... ) :
Byte, September 1986, Sehr zu empfehlen und wohl am
Seiten 115-124, einfachsten zu bekommen. Es werden
Greg Morse, schrittweise und nachvollziehbar
"Calculating CRCs by Bits and Bytes" CRC-Berechnungen und Algorithmen
vorgefuehrt. Sehr ausfuehrlich.
IEEE Micro, August 1985, Beschreibt die kuerzeste und schnellste
To the Editor, Seiten 4, 99, Loesung fuer gewisse Prozessoren,
Ivar Kjelberg, 8086 als Beispiel.
"CRC-16 flies better in Assembler"
IEEE Micro, April 1985, Hier beschreibt der Autor der oft
Letters to the Editor, Seiten 6-8 kopierten Software-Loesung fuer Z80
Leserbrief von Robert M. Richardson (TRS80, GLB), von wem er die
(Software Approach to Packet CRC-Berechnung adaptiert hat, mit
Communications) Source fuer Z80. Auch die Apple- und
C64-Softwareloesung benutzt genau
dieses Verfahren, wenn auch die Tabelle
bei Programmstart erst berechnet wird.
IEEE Micro, Juni 1983, Der Grundlagenartikel zur parallelen
Seiten 40-50, CRC-Berechnung (Tabellenmethode), auf
Aram Perez, den sich alle juengeren Artikel
"Byte-wise CRC Calculations" beziehen. Mit Fortran-Sources zur
Tabellenerstellung.
Computer Design, September 1975, Ein Artikel, den Perez empfiehlt.
Seiten 87-91, Lediglich zur Vollstaendigkeit
A. K. Pandeya, T. J. Cassa angefuehrt.
"Parallel CRC Lets Many Lines
Use One Circuit"
NORD>
2^16 + 2^12 + 2^5 + 1 = 1 0001 0000 0010 0001
"modulo 2" : Wenn ich im Dualsystem modulo 2 rechne, muss ich mich nicht um
Ueberlaeufe kuemmern. Dadurch ist es egal, ob ich 2 Bits
addiere, subtrahiere, oder Exklusiv-Oder, im folgenden als (+)
geschrieben, verknuepfe.
Ohne "modulo 2" wuerde ich im Dualsystem rechnen :
0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 10 (2)
0 - 0 = 0 1 - 0 = 1 0 - 1 = -1 1 - 1 = 0
Mit "modulo 2" rechne ich im Dualsystem :
0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 0
0 - 0 = 0 1 - 0 = 1 0 - 1 = 1 1 - 1 = 0
Das aber entspricht genau der Exklusiv-Oder-Funktion :
0 (+) 0 = 0 1 (+) 0 = 1 0 (+) 1 = 1 1 (+) 1 = 0
Polynome : In Zusammenhang mit "modulo 2" bedeutet es fuer mich, dass ich
alle Rechnungen komponentenweise (stellenweise) ausfuehren kann.
Normal addiere ich : 111 7
+ 1110 + 14
------- ----
= 10101 = 21
d.h. ich muss auf Uebertraege achten und diese durch die
einzelnen Stellen durchschleppen.
Komponentenweise und wegen "modulo 2" verknuepfe ich nun
einfach die Bits stellenweise mit Exklusiv-Oder :
00111
(+) 01110
---------
= 01001
Das ist nun ziemlich einfach, viel einfacher als wenn ich
"normal" rechnen muesste.
(Fuer Mathematiker, die ob meiner schlampigen Erklaerungen
in diesem Zusammenhang sich bereits schwebend in gefaehrlicher
Naehe der Zimmerdecke befinden, eigentlich haette es heissen
muessen : "Gemeint sind binaere Gruppencodes, d.h. Untergruppen
der additiven Gruppe aller binaeren Tupel, die als Koeffizienten
eines Polynoms ueber dem endlichen Koerper GF(2) der Restklassen
der ganzen Zahlen mod 2 aufgefasst werden koennen." -
Nur wuerde d a s keinem weiterhelfen.)
B(X) : Blockinhalt. Meint einfach alle Bytes des Pakets ausser der
FCS und ohne Flags hintereinander ohne Punkt und Komma bitweise
aufgeschrieben. Ist eigentlich der Paketinhalt betrachtet als
eine einzige, ziemlich lange Dualzahl. Aber Vorsicht, gemeint
ist die Bitreihenfolge der Aussendung (ohne Bitstuffing), d.h.
das LSB (Least Significant Bit = das Bit mit der niedrigsten
Wertigkeit, ganz rechts) eines Bytes wird zuerst gesendet.
(Fortsetzung folgt) (hoffentlich)
NORD> 001000000000000000000000
10001000000100001
-----------------
10000001000010000
10001000000100001
-----------------
10010001100010 ---------+
!
000010000000000000000000 !
10001000000100001 !
----------------- !
1000000100001000 ------+ !
! +---------> 10010001100010
000000100000000000000000 +------------> (+) 1000000100001000
10001000000100001 +---------------> (+) 10000001000010
----------------- ! --------------------
10000001000010 ---+ 1000010100101000
Auch, wenn ich jede Stelle nur einmal durch das Generatorpolynome teile,
die Zwischenergebnisse modulo 2 addiere und dann am Ende nochmal durch
das Generatorpolynom teile, aendert das nichts am Ergebnis (man erinnere
sich an schriftliche Division) :
-> 001000000000000000000000
10001000000100001
-----------------
100000010000100000 ---------+
!
000010000000000000000000 !
10001000000100001 !
----------------- !
1000000100001000 ------+ !
! +---------> 100000010000100000
000000100000000000000000 +------------> (+) 1000000100001000
10001000000100001 +---------------> (+) 10000001000010
----------------- ! ----------------------
10000001000010 ---+ 101010010101101010
10001000000100001
----------------------
1000010100101000
Noch eine weitere Betrachtung.
Erster Fall. Bestehe die ganze Nachricht aus einem Bit, und das ist 0.
Also 16 mal linksschieben, durch das Generatorpolynom (im folgenden auch G(X)
genannt) teilen :
00000000000000000
10001000000100001
-----------------
00000000000000000 1. Rest
Zweiter Fall. Die gesamte Nachricht bestehe aus 01.
010000000000000000
( 10001000000100001 ) geht nicht ->
-----------------
10000000000000000 1. Rest
10001000000100001 geht ->
-----------------
00001000000100001 2. Rest
Was man sich merken soll, ist, dass der 1. Rest im zweiten Fall gleich dem
1. Rest im ersten Fall ist, LSB ge-exklusiv-odert mit dem 2. Datenbit. Dies
ist immer der Fall, wenn man die Beispiele ganz oben daraufhin durchsieht,
wird man es auch bemerken.
Betrachtet man den Rest, dann wird jeweils bei einem neu kommenden Datenbit 0
am rechten Ende eine 0 angehaengt, d.h. das Ergebnis wird linksgeschoben (das
ist wie bei der Division der Uebergang zur naechsten Stelle von oben, gleich
0 immer, weil jedes Bit neu ja eine ganze Stelle mit Wertigkeit darstellt, wie
z.B. 200 bei 4235 die 2. Stelle darstellt). Kommt eine 1, dann muss diese
erst einmal zum bestehenden Ergebnis mit Wertigkeit dazuaddiert werden.
Modulo 2 ist dies das Exklusiv-Oder. Danach muss wegen der Wertigkeit der
Stelle auch eine 0 rechts angefuegt werden.
Jetzt ist genug Praxis vorhanden, um aus den gemachten Beobachtungen
einen bitweise arbeitenden Algorithmus aufzuschreiben. Bitweise heisst, dass
ich jedes Datenbit so wie es kommt verarbeiten moechte, hintereinander.
1. Ich fange an mit 16 0en, das erste Datenbit fuege ich links an.
2. Dann dividiere ich durch G(X) falls moeglich (d.h. wenn das erste Datenbit
1 war) und merke mir den Rest, denn der ist der CRC.
3. Ich hole das naechste Datenbit und fuehre ein Exklusiv-Oder mit dem LSB
(= "linkstem" Bit) des Restes (= CRC) aus. Jetzt ist der CRC 16 Bit lang,
nach Teilen durch G(X) ist der CRC immer hoechstens 16 Bit lang.
4. Ich fuege eine 0 am rechten Ende des CRC an (ein Bit linksschieben), es
sind jetzt 17 Bit.
5. Falls das "linkste" Bit 1 ist, dividiere ich durch G(X)
(= komponentenweises Exklusiv-Oder).
6. Ich wiederhole die Schritte 3. bis 5. solange, bis keine Datenbits mehr
vorhanden sind.
Dumm ist, dass ich 17-Bit-Register benoetige. Aber eigentlich tun es bei
geschickter Formulierung auch 16 Bit. Denn entweder ist das "linkste", das
17. Bit, gleich 0, oder, falls es 1 ist, wird es nach der Division durch G(X)
gleich Null. Zugleich dividiere ich ja nur, wenn das 17. Bit gleich 1 ist.
Also reicht es erstens, wenn ich nach dem Linksschieben nur mit 16 Bit des
Generatorpolynoms = 1021 hex Exklusiv-Odere (dividiere ...) und zweitens
dies nur mache, wenn vor dem Linksschieben das hoechste ("linkste") Bit 1 war.
Programmiert man in Maschinensprache, dann wird es noch einfacher, weil das
"linkste" Bit nach einem Linksschieben im leicht abtestbaren Carry-Flag des
Prozessors steht, dabei kann ich schieben, abtesten, und dann je nach
Ergebnis Exklusiv-Odern oder nichts weiter tun.
Man muss beachten, dass das LSB des CRC am Ende nach dem Algorithmus ganz
links steht, dies ist das zuerst zu sendende Bit. Man kann den CRC natuerlich
auch genau andersrum berechnen, d.h. dass am Ende das MSB links steht, wie es
eigentlich normal ist. Aus Linksschiebungen werden dann Rechtsschiebungen, aus
dem Exklusiv-Oder mit 1021 hex wird das Exklusiv-Oder mit 8408 hex.
(Fortsetzung folgt) (hoffentlich)
NORD> B(X) * X^16 = Q(X) * G(X) + R(X) ! - R(X)
-> B(X) * X^16 - R(X) = Q(X) * G(X)
Aus frueher beschriebenen Gruenden (Polynomrechung/Modulo-2-Arithmetik) ist
hier aber Subtraktion gleich Addition, und ich bekomme :
-> B(X) * X^16 + R(X) = Q(X) * G(X)
Jetzt weiss ich aber, dass R(X) hoechstens 16 Bit lang ist, und B(X) * X^16
ist gerade B(X) 16 Bit linksgeschoben. Somit "passt" der CRC genau in das
Ende von B(X) * X^16 und die linke Seite der Gleichung entspricht genau dem,
was ich als Paket aussende, naemlich dem reinen Blockinhalt mit angehaengter
16 Bit Framechecksequenz FCS.
Die rechte Seite der Gleichung sagt mir, dass diese ganze Aussendung,
aufgefasst als eine einzige Zahl, durch das Generatorpolynom teilbar sein
muss. Also teile ich die gesamte Aussendung durch G(X) (Polynom, modulo 2),
und nur dann, wenn sich kein einziger Fehler beim Empfang eingeschlichen hat,
geht die Rechnung auf und ich erhalte 0 als Rest. Das ist die Fehlersicherung.
Nun weiss ich auch, wieso man laut Norm mal X^16 nimmt, nur dann entspricht
die linke Seite obiger Gleichung dem simplen Anhaengen der FCS an den
Blockinhalt.
Ich kann auch das empfangene Paket mit demselben Algorithmus, also auch mit
Malnehmen mit X^16, behandeln wie bei der Sendung, denn an der Teilbarkeit
aendert das Malnehmen mit X^16 nichts. Zu beachten ist bei dieser Methode,
dass ich die angehaengte FCS nicht irgendwie extra behandle, sondern einfach
durch den Algorithmus (das Teilen) mit durchlaufen lasse. Wenn also im
CRC-Register bei Empfang des Paketendeflags 0 steht, habe ich das Paket
richtig empfangen.
Im Falle der CCITT-Berechnung, die wir bei Packet-Radio ja benutzen, wird
allerdings noch mehr gemacht, das Invertieren des CRC und am Anfang das
Vorladen des Registers mit 1. Auch hier waere es zweckmaessig den CRC genauso
"durchzurechnen" wie bei der Sendung. Was passiert, wenn ich auch hier
genauso durchrechne wie bei der Sendung ?
Das Vorladen mit Einsen des CRC-Registers, also das Invertieren der "linksten"
16 Bit der Nachricht * X^16, wirkt sich nicht weiter aus, da ich dies sowohl
bei der Sendung als auch beim Empfang mache. Deshalb lasse ich das in der
folgenden Betrachtung der Uebersichtlichkeit wegen weg, am Ergebnis aendert
sich deswegen nichts. Die obige Formel lautet :
B(X) * X^16 + R(X) = Q(X) * G(X)
Das heisst, dass B(X) * X^16 + R(X) ganzzahlig ohne Rest durch G(X) teilbar
ist, empfangen habe ich aber die linke Seite mit invertiertem R(X).
Ein Invertieren der FCS kann ich als Addition modulo 2 mit 1111111111111111
auffassen :
( B(X) * X^16 + R(X) ) + 1111111111111111
Desweiteren muss ich jetzt in dieser Rechnung das Linksschieben um 16 Bit
beim Empfangsalgorithmus beachten, denn ich habe ja jetzt einen zusaetzlichen
additiven Faktor zu beruecksichtigen :
( B(X) * X^16 + R(X) + 1111111111111111 ) * X^16
= ( B(X) * X^16 + R(X) ) * X^16 + 1111111111111111 * X^16
Jetzt teile ich wie gehabt im Algorithmus durch G(X) :
( B(X) * X^16 + R(X) ) * X^16 / G(X) + 1111111111111111 * X^16 / G(X)
Nach wie vor interessiert mich aber nur der Rest der Rechnung, denn diesen
spuckt mein Algorithmus ja aus. Da B(X) * X^16 + R(X) durch G(X) teilbar ist,
ist sicher auch dieses Polynom mal X^16 durch G(X) teilbar, wie oben schon
angesprochen. Bleibt 1111111111111111 * X^16 / G(X), der Rest dieses Terms
ist der Rest, der am Ende uebrigbleibt. Also ran an die Bleistifte und
tief Luft holen :
1111111111111111 * X^16 : G(X)
= 1111111111111111 * 10000000000000000 : 10001000000100001
= 11111111111111110000000000000000 : 10001000000100001
-> 11111111111111110000000000000000
10001000000100001
------------------
11101111110111110
10001000000100001
------------------
11001111100111110
10001000000100001
------------------
10001111000111110
10001000000100001
----------------------
11100001111100000
10001000000100001
------------------
11010011110000010
10001000000100001
------------------
10110111101000110
10001000000100001
-------------------
11111110110011100
10001000000100001
------------------
11101101101111010
10001000000100001
------------------
11001011010110110
10001000000100001
------------------
10000110100101110
10001000000100001
-----------------
0001110100001111 (aechz - man reiche mir eine Erfrischung)
0001110100001111 ? - Hmmm. Irgendwo hab ich diese Bitfolge doch schon mal
gesehen ... - Richtig, was stand doch gleich in der Norm, "Bei fehlerfreier
Uebertragung wird als Rest die Bitfolge 0001110100001111 erwartet". Also
waere jetzt auch dieser Punkt der Norm geklaert. Beachten muss man dabei,
dass im Gegensatz zum Sender dieser Rest nicht invertiert ist. Wozu auch,
wenn ich eh auf eine Konstante hin abtesten muss. Also, wenn ich den
Blockinhalt einschliesslich FCS beim Empfang bis auf Invertieren am Ende
genauso behandle wie den Blockinhalt allein beim Senden, dann muss ich, wenn
die Uebertragung ohne Fehler ablief, den "CRC" F0B8 hex (= Darstellung MSB
links, bei Rechnung kam ja LSB links heraus) erhalten.
(Fortsetzung folgt) (hoffentlich)
NORD>