Forum: Mikrocontroller und Digitale Elektronik CRC-Algorithmus nachvollziehen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Danish B. (danishbelal)


Bewertung
0 lesenswert
nicht lesenswert
Guten Tag,

ich beschäftige mich derzeit mit dem CRC-Verfahren.
Ich habe verstanden, dass die Eingangsdaten als eine 'große Zahl' 
interpretiert und modulo dem Generatorpolynom gerechnet wird. Das 
Ergebnis ist dann der Prüfwert.

Leider habe ich nicht verstanden, wie der Algorithmus über 
Bitschiebereien, den Modulo berechnet.

Hier ist 'der Algorithmus':
1
Schieberegister := 0000… (Startwert)
2
solange Bits im Datenstrom verbleiben:
3
  falls  das am weitesten links stehende Bit vom Schieberegister
4
        ungleich dem nächsten Bit (z. B. beginnend mit dem MSB, und dann jeweils eins weiter rechts pro Iteration) aus dem Datenstrom ist:
5
    Schieberegister := (Schieberegister linksschieben um 1, rechtes Bit 0)
6
                       xor CRC-Polynom (ohne den Term vom Grad n+1)
7
  andernfalls:
8
    Schieberegister := Schieberegister linksschieben um 1, rechtes Bit 0
9
  nächstes Bit im Datenstrom
10
Schieberegister enthält das Ergebnis.

Quelle: 
https://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung#Umsetzung


Man könnte den umgangssprachlich auch folgendermaßen formulieren:
1
(1) Schieberegister = 0
2
(2) Takte ein Bit des Bitstromes (von rechts nach links) in das Schieberegister ein.
3
    (2a) Ist links ein '1'-Bit herausgefallen, dann XOR'e das SR mit dem Gen-Polynom
4
(3) Wiederhole (2) bis keine Daten mehr vorhanden sind
5
    Der CRC-Wert (Ganzahldivisionsrest) steht nun im Schieberegister.

Nur warum führt obiger Algo dazu, den Modulo eines Bitstroms (gegen ein 
Generator-Polynom) zu berechnen?

von Falk B. (falk)


Bewertung
2 lesenswert
nicht lesenswert
@ Danish Belal (danishbelal)

>Schieberegister := 0000… (Startwert)

Kann auch anders ein, je nach CRC Verfahren.


>Quelle:
>https://de.wikipedia.org/wiki/Zyklische_Redundanzp...

Naja, als C-Code ist das besser lesbar. Siehe CRC und der Klassiker.

http://www.ross.net/crc/download/crc_v3.txt

>Nur warum führt obiger Algo dazu, den Modulo eines Bitstroms (gegen ein
>Generator-Polynom) zu berechnen?

Puhh, da mußt du die Mathematiker fragen, vielleicht steht das auch im 
obigen Artikel.

von R. M. (n_a_n)


Bewertung
0 lesenswert
nicht lesenswert

von Joachim B. (jar)


Bewertung
0 lesenswert
nicht lesenswert

von Danish B. (danishbelal)


Bewertung
0 lesenswert
nicht lesenswert
Falk B. schrieb:
> Naja, als C-Code ist das besser lesbar. Siehe CRC und der Klassiker.
>
> http://www.ross.net/crc/download/crc_v3.txt


Danke für die Links, den Artikel habe ich angefangen und werde ihn 
vermutlich morgen zu Ende durcharbeiten.

von Danish B. (danishbelal)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Guten Abend,

ich sitze nun seit einer Weile an der Implementierung des 
CRC16-Algorithmus.
Die Ergebnisse meiner Implementierung decken sich nicht mit der des 
Online-Rechners [1].

Könnte sich jemand meinen Code ansehen und mir verraten, wo der Fehler 
sitzt?
Ziel des ganzen ist es, einen ATECC508A anzusteuern. Das Datenblatt dazu 
liegt [2].


[1] https://www.lammertbies.nl/comm/info/crc-calculation.html
[2] http://ww1.microchip.com/downloads/en/DeviceDoc/20005927A.pdf
1
#include "crc.h"
2
3
uint16_t crc16_calc(const uint8_t *data, const uint8_t data_length, const uint16_t crc_mask)
4
{
5
    uint16_t crc = 0x0000;
6
    for(int8_t i = 0; i < data_length; ++i)
7
    {
8
        // LSB First
9
        for(int8_t bit_offset = 7; bit_offset >= 0; bit_offset--)
10
        {
11
            uint8_t next_bit = ( data[i] >> (7 - bit_offset) ) & 0x01;
12
            
13
            // Check if LSB is '1'
14
            if(crc & 0x01)
15
            {
16
                crc = (crc >> 1) | (next_bit << 15 );
17
                crc = crc ^ crc_mask;
18
            }
19
            // If not, clock in the next data bit
20
            else
21
            {
22
                crc = (crc >> 1) | (next_bit << 15 );
23
            }
24
        }
25
    }
26
    return crc;
27
}

Aufgerufen wird dieser folgendermaßen:
1
    [...]
2
    uint8_t daten[] = {0x55, 0x55, 0, 0 };
3
    uint16_t crc = crc16_calc(daten, 4, 0x8005);
4
    printf("CRC: 0x%04x\n", crc);
5
    [...]

====================

Das führt zu folgender Ausgabe auf dem Terminal:
1
CRC: 0xc27c

von Detlef _. (detlef_a)


Bewertung
1 lesenswert
nicht lesenswert
Kann schwierig sein: Welche Richtung werden die Bits geschoben, welches 
Polynom, welcher Startwert.

Hier
Beitrag "Yet another CRC32 Code"

steht C-source die das gleiche wie Lammertbies rauskriegt, allerdings 
für 32 Bit. Vllt. hilfts ja.

Cheers
Detlef

von Danish B. (danishbelal)


Bewertung
0 lesenswert
nicht lesenswert
Die Datenbits werden nach rechts geschoben,
Startwert ist 0,
Polynom ist 0x8005

Lammertbies bietet seinen Code ja auch als Lib an, diesen gibt es aber 
nur in der Variante mit der Look-Up Tabelle. Eine solche werde ich 
schlussendlich wahrscheinlich auch nutzen, aber davor sollte der 
einfache Algorithmus gerne laufen.

Die einzige CRC-Information aus dem Datenblatt ist das Generatorpolynom 
(und das es CRC16 ist natürlich).

von Detlef _. (detlef_a)


Bewertung
1 lesenswert
nicht lesenswert
Ich brauchte Spaß und habe den CRC16 Code nachgelegt. Kommt dasgleiche 
raus wie bei Lammertbies.

Hier
Beitrag "Yet another CRC32 Code"

Man muss das Polynom spiegeln, dann gehts.

math rulez!
Cheers
Detlef

: Bearbeitet durch User
Beitrag #5285460 wurde vom Autor gelöscht.
von Danish B. (danishbelal)


Bewertung
0 lesenswert
nicht lesenswert
Vielen Dank!

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]
  • [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.