3-bit CRC Berechnung

[Alex (Gast)]

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

[Jester (Gast)]

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

[Monk (roehrmond)]

Alex schrieb:
> Kann vielleicht einer mit dem C Code hierfür helfen?

Du hast vergessen, den C-Code anzuhängen, zu dem du Hilfe erbittest.

[c-hater (Gast)]

Steve van de Grens schrieb:

> Alex schrieb:
>> Kann vielleicht einer mit dem C Code hierfür helfen?
>
> Du hast vergessen, den C-Code anzuhängen, zu dem du Hilfe erbittest.

Hat er nicht. Er will das wir ihm den liefern. Natürlich für lau.

Ein typischer Nassauer.

[Falk B. (falk)]

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"

[Justin S. (Gast)]

c-hater schrieb:
> Natürlich für lau.

Erwartest Du, dass er Dir Geld überweist?

Vielleicht hat jemand den Code parat oder Lust, das Problem zu knacken, 
und dann einfach wie ein ganz normaler hilfsbereiter Mensch zu 
antworten, der nicht die Frage infrage stellt.

[MaWin (Gast)]

Immer wieder diese freundlichen und hilfsbereiten Leute im Forum hier.

[Jester (Gast)]

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

[A. S. (Gast)]

Eine 3 Bit CRC ... 8 mögliche Werte.

Du kannst jedes Bit einzeln auswerten. Bei 1 gibt es für jeden Wert 
genau einen Folgewert, bei 0 einen anderen.

[Falk B. (falk)]

Ich hab die CRC3 Berechung mal zusammengebastelt. Funktioniert. Aber den 
Quelltext gibt's nicht so einfach. Dazu muss der OP schon etwas 
Eigeninitiative vorweisen. Hier mal der Anfang ;-)

uint8_t crc3(uint16_t data) {
    
    uint8_t i, crc, poly=0x3;
    
    // insert your code here

    return crc;
}

[Wolfgang (Gast)]

Alex schrieb:
> Habe selbst hunderte Varianten probiert

Warum überlässt du das nicht deinem PC?

[Dieter (Gast)]

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

[Kritiker (Gast)]

Jester schrieb:
> https://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung#Umsetzung

Das nervt kollossal, wenn Schlaumeier wie du auf WP linken! Das hat der 
TE ganz sicher direkt auch gemacht.

Was er aber wissen wollte ist, wie er das macht, weil er die Seite nicht 
versteht.

[Nop (Gast)]

Kritiker schrieb:

> Was er aber wissen wollte ist, wie er das macht, weil er die Seite nicht
> versteht.

Dann hätte er in der Vorlesung besser aufpassen sollen.

[Falk B. (falk)]

Nop schrieb:
> Dann hätte er in der Vorlesung besser aufpassen sollen.

Darum geht es nicht. Fragen stellen ist vollkommen OK, das ist der Sinn 
dieses Forums. Aber einen auf dumm machen und sich die Lösung auf dem 
Silbertablett servieren lassen nicht.

Beitrag "Einheitlicher Umgang mit faulen Schülern etc.?"

Hilfe zur Selbsthilfe.

[Gerald K. (geku)]

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.

[Falk B. (falk)]

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!

[Gerald K. (geku)]

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:

{
  C0=0;
  C1=0;
  C2=0;
}

2. Schrittweise (bitweise) CRC3 Berechnung:

{
  Temp= LSBeingangsdatenbit xor C0;
  C1=C2;
  C0=C2 xor Temp;
  C2=Temp;
}

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.

[Falk B. (falk)]

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

[Gerald K. (geku)]

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.

[Dieter (Gast)]

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

/*

  PSI5 3-bit CRC

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

  "3. Concept of the CRC shift register"

  Implement Step 2:

    Shift in the input stream bit by bit. If the popped out MSB is a '1',
    XOR the register value with the generator polynomial.

  Input: 3-bit CRC register (uint8_t crc)
         one data bit (bool bBit)

  Return: updated CRC register

*/

uint8_t psi5_crc_3bit(uint8_t crc, bool bBit)
{
  const uint8_t polynom = 0x03; /* g(x)= 1 + x + x^3  */

  /* shift in data bit */

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

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

  if(crc & 0x08)
    crc = crc ^ polynom;

  /* 3-bit register */

  return crc & 0x07;
}

Den CRC Register beim Start korrekt zu initialiseren und die Funktion 
für die einzelnen Datenbits aufzurufen sollte ja klar sein.

[Gerald K. (geku)]

Dieter schrieb:
> const uint8_t polynom = 0x03; /* g(x)= 1 + x + x^3  */

Stimmt das Polynom?

In der Schaltung mit den Schieberegistern ist zwischen C0 und C1 eine 
Lücke.

$$g(x)= 1 \cdot x^0 + 1 \cdot x^1 + 0 \cdot x^2 + 1\cdot x^3 = 0b1011 = 0x0A$$

Es fehlt C2 x^3

[Dieter (Gast)]

Gerald K. schrieb:
>
> Stimmt das Polynom?

So steht es zumindest in der PSI5 Technical Specification V1.3 auf Page 
16/46, Kapitel "3.2.2  Error Detection".

[Dieter (Gast)]

Gerald K. schrieb:
>
> Es fehlt C2 x^3

Das CRC Register ist 3-Bit lang, x^3 wäre Bit 4.

[Gerald K. (geku)]

Nach dem wir genügend Vorarbeit geleistet haben kann Alex einmal den 
Code ausprobieren. Dann werden wir sehen.

[Gerald K. (geku)]

Dieter schrieb:
> Gerald K. schrieb:
>
>> Es fehlt C2 x^3
>
> Das CRC Register ist 3-Bit lang, x^3 wäre Bit 4.

Für x^0 gibt es kein Register. Dann sind es wieder 3.

Aber ich kann mich durchaus irren.

[Dieter (Gast)]

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.

[Dieter (Gast)]

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

[Gerald K. (geku)]

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.

[Falk B. (falk)]

Dieter schrieb:
> Gerald K. schrieb:
>>
>> Es fehlt C2 x^3
>
> Das CRC Register ist 3-Bit lang, x^3 wäre Bit 4.

Das ist korrekt und Eigenschaft ALLER CRC-Polynome.

[Falk B. (falk)]

Gerald K. schrieb:
>> Das CRC Register ist 3-Bit lang, x^3 wäre Bit 4.
>
> Für x^0 gibt es kein Register. Dann sind es wieder 3.
>
> Aber ich kann mich durchaus irren.

Das tust du ;-)
X^0 ist Bit 0

[Alex (Gast)]

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.

uint8_t crc_calc(uint32_t Input) {
 volatile uint8_t CRC[3]={1,1,1};
 volatile uint8_t CRCa[3];
    
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);
    crc = ((CRCa[2] << 2) | (CRCa[1] << 1) | (CRCa[0] & 0x01));
}
return crc;
}

uint32_t Daten = 0x7FFFFF;
uint8_t crc = 0;

>Vielleicht hat jemand den Code parat

Das war so mein Gedanke

Schöne Grüße

[Dieter (Gast)]

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

Ja, ganz sicher.

> Kann jeder nachrechnen.

Auch das.

Falls Du ernsthaft meinst dass der Code etwas sinnvolles berechnet 
solltest Du besser irgendwas anders machen als in C programmieren.

Tipp: CRCa[2] ist immer 1 und CRCa[1] ist immer 0.

[Alex (Gast)]

Übertragungsfehler, sorry.

uint32_t Daten = 0x000;
uint8_t crc = 0;


uint8_t crc_calc(uint32_t Input) {
 volatile uint8_t CRC[3]={1,1,1};
 volatile uint8_t CRCa[3];

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

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

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



int main(void)
{

crc = crc_calc(Daten);
printf("0x%x\n", crc);

    for(;;)
    {

    }
}

[Wolfgang (Gast)]

Falk B. schrieb:
> 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-)

Das wäre dann etwa das gleiche Niveau, wie machen Steuerberechnung in 
Deutschland.

[Falk B. (falk)]

Alex schrieb:
> Das war so mein Gedanke

Schwachsinn. Weniger trinken, mehr nachdenken!

[Falk B. (falk)]

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.

[Falk B. (falk)]

Hier meine Version mit normaler Bitmanipulation.

#include <stdint.h>

uint8_t crc3(uint16_t data) {
    
    uint8_t i, crc, poly=0x3;

    crc   = 0x7;
    data &= 0x3FF;
    for (i=0; i<13; i++) {
      if (crc & 0x04) {
        crc <<= 1;            
        if (data & 1) crc |= 0x01;        // copy LSB to LSB
        crc ^= poly;
      } else {
        crc <<= 1;            
        if (data & 1) crc |= 0x01;        // copy LSB to LSB
      }
      data >>= 1;
    }
    return crc & 0x7;
}

int main(void) {

    uint16_t crc;

    crc = crc3(0x000);   // CRC 6
    crc = crc3(0x0CC);   // CRC 3       
    crc = crc3(0x151);   // CRC 0
    crc = crc3(0x1E0);   // CRC 3
}

[testo (Gast)]

Falk B. schrieb:
> uint16_t crc;
>     crc = crc3(0x000);   // CRC 6

Wieso du ein u8 als return in einer u16 speicherst ist mir schleierhaft.