Diskussion:Zyklische Redundanzprüfung/Archiv

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Zyklische Redundanzprüfung/Archiv#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Zyklische_Redundanzpr%C3%BCfung/Archiv#Thema_1

Englische Abkürzung

Da sich offensichtlich noch keiner getraut hat, habe ich mal den Mehrheitsbeschluss von dieser Diskussionsseite umgesetzt und die deutsche Abkürzung durch die englische ersetzt. --83.135.133.111 12:42, 19. Dez 2005 (CET)

Meiner meinung nach sollte man die bezeichnung ZRP hier nicht einsetzen und ganz weglassen da niemand diese abkürzung verwendet sondern immer das englische CRC benützt wird.

Ich würde die englische Abkürzung ebenfalls präferieren. Zumal ich die deutsche Variante noch nirgends gesehen habe... MfG--80.139.233.196 19:24, 5. Mai 2005 (CEST)

Ich wäre auch dafür, sinnlose Germanismen wegzulassen. Erath 08:23, 8. Jun 2005 (CEST)

Beispiel

Hallo, ich finde hier fehlt ein Beispiel, und vielleicht könnt ja jemand, der es verstanden hat das Beispiel vervollständigen.

Beispiel zur Berechnung der CRC-32:

Also nehmen wir an, ich habe die Zeichenkette "VOGEL" , dann ist die ganz praktische Frage, welche CRC hat das Datenwort "Vogel"

das gibt als Ascii Werte folgendes :

    Dez.   Binär

V -> 086 -> 01010110 O -> 079 -> 01001111 G -> 071 -> 01000111 E -> 069 -> 01000101 L -> 076 -> 01001101

daraus ergibt sich

         0 1 2 3 4                                5 

         e e e e e                                e 
         t t t t t                                t 
         y y y y y                                y 
         B B B B B                                B 
   

Bit 7 > 0 0 0 0 0 Bit 6 > 1 1 1 1 1 Prüfsummenrechnung > Bit 5 > 0 0 0 0 0 Bit 4 > 1 0 0 0 0 Bit 3 > 0 1 0 0 1 Bit 2 > 1 1 1 1 1 Bit 1 > 1 1 1 0 0 Bit 0 > 0 1 1 1 1

Frage wie kann ich nun mit hilfe des Prüfpolynoms

CRC-32: x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x ^5+x^4+x^2+x+1

das Ergebnisbyte (5tes Byte Berechnen ?????)

vielleicht kann da ja jemand weitermachen, so das man es versteht. Welche Prüfsumme hat das Datenwort "Vogel" ? und wie kommt man da hin ? wie berechnet man dies ?

Das Ergebnis ist ein 32-Bit-Wert. CRCs werden bitweise berechnet, also kann man die Bytes von links nach rechts oder von rechts nach links in bits zerlegen. Im ersten Fall ist das Ergebnis von "VOGEL" 0xa75cb680, wie folgendes Programm (in Perl) zeigt:

   #!/usr/bin/perl
   $DATA[0]=ord('V');
   $DATA[1]=ord('O');
   $DATA[2]=ord('G');
   $DATA[3]=ord('E');
   $DATA[4]=ord('L');
   sub crc_calc
   {	for $i (0..7)
   	{	$bit=$w & (2**(7-$i));
   		$bit=1 if $bit;
   		$hbit=($CRC & 2**31) ? 1 : 0;
   		$CRC<<=1;
   		$CRC &= 0xFFFFFFFF;
   		if ($bit != $hbit) {
   			$CRC ^=$POLY;
   		}
   	}
   }
   $POLY=0x04c11db7; # CRC-32 Polynom
   $CRC=0; # always use 0 for polynom division, 0xFFFFFFFF for CRC-32
   for $w (@DATA) {
   	crc_calc;
   	printf "%x %x\n",$w,$CRC; # Invert for CRC-32 (not shown)
   }

Beachte aber, dass der Standard-CRC32 als Startwert 0xFFFFFFFF verwendet und das Ergebnis invertiert. VOGEL ergibt dann 0x1fb3f2e3.Hubi 13:30, 30. Sep 2005 (CEST)

Prüfsumme

Prüfsummen entstehen nicht nur technisch gesehen durch Addition. Grundsätzlich entstehen Summen bei einer Addition. So wie halt Produkte bei Multiplikation entstehen und Differenzen bei Division usw.

-) ;-) ;-)

Kleiner stilistischer Fehler

1. Unterschreib deine Beiträge bitte. Das geht mit --~~~~

2. Verzichte bitte auf Ironie und bloße Anspielungen und beschreibe stattdessen deutlich, was dein Anliegen ist.

3. Der Urvater der Prüfsumme ist das Paritätsbit. Dieses wird durch Addition in $\mathbb {Z} _{2}$ berechnet, es handelt sich also wirklich um eine Summe. Der Begriff Prüfsumme hat sich so sehr eingebürgert, dass es bei der komplexeren zyklischen Redundanzprüfung beibehalten wurde.--MKI 15:14, 2. Jun 2005 (CEST)

Hups, da hat sich wohl ein Versprecher eingeschlichen... Differenzen entstehen natürlich bei der Subtraktion und bei der Division entstehen Quotienten... --Sixot 14:36, 23. Mär 2006 (CET)

Verfahren

Hallo, ich denke das Verfahren ist missverständlich formuliert. Der Satz "Die Bitfolge der Coderepräsentation der Daten wird durch ein vorher festzulegendes Polynom (das ZRP-Polynom) mod 2 dividiert" hat für mich nämlich keinen Sinn. Was dividiere ich nun womit? Die Datenbitfolge modulo das CRC Polynom, oder was? Für mein mathematisches Verständnis ist hier ein Teiler zuviel. Entweder ich teile durch das CRC Polynom oder durch 2. Andererseits kann man das auch als Bitfolge % CRC Polynom % 2 verstehen.

Leider kann ich auch nicht sagen, wie das korrekt vor sich geht, daher bitte ich jemanden der das Verfahren kennt, das eindeutiger auszudrücken. Achso und auch für "CRC" statt "ZRP" -- Metal 16:50, 20. Jun 2005 (CEST)

Polynome Division Modulo 2 unterscheidet sich gegenüber der normalen Division darin, dass es keinen Übertrag gibt, es sich also eigentlich nru um eine XOR-operation handelt --nirONE

Beispiel

Ich habe das Beispiel ein wenig ergänzt. Ich hoffe ich habe bei der Rechnung keinen Fehler gemacht, wäre nett, wenn da noch mal jemand drüber gucken könnte. --Billen 00:31, 12. Aug 2005 (CEST)

Kategorie Theoretische Informatik

Ist "Theoretische Informatik" denn hier die richtige Einordnung? Wäre für ein so oft eingesetztes Verfahren nicht eher "Angewandte Informatik" oder "Praktische Informatik" besser? 23:46, 31. Okt 2005 (CET)

Theoretische sicher nicht. Stern 11:58, 11. Jan 2006 (CET)

Das ist es alles nicht, es fällt nämlich unter "Technische Informatik". --Sixot 14:36, 23. Mär 2006 (CET)

Beispiel für CRC32 verifiziert?

Ich weiß nicht, ob ich hier auf dem Schlauch stehe, oder wo sonst der Hund begraben liegt. Wenn ich den C-Code aus dem Beispiel übersetze und ausführe, komme ich zu einer anderen Prüfsumme, als andere Beispiele mit Lookup Table errechnen (10001100 ist ja das gespiegelte Bitmuster von ASCII '1'). Ausprobiert habe ich sowohl das genannte Bitmuster, als auch sein Spiegelbild.

Christoph -- Chrisgb 13:56, 1. Feb 2006 (CET)

Korrektes Beispiel in C

Wie schon beschrieben ist das C-Beispiel (vermutlich) nicht korrekt. Zusammen mit einem Kollegen habe ich nun ein Beispielprogramm implementiert, das die gleichen Prüfsummen, wie andere im Web erhältliche CRC32 Beispiele mit Lookup Table liefert:

   #include <string.h>
   #include <stdio.h>
   
   
   #define CRC32_INITIAL	0xFFFFFFFF
   #define CRC32_POLYNOMIAL	0xEDB88320
   #define CRC32_MSB		0x80000000
   #define CRC32_LSB		0x00000001
   #define GET_BIT_TO_LSB(b,i)	(unsigned long)((b & (1 << i)) >> i)
   
   unsigned long CRC32Add(unsigned long crc, unsigned char c)
   {
       int i;
       unsigned long C;
       
       C = c;
       for (i=0; i<8; i++)
       {
           if ((crc & CRC32_LSB) ^ GET_BIT_TO_LSB(C,i))
           {
               crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
               crc |= CRC32_MSB;
           }
           else
               crc = (crc >> 1);
       }
       
       return crc;
   }
   
   unsigned long CalculateCRC32(unsigned char *pucData, unsigned long ulLength)
   {
       unsigned long ulCount;
       unsigned long ulCRC;
       
       ulCRC = CRC32_INITIAL;
       for (ulCount = 0; ulCount < ulLength; ulCount++)
       {
           ulCRC = CRC32Add(ulCRC,pucData[ulCount]);
       }
       return (~ulCRC); /* invertiere Ergebnis */
   }
   
   int main(int argc, char* argv[])
   {
       unsigned long ulCRC;
       unsigned char aucBuffer[100];
       
       /* dieser String hat die Prüfsumme CBF43926 */
       strcpy((char*)aucBuffer,"123456789");
       ulCRC = CalculateCRC32(aucBuffer,9);
       
       printf("\"%s\" -> CRC-32: %lX\n",aucBuffer,ulCRC);
       
       return 0;
   }

Ich würde vorschlagen dieses Beispiel in den Artikel zu übernehmen. Allerdings sollte dann der Pseudocode auch entsprechend geändert werden.

-- Chrisgb 15:18, 1. Feb 2006 (CET)

Was wollt ihr denn? Euer Programm verwendet das "Polynom" 0xEDB88320 das die Bits von rechts nach links enthält, während man in westlicher Links-nach-rechts-Schreibweise doch besser 0x04C11DB7 verwendet, wie im Artikel erwähnt. Entsprechend liefert obenstehendes Programm bei Verwendung von "1" dann auch 83DCEFB7, während das im Artikel angegebene genau die Umkehrung EDF73BC1 liefert, wie es sein muss. Obenstehendes Programm ist viel zu lang, verdeutlicht nicht den bitweisen Charakter der CRC-Berechnung und hat leichte Kodierungsschwächen (C=c ?!). --Hubi 17:30, 1. Feb 2006 (CET)

Es sei noch eine kleine Anmerkung gestattet: Ethernet etwa berechnet die CRC32 so, dass einzelne Bytes mit dem LSB zuerst gesendet werden. Die CRC32 wird aber MSB zuerst gesendet. Ein (illegaler) Ethernetframe mit einer "1" hätte also tatsächlich die Bits 10001100 im Frame und danach die Prüfsumme des obenstehenden Programms. Der CRC-Algorithmus selbst liefert aber 83DCEFB7, daher ist dieses Programm genaugenommen als Beispiel für eine CRC-Berechnung nicht korrekt. Es liefert eine CRC32-Prüfsumme mit anschliessender Bitvertauschung. --Hubi 17:41, 1. Feb 2006 (CET)

Das C=c ist ein Relikt aus der Entwicklung des Codes, das zugegeben unnötig ist und weg sollte. Das Programm entspricht einem CRC32-Schieberegister in Hardware. Als Maßstab für die "Korrektheit" habe ich die Algorithmen genommen, die z.B. in der ZLib oder auch hier http://www.digsys.se/js_crc.html stecken. Um CRC32 zu nutzen müssen doch Sender und Empfänger den gleichen Algorithmus verwenden. Wenn es also mind. zwei Implementierungen gibt, die sich CRC32 nennen, aber verschiedene Ergebnisse liefern, stimmt irgendwo etwas nicht. -- Chrisgb 23:48, 1. Feb 2006 (CET)

CRC ist eine mathematische gesehen eine Polynomdivision ohne Übertrag, die Bit für Bit durchgeführt wird. Da gibt's normalerweise wenig dran zu rütteln. CRC32 für Ethernet etwa modifiziert daran folgendes:

• die ersten 32 Bits des Datenstroms werden invertiert (dies entspricht einem Startwert von 111...).
• das Ergebnis wird invertiert.
• Es werden Bytes verarbeitet, die bitweise von Bit0..Bit7 (LSB zuerst) in den Algorithmus gesteckt werden.
• Der Sender hängt die 32 Bits der CRC an den Datenstrom so an, dass Bit 31 zuerst übertragen wird.
• Der Empfänger invertiert ebenfalls die ersten 32 Bits, liest alles bis zum Ende der CRC, es bleibt die Polynomkonstante im CRC-Register übrig (würde man die Bits nicht umkehren, bliebe 0 übrig).

Der Algorithmus ist jeweils derselbe. Es zeigt sich nur eine Variante des alten NUXI-Problems. --Hubi 07:55, 2. Feb 2006 (CET)

Wie CRC funktioniert ist mir vollkommen klar. Dass es hier ein Problem mit der Endianess gibt nun auch. Was ich eben irritierend fand, war, dass sämtliche anderen Programmbeispiele, die ich so gefunden habe, die CRC-Bits in "umgekehrter" Reihenfolge ausgeben. Die Ergebnisse sind zwar äquivalent, aber eben nicht gleich. Z.B. wird (s.o.) zu "VOGEL" die Prüfsumme a75cb680 bzw. 1fb3f2e3 angegeben, bei allen anderen Beispielen, die ich sonst gefunden habe, ergibt sich 35B7A8A3.

-- Chrisgb 10:45, 2. Feb 2006 (CET)

Mir ist jetzt aufgegangen, was an den Beispielen (Pseudocode und C) im Artikel falsch ist: Sie arbeiten nicht zyklisch, wie es der Name des Algorithmus aber impliziert. Die im Register herausgeschobenen Bits werden nicht am anderen Ende wieder hineingeschoben (siehe in meinem Programm die Zeile crc |= CRC32_MSB;).

-- Chrisgb 11:51, 2. Feb 2006 (CET)

Dann lass die Zeile mal einfach weg und du wirst dein blaues Wunder erleben. --Hubi 17:10, 2. Feb 2006 (CET)

Die Funktion liefert dann irgendwas, aber keine Prüfsumme, wie sie beliebige andere Soft- und Hardware (z.B. http://www.erg.abdn.ac.uk/users/gorry/eg3567/dl-pages/crc.html) liefert. Oder anders: Wie kann man 1fb3f2e3 in 35B7A8A3 überführen nur unter Verwendung von Inversion, Spiegelung und byteweiser Vertauschung? -- Chrisgb 18:12, 2. Feb 2006 (CET)

Warum probierst Du's nicht einfach aus, bevor du losbabbelst. Also (im obigen Programm): Das MSB von (crc >> 1) ist immer 0, XOR mit dem umgekehrten Polynom 0xE... gibt im Highbit dann 1 (da 1 XOR 0 = 1) und dein Reinschieben crc |= 0x8... ist dann wirkungslos, mit anderen Worten wirkungslos (hast du's jetzt kapiert).--Hubi 07:12, 3. Feb 2006 (CET)

Also: Bei obigem Programm kiege ich CBF43926, ob die Zeile crc |= CRC32_MSB nun drin ist oder nicht (Daten: "123456789"). Verwende ich "1" stattdessen kriege ich 83DCEFB7 als Prüfsumme, ebenfalls in beiden Fällen. Dieselbe Prüfsumme ergibt auch das (jetzt) zweite C-Programm im Artikel sowie die oben erwähnte Seite http://www.digsys.se/js_crc.html, wenn man nur 1 eingibt (ohne Return!). Ich sehe das Problem nicht. --Hubi 10:58, 3. Feb 2006 (CET)

Das mit dem crc |= CRC32_MSB war in diesem Fall mein Denkfehler. Was die eigentliche Verwirrung ausgelöst hat, war dass ursprünglich im Artikel nur ein Beispiel vorhanden war, was ein ganz anderes Ergebnis liefert, als andere Implementierungen. Unter CRC-32 wird eben (zumindest bei den Quellen, die ich sonst noch gefunden habe) die nun vorhandene zweite Implementierung (zu 99% mit Lookup Table) verstanden. Ich denke jetzt sind alle Klarheiten beseitigt :-) -- Chrisgb 13:22, 3. Feb 2006 (CET)

Ja, so find ich' s jetzt auch besser. Aufgrund der mathematischen Beschreibung kommt man zum ersten Programm, dem mMn eigentlichen CRC-Algorithmus. Das 2. Programm entspricht den gängigen Implementierung. lg --Hubi 17:48, 5. Feb 2006 (CET)

Erkannte Fehler

Es wird dauernd geschrieben, dass CRC-Verfahren grundsätzlich 2-Bit-Fehler erkennen. Das ist aber nicht korrekt. Ich hab erstmal diesen Punkt entfernt. Ein Beweis könnte so aussehen:

Ausgehen werde ich von diesen beiden Vorraussetzungen:

1. Die folgenden beiden Aussagen sind äquivalent:

Unter der Vorraussetzung, dass der Code höchstens x Fehler hat, erkennt das Verfahren bis zu x Fehler.

-- und --

Unter der Vorraussetzung, dass der Code höchstens x/2 Fehler hat, korrigiert das Verfahren bis zu x/2 Fehler.

(siehe dazu "Technische Informatik - Eine Einleitung", Molitor et al., Verlag Pearson Studium, 2005)

2. Um einen Fehler korrigieren zu können, muss mindestens seine Adresse eindeutig angegeben werden können. Beispielsweise muss eine Adresse für Daten, die aus 2^10 Bit bestehen, 10 Bit umfassen. (siehe Hamming-Code)

Beispielsweise besitzt der CRC-16 16 Schutzbits. Wenn nun gesagt wird, dass er 2 Fehler erkennt, bedeutet das, dass mit mit dem gleichen Schutz 1 Fehler korrigiert werden kann, wenn man davon ausgeht, dass höchstens 1 Fehler vorkommt (Nach Vorraussetzung 1). Das heißt nun, dass die Eingabedaten höchstens 2^16 Bit umfassen dürfen (nach Vorraussetung 2), damit ein Fehler korrigiert werden kann, da sonst der Fehler nicht mehr eindeutig adressiert werden kann. Nun ist das CRC-16-Verfahren aber nicht grunsätzlich auf Daten des Umfangs von 2^16 Bit beschränkt. Das bedeutet, dass ein Fehler in Daten vom Umfang 2^17 Bit nicht mehr korrigert werden kann. Damit ist das Verfahren nicht 2 Fehler erkennend (nach Vorraussetzung 1).

Die Annahme, dass dies aber der Fall für alle Daten kleiner als 2^16 Bit ist, ist ein Trugschluss, denn ein CRC-Code lässt grunsätzlich keine empirische Adressierung der einzelnen Datenbits zu, sodass es schwierig ist, zu zeigen, ob solch Daten mit weniger als 2^16 Bits mit einem Fehler korrigiert werden können. Ein Fehler an verschiedenen Stellen kann zum selben (fehlerhaften) CRC-Code führen.

Ich bitte um Meinung zu diesem Beweis, und wo und ob man ihn überhaupt im Text reinstellen sollte. --Sixot 14:37, 23. Mär 2006 (CET)

Ganz ohne mathematischen Beweis ;-), nur ein Versuch das möglichst allgemein verständlich darzustellen:

* Ein CRC_N über einen Datenblock der Länge M (M>=N) für sich alleine ist kein fehlerkorrigierender Code. Einfach weil das Verfahren keinen Rückschluss auf die Position des Fehlers im Datenblock zulässt, egal wie M gewählt ist. (dieser Rückschluss auf die Position eines Datenfehlers ist eine notwendige Bedingung für die fehlerkorrigierende Eigenschaft)

* Ein CRC_N (mit N Bit, N=32 z.b. bei CRC32) erkennt garantiert alle 1-fach, 2-fach, ..., N-fach Bitfehler in einem Datenblock M (M>=N) Dabei ist es egal wie lange der Datenblock M ist. Aus praktischen Gründen, da ja keine Fehlerkorrektor vorhanden ist und bei einem erkannten Fehler der ganze Block nochmal übertragen werden muss, sollte die Blockgrösse M nicht zu gross gewählt werden.

just my two euro cent, wdwd

Zum ersten Stichpunkt: Das ist absolut meine Meinung, und dieser Satz lässt nur den einen Schluss zu, dass CRC sogar noch weniger kann als Fehler korrigierender Code. Meine Schlussfolgerung war nämlich, dass CRC mindestens das können muss, was ein Fehler korrigierender Code kann. Und damit meine ich nicht, dass er einen Fehler korrigieren muss, sondern 2 Fehler garantiert erkennen soll (und diese Aussagen sind äquivalent). Und dass der Code nicht mal einen Fehler korrigieren kann (der Grund sei dahingestellt), darin sind wir uns ganz offenbar einig. ^^

Zum zweiten Stichpunkt: Dies kann unmöglich stimmen, dass ein CRC-n garantiert bis zu n Fehler erkennt. Um dies zu widerlegen und um meinen Beweis deutlich zu vereinfachen, will ich einfach einmal ein Beispiel anführen:

Sei n = 4 und entsprechend ein Generatorpolynom 10101, der zu schützende Datenblock laute 11011011. Man ermittelt, dass der zugehörtige Rest 0110 ist. Werden nun zwei Bits fehlerhaft übertragen, z. B. das 1. und 6., sodass die empfangenen Daten 01011111 sind, dann ist der zugehörige Rest immer noch 0110. Durch dieses Gegenbeispiel ist gezeigt, dass das CRC-Verfahren nicht garantiert 2 Fehler erkennt.

Ich hoffe, das war verständlich genug für die nicht mathematische Masse unter uns. :-)

--Sixot 19:47, 9. Mai 2006 (CEST)

(@Sixot) Solange man die im Artikel beschriebene, dem Entwurf des Algorithmus zugrunde liegende maximale Rahmenlänge einhält, eignet sich das CRC-Verfahren prinzipiell zur Fehlerkorrektur: Alle CRC-Verfahren haben einen Minimalabstand von drei oder mehr, und können deshalb ein-Bit-Fehler korrigieren. Diese Korrekturfähigkeit haben sie mit den Hamming-Codes gemeinsam, die mit einem Minimalabstand von drei auskommen müssen, und von denen niemand bezweifelt, dass sie Fehler korrigieren können. CRCs wurden nicht speziell für die Korrektur von Fehlern entworfen, und es gibt in der Tat Codes, die in dieser Disziplin wesentlich besser sind: um auch nur zwei-Bit-Fehler korrigieren zu können, ist ein Minimalabstand von mindestens fünf erforderlich, und den hat von den mir bekannten CRCs nur einer: der CAN-CRC. Insofern ist die "Daumenpeilung" für die Adressierung von zwei Fehlerpositionen schon richtig, aber mit ein-Bit-Fehlern geht es definitiv. Das wird aber nur bei kleinen Codes (die zum Teil mit Hamming-Codes identisch sind) auch technisch ausgenutzt. Bei längeren Codes wie CRC-16 oder CRC-32 ist es definitiv einfacher und sicherer, die Daten nochmal zu übertragen.

Die Aussage das CRC-16-Verfahren aber nicht grundsätzlich auf Daten des Umfangs von $2^{16}$ Bit beschränkt ist allerdings nur dann richtig, denn man sich über die dem jeweiligen Polynom zugrunde liegende maximale Rahmenlänge hinwegsetzt. CRC ist mathematisch gesehen ein zyklischer Block-Code, und hat damit eine begrenzte Länge, die durch die Tatsache gegeben ist, dass das Generatorpolynom ein Teiler eines Polynoms $x^{n}+1$ (über GF(2)) sein muss, wobei $n$ die Blocklänge des Codes ist. Bei CRC-16 (sowohl CCITT als auch IBM) teilt das Generatorpolynom das Polynom $x^{32767}+1$. Die maximale Zahl von Bits, auf die man einen CRC-16 sinnvoll anwenden kann, ist deshalb 32767 ($2^{15}-1$). Wegen der in GF(2) geltenden Teilbarkeitsbeziehung $x^{n}+1|x^{kn}+1$ für jedes ganzzahlige, strikt positive $k$ kann man natürlich auch mit einem Vielfachen der ursprünglichen Rahmenlänge einen zyklischen Code bauen. Dann verliert man allerdings die Aussage über den Minimalabstand, und damit die Korrekturfähigkeit.

-- -aw- 13:09, 28. Jul. 2009 (CEST)

Ich möchte hier zwei offensichtliche Missverständnisse aus der Welt schaffen:

Die Aussage, dass CRC zwei verfälschte Bits erkennen kann, ist richtig unter gewissen Einschränkungen. Man kann mit Hilfe der Bitfilter-Theorie zeigen, dass zwei Bitfehler im Abstand von p=2^(n-1)-1, wenn n der Grad des Generatorpolynoms ist, nicht erkannt werden; alle anderen aber schon. Wenn somit n beispielsweise 16 ist, sind dieses über 32000 Bits oder 4000 Bytes, so dass man in üblichen Protokollen (außer FDDI) alle 2-Bitfehler mit Sicherheit erkennen kann. Es sei hier noch erwähnt, dass diese Aussage nur für optimal gewählte Generatorpolynome gilt; genaueres entnehme man der unten angegebenen Referenz.

Die Aussage, dass einzelne Bitfehler korrigiert werden können, ist unter den oben genannten Voraussetzungen ebenfalls richtig, da der Rest - abhängig von der Position des fehlerhaften Bits - stets unterschiedlich ist. Auf diese Weise werden z.B. in Bluetooth (FEC 1/3) einzelne Bitfehler korrigiert.

Die Bitfilter-Theorie lässt sich nachlesen in

"http://einstein.informatik.uni-oldenburg.de/papers/Bitfilter.pdf"

Hab mich zuerst gewundert, warum dann in meinem Beispiel der Fehler nicht erkannt wird, denn da müsste der Abstand 7 sein, ist aber 5. Hab dann weitergelesen und gesehen, dass du von optimal gewählten Generatorpolynomen redest. Damit kann ich durchaus mitgehen, ich glaub dir mal, dass das so in dem Artikel steht ;-). Bloß im Artikel ist nicht davon die Rede, dass nur bei optimal gewählten Polynomen so gut wie keine Fehler erkennen. Vielmehr ist ja sogar davon die Rede, dass jegliche Polynome sämtliche 2-fach-Fehler erkennen. Man sollte es vielleicht in der Hinsicht auf die Wahrscheinlichkeit des tatsächlichen Auftretens der 2-fach-Fehler, die nicht erkannt werden, formulieren. --Sixot 12:01, 31. Aug 2006 (CEST)

Welchen 'Artikel' meinst du? Richtig ist, dass es zu jedem Grad n optimale Polynome (mit gerader Anzahl von Termen) gibt, die 2-Bitfehler in einem Abstand von 2^(n-1)-1 erkennen. Richtig ist auch, dass es bei ungerader Termzahl u.U. Polynome gibt, die 2-Bitfehler in einem Abstand von 2^n-1 erkennen - allerdings erkennen die nicht alle ungeraden Bitfehler, weshalb sie m.E. nicht verwendet werden sollten. In deinem Beispiel scheint mir auch ein Fehler zu sein, da 1000001, also ein Fehler an der 1. und 7. Stelle den Rest null lässt (evtl. meinst du das ja: 1+X^6). Dein Generator 10101 hat einen Bitfilter mit Periode 6, woraus dieses Ergebnis folgt. Der Generator 11001 gleichen Grads 4 z.B. hat einen Bitfilter mit Periode 15, so dass 1000000000000001 keinen Rest lässt, alle kürzeren Abstände aber schon. Bitmaster 13:16, 1. Sep 2006 (CEST)

öhm... wieder n bissl missverständlich erklärt von mir, "Artikel" is beim ersten Nennen der Link oben und beim zweiten Nennen der Artikel hier im Wiki --Sixot 13:41, 31. Jan. 2007 (CET)

hab entfernt dass eine fehlerhafte nachricht als richtig erkannt wird wenn "mehere stellen verfälscht wurden"... das ist falsch! jeder Generator der Form 2^x mit x element N is anfällig gegenüber Einzelbit-Fehlern --Cr4wler 14:20, 7. Jul. 2007 (CEST)

"Korrekter" CRC

Es wird hier viel über "korrekt" und "nicht korrekt" diskutiert. Mathematisch ist das Ergebnis einer Division, auch einer Polynomdivision, eindeutig festlegt. Nicht Gegenstand der Mathematik ist, wie man ein Polynom durch eine Bitfolge darstellt. Hier sind zwei Verfahren üblich: einmal wird das Bit, das in der Ganzzahl-Darstellung den Wert $2^{n}$ hat, als Koeffizient des Polynoms an der Stelle $X^{n}$ verwendet. Beim anderen Verfahren wird das in der Ganzzahl-Darstellung niederwertigste Bit für den höchsten Koeffizienten verwendet. Korrekt sind sie beide, nur muss man beim einen Verfahren die Bits von links nach rechts, und beim anderen von rechts nach links lesen. Das muss man natürlich sowohl für die Datenbits, als auch für das Generatorpolynom machen.

Warum macht man das? Bei der Hardware-Implementierung mittels Schieberegister werden die Bits in der Reihenfolge angeliefert, in der sie übertragen werden. Bei serieller Übertragung (z.B.) Ethernet, ist es üblich, das niederwertigste Bit eines Bytes zuerst zu übertragen. Daher entspricht hier das niederwertigste Bit dem höchsten Koeffizienten.

Bei der Implementierung in Software gibt es aus diesem Grund Verfahren, die erst mal alle Bits in einem Byte spiegeln, dann die Berechnung durchführen, und am Ende das Ergebnis wieder spiegeln. Bei Ross Williams heisst dieses Verfahren "Reflection".

Das funktioniert zwar, scheint mir aber "von hinten durch die Brust ins Auge zu sein". Ich habe deshalb vor einiger Zeit ein paar C++ - Klassen entwickelt, die einen CRC-Algorithmus unabhängig von der Bit-Darstellung implementieren. Für die Darstellung gibt es eigene Klassen, die dann im Algorithmus als Templates verwendet werden. Das Ganze ist öffentlich (GPL) und unter http://www.aweiler.com/crc/index.html zu finden.

---aw- 11:55, 6. Mai 2006 (CEST)

Zyklisch

Die Bezeichnung "Zyklische Redundanzprüfung" ist irreführend. Es handelt sich nicht um eine zyklische Prüfung, auch nicht um eine zyklische Redundanz, sondern um einen zyklischen Code. Diese Codes haben eine feste (!) Blocklänge. Im praktischen Einsatz kann man trotzdem eine variable Nachrichtenlänge verwenden, da bei der Übertragung einfach führende Nullen weggelassen werden. Die feste Blocklänge bestimmt aber die maximale Nachrichtengröße.

Der Begriff "zyklisch" bezieht sich auf Codeworte: ist ein Codewort $k(X)$ gültig (d.h. durch das Generatorpolynom $G(X)$ teilbar), so ist auch das "geshiftete" Codewort $X*k(X)(modX^{n}+1)$ durch $G(X)$ teilbar und damit gültig.

In dieser Diskussion wurde das Gerücht in die Welt gesetzt, das Generatorpolynom müsse irreduzibel sein. Das stimmt nicht. Viele Generatorpolynome sind durch $X+1$ teilbar. Im Hauptartikel gibt es einen guten Hinweis, warum. Die einzige Anforderung an das Generatorpolynom ist, dass es $X^{n}+1$ teilen muss, wobei $n$ die Blocklänge des Codes ist.

Weitere Infos unter meiner Never asked questions Liste. In Englisch, aber bei Interesse/Bedarf kann ich das auch gerne nochmal auf Deutsch wiedergeben. ---aw- 12:16, 6. Mai 2006 (CEST)

Es gibt auch einen Artikel "Zyklischer Code", der vielleicht mit dem dem hier zusammengelegt werden sollte. Kann das jemand überprüfen und entscheiden?

Also das ist ein typischer Fehler der Deutschen, wenn es heißt: "Zyklische Redundanzprüfung", dann ist das ein zusammengesetztes Substantiv mit Adjektiv. Ein Adjektiv bezieht sich immer auf das gesamte zusammengesetzte Substantiv. Das bestimmende Wort eines zusammengesetzten Substantivs ist grunsätzlich das letzte der beiden. In dem Fall also "Prüfung". "Zyklische Redundanzprüfung" heißt umgeschrieben nichts anderes als "zyklische Prüfung von Redundanz", und das ist absolut korrekt. --Sixot 17:29, 23. Feb. 2007 (CET)

CRC-Fehler im SMART-Log

Was bedeuten die dort?

199 UDMA_CRC_Error_Count    0x000a   200   253   000    Old_age   Always       -       698

(ich hab am meisten ... juhu :/) – Simon Diskussion/Galerie 10:21, 9. Okt. 2006 (CEST)

Linkvorschlag

• http://www.joegeluso.com/software/articles/ccitt.htm

--Cybot 08:05, 24. Okt. 2007 (CEST)

Bilder mit Schieberegister

Hallo zusammen,

ich habe drei Bilder mit der Realisierung als Schieberegister gezeichnet. Vielleicht möchte einer der Autoren noch Rückmeldung geben, bevor ich es einfüge.

Das erste Bild ist die Standardschaltung. Daten serielle Zuführen und anschließen noch 4x mit Nullen nachtakten um die Polynomdivision abzuschließen. Der Rest steht nun in den D-FF gespeichert.

Die nächsten zwei Bilder sind das selbe mit kleiner Erweiterung. Daten seriell Zuführen, ohne nachzutakten, denn der Rest der Polynomdivision steht bereits in den Registern. Die untere Variante enthält noch einen Multiplexer. Während die Daten durchgeschoben werden steht MUX auf 1 und zum seriell ausgeben des CRC-Werte geht MUX auf 0. Ein CRC kann quasi im Durchgang erzeugt werden.

--Biezl ✉ 20:10, 21. Jul. 2008 (CEST)

Hi Biezl, hat es einen tieferen Grund, warum die FF-Anschlüsse (D, Q und R) spiegelverkehrt dargestellt sind?--wdwd 14:48, 22. Jul. 2008 (CEST)

Hi wdwd, Die D-FFs sind an der Horizontalachse gespiegelt, da sie entgegen der üblichen vlnr-Richtung arbeiten. Ich habe für das mittlere eine Alternative hoch geladen. Eventuell ist das weniger verwirrend. --Biezl ✉ 18:04, 22. Jul. 2008 (CEST)

Hi Biezl, Spieglung betrifft den Text, also die Symbole D, Q und R welche gespiegelt dargestellt sind. Im mittleren, neu hochgeladenen ist der Text nicht mehr gespiegelt. Kann der Text in den Symbolen trotz "umgedrehter" Arbeitsrichtung normal (nicht spiegelverkehrt) belassen bleiben? (Hmm, oder ist das ein eigenartiger SVG-Fehler? - hab bei mir den SVG2PNG-Konverter über wiki aktiv. SVG native kann mein Browser nicht.) --wdwd 20:40, 22. Jul. 2008 (CEST)

Nachtrag, hier ein Link wie es als PNG ausschaut.--wdwd 20:45, 22. Jul. 2008 (CEST)

Die spiegelverkehrten Buchstaben sind schon Absicht von mir, die wurden mit gespiegelt (kein SVG-Problem, WP:PMS). Nicht gespiegelte Buchstaben finde ich schauen noch verwirrender aus. Man könnte meinen es wär ein rückwärts arbeitendes D-FF, da die Buchstaben eine gewisse Arbeitsrichtung vermitteln. Ist die zweite Version annehmbarer? --Biezl ✉ 21:40, 22. Jul. 2008 (CEST)

Zweite Version ist meiner Meinung ok.--wdwd 22:18, 22. Jul. 2008 (CEST)

Grafiken sind angepasst. Ich frag mich noch wie die mittlere Schaltung heißt, die hatte einen eigenen Namen. Ich meine da war was mit Martin dabei. Ich seh gerade Du hast schon vor längerer Zeit das selbe gezeichnet. Wahr wohl zu gut versteckt --Biezl ✉ 17:19, 23. Jul. 2008 (CEST)

Detailierter bei Einleitungssätzen

Hallo,

ich würde folgendes gern noch präzisieren.

Vor Beginn der Übertragung bzw. Kopie eines Blocks der Daten wird ein CRC-Wert berechnet. Nach Abschluss der Transaktion wird der CRC-Wert erneut berechnet.

Von welchem Teilnehmer der Übertragung (Sender, Empfänger) wird der CRC-Wert berechnet? Vor Beginn vom Sender, nach Übertragung vom Empfänger?

Grüße k00ni 18:21, 21. Okt. 2008 (CEST)

Habe den Einleitungsteil etwas gestrafft und den Passus mit der Transaktion herausgenommen. Letztlich kommt es nicht darauf an, ob der Sender die Berechnung vor oder während der Übertragung durchführt, und auch nicht, ob der Empfänger die Berechnung während oder nach der Übertragung durchführt. Wichtig ist, dass beide denselben Algorithmus ausführen. Wenn das "sauber" gemacht wird, braucht man auch keine Sonderbehandlung für den CRC-Wert. D.h. es ist nicht notwendig, den CRC-Wert mit einem Original zu vergleichen, sondern der Empfänger berechnet den CRC über den gesamten Datenblock, inkl. des vom Sender angefügten CRC-Werts. Da es sich bei diesem Wert um den Rest der Division handelt, muss bei der um den CRC-Wert angereicherten Nachricht der Rest Null herauskommen (Berechnung modulo 2). Soweit die Theorie. In der Praxis führen Implementierungsdetails dazu, dass nicht Null, sondern ein konstanter Wert (das sogen. "Residuum") herauskommt. Diese Details habe ich aber in der Einführung weggelassen. Bei Interesse weitere Erläuterungen hier.

-- -aw- 12:26, 24. Jul. 2009 (CEST)

XModem CRC

Hi Community,

möglicherweise steh ich auf dem Schlauch un überseh was, aber wenn ich nach CRC und XModem google stoße ich immer auf das Polynom x^16 + x^12 + x^5 + 1, nie auf x^16 + x^15 + x^10 + x^3. Zudem kommt es mir komisch vor, dass dieses Polynom kein x^0=1 enthält. Kann mir das einer erklären und ggf. im Artikel ergänzen?

Das Generatorpolynom für XModem ist $x^{16}+x^{12}+x^{5}+1$. Das ist das unter dem Namen CRC-CCITT wohlbekante Polynom. Bei $x^{16}+x^{15}+x^{10}+x^{3}$ handelt es sich um eine falsche Interpretation von 0x8408. Diesen Wert muss man von rechts nach links lesen, dann ergibt sich auch wieder das CCITT-Polynom. Das liegt daran, dass CRCs ursprünglich für die Sicherung von seriellen Datenübertragungen verwendet wurden. Bei diesen wird traditionellerweise das niederwertigste Bit zuerst übertragen. Bei der Berechnung des CRCs trägt aber das zuerst übertragene Bit den höchsten Polynom-Koeffizienten.

Dein Verdacht mit $x^{0}=1$ ist richtig. Ein Blick in ein Buch über algebraische Codierungstheorie zeigt, dass das Generatorpolynom ein Teiler von $x^{n}+1$ sein muss (wobei $n$ die Blocklänge des Codes ist). Diese Teilbarkeit kann aber nicht gegeben sein, wenn es ein Vielfaches von $x$ (oder $x^{3}$) ist.

-- -aw- 12:45, 24. Jul. 2009 (CEST)

Mängel des Artikels

So richtig wird bei dem Artikel nicht klar, was einen CRC jetzt von irgendwelchen anderen Prüfsummenalgorithmen unterscheidet. Fragwürdig ist die Aussage, CRC würde bei "Festplatten-Übertragungen" oder "Schreib-/Lese-Operationen" genutzt. Das ist meiner Kenntnis nach Wissensstand 1982, wo das bei MFM-Winchester-Laufwerken wohl wirklich einmal so gewesen sein muss.

Vermutlich liegt das einfach daran, dass einige der Autoren CRC synonym zu Prüfsummenalgorithmus verwenden, was aber unzutreffend ist. Nicht behandelt werden die Themen Skalierbarkeit und Anwendbarkeit.

Der Artikel leidet übel darunter, dass es sich um Erstsemester-Material Informatik handelt. Für ein Erstsemester ist aber die inhaltliche Einordnung noch praktisch unmöglich.

Fazit: Ein richtig geschwätziger, aber inhaltlich in der Summe wertloser Artikel.

Es wird vorgeschlagen, den Artikel radikal zu kürzen und sich auf die wesentlichen Aussagen zu beschränken. Diese wären leider noch zu ergänzen. --88.69.115.122 08:23, 4. Apr. 2009 (CEST)

Serial ATA verwendet das CRC-32 zur Absicherung der Übertragung ([1]). Bei dieser Gelegenheit habe ich übrigens gemerkt, dass der Artikel Serial ATA auf das Protokoll auf dem Bus noch gar nicht eingeht. Auch die modernsten heutigen Festplatten verwenden intern irgendwelche CRCs, um sicherzustellen, dass die Daten korrekt auf den Scheiben landeten und korrekt gelesen wurden. Zum Thema Skalierbarkeit von CRC noch etwas zu lesen wäre sicherlich interessant, ebenso wie weitere Informationen zur Anwendbarkeit. --Echoray 09:22, 4. Apr. 2009 (CEST)

"Irgendwelche CRCs": Komische Bezeichnung für einen Algorithmus. Sind das nicht vielleicht eher ECCs? --88.69.115.122 11:23, 4. Apr. 2009 (CEST)

Ja, ECC. Asche auf mein Haupt. Es ist mir bislang nicht gelungen, eine Quelle für die interne Verwendung von CRCs in der Festplatte zu finden, ich habe nur folgendes Zitat aus der englische Wikipedia: "Modern hard drives use CRC codes to detect and Reed-Solomon codes to correct minor errors in sector reads". --Echoray 12:04, 4. Apr. 2009 (CEST)

Ich glaube wirklich, dass der Begriff "CRC" zum Teil synonym für irgendwelche Prüfsummenalgorithmen verwendet wird. Auch in White Papers. Aber CRC wird tatsächlich an vielen Orten noch wirklich verwendet, auch wenn es nicht passt, z.B. Ethernet-Protokoll. Ich halte das für ein Problem.--88.69.115.122 12:33, 4. Apr. 2009 (CEST)

Der wichtige Tenor, der mir fehlt, ist hauptsächlich: Mit einem CRC-Algorithmus kann man gut einzelne Bitfehler detektieren. Er kann aber aber nicht gegenüber ECCs (Error Correction Codes) oder Hashes (kryptographischen und nicht-kryptographischen) konkurrieren. Vor allem treten bei moderneren Speicher- und Übertragungssystemen einzelne Bitfehler praktisch nie auf. Auch bei modernen Festplatten wird ein Bitfehler nie auftreten, da ein Bit relativ zu allen anderen gespeichert ist, ergo hat man dabei gegebenenfalls Haufen von Bitfehlern. Und genau dafür eignet sich ein CRC überhaupt nicht.--88.69.115.122 12:00, 4. Apr. 2009 (CEST)

Du möchtest bitte den Abschnitt Erkannte Bitfehler durchlesen. Inbesondere den Unterabschnitt über Bündelfehler und das nachfolgende Beispiel mit dem IBM-CRC16 und dessen Besonderheiten. Von ein CRC eignet sich nicht zur Fehlererkennung von mehr als Bit kann keine Rede sein, das ist genau nicht der Fall, und der von Dir erwähnte "Tenor" ist, so leid ist mir tut, schlicht falsch.

Ich verbessere: Für eine Erkennung von Reihen von Bitfehlern ist CRC nicht geeignet. Ich schwöre, von nun an rhetorische Methodik nur noch anzuwenden, wenn ich adäquaten Gesprächspartnern gegenüber stehe.--88.69.115.122 19:40, 4. Apr. 2009 (CEST)

Das so ein Thema wie CRC mit Randbereichen hin zur Zahlentheorie, und auch sowas wie eine Polynomdivision, abseits Einleitung etwas mehr Vorwissen vorraussetzt und eventuell einfache Grundschulmathematik dafür nicht mehr ausreicht, liegt irgendwie in der Natur der Sache. Was fehlt bzw. passt nun aber an dem Artikel konkret nicht?--wdwd 13:09, 4. Apr. 2009 (CEST)

Das ist ja lieb formuliert. Überhaupt nicht arrogant oder herablassend. Um die Frage zu beantworten: Ich möchte gerne einen Artikel, der sich für eine Enzyklopädie eignet. Dieser Artikel ist strukturell für einen Leser ohne sehr viel Vorwissen nicht geeignet, wie Du ja selber in Deiner Art sagst.--88.69.115.122 19:10, 4. Apr. 2009 (CEST)

Hi, sorry wenn Dich meine Formulierung stört, war keine Absicht. So kam im Absatz unter "Tenor" Aussagen wo (fast) jeder Satz inhaltlich unzutreffend ist. Soll heissen, eine ggf. schwierige Thematik wird durch falsche Aussagen nicht einfacher und zugänglich. Inhaltlich bestehen sicher Optionen zur Verbesserung, so die Aussagen dann nicht falsch sind. Darauf wollte ich, vielleicht etwas überzogen, hinweisen.--wdwd 21:10, 4. Apr. 2009 (CEST)

Rechenfehler?

Also entweder ich bin bloed, oder da drin ist ein Rechenfehler, oder das Ausgangspolynom ist falsch: Bluetooth x5 + x4 + x2 + 1 = (x + 1)(x4 + x + 1) Also wenn ich das ausmultipliziere bekomme ich x^5 + x^4 + x^2 + 2x + 1 (nicht signierter Beitrag von 202.136.14.9 (Diskussion | Beiträge) 06:54, 3. Feb. 2010 (CET))

Das stimmt schon so. Wir rechnen modulo 2, und da gibt es kein 2x, denn 2 = 0 modulo 2.

-- -aw- 00:38, 11. Apr. 2010 (CEST)

Unterschiedliches Polynom in deutschem und englischem Artikel

Hallo, mir scheint sich da ein Fehler eingeschlichen zu haben: Der englische Wikipediaartikel bezeichnet die CRC mit dem Polynom x^8 + x^2 + x + 1 als "CRC-8-CCITT", während der deutsche Artikel hier ein Polynom von x^8 + x^5 + x^4 + 1 als "CRC-CCITT (CRC-8)" bezeichnet. Dieses Polynom wird im englischen Artikel als eines von Dallas/Maxim angegeben. Bei Dallas/Maxim kann man das im englischen Artikel angegebene Polynom auch z.B. im Datenblatt des DS18S20 finden: http://datasheets.maxim-ic.com/en/ds/DS18S20-PAR.pdf. Leider weiß ich nicht, wo das "richtige" Polynom der CRC-8-CCITT zu finden ist, um zu überprüfen, welches denn nun stimmt. Falls jemand eine sichere Quelle hat (ich weiß wie gesagt leider gerade keine), sollte das eventuell korrigiert oder genauer beschriftet werden. -- 62.158.104.149 22:14, 9. Apr. 2010 (CEST)

Die Quelle ist in http://en.wikipedia.org/wiki/Cyclic_redundancy_check angegeben, nämlich http://www.itu.int/rec/T-REC-I.432.1-199902-I/en. Dort steht in Kapitel 7.3.2.2 auf Seite 6 zu lesen: "generator polynomial $x^{8}+x^{2}+x+1$". Der englische Artikel dürfte also korrekt sein. Ich ändere das mal...

-- -aw- 01:02, 11. Apr. 2010 (CEST)

Quotient muss nicht Null sein

Hallo, im Abschnitt Erkannte Fehler steht 'Da $T(x)/G(x)=0$...', es wird also impliziert der Rahmen (mit Anhang) geteilt durch Generatorpolynome müsse bei korrekter Übertragung von $T(x)$ Null sein. Dies erscheint mir falsch. Der Quotient wird schon wieder ein Polynom > 0 sein, es darf lediglich kein Rest-Polynom bleiben. Muss es also nicht heißen, $T(x)$ modulo $G(x)=0$? Auch die darauffolgende Rechnung bzgl. $E(x)$ ist dann zu überarbeiten. -- 213.61.222.21 (09:17, 29. Apr. 2010 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Polynome und Typen

Hallo, die Zeile mit "SD/MMC-Card (CRC-7)" im Abschnitt "Polynome und Typen" ist offensichtich ein Versehen. Ich glaube, das angegebene Generatorpolynom ist nicht der (63,57)-Hamming-Code, sondern der (127,120)-Hamming-Code (vgl. Zyklischer Hamming-Code). Über fachmännische Korrektur (falls möglich) würde ich mich freuen. MfG, --Rad238 13:24, 16. Nov. 2009 (CET)

korrigiert.--wdwd 13:30, 11. Apr. 2010 (CEST)

Die Polynome sind alle Falsch, zumindest ergibt es für mich keinen Sinn, dass bei crc16 ein x^16 vorkommt, wenn das Polynom nur bis x^15 gehen kann da es bei 0 anfängt (z.B crc4 hat nur 4bits wenn das polynom 1,1,1,1 is dann sollte es x^3+x^2+x^1+x^0 entsprechen ein x^4 wär da fehl am Platz). Würde es gern korrigieren allerdings liegt mir keine richtige Tabelle vor. Würde mich freuen wenn das wer machen könnt.

mfg (nicht signierter Beitrag von 212.90.142.126 (Diskussion) 16:08, 31. Mai 2010 (CEST))

Mathematik dahinter

hallo, was mir hier ein wenig fehlt, ist die Mathematik hinter der CRC-Berechnung. was haltet ihr davon? ich frage natürlich aus einem grund: ich kenn mich selber nicht aus, muss ich zu meiner Schande eingestehen. Ich weiss zwar, dass das Generatorpolynom irreduzibel sein muss, dass XOR anstelle einer Division deswegen eingesetzt werden kann, weil es sich um eine Operation in GF(2) handelt - aber warum das Ganze, das bleibt mir verborgen.

Noch eine Frage: ist die 1-Bit Prüfsumme eigentlich äquivalent zu CRC-1? (nicht signierter Beitrag von 81.10.251.217 (Diskussion | Beiträge) 19:52, 25. Apr. 2006 (CEST))

S.M.A.R.T.-Beispiel ziemlich daneben

S.M.A.R.T. protokolliert lediglich auftretende Fehler (unter anderem CRC-Fehler), die CRC-Prüfung selbst ist jedoch Teil des ATA-Protokolls, und wird nicht - wie im Artikel angeführt - von S.M.A.R.T. durchgeführt. (nicht signierter Beitrag von 84.173.226.77 (Diskussion | Beiträge) 04:58, 17. Jan. 2007 (CET))

Abgrenzung zu Hamming-Codes und Crypto-Hashes

Ich würde in diesem Artikel einen Abschnitt begrüßen, der (mit Links) erklärt worin sich CRC von Hamming-Codes einerseits und Crypto-Hashes andererseits abgrenzt, und warum CRCs auch heute noch verwendet werden.

Man könnte dort Aufführen: CRC vs. Hamming: Fokus bei Hamming-Codes ist die Korrigierbarkeit - Haming-Codes können Fehler korrigieren, haben aber einen eingeschränkten Horizont (einzelne Bytes/Worte). CRC kann nicht korrigieren, findet aber Fehlerbündel über Byte/Wortgrenzen hinweg.

CRC vs. MAC: MACs sind dafür gedacht, absichtlich herbeigeführte Änderungen einer Nachricht zu erkennen. CRC kann das nicht, es ist einfach eine Nachricht gezielt so zu verändern, dass die CRC-Summe identisch bleibt. CRCs hingegen erkennen besonders gut Fehler bei der physikalischen Übertragung von Daten, lassen sich einfach in Hardware implementieren, liefern sofort nach Ende der Nachricht eine Ergebnis (MACs brauchen dann noch ein paar Runden) und lassen sich einfach (mit wenigen Gattern) in Hardware implementieren.

Ein Beispiel für Fehlerbündel bei physikalischer Übertragung wären elektromagnetische Impulse durch Einschalten eines Gerätes (Motor/Trafo o.ä), die zeitlich begrenzt sind oder Fehler in der Magnetschicht einer Festplatte, die räumlich begrenzt sind. In beiden Fällen treten Fehler als zusammenhängende Bündel auf - genau das, was CRCs gut erkenne können. (nicht signierter Beitrag von 82.194.111.73 (Diskussion | Beiträge) 23:26, 24. Apr. 2009 (CEST))

Hi, "Unterschied" (zyklische) hamming-codes vs CRC: Bei gleichen generatorpolynom, wie z.b. bei dem CRC7 laut tabelle und Hamming (127,120), ist keiner. Der Unterschied ist in der Anwendung: bei dem Hamming-code muss das Codewort eine fixe Länge haben, ergibt sich aus der Codierungsvorgabe. In diesem Fall 127 Stellen (bits), wobei 120 Bit die Nutzdaten darstellen und 7 Bit die CRC bzw. die "parity-bits" des Hamming-Code. Nur wenn der Nutzdatenblock genau diese 120 Bit länge aufweist, kann dieses Polynom wie bei Hamming aka CRC7 zur Ein-Bit-Fehlerkorrektur verwendet werden. (siehe hamming-code Artikel z.b. mit der syndrom-dekodierung, der wert des CRC7-registers stellt dann einen syndromwert da, der die fehlerstelle beschreibt). Bei der CRC7-Anwendung, also wenn man nur Fehler erkennen aber nicht korrigieren will, kann der Nutzdatenblock auch andere Längen als 120 Bit (bei CRC7) umfassen.

Ad burst-fehler/fehlerbündel: Zur Fehlerkorrektur, da die gleichwertigen Hamming-Codes nun nur 1 Bit fehler pro Codewort korrigieren können, werden die zu übertragenenen/zu speichernden Daten mittels Interleaver "verwürfelt". Damit werden diese Burst Errors auf mehrere Codewörter aufgeteilt, im idealfall immer nur ein Fehler pro Block über eine längere Sequenz verteilt, und so mit höherer Wahrscheinlichkeit der einfachen Hamming-Fehlerkorrektur zugänglich gemacht.--wdwd 13:44, 11. Apr. 2010 (CEST)

CRC ist sehr leicht zu fälschen

Sollte man auch in den Artikel einbauen. (nicht signierter Beitrag von 84.164.53.56 (Diskussion | Beiträge) 20:34, 6. Mai 2008 (CEST))

Dieser Abschnitt kann archiviert werden. Echoray 11:27, 5. Sep. 2010 (CEST)

Allgemein

Ich würde zu Beginn eine leichter verständliche Angabe machen, um ... linepiece (nicht signierter Beitrag von 91.113.7.18 (Diskussion) 21:26, 12. Jul 2010 (CEST))

Erkannte Fehler, Beispiel, Begründung ist falsch

Das Generatorpolynom $G(x)=x^{16}+x^{15}+x^{2}+1$ (IBM-CRC-16) lässt sich als $G(x)=(x^{15}+x+1)(x+1)$ faktorisieren. Wenn ich $G(x)=(x^{15}+x+1)(x+1)$ in Maxima eingebe und expandiere kommt $x^{16}+x^{15}+x^{2}+2x+1$ raus und das ist ja nicht mehr das Generatorpolynom oder? (nicht signierter Beitrag von 188.99.137.194 (Diskussion) 09:32, 28. Nov. 2011 (CET))

Sie müssen im GF(2) rechnen, nicht in $\mathbb {N}$. Dies ist kein Hausaufgabenhilfe Forum. --Moritzgedig 16:19, 7. Feb. 2012 (CET)

Zyklischer Code ungleich CRC

CRC codes sind eine Untermenge der zyklischen codes, nämlich jede die in P(x)*(x+1) zu zerlegen sind, wobei P(x) nicht zerlegbar sein darf. Dieser Artikel ist falsch da er nicht unterscheidet, er behandelt Zyklischer_Codes und geht nicht auf die Besonderheiten von CRC ein. --Moritzgedig 16:41, 7. Feb. 2012 (CET)

Nicht jeder CRC-Code ist zyklisch!

Wir betrachten den 3-Bit-breiten CRC-Code mit dem Generatorpolyom g(x) = x. Die Codewörter sind 000, 010, 100 und 110. Wäre der Code zyklisch, dann müsste auch 001 ein Codewort sein, was nicht der Fall ist. (nicht signierter Beitrag von 109.193.168.154 (Diskussion) 13:35, 20. Feb. 2012 (CET))

Hä? G(z)=z ist kein Generatorpolynom. --Moritzgedig 21:26, 22. Feb. 2012 (CET)

Welche Anforderungen werden an das Generatorpolynom gestellt? Im Text heißt es, das Generatorpolynom ist ein vorher festgelegtes Polynom. Warum kann ich nicht g(x) = x wählen? Gegen welche Forderung verstößt meine Wahl? (nicht signierter Beitrag von 109.193.168.154 (Diskussion) 18:12, 28. Feb. 2012 (CET))

Das Generatorpolynom g(x)=x hat den Grad 1 und ist so in der Lage 0-Bit fehler zu erkennen. Nicht wirklich das, was gewünscht ist, oder? Abgesehen davon: Warum behauptest du 001 sei kein Codewort? --P.C. ✉ 18:31, 28. Feb. 2012 (CET)

Die Codewörter sind die Vielfachen des Generatorpolyonoms, deren Grad < m ist (wobei m die Codewortlänge ist, im meinem Beispiel ist m = 3). Die Codewörter sind dann

x * 0 = 0 (Codewort 000) x * 1 = x (Codewort 010) x * x = x^2 (Codewort 100) x * (x+1) = x^2 + x (Codewort 110)

001 entspricht dem Polynom p(x) = 1. Dieses ist aber kein Vielfaches von g(x) = x und damit ist 001 kein Codewort.

Sinnvoll ist der CRC-Code mit g(x) = x natürlich nicht, aber darum ging es ja nicht. (nicht signierter Beitrag von 109.193.168.154 (Diskussion) 19:15, 28. Feb. 2012 (CET))

Wenn Du schon bei solchen Überlegungen bist: Überleg Dir, welchen Ring du da gerade aufspannst, und welche Elemente eventuell identisch sind. Also anders gefragt: In welcher deiner Ringklassen liegt 001. --P.C. ✉ 08:53, 29. Feb. 2012 (CET)

Dies ist nicht der Ort für Nachhilfe. Der OP hat jedoch in soweit recht, als dass der Artikel so unvollständig ist, dass er falsch ist. Ich habe unter "Zyklischer Code ungleich CRC" darauf hingewiesen. Das kürzeste generatorpolynom ist 11. RichtigeCW: 00*11=000; 01*11=011; 10*11=110; 11*11=101, FalscheCW: 001,010,100,111. Es ist der even parity code. Nur wenige der möglichen CW sind auch richtig und somit duch Multiplikation zu erhalten. Der OP hat mal gar nix verstanden.

Dieser Abschnitt kann archiviert werden. Moritzgedig (Diskussion) 12:22, 6. Mär. 2012 (CET)

--Moritzgedig (Diskussion) 12:22, 6. Mär. 2012 (CET)

Faktorisierung von CRC-8 (ITU-T)

Bei der Faktorisierung von CRC-8 (ITU-T) fehlt meines Erachtens der Term x^4. Vgl. z.B. http://www.ee.unb.ca/cgi-bin/tervo/factor.pl?binary=100000111. Habe den Artikel gerade entsprechend angepasst und bitte um Verifizierung. Danke :) --Plainalt (Diskussion) 23:33, 9. Mai 2012 (CEST)

Kann ich bestätigen! Mit Mathematica berechnet:

In[1]:= Factor[x^8+x^2+x+1,Modulus->2]

Out[2]= (1+x) (1+x^2+x^3+x^4+x^5+x^6+x^7)

Umgekehrt würde die Expansion der (falschen) rechten Seite dazu führen:

In[2]:= Expand[(x+1)(x^7+x^6+x^5+x^3+x^2+1),Modulus->2]

Out[2]= 1+x+x^2+x^4+x^5+x^8

Grüße, Armin Vollmer (nicht signierter Beitrag von 178.25.75.104 (Diskussion) 14:21, 11. Mai 2012 (CEST))

MHD, Hamming Distanz

Im Text steht: "Ein CRC-Algorithmus kann also jeden Fehler erkennen, der innerhalb der angegebenen maximalen Länge weniger als MHD - 1 Bit-Positionen betrifft." Meiner Meinung müsste das enteweder: " .. Länge weniger als MHD Bit-Positionen.." heissen, oder: " .. Länge höchstens MHD - 1 Bit Positionen..". (nicht signierter Beitrag von 88.66.7.35 (Diskussion) 10:43, 11. Jul 2012 (CEST))

Stimmt! Ich korrgiere das. ---aw- (Diskussion) 17:36, 22. Jun. 2013 (CEST)

abschnitt Implementierung

/*Es stellte sich heraus, dass einige Polynome besser „schützen“ als andere. Für CRC häufig verwendete Polynome sind das Ergebnis umfangreicher mathematischer und empirischer Analysen und keine Zufallszahlen, auch wenn sie so aussehen.*/ Lässt sich das genauer erklären? Nur so als Verdacht als Laie, ohne mich da genauer reingeschnüffelt zu haben...."es gelten die Regeln von LFSR" -> Polynom sollte ein primitives Polynom sein und leifert dadurch bessere Werte. --93.220.208.132 00:00, 2. Dez. 2012 (CET)

Der Artikel ist wohl immernoch falsch und geht nicht auf folgenden Umstand ein: "CRC codes sind eine Untermenge der zyklischen codes, nämlich jene die in P(x)*(x+1) zu zerlegen sind, wobei P(x) nicht zerlegbar sein darf. Dieser Artikel ist falsch da er nicht unterscheidet, er behandelt Zyklischer_Codes und geht nicht auf die Besonderheiten von CRC ein. --Moritzgedig 16:41, 7. Feb. 2012 (CET)" CRC Kodes sind auf burst-fehler optimiert. Ein Kode bestimmter Länge kann auf unterschiedliche Fehler optimiert sein. "es gelten die Regeln von LFSR" -> Polynom sollte ein primitives Polynom sein und leifert dadurch bessere Werte" Ja, das stimmt. Ein Kode sollte die Fehler möglichst über seinen ganzen Raum verteilen, sonst nutzt er seine Länge nicht aus.--Moritzgedig (Diskussion) 10:48, 24. Mai 2013 (CEST)

---

@Moritzgedig: Für diese Behauptung (CRC Generator = P(x)*(x+1), P(x) nicht zerlegbar) hätte ich gerne eine Quellenangabe. M.E. ist das auch nicht richtig. Dann wäre der CAN-CRC kein CRC, denn dessen Generator läßt sich in drei Komponenten zerlegen (siehe Hauptartikel). Möglicherweise verwechselst Du das mit BCH-Codes. Damit lassen sich zyklische Codes designen, die einen bestimmten vorgegebenen Minimalabstand haben. Aber das ist meines Wissens keine Anforderung. Anforderung ist, dass das Generatorpoynom $X^{n}-1$ teilt (wobei n die Länge des Codes ist). Um die anonyme Frage vom 2. Dez. 2012 oben zu beantworten: solche Polynome findet man, in dem man $X^{n}-1$ in Primfaktoren zerlegt (über $F_{2}[X]$). Aus den Primfaktoren sucht man sich solche heraus, deren Wurzeln im Zerfällungskörper der Form $x-\zeta ^{j}$ mit möglichst vielen aufeinander folgenden j sind (wg. BCH-Schranke). Das ist hier sehr salopp ausgedrückt. Mehr dazu, viel besser und viel genauer in jedem Buch über algebraische Codierungstheorie, z.B. Anton Betten, Codierungstheorie, Berlin Heidelberg 1998 (ISBN 3-540-64502-0) oder Heise/Quattrocchi, Informations- und Codierungstheorie, Berlin Heidelberg 1983, ISBN 3-540-12774-7.

Die "Optimierung auf Burst-Fehler" kommt dadurch zustande, dass der Rest bei der Polynomdivision immer einen kleineren Grad hat als der Divisor. Deshalb werden alle Fehlerpolynome mit kleinerem Grad als der Divisor (das Generatorpolynom) immer erkannt. Da der Code zyklisch ist, kann man das entsprechende Bitmuster an jede Stelle des Codes verschieben.

---aw- (Diskussion) 18:58, 22. Jun. 2013 (CEST)

"P(x) nicht zerlegbar" P(x) muss ein Primitives Polynom, Irreduzibles Polynom sein. Was das bedeutet verstehe ich nicht. Ich muss es 2012 als "nicht zerlegbar" gedeutet haben. --Moritzgedig (Diskussion) 16:26, 25. Jun. 2013 (CEST)

Ein primitives Polynom ist insbesondere irreduzibel, und das bedeutet, dass es sich nicht in "einfachere" Polynome zerlegen lässt (siehe die von Dir zitierten Artikel). Die "Deutung" war also schon richtig. Ich wüßte aber gerne, wer denn behauptet, dass CRCs nur solche seien, deren Generator von der Form P(x)*(x+1) sind? Es sind in der Tat viele CRCs genau so gebaut (insbesondere die mit MHD = 4), aber das ist keineswegs die Definition eines CRCs. Die englische WP (http://en.wikipedia.org/wiki/Cyclic_redundancy_check) läßt sich über Generatorpolynome dieser "Bauart" aus, aber da geht es darum, die Eigenschaften so konstruierter Codes zu klassifizieren. Es wird nicht behauptet, dass nur diese als CRC bezeichnet werden dürften. Ein CRC-Verfahren ist eine technische Anwendung eines Zyklischen Codes. Punkt. Kurzum: die Behauptung, der Artikel sei falsch, ist m.E. nicht haltbar. ---aw- (Diskussion) 23:08, 25. Jun. 2013 (CEST)

[2] seite 67; [3]; [4] seite 4

Blockkodes > Zyklischekodes > CRC; CRC kodes sind im besonderen jene zyklischen kodes die alle Burstfehler einer bestimmten Länge finden. Ich habe selber schon Zyklischekodes "entwickelt" die keine CRC waren, sondern auf korrektur von Einzelfehlern spezialiesiert sind. --Moritzgedig (Diskussion) 10:12, 26. Jun. 2013 (CEST)

Beispiel optimiert zu früh

Wenn man den Text mit dem englischen Text vergleicht, dann fällt auf, daß im Englischen wirklich bitweise dividiert wird. Auch wenn da bei Zwischenwerten führende #0'en stehen. Das würde es etwas klarer machen, wenn man dies erst strikt so durchführt und anschliessend ausführt, dass man führende #0'en einfach weiterreichen kann und erst wieder wirklich dann dividieren muß, wenn man wieder eine führende #1 erreicht hat. (nicht signierter Beitrag von 193.0.246.4 (Diskussion) 15:16, 5. Feb. 2015 (CET))

Abschnitt Zwei isolierte Einbitfehler

[...] Da $G(x)$ nicht durch $x$ teilbar sein kann [...] Woraus folgt das formal? Vermutlich will man irreduzibel, ungleich 0 und ungleich $x$, oder? Falls das schon wo stehen sollte (ich hab's nicht gefunden), sollte es hier nochmals erwähnt werden. Xlae (Diskussion) 09:15, 10. Mär. 2015 (CET)

CRC versus "normaler" Prüfsumme

Diese Erklärung lässt nicht erkennen was die CRC gegenüber einer normalen Prüfsumme "besonders" macht. Es ist kein Unterschied zu erkennen. Dieser Artikel ist somit redundant. (nicht signierter Beitrag von 91.141.2.124 (Diskussion) 11:38, 19. Jun. 2016 (CEST))

Rest mit Taschenrechner ein anderer?!

Es ist darauf zu achten, dass es sich bei den Einsen und Nullen der Kommunikation mit CRC nicht um die Repräsentation einer Zahl, sondern um ein Polynom handelt. Das bedeutet, dass die Modulodivision mit Binärzahlen (oder Zahlen allgemein) beispielsweise mit dem Taschenrechner nicht auf das richtige Ergebnis führt.

Nach meinem Verständnis ist aber jede Zahl ein Polynom. Weshalb sollte deswegen die Berechnung des Taschenrechners falsch sein? Eine Polynomdivision ist nichts anderes als eine schriftliche Division. Ist mir neu das Taschenrechner und schriftliche Division da unterschiedliche Ergebnisse ausspucken... --Sebi2020 (Diskussion) 16:36, 18. Jan. 2017 (CET)

Ich habe nicht ganz verstanden, was du meinst, aber mMn ist das so gemeint: Wenn man z. B. 1,0,1 und 1,1 als Polynome $x^{2}+1$ und $x+1$ auffasst, dann ist das erste durch das zweite ohne Rest teilbar; als Zahlen 5 und 3 aufgefasst aber nicht. Grüße -- HilberTraum (d, m) 20:08, 18. Jan. 2017 (CET)

Und ich kann dir nicht folgen, da das für mich nicht ohne Rest Teilbar ist:

  x^2 +1 : (x+1) = x - 1
-(x^2 +x)
 --------
      -x + 1
    -(-x - 1)
     --------
           2 <= Rest

Sowie:

  101 : 11 = 1
-(011)
 -----
  010 (2) <= Rest

--Sebi2020 (Diskussion) 20:15, 26. Jan. 2017 (CET)

Du musst beachten, dass die Polynome Koeffizienten modulo 2 haben, das heißt x + 1 und x - 1 ist dasselbe Polynom, außerdem ist 2 = 0, also gilt (x+1)(x+1) = x² + 2x + 1 = x² + 1. Also ist x² + 1 geteilt durch x + 1 gleich x + 1, ohne Rest. -- HilberTraum (d, m) 20:47, 26. Jan. 2017 (CET)

Ich versteh ehrlich gesagt nicht ganz, was Division mod 2 bedeutet? Das wird im artikel auch nicht klar gestellt. Heißt das jetzt das man die Daten durch das generator Polynom teilt und das Ergebnis mod 2 rechnet, oder rechnet man vorher die Daten Mod 2 und teilt dann, oder rechnet man Rest mod 2? Das wird überhaupt nicht deutlich. Vor allen gibt es eigentlich keine Division Modulo n, ist eigentlich nur für Addition und Multiplikation definiert. Bsp: 3= 3 mod 6 = (2/2 * 3) mod 6 = (3*2) / 2 mod 6 = 0/2 = 0 ---Sebi2020 (Diskussion) 16:41, 5. Mär. 2017 (CET) Sebi2020 (Diskussion) 16:41, 5. Mär. 2017 (CET)

Definitionen unklar

Der Pseudocode ist leider sehr unverstaendlich:

Was ist n? hier fehlt eine Definition. CRC32 hat ein Generatorpolynom vom Grad 32 also 33 Koeffizienten.

Was ist das "naechste" Bit aus dem Datenstrom? Vermutlich das naechste Bit beginnend beim MSB und dann pro Iteration ein weiter in Richtung LSB? Hier fehlt eine Definition!

Wenn das Schieberegister beim CRC32 'nur' 32-Bit lang ist, wie dann das bitsweise xor mit einem 33 Bit langen Erzeugerpolynom gebildet? Das ist voellig unklar. (nicht signierter Beitrag von 80.152.50.109 (Diskussion) 16:51, 24. Jan. 2017 (CET))

CRC - Prüfung als Kopierschutz

Ist es möglich, dass die CRC-Prüfung als Kopierschutz für DVD's eimegsetzt wurde? Wenn der DVD-Rekorder auf eine CRC-Prüfung verzichetet, der Computer aber nicht, dann können DVD's vom PC nicht gelesen werden. Anders formuliert: Werden absichtlich CRC-Fehler auf die DVD gebrannt, kann die DVD abgespielt, aber nicht kopiert werden. --Rasmusklump (Diskussion) 23:45, 18. Nov. 2017 (CET)

Nachfrage: Umsetzung

Der Pseudocode in der Umsetzung sagt sinngemäß "Wenn das MSB (höchstwertiges Bit) ungleich dem zweithöchstwertigen Bit, dann tue leftshift und XOR, ansonsten nur leftshift".

Ich habe etwas die Stirn über die Bedingung gerunzelt, denn ich kenne die Bedingung als "Wenn das MSB gesetzt ist". Mag das mal jemand prüfen? Oder kommt es gar aufs gleiche raus? --178.10.214.14 16:15, 6. Jun. 2018 (CEST)

CRC-CCITT Implementierung in der Programmiersprache Pascal/Delphi

Dieser 11:49, 29. Jul. 2020‎ von "VermCad" eingeführte Beispielcode enthält m. E. eine falsche Zeile:

...
CRC := CRC xor (B shl 8);
...

Der Ausdruck "B shl 8" heißt ja wohl, dass der Inhalt des Bytes B achtmal nach links verschoben wird. Beim jedem Linksshift tritt das höchstwertige Bit nach links aus und ist verloren. An die niederwertigste Stelle des Bytes wird ein Null-Bit eingeschoben. Das alles achtmal, sodass das Byte B auf jeden Fall anschließend Null ist. Wird dann das Wort CRC mit dem entstandenen Null-Byte XOR-verknüpft, ändert sich an dessen Wert genau nichts. Wozu also dieses Statement?
Vermutlich müsste die Variable B vom Typ Word sein, damit dann die XOR-Verknüpfung zwischen dem höherwertigen Byte vom Wort CRC und dem von B stattfindet. Ich hoffe, dass der Compiler aber nichts gegen die Zuweisung B := Buffer[I] hat (Zuweisung eines Bytes an eine Word-Variable). Der Typ von Buffer ist hier nicht deklariert, nur in der Überschrift als "Array of Byte" erwähnt.

Alternativ könnte man folgende Formulierung (hier als Pseudocode) schreiben:

...
CRC := HighByteOf(CRC) xor B;
...

--Golter (Diskussion) 13:07, 13. Mär. 2021 (CET)

Alle Arithmetik, auch Bitschnipselei, findet vom Prinzip her 32bittig statt (früher 16bittig, aber auch historisch nie 8bittig). Entsprechend der Zielgröße wird dann rückkonvertiert oder, in vom Compiler beweisbaren Fällen, tatsächlich hin zu einem kürzeren Ergebnistyp optimiert. Jedenfalls liefert (B shl 8) dasselbe wie (B * 256). – Hi…ma 22:21, 4. Sep. 2021 (CEST)

Baustein AV

Für die Sätze

Nun wird der Rahmen mit Anhang von links her durch das Generatorpolynom dividiert. Dabei wird ausschließlich das exklusive OR (XOR) verwendet.

brauchen meiner Meinung nach eine Verbindung, die beschreibt, warum XOR eine Polynomdivision darstellt. Ich weiß es leider nicht. (nicht signierter Beitrag von 62.99.132.26 (Diskussion) 16:11, 14. Apr. 2022 (CEST))