www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik CRC-CCITT Testmuster zur Überprüfung des Algorithmus


Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo.

Ich habe ein Modul zur Berechnung von CRC-CCITT (16-Bit CRC) 
geschrieben.
Jetzt will ich das ganze auf Herz und Nieren prüfen...

Ich habe gehört, dass es spezielle test-pattern für solche Sachen gibt.

Wo bekommt man sowas her?
Gibts da was als Freeware, oder in Tabellenform?

Vielen Dank bereits im vorraus.

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sieht so aus, als ob bei dem Thema nicht viel Erfahrung da ist...

Autor: Hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gähn... weil das der x-te CRC thread ist. google ist Dein Freund
und man kann in der "Erweiterten Suche" auf mikrocontroller.net
einschränken. Selbst die Suche im Forum kann man nicht als
schlecht bezeichnen.

In

    Beitrag "Hilfe bei CRC!"

gibt es einen link auf pycrc, welcher parametrisierbar ist.

Als Default verwendet pycrc als "Check String" 123456789,
ist allerdings auch mit der  --check-string - Option
einstellbar.

Ja, es gibt Standards, in denen für spezielle CRC
Testvektoren mit angegeben werden, aber dazu ist die Frage
bzgl. der Anwendungsdomäne halt recht unspezifisch.

VG,
Hans

PS:
$ pycrc.py --model=ccitt
0x29b1
$ pycrc.py --model=ccitt --check-string="123456789"
0x29b1
$ pycrc.py --model=ccitt --check-string="1234567890"
0x3218

PPS: Anfangswerte, 8/32-Bit-CRC-Modelle, links/rechts-rum:
alles via Kommandozeile einstellbar.

Autor: Johnny B. (johnnyb)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://zorc.breitbandkatze.de/crc.html

(ich musste CRC-CCITT anklicken und "nondirect" wählen, damit das 
Ergebnis mit den Testwerten unten übereinstimmt; also Initialwert FFFF 
und nondirect oder 1D0F und direct)

Der String "123456789" (ohne Anführungszeichen) sollte 0xE5CC ergeben.
256 mal ein "A" sollte 0xE938 ergeben.
Werden keine Daten übergeben, sollte 0x1D0F rauskommen.

Weiss leider nicht mehr, wo ich diese Angaben ursprünglich her hatte 
bzw. scheint die betreffende Website nicht mehr zu existieren.


Edit: Guuuuut gibts noch die Wayback machine!
Habe die Abhandlung mit den Testwerten wieder gefunden:
http://web.archive.org/web/20071229021252/http://w...

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für die Antworten,

aber ich brauch "nur" ne Tabelle mit Testmustern.
Also keine berechneten CRC-Liste von 0x0000 bis 0xFFFF, sondern ich 
dachte an mathematisch (bzw. statistisch) ermittelte Testmuster, die 
eine größtmögliche Funktionsüberprüfung bietet.

Ich habe bei google schon etwas in der Art gefunden, aber dabei handelt 
es sich um eine Patentanmeldung.

Kennt Ihr ne Alternative?

Wiederum Danke bereits im vorraus.

Autor: Hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> aber ich brauch "nur" ne Tabelle mit Testmustern.

Dann generiere sie Dir doch mit der oben referenzierten
Webseite bzw. pycrc. Wie johnnyb bemerkte,
ist da das eingesetzte Modell nochmal abzuklären,
"ccitt" (alleine) kann falsch sein.

>> Also keine berechneten CRC-Liste von 0x0000 bis 0xFFFF, sondern ich

Die CRC-CCITT, welche Bytes als Eingabe hat, hat die Signatur
(16Bit-CRC-State) x (8Bit-Input) -> (16Bit-CRC-State).
Für einen vollständigen Test käme ich daher auf eine CRC-Liste
mit 2^24 (etwa 16 Mio) Zeilen....

>dachte an mathematisch (bzw. statistisch) ermittelte Testmuster, die
>eine größtmögliche Funktionsüberprüfung bietet.

Zu wenig Infos über die Testanforderungen und den Code!

Mache ich Blackbox-Testverfahren, interessiert mich die
Implementierung nicht und ich argumentiere kurzgefaßt wie folgt:
- ich gebe einen Test vor und das Programm errät den richtigen
   Wert mit der Wahrscheinlichkeit 1/2^16. Bei einem zweiten Test
   mit richtigem Ergebnis ist die Wahrscheinlichkeit, dass zweimal
   richtig geraten wurde 1/2^32, etc....

Bin ich ein Whitebox Tester, will ich eine größtmögliche Abdeckung
des Codes bzw. der Pfade und der zugegriffenenen Daten haben:

Falls eine Bit-Implementierung vorliegt, reichen dann wenige
Tests, hat man eine CRC-Tabellenimplementierung,
wäre ein Zugriff auf alle Tabellenfelder sinnvoll. Verschiedene 
Programmpfade
kommen bei einer CRC-Tabellenimplementierung i.d.R. nicht vor.
Vermutlich etwa 260 Tests...

>> Kennt Ihr ne Alternative?
Bei partiell evaluierten CRC-Funktionen wird vorher sowieso eine
andere mathematische Spezifikation/Gleichungssysteme generiert, welche
vom Code her erstmal unverständlich ist, aber wenn man beweist, dass
die Implementierung die Spezifikation impliziert, hat man sein Modul
bewiesen ;-)  Das wird dann als "größtmögliche Funktionsüberprüfung"
verstanden.

Je nachdem wie sicherheitskritisch der Einsatz der Routine (Medizin, 
AKW..)
ist, muss beim Hochfahren oder periodisch die Integrität des Systems
und im Fehlerfall eine "graceful degradation" getestet werden...
Aber das wären wieder andere Methodiken, weil man
in seinem Fehlermodell z.B. auch noch gekippte (Flash-)Bits im
Hinterkopf hat...

>Ich habe bei google schon etwas in der Art gefunden, aber dabei handelt
>es sich um eine Patentanmeldung.
Ich nehme an, Du erwartest keinen Kommentar dazu...

VG,
Hans

Autor: subitus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die oben genannte Abhandlung über die CRC-Testwerte (... 
http://www.joegeluso.com/software/articles/ccitt.htm ...) ist mit vielen 
Fehlern durchsetzt und sollte nicht als Referenz herangezogen werden! 
Diese Seite existiert nicht ohne Grund nur noch im Webarchiv ;-)

So wird zwischen Good_CRC und Bad_CRC verglichen und die Angaben anderer 
Webseiten zitiert, ohne darauf einzugehen, dass diese 
Prüfsummenunterschiede durch zwei unterschiedliche Methoden der 
Initialwertsetzung herrühren:
  1. direkter Initialwert = CRC-Register wird mit diesem Wert 
vorinitialisiert;
  2. indirekter Initialwert = vor der ersten CRC-Operation wird der 
Initialwert geschoben (dies wird erwähnt)

Zwischen beiden Verfahren kann man problemlos konvertieren. Es gibt also 
kein "Good" oder "Bad", sondern "definiert" und "undefiniert".


Es existieren viele verschiedene viele Theorien zur CRC-Berechung und 
noch mehr Umsetzungen. Und wer denkt, dass das simple Tabellenspringen 
"safe" sei, der irrt gewaltig. Kaum ein Code ohne Fehler - selbst Profis 
rechnen "Müll" zusammen.


Wichtige Randparameter, die ein Entwickler zunächst postulieren sollte:
 - Grad des Generatorpolynoms, das Polynom selber, Initialwert, direkte 
oder indirekte Initialisierung, Eingangsspiegelung, Ausgangsspiegelung, 
finale XOR-Verknüpfung am Ende, dynamische oder statische Berechnung, 
...


Wer eine Sprungtabelle in seinem Code verwendet, sollte sich Gedanken 
über diese machen. Auf welchem Polynom basiert diese Tabelle? Wurde sie 
unter Berücksichtigung von Reflektionsparametern erzeugt? Gerade die 
Ein-/Ausgangsspiegelungen erschweren vielen den Zugang zum Durchblick.


Zur Ausgangsfrage:
In der Regel werden CRC-Algorithmen (ALGORITHMEN!) mit einem Prüfstring 
(Pattern) geprüft - bspw. der übliche Zahlentest ASCII 0x31..0x39. Mit 
diesem Test kann man jedoch eine Sprungtabelle nur unzureichend (!) 
testen - eher die XOR und Shift-Operationen beim Table-Lookup. Also: 
Verifizierung des Algorithmus und der Tabelle - getrennt voneinander. 
Wichtiger als die Tabelle ist der Algorithmus - mit diesem könnte man ja 
die Tabelle generieren und verifizieren. Und ab hier ist dann Black- or 
Whitebox-Test angesagt - das hat Hans prima erläutert.

MfG,
subitus

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielen Dank für Eure Antworten.

Ihr habt mir geholfen.


Eine Frage hab ich allerdings noch...


Wenn man ein CRC von Hand berechnet, dann wird in der Regel beim Polynom 
die führende 1 weggelassen. (Bsp.: Polynom x^16+x^12+x^5+1)
Warum darf man das? Muss man das?

Vielen Dank

Autor: Hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Wenn man ein CRC von Hand berechnet, dann wird in der Regel beim Polynom
>die führende 1 weggelassen. (Bsp.: Polynom x^16+x^12+x^5+1)

Nein.

VG,
Hans

Autor: Nils (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
subitus schrieb:

> [...]
> Prüfsummenunterschiede durch zwei unterschiedliche Methoden der
> Initialwertsetzung herrühren:
>   1. direkter Initialwert = CRC-Register wird mit diesem Wert
> vorinitialisiert;
>   2. indirekter Initialwert = vor der ersten CRC-Operation wird der
> Initialwert geschoben (dies wird erwähnt)


> direkte
> oder indirekte Initialisierung,


Hallo subitus,

Wie sieht denn so eine Rechnung aus, in der "indirekt initialisiert" 
wird?

Ich habe folgendes Problem:

Parameter:
CRC16 (CCITT)
Polynom: 0x1021
Startwert: 0xFFFF
LSB first

Zu übertragende Nachricht: "00 00 08 06 07"

Folgendes habe ich gerechnet:

  F    F    F    F
1111 1111 1111 1111 00 00 08 06 07 oooooooooooooooo
1000 1000 0001 0000 1
---------------------
 111 0111 1110 1111 1
 usw.

Mit dem Ergebnis: Rest = 822E

Das wurde mir von der Breitbandkatze auch als richtiger Wert bestätigt, 
allerdings mit der Option "NON-DIRECT".

Mein Device scheint aber die DIREKTE Variante zu benötigen und 
akzeptiert nur die 62EC als Rest für obige Rechnung.

Was muss ich dafür tun?

Ich habe schon den Startwert von FFFF auf 84CF gesetzt und mit der 
NON-DIRECT-Berechnung die 62EC als Rest rausbekommen. Ist das der 
einzige Weg?
Außer in der von Dir angesprochenen Quelle aus dem Webarchiv, habe ich 
diesen Tipp nirgends gefunden.


Mit freundlichen Grüßen

Nils

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.