Binärzählthread

[Root]

0001 1001 1011 0101

[Brontalo]

0001 1001 1011 0110

[Root]

0001 1001 1011 0111

[LuminFlare]

0001 1001 1011 1000

(20.06.2014)404compliant schrieb:  0001 1001 1011 0011

(19.06.2014)LuminFlare schrieb:  What do you mean, evaluate to your post count - zero?

'root' im englischen Mathematik-Sprachgebrauch ist die bzw. jede Nullstelle eines Polynoms. Die klassische Quadratwurzel x = √a ist die Nullstelle von x² - a = 0. In der Algebra werden teilweise erweiterte Zahlkörper gebildet, in dem ganz abstrakt "die 3. Nullstelle vom Polynom p" hinzugefügt wird, ohne sie konkret zu kennen.

Ich wusste nicht, warum √ root heißt Jetzt verstanden.
Edit : Ich verstehe 3. Nullstelle noch nicht... Die quadratische gleichung hat 2 Nullstelle, oder?

[Root]

0001 1001 1011 1001

[Brontalo]

0001 1001 1011 1010

[Root]

0001 1001 1011 1011

[Brontalo]

0001 1001 1011 1100

[404compliant]

0001 1001 1011 1101

(20.06.2014)LuminFlare schrieb:  Edit : Ich verstehe 3. Nullstelle noch nicht... Die quadratische gleichung hat 2 Nullstelle, oder?

Polynome mit höchstem Grad x^n haben bis zu n Nullstellen. Irreduzible Polynome haben gar keine, die als rationale Zahl (ganze Zahl oder Bruch) darstellbar sind. In dem Fall kann man dessen angenommene Nullstellen als zusätzliche Zahlen hinzu nehmen. Nimmt man nur genug dazu, hat jedes Polynom vom Grad x^n genau n Nullstellen, und man kann es komplett ausklammern zu (x-x1)(x-x2)(x-x3)(x-x4). x1, ... ,x4 sind dann die Wurzeln (root) des Polynoms.

Interessiert es jemanden, was Polynome, Binärzahlen und CRC-Prüfsummen mit einander zu tun haben?

[Brontalo]

0001 1001 1011 1110

[Root]

0001 1001 1011 1111

Meinst du das Polynome der Bits zu Berechnung der CRC Prüfsumme benutzt werden?

[LuminFlare]

0001 1001 1100 0000
Wikite alles.. CRC war neue Konzept zu mir
Nun kann ich das verstehen

[Root]

0001 1001 1100 0001
Naja das Konzept kannte ich schon aber die formale Version mit Polynomen hab ich auch aus dem Wiki.

[404compliant]

Im Prinzip wird Bit für Bit in Potenzen von X übersetzt, also 1101 ist x^3 + x^2 + x^0. Dort wird dann aber modulo 2 gerechnet, d.h. es gibt nur 0 und 1, 2 wird wieder zu 0. Entsprechend ist x+x=0 x+x+x=x, x+x+x+x=0, usw.

Interessant daran ist, dass die Addition von Polynomen jetzt das gleiche wie bitweises XOR ist, und die Multiplikation mit x ein bitweiser Links-Shift (das Anhängen einer 0, bzw. das Multiplizieren der Binärdarstellung mit 2) ist. Die sonst so komplizierten Polynom-Operationen sind plötzlich die einfachsten Grundrechenarten der Prozessoren, selbst die verhasste Polynomdivision ist mit ein paar Bit-Tests und XORs erledigt.

Der CRC-Prüfsummen-Algorithmus basiert theoretisch auf genau solchen Polynomen und Polynomdivisionen, und kann so direkt in einfache Bit-Operationen übersetzt werden, die dann jeder Computer schnell ausführen kann.

Dank der Theorie endlicher Körper kann man folgendes machen:
Man legt eine spezielle, geeignete Binärzahl, den Generator, fest, sagen wir mal 32 Bit lang (irreduzibles Polynom, nichts kann ausgeklammert werden). Dieser Generator hat also eine 1 an der 32. Stelle. Nun startet man mit einer 1, und shiftet so lange nach links, bis die 1 an der 32. Stelle angekommen ist. (entspricht Multiplizieren mit X). Jetzt macht man ein XOR mit dem Generator, so dass die 32. Stelle wieder 0 ist (entspricht Rest einer Polynomdivision). Dadurch wurden natürlich auch die unteren 31 Bit ggfs. verändert. Danach kann man wieder weiter links shiften, und jedes mal, wenn an der 32. Stelle eine 1 auftaucht, wendet man das XOR an, um die Stelle wieder zu nullen.
Jetzt der Clou: Diese Schieben-und-XOR Operation kommt genau nach 2^31 Schritten wieder bei der 1 an, und hat in der Zwischenzeit exakt jede Zahl zwischen 1 und 2^31-1 genau ein mal passiert. Und das in einer scheinbar vollkommen zufälligen Reihenfolge.

Für CRC-Prüfsummen muss man jetzt nur beim Shiften bitweise die eigentlichen Datenbits an Stelle 0 hinein shiften, statt immer eine 0 hinein zu shiften.

0001 1001 1100 0010

[Root]

Uh... ich hab grad mal nachgeschaut, dass was ich im Kopf hatte war Blockpartitätssicherung(etwas einfacher ).

0001 1001 1100 0011

[404compliant]

0001 1001 1100 0100

[Root]

0001 1001 1100 0101

[Brontalo]

0001 1001 1100 0110

[Root]

0001 1001 1100 0111

[Brontalo]

0001 1001 1100 1000