MoinMoin ich beschäftige mich gerade mit Zufall bzw Pseudozufall. Dazu hab ich erstmal ein bischen rumgegoogelt und bin auf die linear rückgekoppelten Schieberegister gestoßen. Das hab ich dann mal fix zusammenklöppelt (auf nem Atmega2560 im AtmelStudio6.2 in C). Das schickte dann auch schick wilde Zahlenkolonnen auf serielle Schnittstelle. Nach ner Weile fiel mir auf, dass recht schnell (ca 300? so in der Größenordnung) wieder der Startwert auftauchte. Das Schieberegister ist 16bit breit. Ich hatte das erstmal so verstanden dass die Periodenlänge von so einem Gedöns (2^n)-1 sei, aber das ist die maximale Periodenlänge bei geschickter Wahl der "Rückkopplungspunkte", wie sich nach genauerem Lesen herausstellte. Also fix das ganze Zufallsgefrickel kopiert und Zufall 2 genannt, und mit den Parametern experimentiert. Irgendwann wurd mir die Liste zu lang, um nach den Wiederholungen zu suchen, da kam mir der //ironie geradezu genial graziös geschickte//ironie off Einfall "hey ich hab ja nen µC, denn kann ich ja suchen lassen. Also ne Stopbedingung programmiert, dass er so lange rattert, bis er wieder den Startwert (Seed) erreicht hat, welcher selbstverständlich wie sich dass für anständigen Zufall gehört, 42 ist ;-). Leider hat er nie angehalten, die 16bit sind mehrfach übergelaufen. Um zu testen hab ich den Stopwert dann mal auf den ersten Wert nach dem Seed gesetzt. Da hält er dann auch direkt nach dem ersten Wert von Zufall 1 an, und rattert Zufall 2 mit anderen Rückkopplungspunkten durch, um dort bei nach 5460 Durchläufen auch anzuhalten, und zwar beim Startwert 42. Dann hab ich den Stopwert für Zufall 1 wieder auf 42 gesetzt, und nun rattert und rattert und rattert er wieder. Bei Zufall 1 ver-XOR-e ich bit1 und bit3, und das Ergebnis davon ver-XOR-e ich mit bit4, dieses wird dann an bit 15 vom Zufallswert geschoben, welcher vorher um 1 nach rechts geschoben wurde. Gerade eben hab ich dem werweißnichwievieltem Überlauf zugeguckt.... Warum hält das Ding nich an? P.S. Ich bin mir bewusst, das ganze liefe deutlich schneller, würd ich nicht jedesmal nen Text und den Wert übertragen, sondern nur wenn der Stopwert erkannt wurde. Aber irgendwie find ichs schick, dem Gewusel auf dem Terminal zuzuschauen :D Ich hoffe ich die entscheidenden Teile angehängt, wenn was fehlen sollte liefer ichs nach. Wieder ganz schön lang geworden... :D MfG Chaos
P.P.S. Ich sehe gerade, dass in Zufall 1 (genaugenommen heißt es im Quelltext nur "Zufall" und "Zufall2") das Array, in dem die Zufallszahl sitzt global ist, und in Zufall2 hab ich sie lokal gemacht... Mal daran rumtesten. Ich hab gerade auch noch die Rückkopplung von Zufall auf die von Zufall2 gesetzt, welcher ja bei 5460 anhielt, und nun läuft Zufall bis 4599 um dann anzuhalten, aber Zufall2 läuft nicht mehr an?!?!?
Ich lass sowas auf dem PC laufen. Dann kann auch singlesteppen. Zu den Konfigurationen empfehle ich die XAPP 110 von Xilinx.
Zwölf M. schrieb: > Dann kann auch singlesteppen. Das geht auch im Studio. Aber nebenbei hab ich auch an der USART herumversucht. Und ich kann nicht so schnell Singlesteppen, wie das Terminal Werte entgegennehmen kann. Aber das ist ja auch gar nicht Punkt der Frage.
Entweder laeuft das LFSR mit maximaler Laenge oder mit reduzierter Laenge. Auf einem PC schreibt man die Werte in ein Memo, zum visuell nachpruefen. Und wenn man dann das Vertrauen hat fuehrt man einen Zaehler ein, der zaehlt bis der Startwert wiederkehrt.
Servus, Du musst ein Polynom (das ist das, was die "Rückkopplungspunkte" angibt) für "Maximal Length LFSR feedback" benutzen. Hier gibt es eine Liste mit 2048 möglichen Polynomen für 16-bit maximal length LFSR: https://users.ece.cmu.edu/~koopman/lfsr/16.txt
Thomas E. schrieb: > Servus, > > https://users.ece.cmu.edu/~koopman/lfsr/16.txt Erstmal danke für die Liste, wie lese ich die? 801C --> bit8 mit bit0 ver-XOR-en, damit dann bit1 und damit dann bit12? > Du musst ein Polynom (das ist das, was die "Rückkopplungspunkte" angibt) > für "Maximal Length LFSR feedback" benutzen. Hier gibt es eine Liste mit > 2048 möglichen Polynomen für 16-bit maximal length LFSR: Danke für die Erklärung, das hatte ich inzwischen auch soweit verstanden. Was ich aber nicht verstehe, ist dass 314 (wenn ich die Leseart richtig interpretiert habe) scheinbar nicht anhält, wobei eigentlich jedes LFSR anhalten sollte? Ich werde mal das ganze USART gesende rausnehmen, und nur noch die Überläufe zählen und senden. J. T. schrieb: > Ich hab gerade auch noch die Rückkopplung von Zufall auf die von Zufall2 > gesetzt, welcher ja bei 5460 anhielt, und nun läuft Zufall bis 4599 um > dann anzuhalten, aber Zufall2 läuft nicht mehr an?!?!? Alarm zurück, bzw halb zurück. Ich hatte ein bit falsch rausgefischt, beim setzen der Abbruchdebingung. Mit nun dem selben Polynom, wo der Name schon gefallen ist, wie Zufall2 hält er nun auch nach 5460 an. Aber dennoch läuft Zufall2 nicht mehr los. Zufall2 lief aber los, als ich die Abbruchbedingung für Zufall1 auf den ersten erzeugten Wert setzte...
1 | while (i != 42) |
2 | {
|
3 | j++; |
4 | i = Zufall(); |
5 | if(j == 0) |
6 | {
|
7 | Ueberlaeufe ++; |
8 | UART_Stringsend("Zufallszahl1 "); |
9 | u16toa(cZahl, Ueberlaeufe); |
10 | UART_Stringsend(cZahl); |
11 | UART_Stringsend(" mal übergelaufen"); |
12 | UART_send(13); |
13 | }
|
14 | |
15 | }
|
Mit den gesparten Übertragungen kommt nun ca ein Überlauf die Sekunde, anstatt gefühlten 5min das Terminal anzugucken
Du hast da so rumgefrickelt. Das habe ich auch - mich aber an die Parameter gehalten, die im Internet für LSFRs der verschiedensten Bitlängen veröffentlicht wurden. Und es klappt!!! 1) VERGLEICHEN darfst du die Zufallsdaten nur über die Bit-Länge, für die die Parameter vorgegeben wurden. Bei einem 8-BitLFSR erhältst du einen Zyklus von 255 Bei einem 15-BitLFSR erhältst du einen Zyklus von 32.767 Bei einem 22-BitLFSR erhältst du einen Zyklus von 4.194.303 Die Dinger werden (wenn sie fuktionieren) NIE NULL liefern! Man darf sie auch nicht mit NULL starten, dann könnten sie ewig auf NULL bleiben. = Null-komma-Nix Zufall. ;-) 2) VORSICHT! Oft sind in den Formeln für ein N-Bit-LFSR die Bits von 1...N benannt. - Das sind aber im µC die Bits 0...N-1. RICHTIG programmiert bekommt man schön verteilten Pseudo- Zufall. - Wenn nicht, hat man falsch programmiert, oder falsche Parameter benutzt/oder die Parameter (N ? N-1) falsch eingesetzt...
Jakob schrieb: > 1) VERGLEICHEN darfst du die Zufallsdaten nur über die > Bit-Länge, für die die Parameter vorgegeben wurden. Ist es nicht eher so, dass die vorgegebenen Parameter nur dafür sorgen, dass die Periodendauer (2^n)-1 beträgt, also die maximal mögliche? Aber die Parameter verbieten doch keinen Vergleich? Jakob schrieb: > Bei einem 8-BitLFSR erhältst du einen Zyklus von 255 > Bei einem 15-BitLFSR erhältst du einen Zyklus von 32.767 > Bei einem 22-BitLFSR erhältst du einen Zyklus von 4.194.303 Also (2^n)-1, allgemein gesprochen. Jakob schrieb: > RICHTIG programmiert bekommt man schön verteilten Pseudo- > Zufall. - Wenn nicht, hat man falsch programmiert, oder > falsche Parameter benutzt/oder die Parameter (N ? N-1) falsch > eingesetzt... Ich probiere einfach Parameter aus. Bei einigen kommen sehr kurze Folgen raus, bei einigen längere. Bisher hab ich noch keines getroffen, dass maximale Länge hätte. Aber ich hab hier einen "Parametersatz", der scheinbar unendliche Periodenlänge liefert. Inzwischen ist der Überlaufszähler 2964 mal übergelaufen, und steigt mit jeder sekunde weiter.
Hier mal ein spontan geschriebenes C-Program (für PC):
1 | #define POLY 0x8117
|
2 | |
3 | int main(int argc, char** argv) { |
4 | |
5 | int i; |
6 | uint16_t lfsr = 42; |
7 | |
8 | for(i=1; i<65536; i++) |
9 | {
|
10 | if(lfsr & 0x0001) |
11 | lfsr = (lfsr >> 1) ^ POLY; |
12 | else
|
13 | lfsr >>= 1; |
14 | // printf("%d,",lfsr);
|
15 | if(lfsr == 42) |
16 | break; |
17 | }
|
18 | if(i<65536) |
19 | printf("\nWiederholung nach %d Schleifen.",i); |
20 | else
|
21 | printf("\nWiederholung nicht erreicht!"); |
22 | |
23 | |
24 | return 0; |
25 | }
|
Thomas E. schrieb: > if(lfsr & 0x0001) > lfsr = (lfsr >> 1) ^ POLY; > else > lfsr >>= 1; > // printf("%d,",lfsr); Entweder verstehe ich das nicht, oder es ist was anderes, als ich aus den Beschreibungen die ich so gelesen hab, herausgezogen hab... Bei deiner Variante wird ja ver-XOR-t, wenn der aktuelle Wert ungerade ist, sonst halbiert. Was ich rausgelesen hab ist: Man hat ein Schieberegister der Breite n, an den Ausgängen einigen Ausgängen führt man die Signale über XOR-Gatter zurück. Das Schiebregister wird um 1 Richtung LSB verschoben und das Ergebnis vom XOR wird aufs MSB gesetzt. Das sehe ich da oben irgendwie nicht? Ich verstehe auch nicht so ganz, wie man den umgekehrten Weg gehen kann, also von den Abzweigpunkten zu dem Polynom kommt. Die Verknüpfung mit dem Polynom nur im ungeraden Fall, ist dass nicht was anderes? Und diese Liste der Polynome erzeugt immer Ketten maximaler Länge? Danke dir
Das ist nur eine etwas andere Implementierung, siehe hier: http://www.embedded.com/print/4015086 Unten auf der Seite "One-to-many versus many-to-one implementations" J. T. schrieb: > Bei deiner Variante wird ja ver-XOR-t, wenn der aktuelle Wert ungerade > ist, sonst halbiert. Nee, geschoben (halbiert) wird immer!
Thomas E. schrieb: > J. T. schrieb: >> Bei deiner Variante wird ja ver-XOR-t, wenn der aktuelle Wert ungerade >> ist, sonst halbiert. > > Nee, geschoben (halbiert) wird immer! Ja stimmt, ich dass :"und geschoben/halbiert" vergessen, das war nicht meine Absicht. Aber ich verstehe dennoch nicht, wieso nur bei ungeradem verxort wird. Vermutlich wurde das genauso mit "verxoren bei geradem alten Wert" und invertierten Parametern/Polynom gehen? Liegt das nun nur an den "magischen" Polynomen, bei denen immer ein LFSR maximaler Länge rauskommt, das es reicht bei ungeradem aktuellen Zufallswert zu verxoren? Was ja wiederum hieße, dass alle LFSR maximaler Länge auf jeden Fall das LSB in der Rückkopplung haben müssen? Meine Variante scheint die 42 ja wie die Pest zu meiden.... Wir sind inzwischen bei 5700irgendwas überläufen. Und dennoch wirkten die Werte, als ich sie einzeln ausgeben ließ, sehr chaotisch. Gut das ist nur ein Gefühl und keine statistische Analyse... P.S. sorry den Link erst jetzt gesehen
Eine empfehlenswerte Quelle für LFSRs "beliebiger" Länge (3...168 Bit): https://www.xilinx.com/support/documentation/application_notes/xapp052.pdf Table 3: Taps for Maximum-Length LFSR Counters Aber, wie gesagt: Bei einem 8 Bit LFSR gibt es im µC nur Bit 0...7 zum verwursteln. Bei einem 7 Bit LFSR gibt es im µC nur Bit 0...6 zum verwursteln. Und - der Startwert muss UNGLEICH NULL sein. Also beim 7-Bit-LFSR: Genannt wird: Bit 7, 6 - gemeint sind Bit 6, 5 eines µC-Registers Benutzt wird: Bit0_neu = XOR(Bit 6,Bit 5), ein 1-Bit-Wert Neuer Stand: LFSR = LFSR * 2 + Bit0_neu Oder: LFSR = LFSR << 1 | Bit0_neu Wie diese Bitpfriemelelei in der persönlich bevorzugten Prog-Sprache umgesetzt werden muss, ist halt Prog-Sprachen-abhängig... Richtig gemacht kommt man zum richtigen Ablauf!
Ich habs verstanden. Ich hatte jetzt mal den Stopwert als Variable gemacht, nach dem ersten Durchlauf auf den Wert vom ersten Durchlauf gesetzt (JTAG debugging). Dann dauert es 8193 Durchläufe bis er anhält. Er hat also keine Periodenlänge unendlich, sondern ereicht nur nie wieder den Startwert. Da lag mein Verständnisproblem.
Wieder mal sehr gut um sich das ganze vor Augen zu führen: http://tiweb.hsu-hh.de/LogiFlash/flash/LogiFlash.swf
J. T. schrieb: > Ich habs verstanden. Ich hatte jetzt mal den Stopwert als Variable > gemacht, nach dem ersten Durchlauf auf den Wert vom ersten Durchlauf > gesetzt (JTAG debugging). Dann dauert es 8193 Durchläufe bis er anhält. > Er hat also keine Periodenlänge unendlich, sondern ereicht nur nie > wieder den Startwert. > > Da lag mein Verständnisproblem. Yep, wenn du keinen Zyklus maximaler Länge hast, dann kannst du vom Startwert aus erst eine Sequenz haben, die nur einmal durchlaufen wird und dann in den Zyklus mündet: s->i1->i2->i3->c1->c2->c3->c4->c5->c1->c2->... Für die genauere Theorie (primitive Polynome) empfehlen sich Bücher über Gruppentheorie (Algebra) oder Kryptologie. ;-)
Servus Chaos, der Nachteil der "many-to-one" Implementation gegenüber der "One-to-many" ist die kompliziertere programmtechnische Umsetzung. Auch wenn sich Dein Code sicher auch noch etwas optimieren ließe, auf sowas kurzes, wie bei "One-to-many" wirst Du nicht kommen. Und wenn man den Inhalt des LFSRs direkt als Zufallszahl benutzen möchte und damit z.B. 16 LEDs ansteuert, wird man gleich sehen, daß Z(n+1) nicht so zufällig ist, sondern sich nur um ein Bit unterscheidet - der Rest ist ein hübsches Lauflicht. Das ist zwar bei der "One-to-many" Methode in den Teilen zwischen den Tabs auch der Fall, aber das würde halt nicht sofort so stark ins Auge fallen. Eine diesbezüglich bessere Zahlenfolge erhält man, wenn man bei jeder neuen Zufallszahl des LFSR einmal komplett durchschiebt.
J. T. schrieb: > Thomas E. schrieb: >> Servus, >> > >> https://users.ece.cmu.edu/~koopman/lfsr/16.txt > > Erstmal danke für die Liste, wie lese ich die? Es gibt unterschiedliche Konventionen zur Darstellung der Polynome: * MSB First * LSB First * Koopman https://en.wikipedia.org/wiki/Crc32#Specification > Zufall (Pseudo)-zufällig sind die Folgen nicht: Wenn Wert X einmal aufgetreten ist, dann tritt er die nächsten L-1 mal nicht mehr auf, wobei L die Periodenlänge ist. Man erhält also eine L-stellige Permutation, die man als Permutation der Zahlen 1..L auffassen kann. J. T. schrieb: > Ich probiere einfach Parameter aus. Falls das LFSR Polynomarithmetik über Z/2Z darstellt: Wie gesagt muss es sich dann um ein irreduzibles Polynom (hier über Z/2Z = GF(2)) handeln, damit man maximale Periode von 2^n - 1 erhält. Notwendig dazu sind: 1) Das Polynom hat Grad n. Wenn die Sequenz 7 lang sein soll ist somit n = 3 und das Polynom muss als höchsten Term X^3 haben. Dabei ist zu beachten, dass in vielen Notationen Terme wegen Redundanz weggelassen werden. 2) Das Polynom muss irreduzibel sein. Dies bedeutet insbesondere: 2a) Das Polynom darf nicht durch X teilbar sein => Der Koeffizient beim konstanten Term (also bei X^0) muss 1 sein. 2b) Das Polynom darf nicht durch X + 1 teilbar sein, oder anders ausgedrückt: 1 darf keine Nullstelle des Polynoms sein. Einsetzen von 1 ins Polynom liefert gerade die Spur (Summe aller Koeffizienten) und diese muss ungleich 0, also 1 sein. Da die Koeffizienten in GF(2) sind, ist ihre Summe genau dann 1, wenn eine ungerade Anzahl von Koeffizienten 1 sind => Parität des Polynoms (als Zahl betrachtet) muss 1 sein. Beispiel: X^3 + X^2 + X + 1 erfüll zwar Bedingungen 1) und 2a), nicht aber 2b) denn Einsetzen von 1 ergibt 0. Tatsächlich lässt sich das Polynom faktorisieren als X^3 + X^2 + X + 1 = (X + 1)·(X^2 + 1) = (X + 1)^3 2c) Das Polynom muss quadratfrei sein. Das kann man genauso testen wie bei "normalen" Polynomen, also z.B. solchen über Z: ggT (P, P') = 1. Dabei ist P' die formale Ableitung von P. Die Ableitung berechnet sich genauso wie bekannt, aber wegen 2 = 0 fallen alle ungeraden Koeffizienten weg: d/dX (X^3 + X^2 + X + 1) = 3·X^2 + 2·X + 1 = X^2 + 1. Es muss also ggT (X^3 + X^2 + X + 1, X^2 + 1) = 1 sein. ggT (X^3 + X^2 + X + 1, X^2 + 1) = ggT (X^3 + X^2 + X + 1 - X·(X^2 + 1), X^2 + 1) = ggT (X^2 + 1, X^2 + 1) = X^2 + 1 != 1 Dieses Polynom ist also nicht quadratfrei und damit reduzibel. Das sieht man zwar auch an dessen Faktorisierung (X + 1)^3 von oben, allerdings braucht man zur Berechnung des ggT wie bei den ganzen Zahlen nicht deren Faktorisierung, sondern man verwendet den Euklid'schen Algorithmus. > Bisher hab ich noch keines getroffen, dass maximale Länge hätte. Die obigen Bedingungen genügen allerdings nicht zur Irreduzibilität des Polynoms, es sind lediglich einige fix implementierbare Filter. Falls es dir nicht reicht, solche Polynome nachzuschlagen, dann gibt es mehrer Wege ein irreduzibles zu finden. Eine Konstruktion ist m.W. nicht möglich bzw. nicht bekannt, ähnlich wie bei Primzahlen, für die es keine Konstruktion gibt. > Aber ich hab hier einen "Parametersatz", der scheinbar unendliche > Periodenlänge liefert. Dann hst du irgendwo nen Bug.
Also... - bei einem LFSR maximaler Laenge, dh 2^N-1, kommt jeder Wert ausser der Null genau einmal vor. - wenn man das Register parallel ausliest und es erscheint wegen der anwenung, zB LED zu sehr wie ein Lauflicht, dann steht es einem ja frei, die ausgelesenen Bits vor der Weiterverarbeitung fest zu permutieren.
Thomas E. schrieb: > Auch > wenn sich Dein Code sicher auch noch etwas optimieren ließe Der Zufallsteil sieht bis jetzt so aus. Ich werd jetzt noch mal versuchen, das ganze neu gelesene einzubauen.
1 | uint16_t Zufall1(void) |
2 | {
|
3 | uint16_t Halter1 = LFSR1; |
4 | uint16_t Halter2 = 0; |
5 | |
6 | uint8_t i = 0; |
7 | |
8 | if ( (Zufall1_Flags & (1 << initialisiert)) == 0 ) //Falls init nicht ausgeführt wurde,... |
9 | {
|
10 | Zufall1_Flags |= (1 << initialisiert); |
11 | Zufall1_init(42); //... mit 42 initialisieren; |
12 | }
|
13 | |
14 | //Rückkopplungspunkte ver-xor-en und das Ergebnis aufs MSB setzen
|
15 | Halter1 = ( ( ( LFSR1 & (1 << 14) ) >> 14) ^ ( ( LFSR1 & (1 << 13) ) >> 13) |
16 | ^ ( ( LFSR1 & (1 << 11) ) >> 11) ^ ( ( LFSR1 & (1 << 0) ) >> 0) << 15 ); |
17 | |
18 | //Zufallszahl ein Richtung LSB verschieben
|
19 | Halter2 = (LFSR1 >> 1); |
20 | |
21 | //zusammenführen
|
22 | LFSR1 = Halter1 | Halter2; |
23 | |
24 | return LFSR1; |
25 | }
|
Johann L. schrieb: > (Pseudo)-zufällig sind die Folgen nicht: Wenn Wert X einmal aufgetreten > > Danke dir für deinen ausführlichen Beitrag. Den muss ich mir nochmal genauer zu Gemüte führen.... Johann L. schrieb: >> Aber ich hab hier einen "Parametersatz", der scheinbar unendliche >> Periodenlänge liefert. > > Dann hst du irgendwo nen Bug. Ja hab ihn auch gefunden. Der "Bug" war, das ich wohl eine Folge erwischt habe, die zwar periodisch ist, aber nicht mehr auf ihren Startwert kommt. Und da mein Startwert gleichzeitig mein Stopkriterium war, hat er dann nie angehalten. Zwölf M. schrieb: > wenn man das Register parallel ausliest und es erscheint wegen der > anwenung, zB LED zu sehr wie ein Lauflicht ja das fällt allerdings sehr deutlich ins Auge, wenn ich die Daten als Binär und nicht als ASCII aufs Terminal kommen lass.
Ich seh gerade, dass ganze könnte man auch noch ohne Halter1 und Halter2 hinbekommen einfach: LFSR1 = (die ganze Trumm hinter Halter1 =) | (LSFR1 >>1); und wenn man konsequent vor dem ersten Aufruf initialiert, kann man auch den Test auf initialisierung weglassen. (die ganze Trumm hinter Halter1 =) und wo wir schon dabei sind, die ganze Trumm besteht ja aus den Rückkopplungspunkten ( LFSR1 & (1 << 14) ) >> 14)... wie kann ich den Teil "(1 << 14) ) >> 14)" elegant in ein #define verwandeln, dass ich nur noch sowas wie LFSR1 & B14 schreiben kann? also a la #define Bn (1 << n) ) >> n) dann müsste ich aber im code immer (LFSR1 & B14 schreiben... auch irgendwie nicht schön. versteht der Compiler das überhaupt, mit dem n? oder müsste ich jedes bit einzeln definen?
Nach meinem Geschmack ein wenig zuviel hin- und hergeschiebe... Wenn Du unbedingt bei Deiner "many-to-one" Implementierung bleiben willst, kannst Du ja auch einfach den LFSR-Inhalt mit dem Polynomwert verunden und dann vom Ergebnis die 1-Bits zählen. Und sooft wechselst Du dann das MSB, also ungefähr so:
1 | xor_wert = lfsr & POLY; |
2 | lfsr >>= 1; |
3 | while (xor_wert != 0) |
4 | {
|
5 | if(xor_wert & 0x01) // für jedes gesetzte Bit: |
6 | lfsr ^= 0x8000; // MSB umschalten! |
7 | xor_wert >>= 1; // nächstes Bit auf 1 prüfen... |
8 | };
|
Thomas E. schrieb: > xor_wert = lfsr & POLY; > lfsr >>= 1; > while (xor_wert != 0) > { > if(xor_wert & 0x01) // für jedes gesetzte Bit: > lfsr ^= 0x8000; // MSB umschalten! > xor_wert >>= 1; // nächstes Bit auf 1 prüfen... > }; Nun verstehe ich deine Implementierung, danke für den Vorschlag. Nur ganz klar ist mir das POLY immer noch nicht. Bzw hab ne Vermutung was das macht bin mir aber nicht sicher ob es das wirklich macht. Es gibt ja diese ominöse Wundertabelle, mit den vielen Polynomen. Die sind ja als HEX dargestellt. Wenn ich das jetzt binär darstellen würde, wäre jede 1 ein "Rückkopplungspunkt"? Bitte sag ja :D natürlich nur, wenn es stimmt
:D Danke P.S. Dann verstehe ich jetzt endlich auch wirklich deine one to many version von weiter oben!
>> Dann hst du irgendwo nen Bug. > >Ja hab ihn auch gefunden. Der "Bug" war, das ich wohl eine Folge erwischt habe, die zwar periodisch ist, aber nicht mehr auf ihren Startwert kommt. Eher nicht. Periodisch bedeutet es kehrt zurueck. Nach genau eriner Periode.
Zwölf M. schrieb: > Eher nicht. Periodisch bedeutet es kehrt zurueck. Nach genau eriner > Periode. Tut sie aber dennoch. Ich steppe die Werte mit. Ich sehe, der erste Wert der erzeugt wird, ist 21 also genau die Hälfte vom Initialsierungswert 42. Welch ein Zufall. Meine Stopwert ist als Variable angelegt. Nachdem nun der erste Wert erzeugt ist, erzeuge ich sicherheitshalber noch den nächsten, setze dann per Hand die Stopvariable auf 21 und lasse ihn losrennen. Nach 8000irgendwas Durchläufen der Zufallsfunktion hält er wieder bei 21 an. Und eine Periode dauert halt rein definitionsgemäß genau eine Periode, manchmal dauert die halt nur sehr kurz, Gammastrahlung bspw. manchmal etwa 4 Wochen, bei ner Frau bspw. Wobei die Frau auch nicht von initialsierung an anfängt zu periodisieren. Sie hat quasi auch nen Startwert, der in der Periode später nicht mehr eintritt.
J. T. schrieb: > Johann L. schrieb: >> Dann hst du irgendwo nen Bug. > > Der "Bug" war, das ich wohl eine Folge erwischt habe, die zwar > periodisch ist, aber nicht mehr auf ihren Startwert kommt. Das kann passieren, wenn dein Polynom nicht irreduzibel ist. Einfaches Beispiel: n=2 und das Polynom ist X^2 + 1. Als Startwert nimmt man s_0 = 1, und in jedem Schritt multipliziert man mit X + 1. Dann hat man: s_0 = 1 s_1 = s_0·(X + 1) = 1·(X + 1) = X + 1 s_2 = s_1·(X + 1) = (X + 1)·(X + 1) = X^2 + 1 = 0 s_3 = s_2·(X + 1) = 0 s_4 = 0 s_5 = 0 ... Grund ist dass X^2 + 1 = (X + 1)^2 und daher nicht irreduzibel ist, was zu Nullteilern führt, d.h. es gibt Werte, die != 0 sind, deren Produkt aber 0 ist. Im Beispiel ist X + 1 so ein Nullteiler. Das ist nur ein Beispiel, und zwar für den Fall, dass dein Algorithmus wirklich eine Multiplikation in diesem Sinne implementiert. Momentan hab ich aber eher den Eindruck, dein Algorithus ist "Bits wild mit XOR durcheinanderwirbeln, wird schon was ordentliches rauskommen" :-) > Der Zufallsteil sieht bis jetzt so aus. Die Idee ist folgende: Man betrachtet Polynome über Z/2Z, wobei alle Polynome als gleich betrachtet werden, die sich nur um das Vielfache eines vorgegebenen Polynoms ("Generator") unterscheiden. Die Konstruktion ist also analog der Konstruktion der Komplexen Zahlen C aus den Reellen: Man nimmt alle Polynome mit reellen Koeffizienten, und betrachtet Polynome, die sich nur um ein Vielfaches von X^2 + 1 unterscheiden, als gleich. (Über R ist X^2 + 1 irreduzibel). Beispiel X·X = X^2 und -1 unterscheidet sich um ein Vielfaches von X^2 + 1, denn X^2 - 1·(X^2 + 1) = -1. Anstatt X^2 kann man also auch -1 schreiben. Über R gibt es nur eine endliche Körpererweiterung, nämlich C (vom Grad 2). Grund ist, das jedes Polynom über C in Linearfaktoren zerfällt, d.h. über C gibt es keine irreduziblen Polynome mehr. Über endlichen Körpern ist das jedoch anders: Über jedem endlichen Körper gibt es (mindestens) ein irreduzibles Polynom vorgegebenen Grades. Beispiel: P = X^2 + X + 1 ist irreduzibel über GF(2). Jedes Polynom A über GF(2) lässt sich also reduzieren zu einem Polynom von höchstens Grad 1, und aus der Polynom-Multiplikation und -Addition folgen entsprechende Rechenregeln für die reduzierten Polynome. A = a_1·X + a_0 mit a_i in GF(2) B = b_1·X + b_0 mit b_i in GF(2) Addition: A + B = (a_1 + b_1)·X + (a_0 + b_0) wobei die Addition rechts die Addition in GF(2) ist: a + b = a XOR b. Dies ist der Grund, warum in LFSRs XOR allgegenwärtig ist. Multiplikation: Die lässt sich zusammenbauen aus Addition und Multiplikation mit X: A·X = (a_1·X + a_0)·X = a_1·X^2 + a_0·X Multiplikation ist also nichts anderes als ein Shift um 1 nach links (wobei das natürlich davon abhängt, welche Darstellunskonvention verwendet wird. Ich bevorzuge hier 1 = 0b1, X = 0b10, X^2 = 0b100, ...) Dies ist der Grund, warum in LFSRs Shifts um 1 allgegenwärtig sind. Da a_1 in GF(2), gibt es nun 2 Möglichkeiten für A·X: A·X = a_0·X falls a_1 = 0 A·X = X^2 + a_0·X falls a_1 = 1 Im ersten Fall hat A·X Grad < 2. Im zweiten Falle hat A·X Grad 2 und durch Addition von P wird der X^2-Term zu 0: A·X = X^2 + a_0·X = X^2 + a_0·X + P = (1 + a_0)·X + 1 falls a_1 = 1 Die Fallunterscheidung nach Multiplikation ist der Grund, warum Maskierung auf MSB und Test (bzw. je nach Konvention auf LSB) bei LFSRs allgegenwärtig ist, und warum gegebenenfalls + P (in Binärdarstellung also XOR P) gerechnet wird. Beispiel in binär: P = X^2 + X + 1 = 0b111, A = X + 1 = 0b11. A·X = 0b11 << 1 = 0b110 = A·X + P = 0b110 XOR 0b111 = 0b001 = 1. M.a.W: (X + 1)·X = 1 > Und da mein Startwert gleichzeitig mein Stopkriterium > war, hat er dann nie angehalten. Das ist die ineffizenteste Möglichkeit überhaupt... Maximale Periodenlänge bedeutet, das die Periode 2^N - 1 ist. In Algebra übersetzt: GF(2) / P·GF(2) ist der Körper mit 2^N Elementen, geschrieben als GF(2^N). Die multiplikative Gruppe ist zyklisch, d.h. es gibt einen Erzeuger E, der, wenn er immer wieder aufmultipliziert wird, GF(2^N) \ {0} erzeugt. Beispiel von oben mit E = X und P = X^2 + X + 1: E^0 = 1 E^1 = X E^2 = X^2 = X + 1 E^3 = (X + 1)·X = X^2 + X = 1 E^4 = E^1 E^5 = E^2 ... Da GF(2^N) \ {0} eine zyklische Grupper der Ordnung M = 2^N - 1 ist, gilt: 1) Für jedes A in GF(2^N) \ {0} ist A^M = 1 2) Es gibt einen zyklischen Erzeuger E von GF(2^N) \ {0} mit: 2a) E^M = 1 2b) E^(M/p) != 1 für jeden Primteiler p von M. Ein weiterer Test, ob P irreduzibel ist — und ob es somit taugt, um Sequenzen von maximaler Länge M zu erzeugen — ist daher: Falls man ein A != 0 findet mit A^M mod P != 1 dann ist P nicht irreduzibel. Dabei berechnet man A^M nicht durch fortwährende Multiplikation mit A, sondern A^130 zum Beispiel gemäß (((((((A^2)^2)^2)^2)^2)^2 · A)^2 d.h. man expandiert den Exponenten binär: A^130 = A^0b10000010 = (A^0b1000001)^2 = ((A^0b100000)^2 · A)^2 = ... Und die Reduktion geschieht nicht nach dem Potenzieren, sondern die reduktion mod P ist in jede Multiplikation bereits "eingebaut". Für GF(2^16) kann mal also versuchen P und E zu finden, so dass E^65535 = 1 mod P E^(65535/3) != 1 mod P E^(65535/5) != 1 mod P E^(65535/17) != 1 mod P E^(65535/257) != 1 mod P > Zwölf M. schrieb: >> wenn man das Register parallel ausliest und es erscheint wegen der >> anwenung, zB LED zu sehr wie ein Lauflicht > > ja das fällt allerdings sehr deutlich ins Auge, wenn ich die Daten als > Binär und nicht als ASCII aufs Terminal kommen lass. Dann hat man nur 1 "Schritt" gemacht, der wie oben erklärt i.W. nur aus einem Shift besteht. Da viele LFSRs zudem Polynome mit wenig Einsen verwenden (ist wohl hie und da schneller zu implementieren) brint ein mögliches XOR mit dem Polynom auch nicht viel. Erst wenn man eine Multiplikation wie oben ausführt — und die besteht aus N "Schritten", ergeben sich verwendbare Werte. J. T. schrieb: > Und eine Periode dauert halt rein definitionsgemäß genau eine Periode, > manchmal dauert die halt nur sehr kurz, Du liest zu viel Bindl.
Johann L. schrieb: > Du liest zu viel Bindl. Erwischt :D Da hast du mir ja wieder einiges vorgelegt. Vielen Dank für deine Mühe. Das muss ich auch erst nochmal sacken lassen. Und evtl auch noch ein zweimal lesen.
Angehängte Dateien:
-
LFSR.PNG
9,6 KB
Johann L. schrieb: > Da viele LFSRs zudem Polynome mit wenig Einsen > verwenden (ist wohl hie und da schneller zu implementieren) brint ein > mögliches XOR mit dem Polynom auch nicht viel. Man kann ja auch einfach eins mit vielen Einsen verwenden, z.B. 0x95CC. Aber korrekter ist natürlich, für jede "Zufallszahl" alle 16 Bits komplett durchzuschieben. Von "außen" betrachtet, gibt es dann trotzdem 65535 verschiedene Zahlen:
1 | #define POLY 0x95CC
|
2 | #define START 42
|
3 | |
4 | int main(int argc, char** argv) { |
5 | |
6 | int i,j; |
7 | uint16_t lfsr = START; |
8 | |
9 | for(i=1; i<65536; i++) |
10 | {
|
11 | for(j=0; j<16; j++) |
12 | {
|
13 | if(lfsr & 0x0001) |
14 | lfsr = (lfsr >> 1) ^ POLY; |
15 | else
|
16 | lfsr >>= 1; |
17 | }
|
18 | if(lfsr == START) |
19 | break; |
20 | }
|
21 | if(i<65536) |
22 | printf("\nWiederholung nach %d Schleifen.",i); |
23 | else
|
24 | printf("\nWiederholung nicht erreicht!"); |
25 | |
26 | |
27 | return 0; |
28 | }
|
Johann L. schrieb: > Als Startwert nimmt man s_0 > = 1, und in jedem Schritt multipliziert man mit X + 1 Aber wo bleibt dann das Polynom ??? Ich schau da irgendwie grad verwirrt aus der Wäsche... Johann L. schrieb: > Grund ist dass X^2 + 1 = (X + 1)^2 hier komm ich nicht ganz hinterher... (x + 1)^2 ist doch quasi die binomische Formel? Das wäre dann doch x^2 + 2x + 1^2 = x^2 + 2x + 1 != x2 + 1 ??? Johann L. schrieb: > dein Algorithus ist "Bits wild mit XOR > durcheinanderwirbeln, wird schon was ordentliches rauskommen" :-) Ich hab halt einfach versucht, nachzubauen was ich gesehen hab. Ein Schieberegister: Dafür kann ja wunderbar eine Variable herhalten, dacht ich mir. Ein paar XORs die auf den Eingang gehen: Mhhh, da gehts ja nur um ein bit, also bitx rauspicken ---> Zufallsvaribale & (1 << x) schonmal das bit rausgepickt. Aber ich will ja nur ein bit zurückführen. Wenn ich das einfach so mit bit y ver-xor-e, bekomme ich ja u. U. nicht nur ein bit zurück. Also alle auf die selbe Stelle setzen zum ver-xor-en, daher das >> x) noch dazu. Das soll jetzt auch keine Erklärung sein, wie mein Code funktioniert, ich denke dass hast du schon verstanden ;), aber es soll son bischen meine Gedankengänge aufskizzieren (fast hätte ich aufzeigen gesagt :D) um zu erklären, warum der Code so geworden ist Johann L. schrieb: > wobei alle > Polynome als gleich betrachtet werden, die sich nur um das Vielfache > eines vorgegebenen Polynoms ("Generator") unterscheiden. > > Die Konstruktion ist also analog der Konstruktion der Komplexen Zahlen C > aus den Reellen: Man nimmt alle Polynome mit reellen Koeffizienten, und > betrachtet Polynome, die sich nur um ein Vielfaches von X^2 + 1 > unterscheiden, als gleich. (Über R ist X^2 + 1 irreduzibel). Versteh ich soweit, aber was ist Z/2Z? Johann L. schrieb: > Beispiel X·X = X^2 und -1 unterscheidet sich um ein Vielfaches von X^2 > + 1, denn X^2 - 1·(X^2 + 1) = -1. Anstatt X^2 kann man also auch -1 > schreiben. Hier komm ich wieder nicht hinterher... X*X = X^2 ist soweit klar :D aaaber: X^2 und -1 im Sinne von X^2 + (-1) unterscheidet sich um ein Vielfaches von X^2 + 1 ---> X^2 + (-1) = (X^2 + 1) * y??? X^2 - 1·(X^2 + 1) = -1 und fehlt da ne Klammer um das X^2 - 1 ?? aber irgendwie macht beides grad kein Sinn für mich... Mathe hat mich irgendwie schon immer verwirrt, bis ich es denn endlich mal begriffen hab. Danach kommt dann immer das Gefühl, Mathematiker versuchen einfache Sachverhalte möglichst kompliziert auszudrücken :D Im Fall dass die Klammer fehlen sollte, wäre das Ganze ja wieder die dritte binomische: (X^2 + 1) * (X^2 - 1) = X^4 - X^2 + X^2 + (-1) = X^4 - 1 AAAHHHjetzt grad machts klick, zumindest für diesen Teil. X^2 - 1 * (X^2 + 1) = X^2 - (X^2 - 1) = -1.. Für heute erst mal nur bis hier... den Rest guck ich mir morgen nochmal an...
J. T. schrieb: > Johann L. schrieb: >> Grund ist dass X^2 + 1 = (X + 1)^2 > > hier komm ich nicht ganz hinterher... (x + 1)^2 ist doch quasi die > binomische Formel? Das wäre dann doch x^2 + 2x + 1^2 = x^2 + 2x + 1 != > x2 + 1 ??? Die binomische Formel passt schon. Die Koeffizienten der Polynome sind jedoch keine ganzen Zahlen! Die Koeffizienten sind aus Z/2Z, und dort gilt 1 + 1 = 0 bzw. etwas allgemeiner a + b = a XOR b und a·b = a AND b. Das Rechnen in Z/2Z entspricht dem Rechnen mit geraden Zahlen und ungeraden Zahlen, wobei 1 mit den ungeraden Zahlen identifiziert wird und 0 mit den geraden Zahlen. Die Summe zweier ungerader Zahlen ist immer eine gerade Zahl: ungerade + ungerade = gerade bzw. 1 + 1 = 0. Man rechnet also nur mit den Resten, die nach Division durch 2 bleiben. Der Witz dabei ist, dass das Ergebnis von Multiplikation, Addition, Subtraktion etc. unabhängig davon ist, welche gerade oder ungerade Zahl man verwendet. In Z/10Z, also Rechnen mit den Resten mod 10, kann man's genauso machen: 5·2 = 0 ist also die Kurzschreibe von: Wenn man eine ganze Zahl, die in Dezimaldarstellung auf 5 endet, mit einer multipliziert, die in Dezimaldarstellung auf 2 endet, dann endet das Ergebnis in Dezimaldarstellung auf 0. Analog z.B. für Addition: 7 + 4 = 1. Allgemein gilt in Z/pZ mit p Primzahl, dass (a+b)^p = a^p + b^p. Z.B. in Z/3Z: (a+b)^3 = a^3 + 3·a^2·b + 3·a·b^2 + b^3 = a^3 + b^3 denn in Z/3Z ist 1 + 1 + 1 = 0. Prüf's einfach nach und addiere 3 ganze Zahlen, die bei Division durch 3 Rest 1 haben. Das Ergebnis der Addition ist immer durch 3 teilbar, d.h. 0 mod 3, d.h. die 0 in Z/3Z. > Johann L. schrieb: >> Als Startwert nimmt man s_0 = 1, und in jedem Schritt >> multipliziert man mit X + 1 > > Aber wo bleibt dann das Polynom ??? Ich schau da irgendwie grad verwirrt > aus der Wäsche... Das kommt erst bei der Reduktion ins Spiel, also wenn ein Polynom A entsteht mit grad(A) >= grad(P). Am einfachsten wird die Berechnung bzw. Reduktion mod P, wenn man die Grade der Zwischenwert-Polynome nicht zu groß werden lässt, d.h. nicht über grad(P)-1 wachsen lässt: Wenn grad(A) < grad(P), dann ist grad(A·X) <= grad(P) Falls grad(A·X) < grad(P) fertig Falls grad(A·X) = grad(P) ==> grad(A·X + P) < grad(P) wenn man Polynome über Z/2Z hat: Sowohl A·X als auch P haben einen Term mit X^grad(P), und wegen X^grad(P) + X^grad(P) = 0 hat A·X + P keinen solchen Term mehr => grad(A·X + P) < grad(P). > Johann L. schrieb: >> wobei alle >> Polynome als gleich betrachtet werden, die sich nur um das Vielfache >> eines vorgegebenen Polynoms ("Generator") unterscheiden. >> >> Die Konstruktion ist also analog der Konstruktion der Komplexen Zahlen C >> aus den Reellen: Man nimmt alle Polynome mit reellen Koeffizienten, und >> betrachtet Polynome, die sich nur um ein Vielfaches von X^2 + 1 >> unterscheiden, als gleich. (Über R ist X^2 + 1 irreduzibel). > > Versteh ich soweit, aber was ist Z/2Z? Z sind die ganzen Zahlen. 2Z das 2-fache aller Elemente, d.h. die geraden Zahlen: 2·Z = { ..., -4, -2, 0, 2, 4, 6, ... } Ausgesprochen wird Z/2Z als "Z modulo 2Z" Die Schreibweise bedeutet: Nimm alle ganzen Zahlen, und betrachte zwei Zahlen als "gleich", wenn ihre Differenz in 2Z liegt. Das Ergebnis davon ist die Einteilung der ganzen Zahlen in 2 Klassen: [0] := {..., -4, -2, 0, 2, 4, 6, ... } [1] := {..., -3, -1, 1, 3, 5, ... } Der Witz ist, dass man mit [0] und [1] rechnen kann, indem man die Operationen aus Z übernimmt: Um etwa [0]+[1] zu berechnen, nimmt man irgendein Element aus [0], addiert irgendeines aus [1], und schaut, in welcher Klasse das Ergebnis ist: [0]+[1] = [1]. Das entspriche dem Rechnen mit Resten mod 2. Das entscheidende ist, dass das Ergebnis unabhängig davon ist, welche Elemente man miteinander verknüpft. Relevant ist nur, aus welcher Klasse (gerade oder ungerade) sie stammen. Manchmal wird Z/2Z auch als GF(2) bezeichnet, also also Galois-Field (Endlicher Körper) mit 2 Elementen. Da es ein Körper ist, hat man darin Operationen + und · mit o + und · sind kommutativ, assoziativ und abgeschlossen o + und · besitzen ein neutrales Element, geschrieben als 0 bzw. 1. o + und sind distributiv: (a+b)·c = a·c + b·c etc. o + ist inverterbar: a + c = b + c ==> a = b Das additiv Inverse zu a wird auch notiert als -a. a + (-b) wird auch notiert als a - b. o · ist in GF(p^n) \ {0} invertierbar: a·c = b·c ==> a = b Das multiplikativ Inverse zu a wird auch notiert als a^{-1}. a · b^{-1} wird auch notiert als a / b. Invertierbar in Z/nZ sind nur diejenigen Elemente, die teilerfremd zu n sind. In Z/10Z also 1, 3, 7, 9. 1 / 3 = 7 bedeutet also: Dividiert man eine Dezimalzahl, die durch 3 teilbar ist und auf 1 endet, durch 3, dann endet das Ergebnis auf 7. Für nicht-invertierbare Elemente sind entsprechende Aussagen nicht möglich. > Johann L. schrieb: >> Beispiel X·X = X^2 und -1 unterscheidet sich um ein Vielfaches von X^2 >> + 1, denn X^2 - 1·(X^2 + 1) = -1. Anstatt X^2 kann man also auch -1 >> schreiben. > > Hier komm ich wieder nicht hinterher... Nimm zwei Polynome A und B. Wenn A - B = k·(X^2 + 1) ist, dann betrachte A und B als gleich (modulo X^2 + 1). Dabei muss k ein Wert aus dem Körper sein: Bei der Konstruktion von C aus R ist k ein Element von R, bei Polynomen über GF(2) ist k ein Element von GF(2). > X*X = X^2 ist soweit klar :D aaaber: > > X^2 und -1 im Sinne von X^2 + (-1) unterscheidet sich um ein Vielfaches > von X^2 + 1 ---> X^2 + (-1) = (X^2 + 1) * y??? A = X^2 B = -1 A - B = X^2 + 1 ist ein Vielfaches von P = X^2 + 1, d.h. A und B sind gleich mod P. M.a.W: Man kann beliebige Vielfache von P addieren / abziehen, ohne dass sich der Wert mod P ändert. Ist ganz analog zum Rechnen in Z/nZ: Der Rest bei Division durch n ändert sich nicht, wenn man beliebige Vielfache von n addiert: a mod n = (a + k·n) mod n für beliebige a, k aus Z und n aus Z\{0}. > X^2 - 1·(X^2 + 1) = -1 und fehlt da ne Klammer um das X^2 - 1 ?? Nein. Mit P = X^2 + 1 steht da: X^2 - 1·P = -1. > Danach kommt dann immer das Gefühl, Mathematiker versuchen einfache > Sachverhalte möglichst kompliziert auszudrücken :D Oft gibt es mehrere Möglichkeiten, das gleiche Ding zu betrachten. Feynman:
1 | We could, of course, use any notation we want; do not laugh at |
2 | notations; invent them, they are powerful. In fact, mathematics is, |
3 | to a large extent, invention of better notations. |
> AAAHHHjetzt grad machts klick, zumindest für diesen Teil. X^2 - 1 * (X^2 > + 1) = X^2 - (X^2 - 1) = -1.. :-)
Weiter im Takt =) Johann L. schrieb: > und warum gegebenenfalls + P (in Binärdarstellung > also XOR P) gerechnet wird. Bis dahin verstehe ich es im groben tatsächlich. Hier nur ne kleine Wissenslücke. Ist XOR wirklich +? Also: 0b01 ^ 0b01 = 0b00 oder = 0b10 ? Ich meine beim bitweisen XOR sollte das doch 0 ergeben? Oder gilt XOR <=> + wieder nur in unserem GF(2)? Johann L. schrieb: > wobei das natürlich davon abhängt, welche Darstellunskonvention > verwendet wird Man kann ja einfach sagen "Shift Richtung MSB" oder halt Richtung LSB, statt links und rechts, da wäre man dann konventionsunabhängig Johann L. schrieb: > (X + 1)·X = 1 hieße dass nicht auch ausgeklammert X^2 + x = 1? Und dann könnte man X^2 + X + 1 doch einfach als 1 + 1 schreiben??!?!? Sorry falls du da schon was zu erwähnt hast, aber dass is echt viel neues auf einmal für mich. Mal nebenbei, es macht Spass von dir zu lernen, kein Galileo-Niveau, und wenn ich was nicht versteh, gehst du nochmal drauf, echt super, dass du dir die Mühe machst. Johann L. schrieb: > Da GF(2^N) \ {0} Wie liest man dass jetzt wieder? GF(2^N) Modulo 0??!?!? Johann L. schrieb: > E^65535 = 1 mod P > E^(65535/3) != 1 mod P > E^(65535/5) != 1 mod P > E^(65535/17) != 1 mod P > E^(65535/257) != 1 mod P Hab mich erst gewundert, wo plötzlich die 3 5 17 und 257 herkommen. Aber dass sind einfach nur die Primteiler von 2^16 Johann L. schrieb: > o · ist in GF(p^n) \ {0} invertierbar: a·c = b·c ==> a = b bis hierhin ist wieder einiges klarer geworden. Aber diese 0 in den geschweiften Klammern... ich weiß einfach nicht, was sie mir sagen will... Ansonsten waren das sehr erhellende Worte =) Johann L. schrieb: > Feynman:We could, of course, use any notation we want; do not laugh at > notations; invent them, they are powerful. In fact, mathematics is, > to a large extent, invention of better notations. Und invention of better notations is schwerst notwendig :D. Ich tu mich immer wahnsinnig schwer damit, sowas zu entziffern...
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.