<Irrelevante Backstory>
Bei einer aktuellen Bastelei bekomme ich einen Ausschnitt aus der
Sequenz eines Fibonacci-LFSR mit bekanntem Polynom (0x1d258). Jenachdem
wie lange seit der Initialisierung des "Generators" (auf 0x00001)
vergangen ist werden andere Aktionen ausgeführt.
</Irrelevante Backstory>
Im Grund funktioniert das Konzept auch halbwegs solide. Einziges Problem
ist die Geschwindigkeit. Das Zielsystem (esp32) schafft die Menge an
Bit-Vergleichen die so ein Fibonacci-LFSR braucht nicht grade schnell.
Daher die Idee auf ein Galois-LFSR umzustellen. Dort wird nur ein Bit
verglichen und das Polynom auf das ganze Register ge-XORt.
Laut: http://notabs.org/lfsr/lfsr.html kann ich das gleiche Polynom
nutzen und muss nur die Schieberichtung umdrehen.
Funktioniert aber nicht :(
Hier ein (ziemlich zusammengekürzter) Beispielcode um das Problem zu
verdeutlichen.
uint32_toutreg=0;//Ausgaberegister für Galois-LFSR
44
uint32_tlfsr=1;//Startwert für Galois-LFSR
45
46
for(i=0;i<999999;i++){//Laufzeitbegrenzung für fehlerhafte Initialisierung
47
if(lfsr&1){//Das niedrigste Bit ist der "Ausgang" des Galois LFSR
48
//"Ausgang" == 1
49
lfsr=(lfsr>>1)^poly;//Schieben nach links (andere Richtung als Fibonacci) + XOR mit Polynom
50
outreg=(outreg<<1)|1;//Schieben der 1 in das Ausgaberegister
51
}
52
else{
53
//"Ausgang" == 0
54
lfsr=lfsr>>1;//Nur Schieben (ohne XOR)
55
outreg=outreg<<1;//Schieben der Ausgabe (0 eingefügt)
56
}
57
if((outreg&0x1FFFF)==(state&0x1FFFF))break;//Vergleich der erzeugten Sequenz mit der Empfangenen
58
}
59
returni;
60
}
Die Ausgabe sieht so aus:
1
FIB: counts = 71560
2
GAL: counts = 36751
3
4
Advancing Stream by 10 steps.
5
6
FIB: counts = 71550
7
GAL: counts = 15417
Wie man sieht funktioniert das Fibonacci-LFSR wie erwartet und zählt
korrekt zehn Takte weniger wenn man ihm einen früheren Teil des Streams
"verabreicht".
Das Galois-LFSR springt aber wild rum mit den counts.
Ein Offset war zu erwarten (der interne Zustand beim Galois ist nicht
der gleiche wie beim Fibonacci), aber die Änderung beim Fortschreiten
(bzw. zurückdrehen) des Bit-Streams sollte identisch sein.
tl,dr: Wie krieg ich ein Galois-LFSR das mir den selben Bit-Stream
liefert wie ein Fibonacci-LFSR mit 0x1d258 als Polynom.
Max D. schrieb:> Jenachdem wie lange seit der Initialisierung des "Generators"> (auf 0x00001) vergangen ist werden andere Aktionen ausgeführt.
D.h. du verwendest es als Pseudozufalls-Generator?
Max D. schrieb:> Das Zielsystem (esp32) schafft die Menge an> Bit-Vergleichen die so ein Fibonacci-LFSR braucht nicht grade schnell.>> Daher die Idee auf ein Galois-LFSR umzustellen.
Warum erwartest du, dass ein Galois-LFSR weniger Rechenaufwand
generiert?
Einmal hast du den Aufwand beim Auswerten vom Status und im anderen Fall
mit dem Bitverknüpfung beim Schieben, d.h. an die Stelle der
bitintensiven Auswertung des Zustandes tritt eine bitintensive
Schieberei.
Bist du sicher, dass das schneller geht?
Johann L. schrieb:> D.h. du verwendest es als Pseudozufalls-Generator?
Das Generator-LFSR ist nicht unter meiner Kontrolle und läuft effektiv
als Zähler. Ich versuche den "Zählerstand" von der eingetroffenen
Sequenz zu bestimmen (funktioniert auch wenn ich selber ein Fibonacci
lfsr nehm).
Wolfgang schrieb:> Warum erwartest du, dass ein Galois-LFSR weniger Rechenaufwand> generiert?> Einmal hast du den Aufwand beim Auswerten vom Status und im anderen Fall> mit dem Bitverknüpfung beim Schieben, d.h. an die Stelle der> bitintensiven Auswertung des Zustandes tritt eine bitintensive> Schieberei.>> Bist du sicher, dass das schneller geht?
Praktisch jede CPU (also höchstwahrscheinlich auch der ESP) hat ein
XOR-Mnemonic im Assembler bei dem er zwei Register miteinander
bitweise-xor verknüpft.
Das Auswerten der Bits beim Fibonacci dagegen hat keinen direkten
Assembler-Befehl (auf x86 gabs glaube ich in den SSEs was
entsprechendes, aber RISCs haben da nix).
Grundsätzlich auch egal.
Selbst wenn das Galois-LFSR langsamer wäre sollte es doch trotzdem
funktionieren.
Max D. schrieb:> Johann L. schrieb:>> D.h. du verwendest es als Pseudozufalls-Generator?>> Das Generator-LFSR ist nicht unter meiner Kontrolle und läuft effektiv> als Zähler. Ich versuche den "Zählerstand" von der eingetroffenen> Sequenz zu bestimmen (funktioniert auch wenn ich selber ein Fibonacci> lfsr nehm).
Ich find dieses Bitgefummel ja immer ziemlich unübersichtlich.
Vielleicht geeignet um eine Schaltung aufzubauen, aber die Mathe
dahinter geht dabei flöten...
F_p^n, den endlichen Körper der Ordnung p^n (p prim) kann man
realisieren, indem man ein irreduzibles Polynom q aus F_p vom Grad n
nimmt und alle Potenzen einer Nullstelle von q(x) adjungiert, d.h.
hinzunimmt: q(x) = 0.
Das Verfahren ist genau das gleiche wie bei der Konstruktion der
Imaginären Zahlen aus den Reelen: Dort nimmt man als Polynom x^2 + 1,
die Nullstelle bezeichnet mal als i. Weil i eine Nullstelle des
Polynoms ist, gilt i^2 = -1.
Charakteristik 2 hat den Vorteil, dass die Basisoperationen im Körper
sehr einfach sind. Weil F_2 nur die beiden Elemente 0 und 1 hat, kann
man ein Polynom vom Grad m durch m+1 Bits darstellen, wobei der
höchstwertige Koeffizient 1 sein muss: q(x) = x^m + ...
Addition: Zwei Polynome a(x) und b(x) addiert man, indem man die
einzelnen Koeffizienten addiert. Weil diese aus F_2 sind, ergibt sich
bei der Darstellung als Bitstring: a(x) + b(x) = a XOR b wenn man die
Bitstrings a und b als Zahlen auffasst.
Multiplikation mit x: Alle Koeffizienten wandern zur nächst
höherwertigen Stelle da sie mit x multipliziert werden. Die Elemente
von F_2^n sind ja Polynome in x. Für das F_2^n erzeugende Polynom q(x)
gilt:
q(x) = x^n + r(x) = 0 mit Grad(r) < n, daher: x^n = -r(x) = r(x)
Entstehen beim Linksshift eines Elements a(x) Koeffizienten vom Grad >=
n, dann kann man diese also durch ein Polynom vom Grad < n darstellen.
Die Elemente von F_2^n lassen sich also (eindeutig) durch Polynome vom
Grad < n darstellen, sind also darstellbar durch die n-Bit Zahlen 0 ...
2^n - 1.
Beispiel: F_2^2 = { 0, 1, x, x + 1 } generiert durch q(x) = x^2 + x +
1.
a = x + 1, berechne x·a.
x·a = x·(x + 1) = x^2 + x = x + 1 + x = 1 wegen x^2 = x + 1.
Du hast also sehr einfache Arithmetik in F_2^n. Multiplikation mit
einem Körperelement lässt sich aus Additionen (XOR) und Multiplikationen
mit x (Linksschieben) zusammenbauen.
Im Text wird das als "Galois-LFSR" bezeichnet.
Was "Fibonacci-LFSR" darstellt seh ich jett nicht, aber es ist angeblich
isomorph dazu. Was ist der Isomorphismus?
Johann L. schrieb:> Du hast also sehr einfache Arithmetik in F_2^n. Multiplikation mit> einem Körperelement lässt sich aus Additionen (XOR) und Multiplikationen> mit x (Linksschieben) zusammenbauen.
...und diese wiederum kann man als Multiplikation mit einer Matrix M
darstellen.
Die multiplikative Gruppe F_p^n*, also alle Elemente != 0 in F_p^n ist
zyklisch erzeugt, d.h. es gibt ein Element w in F_p^n* — eine s.g.
primitive Einheitswurzel (primitive root of unity, PRU) — so dass:
1) w^(p^n - 1) = 1
2) Kein anderes m mit 0 < m < p^n - 1 = #(F_p^n*) erfüllt w^m = 1.
Das bedeutet, wenn man eine PRU w gefunden hat[1], dann bekommt man alle
Elemente von F_p^n* indem man w fortwärend mit sich selbst
multipliziert:
1, w, w^2, w^3, ... w^(p^n - 1) = 1 = w^0 liefert also alle Elemente !=
0 des Körpers, d.h. man iteriert für p = 2 durch eine wilde Permutation
der n-Bit Zahlen != 0.
Die Multiplikation mit w lässt sich wie gesagt als Matrixmultiplikation
mit einer Matrix M = M(w) schreiben, und jedes w^m in F_p^n* hat
folglich die Darstellung M^m·1 mit m in 0...p^n - 2. Dabei bedeutet
"·1" Multiplikation mit der 1 in F_p^n* (dargestellt als Vektor) damit
man von einer Matrix wieder auf ein Polynom kommt.
Ein möglicher Isomorphismus wäre also, (M^t)^m zu verwenden anstatt M^m,
wobei ^t Matrixtransposition bezeichnet.
Das das der Isomorphismus zwischen "Galois" und "Fibonacci"?
[1] In einem genau festlegbaren Sinn gibt es "viele" primitive
Einheitswurzeln. Man kann eine PRU also finden, indem man zufällig ein
Element w von F_p^n* wählt und testet, ob es die o.g. Eigenschaften hat.
Falls 1) nicht erfüllt ist, d.h. w^(p^n - 1) != 1 ist, dann bedeutet
dies übrigens, dass q(x) nicht irreduzibel über F_p ist. Nach dem
kleinen Satz von Fermat ist 2) einfach zu testen, vorausgesetzt man
kennt die Faktorisierung von p^n - 1.
Johann L. schrieb:> Ein möglicher Isomorphismus wäre also, (M^t)^m zu verwenden anstatt M^m,> wobei ^t Matrixtransposition bezeichnet.>> Ist das der Isomorphismus zwischen "Galois" und "Fibonacci"?
Falls dem so ist (Hausaufgabe), dann kommt man von einer Darstellung zur
anderen, indem man von rechts mit M^{-m}·M^t^m (bzw. deren Inversen,
also M^t^{-m}·M^m) multipliziert. Oder von links mit M^t^m·M^{-m}
multipliziert (bzw. mir deren Inversen, also M^m·M^t^{-m}).