3-bit CRC Berechnung

Alex Gast #7265047
Lesenswert?
• ▲
▼ 
Guten Tag,

Kann vielleicht einer mit dem C Code hierfür helfen?
Habe selbst hunderte Varianten probiert, aktuell keine Ideen mehr.

Der kurze Beitrag und kein Eigenvorschlag sind der Frustration 
geschuldet.

Schönes Wochenende und liebe Grüße
Angehängte Dateien:
Beitrag melden Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Markierten Text zitieren Antwort Antwort mit Zitat
Falk B. #7265478
Lesenswert?
• ▲
▼ 
Alex schrieb:
> Kann vielleicht einer mit dem C Code hierfür helfen?
> Habe selbst hunderte Varianten probiert,

Das wage ich zu bezweifeln. Man könnte es auch eine glatte Lüge nennen.

> aktuell keine Ideen mehr.

Doch. Jammern und einen auf dumm machen.

> Der kurze Beitrag und kein Eigenvorschlag sind der Frustration
> geschuldet.

Jaja, schöne Ausrede.

> Schönes Wochenende und liebe Grüße

Gleichfalls!

Ansonsten, siehe CRC. HIer gibt es auch eine CRC-Funktion, die kann 
man leicht auf das Polynom anpassen.

Beitrag "Re: Onewire + DS18x20 Library"
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Jester Gast #7265528
Lesenswert?
• ▲
▼ 
MaWin schrieb:
> Immer wieder diese freundlichen und hilfsbereiten Leute im Forum hier.

Auch Falk hat dem TO den entscheidenden Tipp gegeben - neben meinem 
Hinweis auf die Wikipedia.

Eine Lösung ‚frei Haus‘ zu liefern hilt dem TO bei seinen Hausaufgaben 
jedenfalls nicht: Die aufgezeichneten Beispiele sind sehr einfach 
nachvollziehbar - und ich bin der Ansicht, diese kleine Mühe sollte der 
TO sich schon selbst machen.

Aber ich kann mich natürlich auch täuschen...
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Dieter Gast #7265886
Lesenswert?
• ▲
▼ 
Hier ist eine ausführliche Erklärung zur CRC Berechnung:

http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html

Um die PSI5 3-Bit CRC zu implementieren reicht im Prinzip "3. Concept of 
the CRC shift register". Dazu dann aus der PSI5 Spezifikation "3.2.2 
Error Detection" und man bekommst das mit ein paar Zeilen C Code hin, 
der dann auch die gewünschten Ergebnisse liefert (das Polynom ist 0x03, 
die Registerlänge natürlich 3 Bit, initialisiert wird das Register mit 
0x7 und die drei "0" Bits laut der PSI5 Spezifikation sollte man nicht 
vergessen.)
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Gerald K. #7266181
Lesenswert?
• ▲
▼ 
Vielleicht hilft dieser Link weiter:

https://books.google.at/books?id=qydjLSpxqlYC&pg=PA62&lpg=PA62&dq=crc+schieberegister&source=bl&ots=p3vVZXvhT2&sig=ACfU3U0VCoM1tI4c-DZrLWEwQfG24GtLEQ&hl=de&sa=X&ved=2ahUKEwjYiZmtnsz7AhWjXvEDHQvsCfkQ6AF6BAglEAI#v=onepage&q=crc%20schieberegister&f=false

Man braucht nur die Schaltung in eien C-Code umsetzen.

Man braucht sich nur an die Anleitung zu halten. Bei Bedarf kann ich 
eine Anleitung zur Umsetzung geben.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Gerald K. #7266232
Lesenswert?
• ▲
▼ 
Falk B. schrieb:
> Gerald K. schrieb:
>
>> Man braucht nur die Schaltung in eien C-Code umsetzen.
>
> **Ach so, NUR einfach umsetzen. Na dann** . .  .
>> Man braucht sich nur an die Anleitung zu halten. Bei Bedarf kann ich
>> eine Anleitung zur Umsetzung geben.
>
> Was DU so alles kannst, beeindruckend!



Eine Anleitung zur schnellen (Implementierung) bitweisen Lösung in 
Pseudsprache:

1. initalisierung:
1
{

2
  C0=0;

3
  C1=0;

4
  C2=0;

5
}


2. Schrittweise (bitweise) CRC3 Berechnung:
1
{

2
  Temp= LSBeingangsdatenbit xor C0;

3
  C1=C2;

4
  C0=C2 xor Temp;

5
  C2=Temp;

6
}


Nächstes Eingangsbit ins LSB schieben und Schritt 2 bis zum letzten 
Eingangsbit wiederholen.

Dann steht der CRC3 in den Bits C2, C1 und C0 zur Verfügung.

Der Pseudocode braucht nur in die gewünschte Sprache ASM,C, Pascal, VHDL 
... übersetzt werden.

Durch byteweise Verarbeitung wird die Programmausführung schneller, ist 
aber vom Algorithmus anspruchsvoller.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Gerald K. #7266246
Lesenswert?
• ▲
▼ 
Falk B. schrieb:
> Gerald K. schrieb:
>
>> Durch byteweise Verarbeitung wird die Programmausführung schneller, ist
>> aber vom Algorithmus anspruchsvoller.
>
> Bei nur 10 Bit Telegrammlänge könnte man auch einfach eine Tabelle mit
> 1024 Einträgen machen. Aber auch die muss erstmal berechnet werden 8-)

Geht dann natürlich schneller, dafür ist der Speicheraufwand (2^10 x 
3Bit) für den Programmcode (nur Tabelle) viel größer. Mit eiem Trick 
(1/2 Bit pro Eintrag) kommt man mit 512 Bytes aus.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Dieter Gast #7266259
Lesenswert?
• ▲
▼ 
Unglaublich wie hier über ein paar triviale C Code Zeilen diskutiert 
wird.

Man könnte das z.B. so machen (Optimieren kann man das später beliebig):

1
/*

2


3
  PSI5 3-bit CRC

4


5
  see http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html

6


7
  "3. Concept of the CRC shift register"

8


9
  Implement Step 2:

10


11
    Shift in the input stream bit by bit. If the popped out MSB is a '1',

12
    XOR the register value with the generator polynomial.

13


14
  Input: 3-bit CRC register (uint8_t crc)

15
         one data bit (bool bBit)

16


17
  Return: updated CRC register

18


19
*/

20


21
uint8_t psi5_crc_3bit(uint8_t crc, bool bBit)

22
{

23
  const uint8_t polynom = 0x03; /* g(x)= 1 + x + x^3  */

24


25
  /* shift in data bit */

26


27
  crc = (crc << 1) | (bBit ? 0x01 : 0x00);

28


29
  /* check if popped out MSB of 3-bit register is set */

30


31
  if(crc & 0x08)

32
    crc = crc ^ polynom;

33


34
  /* 3-bit register */

35


36
  return crc & 0x07;

37
}


Den CRC Register beim Start korrekt zu initialiseren und die Funktion 
für die einzelnen Datenbits aufzurufen sollte ja klar sein.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Dieter Gast #7266293
Lesenswert?
• ▲
▼ 
Gerald K. schrieb:
> Nach dem wir genügend Vorarbeit geleistet haben kann Alex einmal den
> Code ausprobieren. Dann werden wir sehen.

Bei meinem Test mit obigen Code kam das raus was in "3-bit_CRC.png" zu 
sehen ist. Den Hinweis mit der richtigen Initialisierung des CRC 
Register und den drei zusätzlichen "0" Bits haben ich bereits gegeben.

Man kann das Ganze auch ohne Programmierung mit dem passenden Tool, z.B. 
CRC RevEng verifizieren.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Dieter Gast #7266302
Lesenswert?
• ▲
▼ 
Gerald K. schrieb:
>
> Für x^0 gibt es kein Register. Dann sind es wieder 3.

Nein, die höchste Stelle des Polynom ist hier überflüssig. x^0 ist das 
LSB des Polynom. Im Bild aus der PSI5 Spezifikation sieht man das gut 
(auch wenn die Datenbits von links rein kommen, von rechts wäre es noch 
offensichtlicher).
Angehängte Dateien:
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Gerald K. #7266314
Lesenswert?
• ▲
▼ 
Es zählen nur die Terme mit den Rückkopplungen über xor.

Das Polynom bezieht sich nicht auf die Bit, sondern auf die 
Rückkopplungen.

Mit ist noch ein Unterschied zur Schaltung im Link

https://books.google.at/books?id=qydjLSpxqlYC&pg=PA62&lpg=PA62&dq=crc+schieberegister&source=bl&ots=p3vVZXvhT2&sig=ACfU3U0VCoM1tI4c-DZrLWEwQfG24GtLEQ&hl=de&sa=X&ved=2ahUKEwjYiZmtnsz7AhWjXvEDHQvsCfkQ6AF6BAglEAI#v=onepage&q=crc%20schieberegister&f=false

aufgefallen. Die Schieberichtung ist umgekehrt.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Alex Gast #7266993
Lesenswert?
• ▲
▼ 
Guten Tag,

nachdem ich den Anfang vom Thread gelesen habe, habe ich länger nicht 
mehr reingeschaut.
Vielen Dank an alle, die sich zum Thema beteiligt haben.

Hier ist meine Lösung, die ganz sicher funktioniert.
Das ist nicht komplett meine, aber ich habe es soweit angepasst, dass es 
passt.
In meinem Fall sind es 20 Bits Nutzdaten.
Kann jeder nachrechnen.
1
uint8_t crc_calc(uint32_t Input) {

2
 volatile uint8_t CRC[3]={1,1,1};

3
 volatile uint8_t CRCa[3];

4
    

5
for(int i=0; i<=22 ; i=i+1){

6
    CRCa[2]= CRC[1];

7
    CRCa[1]= CRC[0]^CRC[2];

8
    CRCa[0] = CRC[2]^((Input >> i) & 0x01);

9
    crc = ((CRCa[2] << 2) | (CRCa[1] << 1) | (CRCa[0] & 0x01));

10
}

11
return crc;

12
}

13


14
uint32_t Daten = 0x7FFFFF;

15
uint8_t crc = 0;

>Vielleicht hat jemand den Code parat

Das war so mein Gedanke

Schöne Grüße
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Alex Gast #7267034
Lesenswert?
• ▲
▼ 
Übertragungsfehler, sorry.

1
uint32_t Daten = 0x000;

2
uint8_t crc = 0;

3


4


5
uint8_t crc_calc(uint32_t Input) {

6
 volatile uint8_t CRC[3]={1,1,1};

7
 volatile uint8_t CRCa[3];

8


9
for(int i=0; i<=12 ; i=i+1){

10
        CRCa[2]= CRC[1];

11
        CRCa[1]= CRC[0]^CRC[2];

12
        CRCa[0] = CRC[2]^((Input >> i) & 0x01);

13


14
        CRC[0] = CRCa[0];

15
        CRC[1] = CRCa[1];

16
        CRC[2] = CRCa[2];

17


18
        crc = ((CRCa[2] << 2) | (CRCa[1] << 1) | (CRCa[0] & 0x01));

19
    }

20
    return crc;

21
}

22


23


24


25
int main(void)

26
{

27


28
crc = crc_calc(Daten);

29
printf("0x%x\n", crc);

30


31
    for(;;)

32
    {

33


34
    }

35
}
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Falk B. #7268178
Lesenswert?
• ▲
▼ 
Alex schrieb:

> Hier ist meine Lösung, die ganz sicher funktioniert.

Damit wäre das Problem doch gelöst.

> Das ist nicht komplett meine, aber ich habe es soweit angepasst, dass es
> passt.
> In meinem Fall sind es 20 Bits Nutzdaten.
> Kann jeder nachrechnen.uint8_t crc_calc(uint32_t Input) {
>  volatile uint8_t CRC[3]={1,1,1};
>  volatile uint8_t CRCa[3];

Wozu soll volatile gut sein? Braucht hier keiner.
Und warum nutzt du zwei Array die die CRC? Das kann man zwar machen, ist 
aber weder üblich noch von Vorteil.

> for(int i=0; i<=22 ; i=i+1){
>     CRCa[2]= CRC[1];
>     CRCa[1]= CRC[0]^CRC[2];
>     CRCa[0] = CRC[2]^((Input >> i) & 0x01);

Naja, das funktioniert zwar, ist aber sehr akademisch.

>     crc = ((CRCa[2] << 2) | (CRCa[1] << 1) | (CRCa[0] & 0x01));

Und hier muss das Array wieder in einen normalen 3 Bit Wert umgewandelt 
werden. Warum muss das bei jedem Schleifendurchgang erfolgen? Das reicht 
auch auch EINMALIG nach der Schleife.

Wenn man es gleich richtig macht, entfällt das alles. Siehe 
Bitmanipulation.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Falk B. #7268180
Lesenswert?
• ▲
▼ 
Hier meine Version mit normaler Bitmanipulation.

1
#include <stdint.h>

2


3
uint8_t crc3(uint16_t data) {

4
    

5
    uint8_t i, crc, poly=0x3;

6


7
    crc   = 0x7;

8
    data &= 0x3FF;

9
    for (i=0; i<13; i++) {

10
      if (crc & 0x04) {

11
        crc <<= 1;            

12
        if (data & 1) crc |= 0x01;        // copy LSB to LSB

13
        crc ^= poly;

14
      } else {

15
        crc <<= 1;            

16
        if (data & 1) crc |= 0x01;        // copy LSB to LSB

17
      }

18
      data >>= 1;

19
    }

20
    return crc & 0x7;

21
}

22


23
int main(void) {

24


25
    uint16_t crc;

26


27
    crc = crc3(0x000);   // CRC 6

28
    crc = crc3(0x0CC);   // CRC 3       

29
    crc = crc3(0x151);   // CRC 0

30
    crc = crc3(0x1E0);   // CRC 3

31
}
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren