Einleitung
Diese Seite lässt sich in einem Satz zusammenfassen: Wenn man das Polynom eines LFSR von der Galois-Form in die Fibonacci-Form umwandeln möchte, dreht man die Reihenfolge der Koeffizienten einfach um.
Als Beispiel zeigt das folgende Schaltbild das LFSR, das häufig in Verwürflern (engl. scrambler) verwendet wird:
Jeder Block, der mit D markiert ist, ist eine Verzögerung um einen Taktzyklus. Die Darstellung dieses LFSR als Galois-Polynom lautet:
G(x) = x16 + x5 + x4 + x3 + 1
Beachten Sie: Die Exponenten im Polynom (3, 4 und 5) geben an, wie viele Verzögerungsglieder sich links von jedem XOR befinden.
Dasselbe LFSR kann auch in Fibonacci-Form implementiert werden, wie dieses Schaltbild zeigt:
Trotz der Ähnlichkeit der beiden Schaltbilder sind die Pfeilrichtungen umgekehrt. Die Implementierungen der LFSRs sind vollkommen verschieden.
Das Fibonacci-Polynom (auch Rückkopplungspolynom genannt) lautet:
F(x) = x16 + x13 + x12 + x11 + 1
Der Grad des Polynoms ist n=16, daher wird jedes xi in G(x) in F(x) durch xn-i dargestellt. Der Rest dieser Seite zeigt, warum das kein Zufall ist.
Eine allgemeine Erklärung zu LFSRs finden Sie auf der Wikipedia-Seite zu diesem Thema.
LFSR und digitale Filter
Die Theorie digitaler Filter (z. B. FIR-Filter und IIR-Filter) wird normalerweise auf dem Körper der komplexen Zahlen angewendet. Man kann diese Theorie jedoch auch auf GF(2) anwenden, also auf den endlichen Körper (Galois-Feld), der aus den zwei Zahlen 0 und 1 besteht. Dabei sind ein paar Dinge zu beachten:
- Das Pluszeichen in diesem Körper entspricht einer XOR-Verknüpfung.
- Alle Multiplikationen betreffen ausschließlich ganze Zahlen. Tatsächlich ist die Multiplikation mit einer geraden Zahl äquivalent zu einer Multiplikation mit 0. Ebenso ist die Multiplikation mit einer ungeraden Zahl äquivalent zu einer Multiplikation mit 1. Ob die Zahl positiv oder negativ ist, spielt dabei keine Rolle.
- Wegen dieser Regel bei den Multiplikationen bedeuten Plus und Minus dasselbe. Beide können durch ⊕ ersetzt werden, das für XOR steht.
Die grundlegende Theorie digitaler Filter setzt lediglich voraus, dass das System linear und zeitinvariant (LTI) ist. Ein LFSR erfüllt diese Voraussetzungen, denn XOR ist linear, und das Verhalten eines LFSR ist zeitinvariant.
Die interessanteste Konsequenz ist, dass man die z-Transformation zur Analyse von LFSRs verwenden kann. Betrachten wir zum Beispiel dieses Schaltbild:
Das lässt sich durch die folgende Gleichung beschreiben:
y(t) = x(t) ⊕ x(t-1)
t ist eine ganze Zahl, die die Zeit repräsentiert.
Man kann das als FIR-Filter behandeln und die z-Transformation dieser Gleichung aufschreiben:
Y(z) = X(z) + X(z)z-1 = X(z) (1 + z-1)
Die „Impulsantwort“ kann also wie üblich definiert werden: H(z) = Y(z)/X(z), oder einfach:
H(z) = 1 + z-1
Was aber passiert, wenn man zwei dieser Filter hintereinanderschaltet? Wie lautet dann die „Impulsantwort“ dieses Filters?
Die Theorie digitaler Filter liefert eine einfache Antwort:
H2(z) = H(z)H(z) = (1 + z-1)(1 + z-1) = 1 + 2z-1 + z-2
Zur Erinnerung: In GF(2) entspricht die Multiplikation mit einer geraden Zahl der Multiplikation mit null. Entsprechend gilt:
H2(z) = 1 + 2z-1 + z-2 = 1 + 0z-1 + z-2 = 1 + z-2
Das entspricht folgendem Schaltbild:
Es ist nicht leicht zu erkennen, dass die in den beiden letzten Abbildungen gezeigten Filter äquivalent sind. Beide Filter erzeugen jedoch dasselbe y(t), wenn sie mit demselben x(t) gespeist werden. Die Filter sind also identisch, auch wenn die im zweiten Verzögerungsglied gespeicherten Werte nicht übereinstimmen.
Dieses Beispiel zeigt den Vorteil der z-Transformation (und ähnlicher Polynommethoden) bei der Analyse logischer Filter.
Erwähnen sollte ich noch, dass statt z-1 häufig die Symbole D oder D-1 verwendet werden. Das x in den Galois- und Fibonacci-Polynomen hat dieselbe Bedeutung wie z-1. Alle diese Symbole bezeichnen eine Verzögerung.
Das Galois-LFSR
Um die Fibonacci-Darstellung zu finden, betrachte ich zuerst das Galois-LFSR.
Schauen wir uns das obige Schaltbild des Galois-LFSR an. Die Reihe aus Verzögerungsgliedern und Abgriffen kann als FIR-Filter aufgefasst werden, das ich mit A(z) bezeichne. Das Galois-LFSR ist also äquivalent zu folgendem Aufbau:
Wegen der Rückkopplung ergibt sich die Gleichung für Y(z):
Y(z) = Y(z)A(z)
Welcher Zusammenhang besteht also zwischen den Parametern dieses FIR-Filters und dem Galois-Polynom? Schreiben wir die allgemeine Form des Galois-Polynoms auf:
G(x) = xn + gn-1xn-1+ gn-2xn-2+…+ g0
Beachten Sie, dass gn in diesem Ausdruck nicht vorkommt, um die Mathematik weiter unten zu vereinfachen. Außerdem ist gn immer gleich 1.
Der Zusammenhang zwischen G(x) und A(z) ist folgender:
A(z) = gn-1z-1+gn-2z-2+…+g1z1-n+g0z-n
Warum ist das richtig? Nehmen wir das Galois-LFSR aus dem obigen Schaltbild und sehen uns an, wie dieser Ausdruck zustande kommt.
Zuerst schauen wir auf das XOR, das zu g5 gehört. Die Zahl 5 bedeutet, dass sich fünf Verzögerungsglieder auf der linken Seite dieses XOR befinden. Der Exponent von z hängt jedoch von der Anzahl der Verzögerungsglieder zwischen dem XOR und dem Ausgang des FIR-Filters ab. Gemeint sind die Verzögerungsglieder auf der rechten Seite des XOR. Insgesamt gibt es 16 Verzögerungsglieder. Deshalb erscheint g5 in A(z) als g5z-11. Das passt zu dem Muster gn-iz-i.
Eine andere Erklärung besteht darin, A(z) im Zeitbereich als FIR-Filter zu betrachten. Der Eingang dieses FIR-Filters ist x(t), sein Ausgang y(t):
y(t) = x(t–16) ⊕ x(t–13) ⊕ x(t–12) ⊕ x(t–11)
Auch hier ist t eine ganze Zahl, die die Zeit repräsentiert. Dieser Ausdruck beschreibt das Galois-LFSR ohne Rückkopplung. Die Übertragungsfunktion dieses FIR-Filters lautet:
A(z) = Y(z)/X(z) = z-16 + z-13 + z-12 + z-11
Das passt zu dem allgemeinen Ausdruck für A(z) mit G(x) = x16 + x5 + x4 + x3 + 1.
Das Fibonacci-Äquivalent
Ein LFSR in Fibonacci-Form wird durch das folgende Polynom dargestellt:
F(x) = fnxn+fn-1xn-1+…+f1x + 1
Beachten Sie, dass f0 in diesem Polynom nicht auftaucht, weil es immer gleich 1 ist. Das ist ähnlich wie bei gn, das in G(x) nicht auftaucht.
Die Implementierung dieses Polynoms lässt sich so schreiben:
y(t) = f1y(t-1) + f2y(t-2) +…+ fny(t-n)
Die z-Transformation lautet entsprechend:
Y(z) = f1Y(z)z-1+f2Y(z)z-2+…+fnY(z)z-n
Wir definieren B(z) wie folgt:
B(z) = f1z-1+f2z-2+…+fnz-n
Y(z) lässt sich damit folgendermaßen schreiben:
Y(z) = Y(z)B(z)
Zur Erinnerung an oben: Y(z) = Y(z)A(z). Wenn sich die Fibonacci-Form des LFSR also genauso verhält wie das LFSR, das durch das Galois-Polynom gegeben ist, folgt daraus, dass A(z) = B(z) ist. Das bedeutet wiederum:
fi=gn-i (i=1,2, … , n)
Es gilt also, wie ich von Anfang an gesagt habe: Um ein LFSR-Polynom von der Galois-Form in die Fibonacci-Form umzuwandeln, muss man die Reihenfolge der Koeffizienten umkehren.
Das inverse Filter des LFSR
Noch einmal: Dies ist die Fibonacci-Implementierung des LFSR:
y(t) = f1y(t-1) + f2y(t-2) +…+ fny(t-n)
Man kann diesen Ausdruck jedoch auch wie folgt umschreiben:
y(t) + f1y(t-1) + f2y(t-2) +…+ fny(t-n) = 0
(Zur Erinnerung: + und – sind in GF(2) dasselbe.)
Die Koeffizienten des Fibonacci-Polynoms sagen uns also auch, wie wir die Werte von y(t-i) miteinander per XOR verknüpfen müssen, um immer den Wert null zu erhalten. Mit anderen Worten beschreibt dies ein interessantes FIR-Filter.
Die z-Transformation des letzten Ausdrucks lautet:
Y(z) + f1Y(z)z-1+f2Y(z)z-2+…+fnY(z)z-n = 0
Oder äquivalent:
Y(z)(1+ f1z-1+f2z-2+…+fnz-n) = Y(z)H(z) = 0
Y(z)H(z) ist der Ausgang, der entsteht, wenn man das Filter H(z) auf Y(z) anwendet. Und dieser Ausgang ist null.
H(z) ist also die Übertragungsfunktion eines FIR-Filters. Speist man dieses FIR-Filter mit dem Ausgang des durch F(x) definierten LFSR, bleibt der Ausgang zu jedem Zeitpunkt null. Aus der obigen Definition von B(z) ergibt sich die Übertragungsfunktion dieses FIR-Filters zu:
H(z) = 1 + f1z-1+f2z-2+…+fnz-n
Oder im Zeitbereich, wenn der Eingang x(t) und der Ausgang y(t) ist:
y(t) = x(t) ⊕ f1x(t-1) ⊕ f2x(t-2) ⊕ … ⊕ fnx(t-n)
Wenn x(t) der Ausgang des LFSR ist, das durch F(x) definiert ist, ist y(t) für alle t null.