www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik CRC Polynome und die zugehörige Bitfolge


Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich steh hier grad vor einem kleinen Problem:
Mir will irgendwie nicht klar werden, wie diese Polynome zu den
Bitfolgen passen. Laut avr-libc ist das Polynom
x^16 + x^12 + x^5 + 1 gleich der Bitfolge 0x1021 (also 0001 0000 0010 
0001). Aber ich kommen umgekehrt von der Bitfolge nur auf ein
Polynom x^12 + x^5 + 1.
Woher kommt das x^16?
Für mich würde sich dann nämlich die Bitfolge
1 0001 0000 0010 0001 ergeben.

Autor: 6636 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das man von LSB nach MSB schiebt kommt das MSB sowieso dran, nehm ich 
an.

Autor: Hans-jürgen Herbert (hjherbert) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das 17te Bit ist nicht in der Konstanten (0x1021) sondern im Code. 
Vielleicht dadurch, dass immer 16 Bit verwendet werden.

Autor: Hans Hein (hanshein)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Für mich würde sich dann nämlich die Bitfolge
> 1 0001 0000 0010 0001 ergeben.

Perfekt!

Im GF(2)-Koerper ist die Addition/Subtraktion gleich
einem XOR. Die CRC-Operation entspricht einem (Polynom-)
Teilen mit Rest.

Wie beim schriftlichen Dividieren sucht man sich die "linkeste"
Stelle wo man die Operation ausfuehren kann, also etwa

1 abcd efgh ijkl mnop    ( a..p \elem {0,1} )

darunter schreibt man wie beim schriftlichen Dividieren:

1 0001 0000 0010 0001

als erste Stelle kommt (IMMER) durch das XOR eine Null

0 .... .... .... .... ( "." = irgendwas, momentan unwichtig)

das heisst aber, dass ich das "linkeste Bit" auch fuer
die "eigentliche" XOR-Operation vergessen kann.

-Hans

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]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [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.