Hilfe CRC zu verstehen

Die Wikipedia liefert hierzu unter:

http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung

einiges an Info.

Das habe ich natürlich auch gelesen. Nur entweder bin ich nicht in der 
Lage die richtige Antwort aus dem dortigen Text herrauszuinterpretieren 
oder es steht doch schlicht nicht beschrieben.
Das dass nette Generatorpolynom ein zuvor festgelegter Wert ist wusste 
ich schon :/

Hallo,
der Deutsche Text in wikipedia überspringt meiner Meinung nach auch 
etwas wesentliches in seinem ersten Beispiel - ich hab' mal unter 
"Diskussion" einen entsprechenden Kommentar für den Autor gemacht.
Sieh' Dir besser auch mal die Englische Version in Wikipedia an.

Die Beschreibung unter Verwendung des Begriffes "Generator-Polynom" ist 
auch eher "abschreckend" als erhellend. Erinnert mich an meinen 
Mathe-Unterricht in der Schule, wo ich immer nicht verstanden habe, was 
"hinreichende" und was "ausreichende" Bedingungen sind und wo da der 
Unterschied ist :-)

Ich versuch's mal:

Wo kommen wir zu diesen "Polynomen"?

Das in einem Computer nun mal gebräuchliche "Zahlen-Format" sind 
Binärwerte - dargestellt als Folgen von Nullen und Einsen.
Z.B. nehmen wir mal einen 8-stellige Wert wie:

   10101010 (binär) = #170 (decimal)

Bei der Binär-Darstellung kann jede Ziffer nur einen der zwei Werte #0 
oder #1 annehmen (daher binär).
Das man dadurch jeden beliebigen Zahlenwert darstellen kann, liegt 
daran, daß man man jeder #0 oder #1 in einer binären Zahlenfolge eine 
unterschiedliche Wertigkeit zuordnet - abhängig von ihrer Position in 
der Binären Zahlenfolge.

Das kennst Du wahrscheinlich schon - aber der Vollständigkeit halber 
hier noch mal dargestellt, indem ich die oben stehende Binärzahl 
vertikal aufschreibe

Ziffer (vorderste zuerst)   | Wert       | gesetzt j/n?
=================================================
1                           | 128  (2^7) | 128 (j)
0                           |  64  (2^6) |   0 (n)
1                           |  32  (2^5) |  32 (j)
0                           |  16  (2^4) |   0 (n)
1                           |   8  (2^3) |   8 (j)
0                           |   4  (2^2) |   0 (n)
1                           |   2  (2^1) |   2 (j)
0                           |   1  (2^0) |   0 (n)
=================================================
Summe                                      170

Die Binäzahl 10101010 kann man also aus Ihren einzelnen bewertetet 
Ziffern auch aufschreiben als:

  1 * 2^7
+ 0 * 2^6
+ 1 * 2^5
+ 0 * 2^4
+ 1 * 2^3
+ 0 * 2^2
+ 1 * 2^1
+ 0 * 2^0

So kommen die Polynome ins Spiel.

Was die CRC Berechnung letztendlich macht, ist, einen vorhandenen Strom 
von Bits - quasi als eine riesige Ganze Zahl betrachtet - durch eine 
andere Bitfolge (andere Ganze Zahl - dem Generatorpolynom) zu teilen.
Bei solch einer Division kommt am Ende ein Rest heraus (der auch #0 sein 
kann).
Dieser Rest wird dann dem Original-Datenstrom am Ende angehängt.
Dann wird der dieser erweiterte Datenstrom z.B. irgendwohin übertragen.
Der Empfänger wiederholt dann die Prozedur - angewendet auf diesen 
erweiterten Datenstrom. Zahlenmäßig ergibt sich dann durch das 
Binärformat selbst, daß bei der erneuten Division mit dem selben 
"Generatorpolynom" (hier müßte es eigentlich "Verfikationspolynom" 
heißen) am Ende als Rest #0 herauskommen MUSS.
Wenn dem nicht so sein sollte, ist irgendwas an dem Datenstrom nicht so 
beim Empfänger angekommen, wie es vom Sender versandt wurde.

Das man diese dafür diese "kompliziert/aufwendig aussehende" Division 
entlang des Bitstroms macht, liegt - vereinfacht formuliert - daran, 
dass man dadurch eine Streuung der Original-Daten macht, so das 
Mehrfach-Fehler nicht so einfach dazu führen, daß sie nicht erkannt 
werden (glaube ich zumindest - ist schon ein bißchen her, daß ich damit 
zu tun hatte).

Gruss,
Frank

Das man diese Polynome (d.h. Polynome über dem Körper Z2) iA nimmt,
liegt an ihrer einfachen Implementierung per AND, OR, XOR, NOT etc.
Der Umgang damit wird in jedem guten Grundlagenkurs gelehrt.

Deine Frage ist aber, warum diese Speziellen. Um das zu verstehen,
musst du statt E-Tech bzw. Informatik Mathematik studieren. Da lernst
du in Algebra/Zahlentheorie Polynome in Verbindung mit Ringen und
Körpern, Begriffe wie Teilbarkeit, Irreduzibilität etc. Durch die
Division im CRC-Algo werden die Eingabebitvektoren in Klassen
eingeteilt, und je nach Teiler (CRC-Polynom) haben diese Klassen
bestimmte Eigenschaften, z.B. bei einem Ausgaberesultat = 0 sind
z.B. keine 1-Bit-Fehler vorhanden etc. Aber um das grundlegend
zu verstehen und damit geeignete Polynome zu finden sind mind. 2-3
Semestervorlesungen in dem Bereich erforderlich. betrachte also
diese Polynome einfach abstrakt als "gute" Polynome, die ihre
Aufgabe erfüllen.

Falk Brunner schrieb:
> Ich hab damals den Klassiker im Internet gefunden, tagelang gelesen und
> probiert, am Ende mehrere CRC-Funktionen in AVR-Assembler programmiert
> (Seriell, Nibble und Byteverarbeitung). Und es hat gepasst!
>
> http://www.ross.net/crc/download/crc_v3.txt

ich habe bis heute keine bessere Erklaerung/Beschreibung (auch das 
"warum") gefunden. Lohnt sich wirklich, sich das Papier mehrmals 
vorzunehmen und vor allem die Beispiele mal selber auf'm Blatt Papier 
nachzuvollziehen.

>
> Auch wenn ich die echte Mathematik dahinter bis heute nicht wirklich zu
> 100% verstanden habe, kann ich CRC anwenden und verstehen. Das sollte
> auch dein Ziel sein. Mathematiker wirst du nicht werden.

Full ACK

Moin,

ich probier auch noch 'einen':

- LFSR (Linear Feedback Shift Register) anschauen, nachprogrammieren
- Pseudozufälligkeit verstehen (Warum pseudo, Wiederholungs-Intervall)
- Wie kommt man davon zur Idee der "Checksumme"
- Warum hilft die Pseudozufälligkeit "besser" bei der Detektion von 
gekippten Bits (also den Fehlern) im Datenstrom?

Das kann man meiner Meinung nach bei einer Präsentation für Laien oder 
Mitschüler auch gut&gerne empirisch und mit viel Grafik erschlagen. Oder 
ASCII-Art :-)


Grüsse,

- Strubi

Oh man, das hat mir alles schon wirklich weiter geholfen.

@Frank
Danke für die Mühe und den langen Text. Du hast das wirklich fantastisch 
beschrieben, so kann selbst ein Minusmathematiker wie ich damit was 
anfangen.

@Falk Brunner
Auch wenn meine Frage in deinen Ohren eventuell lächerlich klang und du 
mich mit deiner Antwort etwas zum narren hälst hast du mir trozdem sehr 
geholfen :)


Eine kleine Frage habe ich da aber noch.
Das Generatorpolynom ist ja beliebig, also es gibt Qualitätsunterschiede 
zwischen dem gewählten und einem anderen.
So wie ich das jetzt verstanden habe gibt es keine Regel dafür das dass 
Generatorpolynom bei einem wachsenden Datenwort im Verhältnis mitwachsen 
muss.

CRC ist "nur" eine Art von Checksum Verfahren (eines unter vielen 
anderen).
Als solches kann nur die Sicherheit dafür, daß Übertragungsfehler 
erkannt werden können, erhöhen. Es kann aber generell nicht ALLE 
Übertragungsfehler erkennen. Das ergibt sich allein schon dadurch, daß 
diese Prüfsumme eine begrenzte Länge hat - in der Regel eine wesentlich 
kleinere Länge als die Nutzdaten, die Du übertragen willst. Daraus 
ergibt sich rein logisch schon automatisch, daß eine Reihe von 
verschiedenen Nutzdaten (Möglichkeiten) bei der CRC Berechnung dieselben 
CRC Prüfsumme ergeben MUSS. Wenn Du jetzt einen Übertagungsfehler hast, 
der Deine original Nutzdaten X zufäligerweise in ein Nutzdaten Image Y 
verfälscht, das dummerweise dieselbe CRC Prüfsumme ergibt, dann wirst 
der Empfänger diesen Wechsel von Original X nach Image Y nicht erkennen 
können. Er "denkt" Du hast ihm tatsächlich Daten Y geschickt.
Die verschiedenen Verfahren versuchen nur die Wahrscheinlichkeit für 
solche Fälle zu vermindern. Interessanterweise sind da nicht nur die 
Generator-Polynome (und dabei auch deren Länge) an sich dafür 
heranzuziehen, sondern auch die Art der Daten, die man da übertragen 
möchte. Je nachdem, wie die Original-Daten strukturiert und codiert 
sind, kann das eine Verfahren besser sein, als das andere.

BTW. Schau' die mal den aktuellen Film "The Imitation Game" an.
Der weckt vielleicht das Interesse, da mehr herausfinden zu wollen und 
sich vielleicht sogar ein bißchen mehr mit dem mathematischen Grundlagen 
auseinanderzusetzen.

Gruss,
Frank

Bzgl. CRC sollte eigentlich auch das Wort Polynomdivision fallen - das 
habe ich hier bisher vermisst.

Frank schrieb:
> CRC ist "nur" eine Art von Checksum Verfahren

Da kann ich nicht zu 100% zustimmen. Ein CRC ist nicht nur eine 
"Checksum" - diese ist viel mehr. Mit einem CRC ist es nicht nur möglich 
Bitfehler zu detektieren, es ist auch möglich damit Bitfehler zu 
korrigieren. Wieviele Bits pro Paket und welche Art von Bitfehler es 
sein dürfen (zufällige oder burst) ist abhänging von Anzahl der Bits des 
CRC, der gesamten Paketgröße und des Generatorpolynoms selbst. Und genau 
das unterscheidet den CRC von einer Checksum.

Leider muss man sich, wenn man diese Thematik verstehen will, wirklich 
länger hinsetzen (siehe meine Vorredner bzgl. der Mathematikvorlesung).

Ist es nicht wie mit der Hammingdistanz? Bloss, dass ich die Redundanz 
nachtraeglich einfuege?
D.h. wenn ich weiss und voraussetze, dass nur eine bestimmte Menge von 
Fehlern passiert ist, dann kann ich automatisch korrigieren. Wenn ich 
aber mehr Fehler habe, dann wird meine auto-Korrektur zu einem anderen 
Ergebnis fuehren, als die Originaldaten. Oder?

Als einfaches Beispiel für "Fehlererkennungsverfahren" und
"Fehlerkorrekturverfahren" kann man sich z.B. folgendes
Szenario betrachten:

Es werden nur gerade Zahlen übertragen. Eine Division durch
"Zwei" teilt ein in "Richtig" und "Falsch" (2 Klassen). Hier
kann aber nicht korrigiert werden, jedenfalls nicht ohne
zusätzliche Informationen.
Nehme ich aber zusätzlich an, dass ein Fehler nur aufgrund
von Abrundung stattfindet, dann kann ich sogar korrigieren.

Bei der Polynomdivision ist es ähnlich. Die Mathematik,
speziell Algebra, liefert hier ein ganzes Universum von
Aussagen über diese Klassen bzw. deren Möglichkeiten für
die Zielanwendung.

Dagegen ist die "CheckSum" basierend auf der Addition
wesentlich fehleranfälliger, ABER einfachst zu implementieren.
Um um dieses ABER geht's häufig.

Falk Brunner schrieb:
> @ Frank Bergemann (fbergemann)
>
>>Eine Checksum (z.B. Parity bit) gehört zu dem
>>"Fehlererkennungsverfahren".
>>CRC ist ein "Fehlerkorrekturverfahren".
>
> Na dann zeig mit mal EIN Beispiel, wo NUR mit einer CRC ein Fehler
> KORRIGIERT wird!

Ich habe auch so ein bissle den Eindruck, dass hier CRC (Cyclic 
Redundancy Checksum) mit ECC (Error Correction Code) oder aehnlichem 
durcheinander geworfen wird...
CRC wird meist nur zum 'checken' benutzt, wohingegen ECC bzw. SECDED 
(Single-Error-Correction-Double-Error-Detection) weit darueber hinaus 
geht (bis hin zu RAID fuer Festplatten und RAIM fuer SDRAM), natuerlich 
mit entsprechendem HW-Aufwand

berndl schrieb:
> Falk Brunner schrieb:
>> @ Frank Bergemann (fbergemann)
>>
>>>Eine Checksum (z.B. Parity bit) gehört zu dem
>>>"Fehlererkennungsverfahren".
>>>CRC ist ein "Fehlerkorrekturverfahren".
>>
>> Na dann zeig mit mal EIN Beispiel, wo NUR mit einer CRC ein Fehler
>> KORRIGIERT wird!
>
> Ich habe auch so ein bissle den Eindruck, dass hier CRC (Cyclic
> Redundancy Checksum) mit ECC (Error Correction Code) oder aehnlichem
> durcheinander geworfen wird...

Dem schliesse ich mich an, nur eine kleine Korrektur, es heisst Cyclic
Redundancy Check. Es ist keine Summe!

Der theoretische Hintergrund ist zwar der gleiche wie bei einigen 
Korrekturverfahren und stammt auch von den gleichen Forschern, aber es 
bleibt trotzdem nur ein Check.
Es geht bei CRC um die zuverlässige Erkennung von zufälligen 
Mehrfachfehlern und Fehlerbursts. Eine normale Prüfsumme leistet das 
nicht.

> CRC wird meist nur zum 'checken' benutzt, wohingegen ECC bzw. SECDED
> (Single-Error-Correction-Double-Error-Detection) weit darueber hinaus
> geht (bis hin zu RAID fuer Festplatten und RAIM fuer SDRAM), natuerlich
> mit entsprechendem HW-Aufwand

Wobei einfache Hammingcodes für ECC und SECDED relativ primitiv sind, 
und der Aufwand auch exponentiell wächst je mehr Bits man korrigieren 
möchte. Dafür ist aber der Korrekturprozess bei nur 1 oder 2 Bits sehr 
direkt und schnell. Wäre ja sonsts für RAMs unbrauchbar.

Bei aktuellen Nandflashes reichen 2 Bits nicht mehr, weswegen inzwischen 
auch BCH Codes verwendet werden. Damit sind wir dann wieder bei 
Polynomen wären.

Lattice User schrieb:
>  Damit sind wir dann wieder bei
> Polynomen wären.

Ach Mist, wie war das mit Korrekturlesen VOR dem Absenden? Das letzte 
"wären" bitt streichen.

Gibt es für solche Verfahren Standardimplementierungen, die man fertig 
verwenden können könnte?

danke

Reinhard S. schrieb:
> Gibt es für solche Verfahren Standardimplementierungen, die man fertig
> verwenden können könnte?
>

Für CRC kann man hier sich Verilog und VHDL code generieren lassen:
http://www.easics.com/webtools/crctool

>Kann ich mir angucken, aber erklärt was ein "Generator-Polynom" ist,
geschweigedenn wie man auf diesen kommt,

Im Prinzip sind das (meist sehr große) Primzahlen, mit denen die 
Nachricht beim Senden multipliziert wird (dadurch wird die Nachricht 
länger) und durch die beim Empfangen dividiert wird.
Beim Empfang interessiert nur der Rest der Division, denn der hat 0 zu 
sein, wenn kein Übertragungsfehler aufgetreten ist.

Wie bekannt sein dürfte, sind Multiplikationen und Divisionen Modulo 2 
sehr einfach durch Schiebeoperationen zu realisieren.
Für die komplizierteren Polynome wird das Schieberegister an bestimmten 
Stellen angezapft, und der Datenstrom wird mittels XOR mit dem Inhalt 
dieser Anzapfung(en) verknüpft und das ergibt dann den Input für das 
Schieberegister.
Immer wird auch die letzte Stelle, also der Ausgang, des 
Schieberegisters mitverwendet und durch diese Rückkopplung des Ausgangs 
auf den Eingang kommt das Wort "zyklisch" ins Spiel.
Der Aufbau und die Anzapfungen der Schieberegister zum Senden und zum 
Empfangen ist nahezu identisch.

Die Redundanz ergibt sich wegen des "Aufblähens" der Meldung durch die 
Multiplikation mit der Primzahl.
Wenn du die Einsen und Nullen der Meldung als eine vielstellige Zahl 
auffasst, so ist die Meldung einschliesslich CRC immer ein Vielfaches 
dieser Zahl.
Wenn ich z.B. Meldungen mit den Inhalten 1, 2, 3, 4, 5, ... mit der 
Primzahl 13 multipliziere, müssen am Empfänger die Zahlen 13, 26, 39, 
52, 65, ... ankommen, und wenn man am Empfänger diese Zahlen durch 13 
dividiert, bleibt als Rest 0.

Alle anderen Codeworte, z.B. 25, werden nvomm Empfänger als illegal 
erkannt, dennn ergeben bei der Modulo-13 Division einen Rest ungleich 0, 
und dann weiss man, das bei der Übertragung etwas schief gegangen ist.
Diese 13, um die sich hier gültige Codeworte unterscheiden, ist die so 
genannte Hamming-Distanz.

Bei der Paritätsprüfung (z.B. bei RS-232) ist die Hamming Distanz nur 1, 
weshalb man nur entdecken kann, ob ein Bit umgefallen ist. 
Mehrbit-Fehler könnten unentdeckt bleiben.
Da ist unsere Hamming Distanz 13 vom Beispiel schon besser,  aber sie 
benötigt eben auch mehr Bits für die Prüfsumme.

In der Tat gibt es kompliziertere Polynome, mit denen man nicht nur 
entdecken kann, OB ein Bitfehler aufgetreten ist, sondern man kann sogar 
berechnen, an welcher Stelle das passiert ist.
Das wäre dann ein Fehler korrigierender  Code, neudeutsch ECC, im 
Gegensatz zum oben erläuterten Fehler erkennenden Code EDC.

Im Prinzip gibt es viele Codes, die sich für solche Zwecke eignen.
Die hohe Kunst ist es solche auszuwählen, die für die in der Praxis zu 
erwartenden Störungen besonders geeignet sind.
Beim 64-Bit Speicherwort eines Computers reichen z.B. 8 zusätzliche 
Bits, also 72 Bit pro Speicherriegel, um alle 1-Bit Fehler korrigieren 
zu können, und alle der sehr seltenen 2-Bit Fehler erkennen zu können. 
Unter bestimmten Umständen kann man sogar 2 Bit Fehler korrigieren.

Bei einer CDROM z.B. sieht die Sache anders aus, denn dort treten die 
Fehler wahrscheinlich nicht unabhängig voneinander oder gar einzeln auf, 
sondern z.B. durch einen Kratzer werden ganze Gruppen von benachbarten 
Bits, so genannte Burst Errors, unleserlich.
Aus diesem Grund werden dort sehr viel längere CRC zur Fehlerkorrektur 
verwendet und  außerdem wird der Inhalt eines jeden Datensektors mit den 
benachbarten Sektoren verwoben.
Auf diese Weise soll es möglich sein, in eine CDROM ein 2mm Loch zu 
bohren, und trotzdem die Information fehlerfrei  auszulesen.


Falk B. schrieb:
> Na dann zeig mit mal EIN Beispiel, wo NUR mit einer CRC ein Fehler
> KORRIGIERT wird!

Im bereits angesprochenen Beispiel von Speicherfehlern in Rechnern macht 
man das.
Dass dort der CRC mit einem ganzen Sack voll XORs parallel erzeugt wird, 
tut nichts zur Sache.
Vielleicht findest du im Netz noch diese Applikationsschrift von TI.
Iiirc gab von AMD entsprechende Chips.
4 Jahre vorher musste ich mich mit CRCs auf die ganz harte Tour 
auseinandersetzen: Die Datenbits eines Floppy-Controllers waren im 
Layout falschrum angeschlossen, weil sie gemäß IBM-Notation 1,2,3,...8 
nummeriert waren und nicht 7..0.

dem waere nur noch ein schoenes Paper hinzu zu fuegen (der Klassiker):
http://www.zlib.net/crc_v3.txt

Schwere Kost, aber einfach mal die ersten Seiten durch exerzieren...