Ein Schieberegister, das sich selbst speist

Ein gewöhnliches Schieberegister braucht einen externen seriellen Eingang. Ein Schieberegister mit linearer Rückkopplung (LFSR) berechnet diesen Eingang stattdessen selbst, indem es eine feste Teilmenge der eigenen Bits des Registers (seine „Abgriffe") per XOR verknüpft und das Ergebnis zurück in die erste Stufe einspeist.

Warum XOR-Rückkopplung lange Folgen erzeugt

Weil die XOR-Rückkopplung linear ist, durchläuft das Register eine lange Folge unterschiedlicher Zustände, bevor sie sich wiederholt — bei gut gewählten Abgriffen besucht ein N-Bit-LFSR alle 2^N−1 von null verschiedenen Zustände genau einmal, bevor es zu seinem Startwert zurückkehrt, eine sogenannte Folge maximaler Länge. Der Ausgang wirkt statistisch wie Rauschen, obwohl das Ganze vollständig deterministische sequentielle Logik ist.

Eines aus Boolflows SHIFT4 bauen

Nehmen Sie einen SHIFT4-Block, verknüpfen Sie zwei seiner Ausgangsbits per XOR (die beiden obersten Stufen Q2 und Q3 sind ein Abgriffpaar, das für 4 Bit eine Folge maximaler Länge liefert), und speisen Sie den Ausgang dieses XOR statt eines externen Signals in den seriellen Eingang des Schieberegisters ein. Einen Haken gibt es: Boolflows Register starten bei 0000, und ein reines XOR-LFSR bliebe dort für immer stecken, da XOR von Nullen immer null ergibt. Nehmen Sie stattdessen ein XNOR-Gatter — der Haltezustand wandert nach 1111, 0000 wird ein gewöhnlicher Zustand, und das Register durchläuft 15 seiner 16 Werte.

Wo es eingesetzt wird

Genau dieselbe Struktur, die pseudozufällige Testmuster für den Selbsttest von Chips erzeugt, berechnet auch CRC-Prüfsummen zur Erkennung von Übertragungsfehlern — eine CRC ist einfach ein LFSR, das über die Nachrichtenbits statt über seine eigene freilaufende Rückkopplung läuft. Bauen Sie eines im Schaltungseditor, schalten Sie CLOCK um und beobachten Sie, wie der 4-Bit-Ausgang 15 verschiedene Werte durchläuft, bevor er sich wiederholt.