Hallo zusammen,
ich versuche gerade ein Polynomdivision Schieberegister zu
implementieren.Ich habe einen alten Assembler Code, dass ich in
C-Sprache umformen möchte.
N[21]=[101000000000000000000]
r[10]=[0000000000]
Do i=1,21,1
x = N[21] exor r[10]
r[10]= r[9] exor x
r[9] = r[8] exor x
r[8] = r[7] exor x
r[7] = r[6] exor x
r[6] = r[5] exor x
r[5] = r[4] exor x
r[4] = r[3] exor x
r[3] = r[2] exor x
r[2] = r[1] exor x
r[1] = x
Do k = 21,2,1
N[k]=N[k-1]
N[1]=0
END D0
END D0
hier ist mein Umformen in C, aber es funktioniert nicht. Kann jemand mir
sagen, was ist nicht klar?
#include <stdio.h>
#include <stdlib.h>
int main()
{
char N[22]="101000000000000000000";
char r[11]="0000000000";
int i,j;
printf(" N = %s\n",N);
printf(" r = %s\n",r);
i= 1;
do{
int x = N[22]^r[11];
r[10]= r[9]^x;
r[9] = r[8]^x;
r[8] = r[7]^x;
r[7] = r[6]^x;
r[6] = r[5]^x;
r[5] = r[4]^x;
r[4] = r[3]^x;
r[3] = r[2]^x;
r[2] = r[1]^x;
r[1] = x;
int k = 21;
do {
r[k] = N[k-1];
N[1] = 0;
k -=2;
}while(k>1);
i++;
}while(i<=21);
printf("End r = %s\n",r);
return 0;
}
Gruß fef
Gast
#4861916
Du kodierst die Bitfolge als ASCII-String, verwendest aber den Bitweise Operator '^'.
ich bedanke mich für deinen Beitrag. nun die Exclusiv-Oder in C-Sprache ist doch '^' Oder habe ich falsch kapiert? Bitte kannst du noch ein bisschen erklären?
Gast
#4861977
char N[22]="101000000000000000000"; das ist eine ascii zeichenfolge... "0" => 48 (30hex) "1" => 49 (31hex) beim gcc gibts eine extention um das einfach einzutippen... https://gcc.gnu.org/onlinedocs/gcc/Binary-constants.html 73
Gast
#4861979
Fef F. schrieb: > ich bedanke mich für deinen Beitrag. > > nun die Exclusiv-Oder in C-Sprache ist doch '^' > Oder habe ich falsch kapiert? > > Bitte kannst du noch ein bisschen erklären? Kann ich versuchen. Der erste Punkt bei sowas ist immer, die Kodierung der Daten im Auge zu haben. In Deinem Assemblerprogramm (die Syntax kann ich leider keinem Assembler zuordnen, mich erinnert das ein bisschen an FORTRAN), verwendest Du anscheinend ein Literal in der Form einer indexierbaren Bitfolge. In dem C-Programm verwendest Du aber ein Literal in der Form einer indexierbaren Folge von ASCII-Zeichen. Die ASCII-Zeichen '0' und '1' haben die Bitfolge 00110000 und 00110001. Wenn Du diese Bitfolgen bitweise Exklusiv oder verknüpfst, kommt dabei folgendes heraus. 00110000 ^ 00110000 = 00000000, was dem ASCII-Zeichen NUL, einem Steuerzeichen entspricht, aber keinesfalls einem der ASCII-Zeichen '0' oder '1'. Ebenso bei 00110000 ^ 00110001 = 00000001 und 00110001 ^ 00110000 = 00000001 was auch einem ASCII-Steuerzeichen entspricht. Und schliesslich bei 00110001 ^ 00110001 = 00000000 wieder ASCII-NULL
@ Fef Frank (Firma: Gast) (fef) >ich versuche gerade ein Polynomdivision Schieberegister zu >implementieren.Ich habe einen alten Assembler Code, dass ich in >C-Sprache umformen möchte. Siehe [CRC]] >#include <stdio.h> >#include <stdlib.h> >int main() >{ >char N[22]="101000000000000000000"; >char r[11]="0000000000"; >int i,j; >printf(" N = %s\n",N); >printf(" r = %s\n",r); Das kann man prinzipiell zwar so machen, praktisch wird man die Daten aber bitweise in einer passenden Variable halten. Das ist deutlich kompakter und schneller, außerdem eleganter. Die Verknüpfung per ^ ist OK, funktioniert aber nicht mit ASCII-Zeichen!!!
Gast
#4861989
Falk B. schrieb: > [...] > Die Verknüpfung per ^ ist OK, funktioniert aber nicht mit > ASCII-Zeichen!!! Sag ich doch! :-)
Ein XOR mit ASCII 1 und 0 sieht so aus, kann man als Macro schreiben
1 | |
2 | |
3 | |
4 | |
5 | |
Es handelt sich um Polynomdivision für univariate Polynome in Charakteristik 2 (d.h. 2 = 0). * Jedes Bit repräsentiert ein Monom. * Zwei Monome werden addiert, indem die Koeffizenten addiert werden, und bei der vorliegenden Darstellung entspricht das einem XOR (^). * XOR zweier Polynome entspricht also der Addition der beiden Polynome, indem alle Monome parallel addiert werden. * Ditto für Subtraktion, da Addition und Subtraktion in Charakteristik 2 die gleiche Operation Darstellen. * Der Grad eines Polynoms ergibt sich aus dem höchsten gesetzten Bit. Beispiele in Z2[x]: 0 ~ 0 1 ~ 1 0b10 ~ x 0b11 ~ x + 1 0b101 ~ x^2 + 1 Multiplikation mit x entspricht Schieben nach links: 0b101 << 2 = 0b10100 ~ x^2 * (x^2 + 1) = x^4 + x^2 Schieben nach rechts entspricht Division mit Rest durch x, wobei das herausfallende Bit 0 (Carry) den Rest darstellt: 0b101 >> 1 = 0b10, Carry=1 ~ x Rest 1 = (x^2 + 1) Div x etc. Ansonsten ist der Algorithmus für die Polynomdivision exakt der gleiche wie für "normale" Polynome (z.B. aus Q[x]) auch; aber in Charakteristik 2 kann eben Bit-gepackte Darstellung ausgenutzt werden sowie "parallele" Addition und Vergleich (zumindest falls das Polynom in ein Word passt). Zum Bestimmen des Polynomgrads können Funktionen wie CLZ (countz leading zeroes) genutzt werden. Den Algorithmus würd ich auch nicht "portieren" sondern nachdem du ihn verstanden hast neu in Hochsprache implementieren.
Falk Brunner. schreibt: >praktisch wird man die Daten >aber bitweise in einer passenden Variable halten. Das ist deutlich >kompakter und schneller, außerdem eleganter. wenn ich alles zusammenfasse, bin ich am Bahnhof mit meinem Umformen. kannst du bitte eine kleine Beispielart mir zeigen?
@Johann L. (gjlayde) Benutzerseite >Es handelt sich um Polynomdivision für univariate Polynome in >Charakteristik 2 (d.h. 2 = 0). >* Jedes Bit repräsentiert ein Monom. Da spricht der Mathematiker . . . und ich bin raus ;-)
@ Fef Frank (Firma: Gast) (fef) >kannst du bitte eine kleine Beispielart mir zeigen? Ich sagte ja, siehe CRC, dort gibt es einen Link auf den Klassiker. http://www.ross.net/crc/download/crc_v3.txt
Falk B. schrieb: > @Johann L. (gjlayde) Benutzerseite > >>Es handelt sich um Polynomdivision für univariate Polynome in >>Charakteristik 2 (d.h. 2 = 0). > >>* Jedes Bit repräsentiert ein Monom. > > Da spricht der Mathematiker . . . und ich bin raus ;-) x^2 + x^3 besteht aus 2 Monomen -- nennt man dann auch "Polynom" oder manchmal auch "Binom".