Linear rückgekoppeltes Schieberegister
Ein linear rückgekoppeltes Schieberegister (engl. linear feedback shift register, 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 seed. 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.