Fibonacci-LFSR umwandeln in Galois-LFSR

[Max D. (max_d)]

<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.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>


uint32_t findLFSRstateFIB(uint32_t poly, uint32_t state);
uint32_t findLFSRstateGAL(uint32_t poly, uint32_t state);


int main()
{
    uint32_t inreg = 0x2219702cab68; //(Hier simulierte) Übergabe des LFSR-Zustandes von dem anderen Prozess.
    uint32_t fibpoly = 0x1d258; //Polynom des Fibonacci LFSR. Hier auf 0x1d258 initialisiert
    uint32_t galpoly = fibpoly; //Polynom des Galois LFSR. Laut http://notabs.org/lfsr/lfsr.html identisch zu Fibonacci


    printf("FIB: counts = %ld\n",findLFSRstateFIB(fibpoly,inreg));//Ausgabe des Fibonacci-LFSR (71560)
    printf("GAL: counts = %ld\n",findLFSRstateGAL(galpoly,inreg));//Ausgabe der Galois-LFSR Zählung(36751)
    
    inreg = inreg >> 10; //Schieben simuliert früheren Teil des Bit-Streams
    printf("\nAdvancing Stream by 10 steps.\n\n");

    printf("FIB: counts = %ld\n",findLFSRstateFIB(fibpoly,inreg));//Ausgabe des Fibonacci-LFSR (71550, korrekt)
    printf("GAL: counts = %ld\n",findLFSRstateGAL(galpoly,inreg));//Ausgabe der Galois-LFSR Zählung (15417, FALSCH !!! Richtig wäre 36751+10 = 36761)
    
    return 0;
}


uint32_t findLFSRstateFIB(uint32_t poly, uint32_t state){
    uint32_t i;
    uint32_t lfsr = 1; //Startwert für Fibonacci-LFSR
    for(i=0;i<999999;i++){ //Laufzeitbegrenzung für fehlerhafte Initialisierungen
        lfsr = (lfsr << 1)|(!__builtin_parity(lfsr & poly)); //Iteration des Fibonacci LFSR
        if((lfsr & 0x1FFFF) == (state&0x1ffff)) break; //Vergleich mit Empfangener Sequenz
    }
    return i;
}


uint32_t findLFSRstateGAL(uint32_t poly, uint32_t state){
    uint32_t i;
    uint32_t outreg = 0; //Ausgaberegister für Galois-LFSR
    uint32_t lfsr = 1; //Startwert für Galois-LFSR

    for(i=0;i<999999;i++){ //Laufzeitbegrenzung für fehlerhafte Initialisierung
        if(lfsr & 1){ //Das niedrigste Bit ist der "Ausgang" des Galois LFSR
            //"Ausgang" == 1
            lfsr = (lfsr >> 1)^poly; //Schieben nach links (andere Richtung als Fibonacci) + XOR mit Polynom
            outreg = (outreg << 1)|1; //Schieben der 1 in das Ausgaberegister
        }
        else{
            //"Ausgang" == 0
            lfsr = lfsr >> 1; //Nur Schieben (ohne XOR)
            outreg = outreg << 1; //Schieben der Ausgabe (0 eingefügt)
            }
        if((outreg & 0x1FFFF) == (state & 0x1FFFF)) break; //Vergleich der erzeugten Sequenz mit der Empfangenen
    }
    return i;
}

Die Ausgabe sieht so aus:

FIB: counts = 71560
GAL: counts = 36751

Advancing Stream by 10 steps.

FIB: counts = 71550
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.

[Johann L. (gjlayde)]

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?

[Wolfgang (Gast)]

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?

[Max D. (max_d)]

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.

[Johann L. (gjlayde)]

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. (gjlayde)]

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. (gjlayde)]

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}).