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 (Bit 3 und Bit 2 ist 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. Laden Sie das Register mit einem beliebigen von null verschiedenen Wert — ein durchgehend nulles LFSR bleibt für immer bei null stecken, da XOR von Nullen immer null ergibt.

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 alle 15 von null verschiedenen Werte durchläuft, bevor er sich wiederholt.