CRC Verständnisfrage

[regatti (Gast)]

Hallo!

Das CRC Tutorial (http://www.mikrocontroller.net/articles/CRC) habe ich 
mir bereits angesehen. Hierzu habe ich noch eine Frage:

So sieht im Artikel die Vorgehensweise aus:

1. An die zu schützenden binären Daten werden N Bits mit dem Wert Null angefügt, wobei N die Anzahl Bits des Generatorpolynoms ist. (CRC16 -> 16 Bits)

2. Die entstandene neuen binären Daten werden durch das Generator-Polynom geteilt und der Rest wird ermittelt!

3. Der Rest wird zu den binären Daten hinzugefügt, er stellt die Prüfsumme dar.

Weiter unten steht im Beispiel:

Das Generator-Polynom sei x5 + x2 + x. Dies entspricht der binären Zahl 100110. Das Polynom ist vom 5. Grad, weil das höchste gesetzte Bit den Wert 2^5 hat. Gerechnet wird aber immer nur mit den unteren 5 Bit, hier also 00110. Jetzt ist natürlich auch noch ein binäre Zeichenkette notwendig, die unsere Daten darstellt. Beispielsweise 1110100111001 (willkürlich gewählt). 

    *  An die Daten werden 5 Nullen angehängt: 

    1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0

    * Die Daten müssen jetzt durch das Generator-Polynom dividiert und somit der Rest ermittelt werden: 

    1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0
    1 0 0 1 1 0
    0 1 1 1 0 0 0
      1 0 0 1 1 0
      0 1 1 1 1 0 1
        1 0 0 1 1 0
        0 1 1 0 1 1 1
          1 0 0 1 1 0
          0 1 0 0 0 1 1 
            1 0 0 1 1 0
            0 0 0 1 0 1 0 0 1
                  1 0 0 1 1 0
                  0 0 1 1 1 1 0 0
                      1 0 0 1 1 0
                      0 1 1 0 1 0 0
                        1 0 0 1 1 0
                        0 1 0 0 1 0 0
                          1 0 0 1 1 0
                          0 0 0 0 1 0 0

Sie schreiben hinzu das nur mit den untersten 5 Bits des Polynoms 
gerechnet wird, in der Rechnung erscheinen dann aber doch wieder 6 Bits? 
Was jetzt????


Noch eine Frage:

Wie das Generatorpolynom aussieht ist doch eigentlich belanglos oder 
sehe ich das falsch.

Danke für eure Hilfe!


Grüße

[g457 (Gast)]

> Wie das Generatorpolynom aussieht ist doch eigentlich belanglos oder
> sehe ich das falsch.

Das siehst Du falsch [1, 2]

HTH

[1] 
http://de.wikipedia.org/wiki/Cyclic_Redundancy_Check#Polynome_und_Typen
[2] 
http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Designing_CRC_polynomials

[regatti (Gast)]

Danke g457!

Ja die standartisierten Typen hab ich im Wiki auch schon gesehen.
Das was daunter steht habe ich dort noch nicht gelesen. Scheint also 
sicherheitstechnisch echt einen Unterschied zu machen welchen Wert die 
jeweiligen Bits haben angeordnet sind.

Kann mir jemand die erste Frage beantworten?

[123 (Gast)]

Malzeit

Das Oberste Bit des Polynoms muss immer 1 sein. da 1 xor 1 = 0 muss das 
nicht explizit berechnet werden. da das ja implizt vom Alg gefordert 
ist. somit sind nur die restlichen bits wirklich zu berechnen.

hat zur folge, das bei 17 bit Polinom wie beim CRC 16 ( x16 + ... ) der 
rest immer 16 bit gross ist.

und der aufbau des Polinoms ist nicht egal. da haben sich einige schlaue 
mathematiker den keks gehörig verbogen um zu beweisen welche was taugen 
und welche nicht.

[regatti (Gast)]

Hey danke dir! Super verständlich erklärt. Für mich ist somit alles 
beantwortet.


Grüße

[gtf (Gast)]

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
xxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
xxx
                      NEUES THEMA: Table-Driven CRC
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
xxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
xxx


Hallo Community,

Ich möchte eine CRC8 Tabelle generieren. Leider bin ich momentan etwas 
verunsichert, ob meine Vorgehensweise korrekt ist.

1) Das angehängte Bild zeigt wie ich mir das ganze vorstelle. Ist das so 
richtig?

Bei einer Bitweise(Seriell) CRC- Berechnung benutze ich als Startwert 
0xFF.
Um eine CRC8- Tabelle zu generieren, nehme ich zuerst einen 
Startwert(0xFF) mit einem Prüfbyte(=0), und erzeuge daraus 
Bitweise(Seriell)  die Prüfsumme.
Diese Prüfsumme wird in der Tabelle gespeichert, und anschließend das 
Prüfbyte um eins erhöht.
Soweit so gut.
Doch jetzt wo das Prüfbyte(=1) eins beträgt,
soll es jetzt wieder mit dem Startwert(0xFF) Bitweise verknüpft werden,
Oder soll der vorherige Remainder Wert aus der ersten Polynomdivision 
mit dem neuen Prüfbyte Wert(=1) verknüpft werden???

Kurzfassung:
;--------------------------------
1) Startwert(0xFF)---Bitweise EXOR--- Prüfbyte(=0)
2) Inkrement Prüfbyte(+1)
3) Startwert(0xFF)--- Bitweise EXOR ---Prüfbyte(=1)
      oder
     Remainder--- Bitweise EXOR ---Prüfbyte(=1) ????

4) Inkrement Prüfbyte(+1)
    u.s.w.


Beide Möglichkeiten führen zu einem Ergebnis, doch welches von beiden 
ist das Richtige?
Was meint Ihr?

; Routine zum generieren einer CRC8- Tabelle
;---------------------------------------------
CRC_Build_main:  
    ldi    temp3, CRC_Init        // mit CRC_Init laden = $FF, Remainder
    clr    temp1            // CRC- Prüfbyte löschen
    ldi    YL,  Low(SRAM_START)      // CRC-Tabellen Speicherort
    ldi    YH,  High(SRAM_START)    // init
CRC_Build_m_loop:
    mov    b0, temp1          // CRC- Prüfsumme für's
    rcall  CRC8_Build_Tab        // Prüfbyte errechnen
    ST    Y+, temp3          // CRC- Ergebnis abspeichern
    inc    temp1            // Prüfbyte um 1 erhöhen
    tst    temp1            // CRC- Prüfung für 2^8 Bytes
    Brne  CRC_Build_m_loop      // ausgeführt?
  ret                    // Wenn ja, dann return
;************************************************************
;* CRC8- Berechnungen
;* -------------------
;* Parameter: 
;* 1) temp0- Bitcounter. Zählt die schiebeoperationen
;* 2) temp2- CRC8- Polynomregister
;* 3) temp3- remainder. 
;* 4) b0   - Message Data. 
;*
;************************************************************
CRC8_Build_Tab:                // Optimized for actual Application
; CRC8 Table generator init
    ldi    temp2, Polynom        // load polynom
    ldi    temp0, 8            // bit counter load to 7, EXOR are one time executed
CRC8_BT_bit_loop:
    lsl    b0              // shift next data bit into carry  
    rol    temp3            // shift in new data bit and shift out old MSB  
    Brcc  CRC8_BT_no_XOR        //
    eor    temp3, temp2        // XOR data with poly
CRC8_BT_no_XOR:
    dec    temp0            // dec bitcounter
    brne  CRC8_BT_bit_loop      // branch if not zero    
  ret

Danke im Voraus für eure Bemühungen!

Mit freundlichen Grüßen
gtf