LFSR-Rechner - Lineares Schieberegister

Ein Linear Feedback Shift Register (LFSR) ist ein Schieberegister, dessen Eingangsbit eine lineare Funktion (XOR) einiger vorheriger Zustandsbits ist. Bei jedem Takt verschiebt das Register alle Bits um eine Position, das neue Eingangsbit wird durch XOR der Bits an bestimmten Positionen, den sogenannten Feedback-Taps, berechnet, und das Ausgangsbit ist das herausgeschobene Bit. Die resultierende Binärsequenz wirkt zufällig, ist aber vollständig deterministisch und wiederholt sich mit einer Periode, die von Registerlänge und Tap-Auswahl abhängt. LFSRs werden häufig in digitaler Kommunikation, Kryptografie, BIST-Schaltungen (Built-In Self-Test), Spreizspektrum-Systemen und der Pseudozufallszahlenerzeugung eingesetzt. Da ein n-stufiges LFSR vor der Wiederholung höchstens 2ⁿ − 1 Bits erzeugen kann (der All-Nullen-Zustand ist ausgeschlossen) und diese maximale Folge mit sorgfältig gewählten primitiven Polynom-Taps erreicht werden kann, sind LFSRs eine effiziente Hardware-Implementierung von Pseudorandomität. Es gibt zwei gängige LFSR-Architekturen. Beim Fibonacci-LFSR (externe Rückkopplung) wird das Feedbackbit aus einer festen Menge von Tap-Positionen berechnet und in die linke Stufe eingespeist, während alle anderen Stufen nach rechts verschieben. Das Ausgangsbit wird von der rechten Stufe entnommen. Beim Galois-LFSR (interne Rückkopplung) wird das Feedbackbit direkt in mehrere Zwischenstufen XOR-verknüpft, statt nur an den Eingang zurückgeführt zu werden. Galois-LFSRs sind in Hardware schneller, weil alle XOR-Operationen parallel und nicht seriell erfolgen. Ein LFSR mit maximaler Länge — also eines, das vor der Wiederholung alle 2ⁿ − 1 nicht nullen Zustände durchläuft — benötigt ein primitives Polynom als Feedback-Polynom. Die Tap-Positionen entsprechen den von null verschiedenen Koeffizienten dieses Polynoms. Für ein 4-Bit-LFSR mit Taps an Position 4 und 3 ist das primitive Polynom x⁴ + x³ + 1, und das LFSR durchläuft alle 15 nicht nullen Zustände. Mit diesem Rechner können Sie beliebige Kombinationen aus Registerlänge, Seed, Tap-Positionen und LFSR-Typ ausprobieren. Sie können prüfen, ob Ihre gewählten Taps eine Folge maximaler Länge erzeugen, indem Sie die Periode in den Ergebnissen betrachten — ist die Periode gleich 2ⁿ − 1, bilden die Taps ein primitives Polynom. Anhand der Beispiele sehen Sie bekannte Konfigurationen mit maximaler Länge. LFSRs werden in vielen Bereichen eingesetzt. In Wi‑Fi und Bluetooth liefern sie die Spreizcodes für Frequency Hopping und Direct Sequence Spread Spectrum. In Speicher- und Kommunikationssystemen werden CRC-Schaltungen (zyklische Redundanzprüfung) als LFSRs implementiert. In kryptografischen Stromchiffren bilden LFSRs das zentrale Primitive (moderne Chiffren kombinieren jedoch mehrere LFSRs mit nichtlinearen Komponenten, um lineare Kryptanalyse zu erschweren). In der Chipprüfung komprimiert die auf LFSRs basierende Signaturanalyse Testantwortdaten zu einer kompakten Signatur.