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.
Angehängte Dateien:
-
crc.PNG
11 KB
habe meine Rechnung noch mal sauber in Excel gemacht. Ich muss den CRC unbedingt per Hand bringen. Irgendwas läuft dort falsch!?
du meinst nochmal folgende Operation? 1101011110 1110000101 ---------- 11011011 Das ist aber dann auch nicht das richtige Ergebnis. :-(
die erste blaue Null müsste rot sein, Fehler von mir Leider ändert das nichts.... Ich brauch mal ne kleine Hilfe...
habe ich zumindest nicht falsch gerechnet?? Das wär ja mal schon viel Wert.
so im Überblick hab ich keinen Rechenfehler gefunden, kannst ja mal die Gegenprobe machen und schauen ob dann 0 raus kommt
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 :-\
ja ich kenne den, habe ich schon x-mal probiert. Der funzt irgendwie nicht richtig.
>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
Oh, yes!
Der Startwert steht am Anfang, der CRC hat i.d.R. ein "Problem" bei
Ue-Fehler bei fuehrenden Nullen (Der Mathematiker interpretierts
als vorangegangener Rest einer fiktiven Uebertragung):
Nutzdaten: 0xC018A
CRC Polynom: 0x385 (10 Bit)
Startwert: 0x1A
1--A-
1101011000000000110001010ooooooooo
1110000101
1101110100
1110000101
1111000100
1110000101
1000001001
1110000101
1100011001
1110000101
1001110000
1110000101
1111101010
1110000101
1101111101
1110000101
111110000o
1110000101
1100101ooo
1110000101
10101101oo
1110000101
100110001o
1110000101
1111001110
1110000101
01001011o
0.96h
1101011000000000110001010010010110
1110000101
1101110100
1110000101
1111000100
1110000101
1000001001
1110000101
1100011001
1110000101
1001110000
1110000101
1111101010
1110000101
1101111101
1110000101
1111100000
1110000101
1100101100
1110000101
1010100110
1110000101
1001000111
1110000101
1110000101
1110000101
00000000000 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
@ Martin Metzler Der Onlinerechner http://www.zorc.breitbandkatze.de/crc.html funktionier tadellos ;=)
@ 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
Angehängte Dateien:
-
psi5.jpg
86 KB
Kann das jemand von Hand rechnen? Ich komme ums Verrecken nicht auf die 0x4. Danke.
0011010010110101 / 1011
1011
----
1100
1011
----
1110
1011
----
1011
1011
----
0000001101
1011
----
1100
1011
----
1111
1011
----
100 (daDA!)
ja, die "Hardware" ist gemeinerweise anders dargestellt.
VG,
Hans
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...
Hans Hein schrieb: > PS: Nett waere eine Zitatangabe des Scans... Die komplette Spezifikation findest du hier: http://www.psi5.org/en/en/psi5/home/index.aspx
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
Angehängte Dateien:
-
freescale_psi5_crc.jpg
55 KB
Danke schonmal für die Mühe, die du dir machst. Habe bei Freescale in der Spec eines PSI5 Sensors eine Tabelle gefunden (siehe Anhang). Originallink: http://cache.freescale.com/files/sensors/doc/data_sheet/MMA52xxWR2.pdf
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
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.