501px|mini|Ein 4-bit-Fibonacci-LFSR und seine Zustände. Das Register schiebt die Bits von links nach rechts. Das Exklusiv-Oder-Gatter wird von den beiden hinteren Bits des Registers gefüttert und liefert diesem vorne damit wiederum die Eingabe. Die maximale Ausgabesequenz besteht aus jedem möglichen Zustand mit Ausnahme des Zustands "0000". Ein linear rückgekoppeltes Schieberegister (engl. , kurz LFSR) ist ein rückgekoppeltes Schieberegister, das zur Erzeugung von streng deterministischen Pseudozufallszahlenfolgen eingesetzt werden kann. Zur Rückkopplung wird die lineare logische Funktion XOR verwendet.

Den Startwert bezeichnet man als . Da die Ausgabe des Registers streng deterministisch ist und vollständig von seinem momentanen Zustand abhängt, das Register jedoch gleichzeitig nur eine endliche Anzahl an Zuständen hat, muss es zwangsläufig irgendwann wieder bei seinem Startwert ankommen. Bei n Bit breiten Schieberegistern ergibt sich damit eine maximale Periodenlänge von 2n−1. Ab diesem Zeitpunkt wiederholt sich die Ausgabesequenz, das Register befindet sich in einem Wiederholzyklus. Je nach gewählter Implementierung ist diese Sequenz unterschiedlich lang, allerhöchstens können Folgen maximaler Länge erzeugt werden.

Anwendungen liegen neben der Erzeugung von Pseudozufallszahlenfolgen im Bereich schneller digitaler Synchronzähler, da diese Zähler ohne Übertrag arbeiten, im Bereich der Nachrichtentechnik und Kryptografie bei Scramblern, um Datenfolgen spektral weiß zu machen, in der Kodierungstheorie bei der Kodierung und Dekodierung von zyklischen Codes, wie beispielsweise bei der zyklischen Redundanzprüfung (CRC) oder dem Hamming-Code, und im Bereich der digitalen Modulationstechnik bei den Codemultiplexverfahren (CDMA) und im Bereich der Steganographie.

Linear rückgekoppelte Schieberegister können effizient sowohl direkt in Hardware, wie beispielsweise FPGAs, als auch in Software implementiert werden. Bei der Softwareimplementierung wird, da die meisten Prozessoren mit Registerbreiten größer als ein Bit arbeiten, typischerweise mit im Voraus berechneten Tabellen gearbeitet, die direkt den inneren Zustand des Schieberegisters abbilden.

Funktionsweise Ein LFSR ist in der Digitaltechnik als ein Schieberegister mit n Speicherelementen realisiert. Die einzelnen Speicherelemente sind typischerweise D-Flipflops, welche je ein Bit speichern können. Im Gegensatz zu einem gewöhnlichen Schieberegister bestehen zwischen bestimmten D-Flipflops Abzweigungen, welche die Rückkopplungen darstellen. Die Anzahl und die Position dieser Abzweigungen in der Registerkette wird zur Erzielung der maximal möglichen Periodenlänge von 2n−1 durch ein primitives Polynom, das sogenannte Generatorpolynom, bestimmt. n ist in diesem Fall auch gleich dem Grad des Generatorpolynoms.

Ein primitives Polynom als Generatorpolynom ist nicht zwingend notwendig, allerdings ergeben nicht-primitive Polynome kürzere Periodenlängen. Kürzere Periodenlängen sind jedoch auch mit einer geringeren Anzahl von Flipflops und Verwendung eines entsprechenden primitiven Polynoms geringeren Grades erreichbar, weshalb als Generatorpolynome praktisch ausschließlich primitive Polynome Einsatz finden. Die mögliche Gesamtanzahl aller linear rückgekoppelten Schieberegister beträgt 2^(n - 1) - 1, (mindestens ein XOR-Gatter), allerdings sind von dieser Gesamtzahl nur ein kleiner Anteil solche Schieberegister, deren Periodenlänge maximal ist ("m-Sequenz"), also durch ein primitives Polynom bestimmt. Die Anzahl verfügbarer m-Sequenzen für gegebenes n berechnet sich zu φ(2^n - 1)/n. Darin ist φ(x) die sogenannte "Eulerfunktion". Die "On-Line Encyclopedia of Integer Sequences", OEIS, listet die Zahlenfolge dafür unter A011260.

Zur Initialisierung, im Englischen wird dieser Startwert auch als seed bezeichnet, kann das Schieberegister mit XOR-Rückkopplung mit beliebigen Werten gefüllt werden – bei positiver Logik jedoch nicht nur mit Nullen, da dann das Register aus diesem Zustand niemals herauskäme, das Schieberegister also eine triviale Folge konstanter Nullen generieren würde. Es können statt der XOR-Verknüpfungen auch XNOR-Verknüpfungen eingesetzt werden (negative Logik); in diesem Fall sind als Startwert alle Werte außer lauter Einsen erlaubt, was auch wieder eine maximale Periodenlänge von 2n−1 ergibt. Je nach Technologie ist es einfacher, den Zustand mit lauter Nullen als definierten Anfangszustand zu implementieren. Die Verknüpfung mittels XNOR hat hierbei den Vorteil, dass dieser Zustand mit lauter Nullen als Startwert geeignet ist und nicht, wie bei XOR, zu der trivialen konstanten Nullfolge führt.

Ein LFSR kann auch so implementiert werden, dass es die maximale Periodenlänge von 2n aufweist. Hierbei treten nach einem Durchlauf lauter '0' im Schieberegister auf, die als Sonderfall durch eine zusätzliche Logikschaltung erkannt und durch daraufhin aktivierte Invertierung der Rückkopplung kompensiert werden müssen. Diese Möglichkeit besteht analog auch bei XNOR-Verknüpfungen; der Sonderfall ist hierbei stattdessen der Zustand mit lauter Einsen.

Wie jedes andere Schieberegister verfügt auch das LFSR über einen Takteingang: Bei jedem Taktimpuls wird in den Folgezustand gewechselt und für einen vollständigen Durchlauf aller Kombinationen sind 2n−1 Taktimpulse notwendig (sofern, wie oben beschrieben, ein primitives Polynom zum Einsatz kommt und auf das erwähnte „Aufbohren“ der Rückkopplung auf 2n Zustände verzichtet wurde).

Ein LFSR bildet wegen seiner Linearität der erzeugten Folgen für sich alleine für kryptologische Anwendungen einen schlechten Pseudozufallszahlengenerator. LFSR werden als Grundelement und in Verbindung mit nichtlinearen Funktionen oder als eine Kombination mehrerer LFSR verwendet.

Neben den in digitalen Schaltungen üblichen binären LFSR in GF(2) existieren auch nichtbinäre LFSR mit einer Anzahl an Elementen q größer als 2. Die XOR-Operation, sie stellt eine Addition modulo 2 dar, wird im allgemeinen Fall durch eine Addition modulo q ersetzt, die Speicherelemente müssen je q Zustände speichern können.

Arten Es gibt in der Realisierung zwei verschiedene Arten von LFSR:

Fibonacci-LFSR, benannt nach dem italienischen Mathematiker Leonardo Fibonacci, und Galois-LFSR, benannt nach dem französischen Mathematiker Évariste Galois.

Beide Typen sind zueinander gleichwertig und weisen die gleichen Periodenlängen auf, wenngleich die erzeugten Folgen unterschiedlich sind. Sie unterscheiden sich in der Realisierung, wie in den Abbildungen dargestellt, wobei CLK den Takteingang und Y den Ausgang des LFSR darstellen. Die XOR-Operatoren sind mit „“ dargestellt.

mini|zentriert|650px|Fibonacci-LFSR mini|zentriert|650px|Galois-LFSR

Die beiden Formen ergeben sich aus dem Umstand, dass jedes primitive Polynom vom Grad n > 2 ein „Zwillingspolynom“ besitzt, welches ebenfalls primitiv ist. In den beiden Abbildungen wurde für das Fibonacci-LFSR ein Generatorpolynom vom 8. Grad verwendet:

Die Abzweigstellen entsprechen direkt den Exponenten. Das dazu gleichwertige primitive Generatorpolynom vom 8. Grad im Galois-LFSR ist:

Welche der beiden gleichwertigen Formen konkret gewählt wird, hängt unter anderem von Optimierungen bei der Implementierung ab. So können beispielsweise die drei Exklusiv-Oder-Gatter mit je zwei Eingängen in der Fibonacci-Struktur zu einem Exklusiv-Oder-Gatter mit vier Eingängen zusammengefasst werden. Diese Form lässt sich in FPGAs mit Lookup-Tabellen, welche vier Eingänge aufweisen, effizient implementieren.

Polynomauswahl Neben dem Grad n, welcher die Periodenlänge festlegt, existieren bei einem bestimmten Grad n > 2 immer mehrere primitive Polynome, welche zueinander gleichwertig sind. Je nach Anwendung können weitere Auswahlkriterien hinzukommen. Beispielsweise werden in der Nachrichtentechnik im Bereich von Scramblern sogenannte dünn besetzte Generatorpolynome bevorzugt. Dies sind Polynome, welche mit einer minimalen Anzahl von Rückkoppelstellen bzw. mit einer minimalen Stellenanzahl ungleich 1 im Generatorpolynom auskommen. Dies hat den Grund, den Hardwareaufwand und bei selbstsynchronisierenden Scramblern die Vervielfachung von Empfangsfehlern im Descrambler zu minimieren. Im Bereich der Kodierungstheorie, wie bei zyklischen Kodes (CRC) oder bei kryptografischen Anwendungen, werden hingegen dichtbesetzte Polynome nach anderen Auswahlkriterien bevorzugt.

Primitive Polynome unterschiedlicher Grade sind in Tabellenwerken aufgelistet. In nachfolgender Tabelle sind einige primitive Polynome mit minimaler Besetzung angeführt:

Grad Exponenten Grad Exponenten1 1 14 14, 13, 11, 92 2, 1 15 15, 143 3, 2 16 16, 14, 13, 114 4, 3 17 17, 145 5, 3 18 18, 116 6, 5 19 19, 18, 17, 147 7, 6 20 20, 178 8, 6, 5, 4 21 21, 199 9, 5 22 22, 2110 10, 7 23 23, 1811 11, 9 24 24, 23, 21, 2012 12, 11, 8, 6 … …13 13, 12, 10, 6 9689 9689, 84

Programmierung Der folgende Quelltext implementiert ein Galois-LFSR vom Grad 32 mit Periodenlänge : unsigned lfsr() { static unsigned r = 1; unsigned b = r & 1; r = (r >> 1) ^ (-b & 0xc3308398); return b; } Der folgende Quelltext in C++ zeigt die Implementierung eines weiteren Galois-LFSR, dessen Generatorpolynom der Benutzer selbst eingeben kann. Das Programm ermittelt die Periodenlänge des LFSR und gibt sie aus: #include <iostream> using namespace std;

unsigned lfsr2(unsigned _startState, unsigned _shiftBits) { unsigned m = _shiftBits; m |= m >> 1; m |= m >> 2; m |= m >> 4; m |= m >> 8; m |= m >> 16; _startState &= m; // Entfernt überzählige Bits unsigned lfsr = _startState; // Initialisiert den Zustand unsigned periodLength = 0; do

unsigned lsb = lfsr & 1u; // Berechnet das Ausgabebit lfsr >>= 1; // Verschiebt die Zustandsbits um eine Bitposition nach rechts if (lsb == 1) // Wenn das Ausgabebit gleich 1 ist

lfsr ^= _shiftBits; // XOR-Rückkopplung

++periodLength; } while (lfsr != _startState); return periodLength; }

int main() { string _startStateText; string _shiftBitsText; cin >> _startStateText; // Eingabe des Startzustands als Binärzahl über die Konsole cin >> _shiftBitsText; // Eingabe des Generatorpolynoms als Binärzahl über die Konsole unsigned _startState = stoi(_startStateText, 0, 2); // Typumwandlung von string nach unsigned unsigned _shiftBits = stoi(_shiftBitsText, 0, 2); // Typumwandlung von string nach unsigned cout << lfsr2(_startState, _shiftBits) << endl; // Ausgabe der Periodenlänge return 0; }Der Startzustand und das Generatorpolynom werden hier als Binärzahl über die Konsole eingegeben. Dafür ist eine Typumwandlung notwendig.

Beispiel

Für den Startzustand 1010110011100001 und das Generatorpolynom mit der Binärdarstellung 1011010000000000 ergeben sich für die ersten 6 Durchläufe der do-while-Schleife folgende Werte für das Schieberegister:

1. Durchlauf: Ergebnis nach Rechtsshift: 0101011001110000, Ausgabebit 1, Ergebnis nach XOR-Operation: 1110001001110000 2. Durchlauf: Ergebnis nach Rechtsshift: 0111000100111000, Ausgabebit 0 3. Durchlauf: Ergebnis nach Rechtsshift: 0011100010011100, Ausgabebit 0 4. Durchlauf: Ergebnis nach Rechtsshift: 0001110001001110, Ausgabebit 0 5. Durchlauf: Ergebnis nach Rechtsshift: 0000111000100111, Ausgabebit 0 6. Durchlauf: Ergebnis nach Rechtsshift: 0000011100010011, Ausgabebit 1, Ergebnis nach XOR-Operation: 1011001100010011

Parallele Berechnung

Zustand und resultierende Bits können auch kombiniert und parallel berechnet werden (besonders effizient ist das, wenn die Anzahl der zu schiebenden Bits einer Registergröße entspricht und auch das Übertragsbit benutzt werden kann, wie bei dem Polynom 63. Grades auf einer 32-Bit-Architektur). Die folgende Funktion berechnet jeweils die nächsten 32 Bits mittels 31-Bit-Galois-LFSR mit Polynom x³¹ + x²⁸ + 1 in 2 Schritten:

#include <stdint.h>

uint32_t prsg31(uint32_t lfsr) { lfsr = lfsr << 16 | (lfsr<<1 ^ lfsr<<4) >> 16; lfsr = lfsr << 16 | (lfsr<<1 ^ lfsr<<4) >> 16; return lfsr; }

Entsprechendes Fibonacci-LFSR mit 32 Schritten: