Linear rückgekoppeltes Schieberegister

Es gibt in der Realisierung zwei verschiedene Arten von LFSR:

1. Fibonacci-LFSR, benannt nach dem italienischen Mathematiker Leonardo Fibonacci, und
2. Galois-LFSR, benannt nach dem französischen Mathematiker Évariste Galois.

Beide Typen sind zueinander gleichwertig und weisen die gleichen Periodenlängen auf, wenngleich die erzeugten Folgen unterschiedlich sind. Sie unterscheiden sich in der Realisierung, wie in den Abbildungen dargestellt, wobei CLK den Takteingang und Y den Ausgang des LFSR darstellen. Die XOR-Operatoren sind mit „${\displaystyle \oplus }$“ dargestellt.

Fibonacci-LFSR

Galois-LFSR

Die beiden Formen ergeben sich aus dem Umstand, dass jedes primitive Polynom vom Grad n > 2 ein „Zwillingspolynom“ besitzt, welches ebenfalls primitiv ist.[1] In den beiden Abbildungen wurde für das Fibonacci-LFSR ein Generatorpolynom vom 8. Grad verwendet:

${\displaystyle p_{f}(x)=x^{8}+x^{6}+x^{5}+x^{4}+1}$

Die Abzweigstellen entsprechen direkt den Exponenten. Das dazu gleichwertige primitive Generatorpolynom vom 8. Grad im Galois-LFSR ist:

${\displaystyle p_{g}(x)=x^{8-8}+x^{8-6}+x^{8-5}+x^{8-4}+x^{8-0}=x^{8}+x^{4}+x^{3}+x^{2}+1}$

Welche der beiden gleichwertigen Formen konkret gewählt wird, hängt unter anderem von Optimierungen bei der Implementierung ab. So können beispielsweise die drei Exklusiv-Oder-Gatter mit je zwei Eingängen in der Fibonacci-Struktur zu einem Exklusiv-Oder-Gatter mit vier Eingängen zusammengefasst werden. Diese Form lässt sich in FPGAs mit Lookup-Tabellen, welche vier Eingänge aufweisen, effizient implementieren.

Neben dem Grad n, welcher die Periodenlänge festlegt, existieren bei einem bestimmten Grad n > 2 immer mehrere primitive Polynome, welche zueinander gleichwertig sind. Je nach Anwendung können weitere Auswahlkriterien hinzukommen. Beispielsweise werden in der Nachrichtentechnik im Bereich von Scramblern sogenannte dünn besetzte Generatorpolynome bevorzugt. Dies sind Polynome, welche mit einer minimalen Anzahl von Rückkoppelstellen bzw. mit einer minimalen Stellenanzahl ungleich 1 im Generatorpolynom auskommen. Dies hat den Grund, den Hardwareaufwand und bei selbstsynchronisierenden Scramblern die Vervielfachung von Empfangsfehlern im Descrambler zu minimieren. Im Bereich der Kodierungstheorie, wie bei zyklischen Kodes (CRC) oder bei kryptografischen Anwendungen, werden hingegen dichtbesetzte Polynome nach anderen Auswahlkriterien bevorzugt.

Primitive Polynome unterschiedlicher Grade sind in Tabellenwerken aufgelistet.[2][3] In nachfolgender Tabelle sind einige primitive Polynome mit minimaler Besetzung angeführt:

Der folgende Quelltext implementiert ein Galois-LFSR vom Grad 32 mit Periodenlänge ${\displaystyle 2^{32}-1}$:

unsigned lfsr()
{
    static unsigned r = 1;
    unsigned b = r & 1;
    r = (r >> 1) ^ (-b & 0xc3308398);
    return b;
}

Der folgende Quelltext in C++ zeigt die Implementierung eines weiteren Galois-LFSR, dessen Generatorpolynom der Benutzer selbst eingeben kann. Das Programm ermittelt die Periodenlänge des LFSR und gibt sie aus:

#include <iostream>
using namespace std;

unsigned lfsr2(unsigned _startState, unsigned _shiftBits)
{
    unsigned m = _shiftBits; m |= m >> 1; m |= m >> 2; m |= m >> 4; m |= m >> 8; m |= m >> 16;
    _startState &= m; // Entfernt überzählige Bits
    unsigned lfsr = _startState; // Initialisiert den Zustand
    unsigned periodLength = 0;
    do
    {
        unsigned lsb = lfsr & 1u; // Berechnet das Ausgabebit
        lfsr >>= 1; // Verschiebt die Zustandsbits um eine Bitposition nach rechts
        if (lsb == 1) // Wenn das Ausgabebit gleich 1 ist
        {
            lfsr ^= _shiftBits; // XOR-Rückkopplung
        }
        ++periodLength;
    } while (lfsr != _startState);
    return periodLength;
}

void main()
{
    string _startStateText;
    string _shiftBitsText;
    cin >> _startStateText; // Eingabe des Startzustands als Binärzahl über die Konsole
    cin >> _shiftBitsText; // Eingabe des Generatorpolynoms als Binärzahl über die Konsole
    unsigned _startState = stoi(_startStateText, 0, 2); // Typumwandlung von string nach unsigned
    unsigned _shiftBits = stoi(_shiftBitsText, 0, 2); // Typumwandlung von string nach unsigned
    cout << lfsr2(_startState, _shiftBits) << endl; // Ausgabe der Periodenlänge
}

Der Startzustand und das Generatorpolynom werden hier als Binärzahl über die Konsole eingegeben. Dafür ist eine Typumwandlung notwendig.

Beispiel

Für den Startzustand 1010110011100001 und das Generatorpolynom mit der Binärdarstellung 1011010000000000 ergeben sich für die ersten 6 Durchläufe der do-while-Schleife folgende Werte für das Schieberegister:

• 1. Durchlauf: Ergebnis nach Rechtsshift: 0101011001110000, Ausgabebit 1, Ergebnis nach XOR-Operation: 1110001001110000
• 2. Durchlauf: Ergebnis nach Rechtsshift: 0111000100111000, Ausgabebit 0
• 3. Durchlauf: Ergebnis nach Rechtsshift: 0011100010011100, Ausgabebit 0
• 4. Durchlauf: Ergebnis nach Rechtsshift: 0001110001001110, Ausgabebit 0
• 5. Durchlauf: Ergebnis nach Rechtsshift: 0000111000100111, Ausgabebit 0
• 6. Durchlauf: Ergebnis nach Rechtsshift: 0000011100010011, Ausgabebit 1, Ergebnis nach XOR-Operation: 1011001100010011

Parallele Berechnung

Zustand und resultierende Bits können auch kombiniert und parallel berechnet werden (besonders effizient ist das, wenn die Anzahl der zu schiebenden Bits einer Registergröße entspricht und auch das Übertragsbit benutzt werden kann, wie bei dem Polynom 63. Grades auf einer 32-Bit-Architektur). Die folgende Funktion berechnet jeweils die nächsten 32 Bits mittels 31-Bit-Galois-LFSR mit Polynom x³¹ + x²⁸ + 1 in 2 Schritten:

#include <stdint.h>

uint32_t prsg31(uint32_t lfsr) {
    lfsr = lfsr << 16 | (lfsr<<1 ^ lfsr<<4) >> 16;
    lfsr = lfsr << 16 | (lfsr<<1 ^ lfsr<<4) >> 16;
    return lfsr;
}

Gold-Folgen wurden 1967 von Robert Gold vorgestellt und besitzen ebenfalls zwei LFSRs mit unterschiedlichen Generatorpolynomen allerdings von gleicher Länge m.[4] Die maximale Codefolgenlänge der Gold-Folge ist daher auch nur 2^m−1. Hält man den Anfangszustand eines LFSR fest und verändert den Anfangszustand („Phasenverschiebung“) des anderen zyklisch, lassen sich 2^m−1 neue Codefolgen erstellen, die alle ein relativ kleines periodisches Kreuzkorrelationsmaximum zueinander aufweisen, d. h., sie stehen fast orthogonal zueinander. Dies bedeutet, dass diese Codefolgen sich im Bereich des Codemultiplex (CDMA) verwenden lassen und damit eine Unterscheidung je nach verwendeter Gold-Folge ermöglichen.

Die Gold-Folgen sind auch wegen ihrer einfachen Erzeugung die in der Praxis am häufigsten eingesetzten Spread-Spectrum-Signale. Anwendungsbereiche liegen neben Mobilfunksystemen (UMTS), welche mit CDMA arbeiten, auch bei dem zivil nutzbaren C/A-Code des globalen Positionssystems GPS und bei WLANs.

Kasami-Codegenerator wie er bei GLONASS-K Satelliten eingesetzt wird

Kasami-Folgen wurden 1966 von Tadao Kasami vorgestellt und weisen ein relativ kleines periodisches Kreuzkorrelationsmaximum zueinander auf, d. h., sie stehen fast orthogonal zueinander und werden wie die Gold-Folgen im Bereich des Codemultiplex (CDMA) eingesetzt.[5] Anwendungsbereiche dieser LFSRs liegen in Codemultiplexverfahren (CDMA) wie unter anderem im russischen Positionssystems GLONASS wo Kasami-Codefolgen ab der Satellitengeneration GLONASS-K eingesetzt werden.

Kasami-Codefolgen werden erzeugt, indem zunächst eine Maximalfolge gebildet, diese dezimiert und sodann mit der Maximalfolge mittels XOR-Operation wiederholend verknüpft wird. Es gibt zwei Gruppen von Kasami-Codefolgen, die kleine und die große Gruppe. Die kleine Gruppe besteht aus zwei LFSRs, die große Gruppe wird mit drei LFSRs gebildet.

Zur Erzeugung einer Kasami-Codefolge aus der kleinen Gruppe wird ein LFSR genommen, in rechter Schaltung unten dargestellt, welches die Folge ${\displaystyle a[n]}$ mit ${\displaystyle n=1..2^{N}-1}$ erzeugt. Als Einschränkung muss ${\displaystyle N}$ gerade sein. Ein zweites LFSR, in der Darstellung darüber, erzeugt die Folge ${\displaystyle b[n]=a[q\cdot n]}$ mit dem Indexfaktor ${\displaystyle q=2^{N/2}+1}$. Die endgültige Kasamifolge ${\displaystyle k[n]}$ wird dadurch gebildet, indem die beiden Teilfolgen miteinander XOR-verknüpft werden:

${\displaystyle k[n]=a[n]\oplus b[n]}$

Die Kasami-Folge weist eine Länge von ${\displaystyle 2^{N}-1}$ auf. Als Besonderheit nehmen Kasami-Folgen sowohl bei der Kreuzkorrelation als auch Autokorrelation nur folgende vier Werte an, wenn die erzeugte Codefolge mit den Elementen ${\displaystyle \{-1,+1\}}$ repräsentiert wird:

${\displaystyle \left\{1,-{\frac {1}{N}},-{\frac {2^{N/2}-1}{N}},{\frac {2^{N/2}-1}{N}}\right\}}$

JPL-Folgen bestehen aus zwei LFSRs deren Codefolgenlänge L_a und L_b teilerfremd (relativ prim) sein müssen.[6] In diesem Fall ist die Codefolgenlänge der erzeugten Gesamtfolge L_c gleich:

${\displaystyle L_{c}=L_{a}\cdot L_{b}=(2^{n}-1)(2^{m}-1)}$

Es können auch mehr als zwei LFSRs mittels mehrfachen XOR am Ausgang zusammengeschaltet werden. Es müssen nur alle Codefolgelängen der einzelnen LFSR teilerfremd zueinander sein.

Entwickelt wurden JPL-Folgen in den Jet Propulsion Labs, wovon sich auch der Name für diese Codefolgen ableitet. Einsatzbereiche sind unter anderem im Bereich der Entfernungsmessung mittels Spread-Spectrum-Signalen bei Satelliten und im Bereich der Weltraumtechnik und bei dem militärisch genutzten und genaueren P/Y-Code im globalen Positionssystem GPS.