Rückgekoppelte Schieberegister (LFSR)

1. Was ist ein rückgekoppeltes Schieberegister?

Ein rückgekoppeltes Schieberegister (LFSR, Linear Feedback Shift Register) ist ein Register aus $n$ Speicherzellen (Flip-Flops), das bei jedem Takt seinen Inhalt um eine Position weiterschiebt. Das dabei neu eingeschobene Bit stammt nicht von außen, sondern wird aus dem aktuellen Registerinhalt selbst berechnet — durch XOR-Verknüpfung bestimmter Bitpositionen, der sogenannten Taps. Diese Rückkopplung macht das Register zu einem autonomen, deterministischen Erzeuger einer Bitfolge, die auf den ersten Blick zufällig aussieht, tatsächlich aber vollständig reproduzierbar ist — daher der Name Pseudozufallsfolge (PRBS, Pseudo-Random Binary Sequence).

Zwei Bauformen sind gebräuchlich:

• Fibonacci-Konfiguration: Die Tap-Bits werden gemeinsam XOR-verknüpft, das Ergebnis wird am einen Ende neu eingeschoben; am anderen Ende fällt das Ausgangsbit heraus. Anschaulich, aber die XOR-Kette über mehrere Taps kann bei hohen Taktraten zum kritischen Pfad werden.
• Galois-Konfiguration: Die Rückkopplung wird stattdessen an mehreren Registerzellen gleichzeitig verteilt eingespeist. Elektrisch günstiger (nur ein XOR pro Zelle, kein langer Gatterpfad), erzeugt bei passendem Rückkopplungsmuster dieselbe Sequenzlänge und dieselben Korrelationseigenschaften wie die äquivalente Fibonacci-Form.

Für die Dimensionierung und die erzeugte Sequenz selbst sind beide Formen gleichwertig — der Unterschied liegt nur in der Hardware-/Implementierungseffizienz.

2. Rückkopplungspolynom und Maximalfolgen

Welche Bitpositionen als Taps dienen, wird durch ein Rückkopplungspolynom über GF(2) festgelegt, z. B. $x^5 + x^3 + 1$ für ein 5-Bit-Register mit Taps auf Position 5 und 3. Nicht jedes Polynom ist gleich gut geeignet:

• Ist das Polynom primitiv, durchläuft das Register bei jedem beliebigen Startzustand $\neq 0$ alle $2^n-1$ möglichen Nichtnull-Zustände genau einmal, bevor die Folge sich wiederholt. Das Ergebnis ist eine Maximalfolge (m-Sequenz) der Länge $N = 2^n - 1$.
• Ist das Polynom nicht primitiv (reduzibel), zerfällt der Zustandsraum in mehrere kürzere Zyklen — die tatsächliche Periode ist dann ein Teiler der möglichen Maximallänge, oft deutlich kürzer.

Maximalfolgen haben zwei Eigenschaften, die sie für die Signalverarbeitung besonders wertvoll machen:

Balance-Eigenschaft: In jeder Periode kommen Einsen genau einmal häufiger vor als Nullen — bei $N=31$ also 16 Einsen und 15 Nullen. Die Folge ist damit im Mittel nahezu gleichverteilt wie echtes Rauschen.

Ideale (zweiwertige) Autokorrelation: Bipolar codiert (0→+1, 1→−1) ergibt die zyklische Autokorrelation einer Maximalfolge exakt:

$$
R(k) = \begin{cases} N & k \equiv 0 \pmod N \ -1 & \text{sonst} \end{cases}
$$

Genau diese Eigenschaft macht Maximalfolgen zur Grundlage für Entfernungsmessung, Synchronisation und Spreizspektrumverfahren: Der Empfänger kann die Position der Folge im empfangenen Signal (Zeitverschiebung, Phasenlage) eindeutig über den Korrelationspeak bestimmen, ohne durch Nebenmaxima in die Irre geführt zu werden.

3. Dimensionierung

4. Einsatz in der Praxis

Spreizspektrum-Übertragung (DSSS/CDMA): Das Nutzsignal wird mit der Chip-Folge multipliziert und dadurch auf eine deutlich größere Bandbreite gespreizt. Der Empfänger entspreizt durch Korrelation mit einer lokal erzeugten, identischen Referenzfolge — genau das Funktionsprinzip von GPS (siehe Gold-Code unten).

Zeit- und Phasenreferenzsignale: Die PZF-Sequenz von DCF77 nutzt ein 9-Bit-LFSR (Polynom 0x110, Taps auf Position 9 und 5), um dem 77,5-kHz-Träger eine amplitudenneutrale Phasenmodulation aufzuprägen. Der Empfänger erzeugt lokal eine bitidentische Referenz und gewinnt per Matched Filter eine Zeitauflösung im Mikrosekundenbereich statt der Millisekunden, die die reine AM-Auswertung liefert (siehe Korrelative Phasenauswertung).

Scrambling: In Übertragungsstandards (z. B. Ethernet, DVB) wird der Nutzdatenstrom vor der Übertragung mit einer LFSR-Folge XOR-verknüpft, um lange Ketten gleicher Bits zu vermeiden — wichtig für die Taktrückgewinnung beim Empfänger.

Testmustergenerierung (BIST): In der Digitaltechnik erzeugen LFSRs preiswert lange, gleichverteilte Testvektoren für den Selbsttest von Schaltungen (Built-In Self-Test).

5. Von der Maximalfolge zum Gold-Code

Eine einzelne Maximalfolge ist ideal für eine Punkt-zu-Punkt-Verbindung — sobald aber mehrere Teilnehmer gleichzeitig im selben Frequenzband senden sollen (wie die GPS-Satelliten), reicht die Eigenkorrelation allein nicht mehr aus: Es kommt zusätzlich auf die Kreuzkorrelation zwischen den Folgen verschiedener Teilnehmer an, die möglichst niedrig sein muss, damit sich die Signale sauber trennen lassen.

Der Gold-Code löst genau dieses Problem: Er kombiniert zwei verschiedene Maximalfolgen gleicher Länge $n$ (ein sogenanntes „preferred pair") durch bitweise XOR-Verknüpfung. Durch Verschieben der zweiten Folge gegeneinander entsteht eine ganze Familie von $2^n+1$ Folgen, die zwar einzeln keine ganz so scharfe Autokorrelation wie eine reine Maximalfolge haben, dafür aber untereinander eine garantiert niedrige, wohldefinierte Kreuzkorrelation — die Grundlage für CDMA-Systeme wie GPS, bei denen jeder Satellit einen eigenen Gold-Code aus derselben Familie nutzt.

6. Referenzimplementierung

Das folgende Skript erzeugt und verifiziert die in Abschnitt 2 gezeigten Zahlenwerte für ein 5-Bit-LFSR in Galois-Konfiguration:

def galois_lfsr(mask, seed, n, steps):
    """Galois-LFSR: mask kodiert die Tap-Positionen des Rückkopplungspolynoms."""
    state = seed
    out = []
    for _ in range(steps):
        out.append(state & 1)
        lsb = state & 1
        state >>= 1
        if lsb:
            state ^= mask
    return out

n, full = 5, 2**5 - 1
mask_primitive = 0b10100      # primitives Polynom (Maximalfolge)
mask_reduzibel = 0b01100      # nicht-primitives Polynom (Vergleich)

seq = galois_lfsr(mask_primitive, seed=1, n=n, steps=2 * full)
print("Sequenz (31 Chips):", "".join(map(str, seq[:full])))
print("Periode 31 bestätigt:", seq[:full] == seq[full:2 * full])
print("Anzahl Einsen:", sum(seq[:full]), "von", full)

import numpy as np
bip = 1 - 2 * np.array(seq[:full])
autokorr = [int(sum(bip * np.roll(bip, k))) for k in range(6)]
print("Autokorrelation (Shift 0..5):", autokorr)

def galois_lfsr(mask, seed, n, steps):
    """Galois-LFSR: mask kodiert die Tap-Positionen des Rückkopplungspolynoms."""
    state = seed
    out = []
    for _ in range(steps):
        out.append(state & 1)
        lsb = state & 1
        state >>= 1
        if lsb:
            state ^= mask
    return out

n, full = 5, 2**5 - 1
mask_primitive = 0b10100      # primitives Polynom (Maximalfolge)
mask_reduzibel = 0b01100      # nicht-primitives Polynom (Vergleich)

seq = galois_lfsr(mask_primitive, seed=1, n=n, steps=2 * full)
print("Sequenz (31 Chips):", "".join(map(str, seq[:full])))
print("Periode 31 bestätigt:", seq[:full] == seq[full:2 * full])
print("Anzahl Einsen:", sum(seq[:full]), "von", full)

import numpy as np
bip = 1 - 2 * np.array(seq[:full])
autokorr = [int(sum(bip * np.roll(bip, k))) for k in range(6)]
print("Autokorrelation (Shift 0..5):", autokorr)

Ausgabe:

Sequenz (31 Chips): 1001011001111100011011101010000
Periode 31 bestätigt: True
Anzahl Einsen: 16 von 31
Autokorrelation (Shift 0..5): [31, -1, -1, -1, -1, -1]

Sequenz (31 Chips): 1001011001111100011011101010000
Periode 31 bestätigt: True
Anzahl Einsen: 16 von 31
Autokorrelation (Shift 0..5): [31, -1, -1, -1, -1, -1]

Warum diese Werte: 16 von 31 Chips sind Eins — exakt die erwartete Balance $(N+1)/2 = 16$ einer Maximalfolge. Die Autokorrelation trifft den theoretischen Idealfall (Abschnitt 2) exakt: Peak $N=31$ bei Verschiebung 0, konstant $-1$ bei jeder anderen Verschiebung. Mit dem nicht-primitiven Vergleichspolynom mask_reduzibel erreicht dasselbe Register dagegen nur eine Periode von 15 Takten statt der möglichen 31 — ein direkter Beleg dafür, dass die Wahl des Rückkopplungspolynoms, nicht die Registerlänge allein, über die Sequenzqualität entscheidet.