Hallo Freunde,
Bei folgender CRC Geschichte zerbreche ich mit den Kopf. Denn ich
bekomme als Ergebnis nicht das raus was soll. Ich habe mal folgende
Werte:
Nutzdaten: 0xC018A
CRC Polynom: 0x385 (10 Bit)
Startwert: 0x1A
Als Rest soll am Ende rauskommen: 0x5FB (11 Bit)
Habe ich surch eine Rechenroutine bestätigt.
Leider bekomme ich es per Hand nicht so richtig hin. Ich denke ich
machen immer Fehler mit dem Startwert.
Ich würde so anfangen:
0xC018A plus (10-1) Nullen anhängen, welche mit dem Startwert addiert
werden.
Dann durch 0x385 teilen:
11000000000110001010000011010
1110000101
----------
Wenn ich das so durchrechne komme ich nicht auf 0x5FB. Kann mir da
jemand den entscheidnen Hinweis geben?
Danke schonmal.
Ich möchte nicht viel Lerm machen, aber auf:
http://www.zorc.breitbandkatze.de/crc.html
gibt ein "online" Rechner, und mit deinen Data, die CRC-Wert betrug:
0x1C7
Weiss es nicht wie gültig es ist :-\
>Nutzdaten: 0xC018A>CRC Polynom: 0x385 (10 Bit)>Startwert: 0x1A>Als Rest soll am Ende rauskommen: 0x5FB (11 Bit)
Wenn ich durch ein Polynom teile, das 10 Bit hat, kommt
etwas mit 9 Bit als Rest raus. Daher: 0x5FB ist garantiert
falsch.
>Habe ich surch eine Rechenroutine bestätigt.
Tja, jetzt kommt noch die Fehlersuche in der Software dazu ;-)
Nutzdaten: 0xC018A
CRC Polynom: 0x385 (10 Bit)
Startwert: 0x1A
11000000000110001010ooooooooo
1110000101
1000010101
1110000101
1100100001
1110000101
1010010000
1110000101
1000101010
1110000101
1101011111
1110000101
1101101001
1110000101
111011000o
1110000101
110101oooo
1110000101
11010101oo
1110000101
11010001oo
1110000101
011000001
0.61h
Probe:
11000000000110001010011000001
1110000101
1000010101
1110000101
1100100001
1110000101
1010010000
1110000101
1000101010
1110000101
1101011111
1110000101
1101101001
1110000101
1110110000
1110000101
1101011100
1110000101
1101100100
1110000101
1110000101
1110000101
----------
0 Yippie!
-Hans
Hi,
ich wundere mich nur, dass die Division bei der Überprüfung nicht exakt
dort mit 9 Nullen Endet, wo auch der zu Teilende Rest zu Ende ist
(in diesem Fall 010010110). Denn es steht ja nicht immer eine 0 am
Ende, oder etwa doch? Und wenn man eine 1 herunterziehen würde, könnte
dass ja bei der Überprüfung nie Null ergeben. Hmmm, so ganz habe ich
das "System als Ganzes" wohl noch nicht verstanden...
wenn eine 0 am Ende steht dann endet die Division eins vorher,
steht aber eine 1 am Ende dann läßt sich halt noch mal dividieren (falls
kein Fehler in der Übertragung war)
>ich wundere mich nur, dass die Division bei der Überprüfung nicht exakt>dort mit 9 Nullen Endet, wo auch der zu Teilende Rest zu Ende ist>(in diesem Fall 010010110).
Die Methode funtioniert genau wie das schriftliche Dividieren,
der einzige Unterschied ist, dass anstatt der Operationen
+/-,(*) ein EXOR (ein EXOR ist "mit sich selbst invers", daher ersetzt
es + und -) und anstatt einer Multiplikation(*) das AND (wobei das
mit 0/1 auf dasselbe rauskommt:-) steht. Beim schriftlichen Dividieren
wuerde man auch frueher aufhoeren, einfach stumpfsinning den bekannten
Divisionsschulalgorithmus mit den veraenderten Operationen anwenden....
>Hmmm, so ganz habe ich>das "System als Ganzes" wohl noch nicht verstanden...
Wenns hilft ggf. auch mal rechts (wie gewohnt) das Divisionsergebnis
mitnotieren! Da gibt es nichts zu "verstehen", man muss nur die
veraenderten Operationen akzeptieren ;-)
-Hans
Hi,
ok, danke, soweit ist das jetzt klar.
Wenn ich mich für einen Startwert entscheide, muss ich ihn doch bei
jedem Datenpaket senden, egal ob ich führende Nullen am Anfang habe,
oder? Denn wenn die Nutzdaten die Paketgröße überschreiten, muss der
Empfänger ja wissen, wo in den Paketen die Nutzdaten beginnen...
>Wenn ich mich für einen Startwert entscheide, muss ich ihn doch bei>jedem Datenpaket senden, egal ob ich führende Nullen am Anfang habe,
Nein, das ist Konvention, dass die CRCs mit einem Rest initialisiert
sind (quasi von einer fiktiven Uebertragung).
>oder? Denn wenn die Nutzdaten die Paketgröße überschreiten, muss der>Empfänger ja wissen, wo in den Paketen die Nutzdaten beginnen...
Wir machen es mal nicht binaer und nicht im (1,0,EXOR/AND)-Koerper...
Nehmen wir an, ich moechte 47114711 (mit dem "normalen" vorangehenden
Startwert 0 (den ich nicht hinschreibe)) uebertragen. Ich teile
durch 111. Das Ergebnis 424456 ist vollkommen uninteressant,
mich interessiert nur der Rest 95.
47114711 / 111 = 424456
444
271
222
->49
weiter:
494
444
507
444
631
555
761
666
Rest 95
OK? Einfach.
Jetzt tue ich so, dass ich bei all meinen Uebertragungen 4711
vorher fiktiv uebertragen habe. Dann starte ich mit dem
Restwert 49 ("Startwert", s.o. bei "->"). Den uebertrage ich NICHT,
weil sowohl Sender wie auch Empfaenger so tun als waere 4711 (immer)
vorher uebertragen worden und daher muss man mit dem
Startwert 49 initialisieren. Durch die Resteuebertragung steige
ich mitten in der Division ein (das unten ist eine Fast-Replik
ab "->" von oben! Nachsehen!) Remember: mich interessiert nur der Rest!
|| <-Startwert, (der normale Startwert=0)
494711 / 111 = irgendwas
444
507
444
631
555
761
666
Rest 95
Ich uebertrage also: 4711 Rest 95 ("CRC").
Der Empfaenger macht denselben Test. (Das das mit dem Restevergleich
so schoen im (1,0,exor,and)-Koerper funktioniert durch Einbeziehung
der CRC geht und Vergleich auf 0, ist eine "schmutzige" Abkuerzung...)
-Hans
@ Hans Hein
Zitat:
"(Das das mit dem Restevergleich so schoen im (1,0,exor,and)-Koerper
funktioniert durch Einbeziehung der CRC geht und Vergleich auf 0, ist
eine "schmutzige" Abkuerzung...)"
Was ist daran "schmutzig"? Genau DAS ist das Wesen einer
Polynomdivision, auf der die zyklische Redundanzprüfung (CRC) nunmal
basiert.
Gruß,
subitus
subitus wrote:
> @ Martin Metzler> @ Hans Hein
Beide sind nicht angemeldet, können also die Email-Benachrichtigung
nicht nutzen. Glaubst du ernsthaft, die schauen nach fast 2 Jahren noch
hier nach, ob es neue Beiträge gibt?
>Beide sind nicht angemeldet, können also die Email-Benachrichtigung>nicht nutzen. Glaubst du ernsthaft, die schauen nach fast 2 Jahren noch>hier nach, ob es neue Beiträge gibt?
@sternst:
Manche Gaeste fanden das Forum so gut, dass sie sich angemeldet haben
;-)
.... und durch Zufall lesen sie auch Threads, bei denen die
Emailbenachrichtigung noch nicht aktiv war.
@subitus:
Manchmal verwendet man Anfuehrungszeichen fuer Zitate wie dieses hier:
"Anführungszeichen können außerdem verwendet werden, um Wörter,
Wortgruppen und Teile eines Textes oder Wortes hervorzuheben,
zu denen man Stellung nehmen möchte, über die man eine Aussage
machen will oder von deren Verwendung man sich – etwa ironisch
oder durch die Unterlegung eines anderen Sinns – distanzieren
möchte."
Zitat aus Wikipedia zu "Anführungszeichen" :-)
Um "das Wesen einer Polynomdivision" (hmmmmm) im Hinblick auf die
"schmutzige" Bemerkung zu erlaeutern:
Die mathematische Sichtweise und die Implementierung differieren!
Aus der Implentierungssicht empfinde ich das als "schmutzig",
aber ueber geschmackliche Fragen lohnt es nur bedingt, einen
Diskurs anzufangen.....
Der Koenigsweg waere sicher eine Myriade von mathematischen Formalia
gewesen... aber dann haette auch eine Referenz auf ein Standardwerk
in RTFM-Manier gelangt (und vermutlich nicht "geholfen").
-Hans Hein
@Hans Hein
(oder besser Hänschen Klein)?
Jedenfalls fühlt sich da ein Oberlehrer auf den Schlips getreten?
Vielleicht üben wir uns doch erst einmal in der deutschen Orthografie,
bevor wir an Andernen herumnörgeln? Ich empfinde dies als "primitiv".
--
Die mathematische Sichtweise gibt die Implementierung vor - was
schließlich von Hardware-Kodierern genutzt wird. Natürlich gibt es
Variationen, die "sauberer" sind als Andere.
Gruß,
subitus
Ah, ich hab das oberste Bit immer weggelassen, also mit 011 als Polynom
gerechnet.
Aber bei der deiner Berechnung scheint doch jetzt der Initialwert des
Schieberegisters (111) nicht vorzukommen, oder habe ich da was
übersehen?
Danke.
>Aber bei der deiner Berechnung scheint doch jetzt der Initialwert des>Schieberegisters (111) nicht vorzukommen, oder habe ich da was>übersehen?
Da ist der Text IMHO widerspruechlich:
>> with a binary CRC initialization value 111
!=
>> extends the data bits by three zeros (MSB)
Steht dazu mehr im Text?
Der Anfangswert ist der Rest einer vorangegangen
Polynomdivision. Nun gibt es CRCs, welche einen
invertierten Schlusswert erfordern. Pragmatisch macht
man das in der CRC Routine oft so:
CRC8B: invertiere den CRC Wert
rechne "normal" die 8 Bit durch
invertiere wieder und speichere den Wert.
return
Damit ist keine Finalinversion notwenig.
Das waere die einzige logische Modell fuer den
dann nunmehr "nicht mehr widerspruechlichen" Text,
denn der Anfangswert ist 111, wird invertiert 000,
damit ist 000 der Anfangswert in der Polynomdivision.
Analog wie ich fuer die Zahl "42" haette "000042"
schreiben koennen, koennte ich veranschaulichend
fuer den (invertierten) Startwert notieren:
000 0011010010110101 / 1011 (Space wegdenken)
... (dieselbe Rechnung)
Allerdings waere dann am Schluss 100 invertiert die
richtige Loesung gewesen :-\
VG,
Hans
PS: Nett waere eine Zitatangabe des Scans...
Wenn man sich sklavisch an den Text haelt und das zu
uebertragende Datenwort mit unnoetigen 3 MSB Bits
aufmuellt, erhaelt man folgendes:
0xAD2C = 1010 1101 0010 1100
plus 3xMSB Nullen (WOZU???):
000 1010 1101 0010 1100
Uebertragung LSB first (siehe 3.2 data link layer)
(reverse vorangeganges Bitpattern):
0011 0100 1011 0101 000
Startwert CRC: 111
111 0011 0100 1011 0101 000
1110011010010110101000 / 1011
1011
----
1010
1011
----
1110
1011
----
1011
1011
----
0001011
1011
----
001010
1011
----
100
Alles ohne Gewaehr!!! Kommst Du an weitere Testvektoren?
(das Ergebnis koennte ein 1:8 Zufall sein ;-)
Vielleicht kann man bei psi5 nachfragen, was die sich
bzgl der 000-Auffuellung gedacht haben (falls dem so ist)!?!
VG,
Hans
Hans Hein schrieb:> Alles ohne Gewaehr!!! Kommst Du an weitere Testvektoren?> (das Ergebnis koennte ein 1:8 Zufall sein ;-)
Mit der Methode kommen jetzt bei mir die richtigen Ergebnisse für die
Testvektoren von Freescale raus.
Danke
Noch ein paar Gedanken zu dem "drei virtuellen
Nullen Mysterium".... denn wenn Bosch Ingenieure
die Finger im Spiel haben, ist es meist gut
durchdacht :-)
Die CRC3 kann ich als Abbildung mit "^" := EXOR
und den drei CRC-Registern (a,b,c) mit a=MSB, c=LSB
und i das Inputbit wie folgt darstellen:
( a , b , c ) -> (b, a^c , i^a)
Rechnet man nun die drei virtuellen Nullen durch,
folgt:
CRC ohne die virtuellen Nullen: (a,b,c)
(1) i=0 ( a , b , c ) -> ( b, a^c , a )
--
(2) i=0 ( b , a^c, a ) -> ( a^c, a^b, b )
--
(3) i=0 ( a^c, a^b, b) -> ( a^b, a^b^c, a^c)
--
CRC (mit den drei virtuellen Nullen) ist also
aus dem CRC-Ursprungswert a,b,c:
( a^b, a^b^c, a^c)
berechenbar.
Rechnet man das Ganze rueckwaerts mit den
Startwerten (x,y,z) (also der CRC x,y,z mit den
virtuellen Nullen), kommt man auf
(I) ( x, y, z ) -> ( x^y^z, y^z, x^y )
("virtuelle Nullen rausrechnen")
Folglich hat man keinen "rechnerischen Gewinn"
aus den drei virtuellen Nullen, da die CRCs
dieselbe Information tragen und jeweils ineinander
ueberfuehrbar sind. Gluecklicherweise hat man
auch kein weiteres Risiko, denn die Nullen werden
ja nicht tatsaechlich uebertragen.
Wenn man nun die Hypothese verfolgt, man wolle
den Serializer fuer die Uebertragung sparen,
findet man tatsaechlich die 3 CRC
Stellen (s.u.:unterstrichen), man haette aber
dann die Uebertragungsreihenfolge mit
( a^c, a^b, a^b^c) festlegen muessen.
Das waere nett gewesen.
Ferner haette man das "billiger" auch ohne
die virtuellen Nullen haben koennen (siehe
(1)(2)(3), jeweils letztes Argument: c,a,b)
Wenn man mit virtuellen "0" weitertaktet gibt es:
(4) i=0 ( a^b, a^b^c, a^c) -> (a^b^c, b^c, a^b)
---
(5) i=0 (a^b^c, b^c, a^b) -> (b^c, c, a^b^c)
---
(6) i=0 (b^c, c, a^b^c) -> ( c, a, b^c)
-----
(7) i=0 ( c, a, b^c) -> (a, b, c)
Wie man in Schritt (4) sieht, kann man das
Rueckrechnen (I) in einem CRC Schritt erledigen,
d.h. bei der (De-)Serialisierung im Empfaenger
laeuft die CRC Berechnung mit den tatsaechlich
uebertragenen Bits mit und anstatt die virtuellen
Bits reinzurechnen, kann man den um eine mit
einer vitrtuellen Null uebertragenen CRC Wert den
urspruenglichen CRC-Wert a,b,c berechnen und
mit dem (ggf. taktsynchronen) CRC a,b,c vergleichen.
Ob die kompliziertere HW-Steuerlogik diese
"Einsparung" rechtfertigt, waere aber im konkreten
Fall zu pruefen ;-)
VG,
Hans
Hallo Leute,
auch ich habe ein Problem mit der händischen Berechnung einer Checksum.
Parameter:
CRC16 (CCITT)
Polynom: 0x1021
Startwert: 0xFFFF
LSB first
Ich muss Paket mit den Befehlen "0x00 0x0800 0x0706" und der Checksum (2
Byte) verschicken.
Laut der oben verlinkten "Breitbandkatze" beträgt die Checksum 0x62EC im
Modus CRC-CCITT bei einer Eingabe von %00%00%08%06%07. (LSB first!)
"0x00 0x00 0x08 0x06 0x07 0xEC 0x62" akzeptiert mein Empfänger auch als
gültiges bzw. korrekt übertragenes Paket.
Nun versuche ich, händisch auf die 0x62EC zu kommen, was mir nach zig
(=5) Anläufen nicht gelingt.
So habe ich begonnen:
Startwert-Nutzdaten-angehängteNullen
F F F F - 0 0 0 0 0 8 0 6 0 7
1111.1111.1111.1111-0000.0000.0000.0000.0000.1000.0000.0110.0000.0111.
durch das Polynom:
1 0 2 1
1.0000.0010.0001 (1. Versuch, 12 Nullen angehängt)
1.0001.0000.0010.0001 (2. Versuch, 16 Nullen angehängt)
Beide Male kam das falsche Ergebnis raus.
__________________
Beim dritten Versuch habe ich die einzelnen Bytes gedreht.
F F F F - 0 0 0 0 0 8* 0 6* 0 7*
1111.1111.1111.1111-0000.0000.0000.0000.0000.0001.0000.0110.0000.1110.
Durch das Polynom:
1 0 2 1
1.0001.0000.0010.0001 (3. Versuch)
Wieder nicht das richtige Ergebnis.
__________________
Beim vierten Versuch habe ich die kompletten Nutzdaten gedreht:
F F F F - 7* 0 6* 0 8* 0 0 0 0 0
1111.1111.1111.1111-1110.0000.0110.0000.0001.0000.0000.0000.0000.0000.
Durch das Polynom:
1 0 2 1
1.0001.0000.0010.0001
Erneut falsch.
__________________
Beim fünften Versuch habe ich es so gemacht:
F F F F - 7 0 6 0 8 0 0 0 0 0
1111.1111.1111.1111-0111.0000.0110.0000.1000.0000.0000.0000.0000.0000.
Durch das Polynom:
1 0 2 1
1.0001.0000.0010.0001
Wieder nix.
__________________
Wo mache ich den Fehler?
Dass es nur eine richtige Variante geben kann ist mir klar.
Aber war sie schon dabei und habe ich mich evtl. bloß verrechnet?
Ich bin für jede Antwort dankbar und sei es nur ein kleiner Hinweis!
Mit freundlichem Gruß,
Nils
