CRC-Algorithmus nachvollziehen

[Danish B. (danishbelal)]

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':

Schieberegister := 0000… (Startwert)
solange Bits im Datenstrom verbleiben:
  falls  das am weitesten links stehende Bit vom Schieberegister
        ungleich dem nächsten Bit (z. B. beginnend mit dem MSB, und dann jeweils eins weiter rechts pro Iteration) aus dem Datenstrom ist:
    Schieberegister := (Schieberegister linksschieben um 1, rechtes Bit 0)
                       xor CRC-Polynom (ohne den Term vom Grad n+1)
  andernfalls:
    Schieberegister := Schieberegister linksschieben um 1, rechtes Bit 0
  nächstes Bit im Datenstrom
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) Schieberegister = 0
(2) Takte ein Bit des Bitstromes (von rechts nach links) in das Schieberegister ein.
    (2a) Ist links ein '1'-Bit herausgefallen, dann XOR'e das SR mit dem Gen-Polynom
(3) Wiederhole (2) bis keine Daten mehr vorhanden sind
    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?

[Falk B. (falk)]

@ 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.

[R. M. (n_a_n)]

eine gute Erklärung gibt es hier:

http://www-stud.rbi.informatik.uni-frankfurt.de/~haase/crc.html

[Joachim B. (jar)]

Falk B. schrieb:
> Puhh, da mußt du die Mathematiker fragen

http://www.lokalkompass.de/oberhausen/spass/gedicht-von-heinz-erhardt-d286800.html

nur manchmal sind deren Antworten richtig, helfen aber nicht

http://www.klein-singen.de/statistik/t/Am_ue_santes/ballonfahrer.html

[Danish B. (danishbelal)]

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.

[Danish B. (danishbelal)]

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

#include "crc.h"

uint16_t crc16_calc(const uint8_t *data, const uint8_t data_length, const uint16_t crc_mask)
{
    uint16_t crc = 0x0000;
    for(int8_t i = 0; i < data_length; ++i)
    {
        // LSB First
        for(int8_t bit_offset = 7; bit_offset >= 0; bit_offset--)
        {
            uint8_t next_bit = ( data[i] >> (7 - bit_offset) ) & 0x01;
            
            // Check if LSB is '1'
            if(crc & 0x01)
            {
                crc = (crc >> 1) | (next_bit << 15 );
                crc = crc ^ crc_mask;
            }
            // If not, clock in the next data bit
            else
            {
                crc = (crc >> 1) | (next_bit << 15 );
            }
        }
    }
    return crc;
}

Aufgerufen wird dieser folgendermaßen:

    [...]
    uint8_t daten[] = {0x55, 0x55, 0, 0 };
    uint16_t crc = crc16_calc(daten, 4, 0x8005);
    printf("CRC: 0x%04x\n", crc);
    [...]

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

Das führt zu folgender Ausgabe auf dem Terminal:

CRC: 0xc27c

[Detlef _. (detlef_a)]

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

[Danish B. (danishbelal)]

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).

[Detlef _. (detlef_a)]

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

[Danish B. (danishbelal)]

Vielen Dank!