Quelltext der Seite Linear rückgekoppeltes Schieberegister

[[Datei:LFSR-F4.GIF|501px|mini|Ein 4-bit-Fibonacci-LFSR und seine [[Zustandsübergangsdiagramm|Zustände]]. Das Register schiebt die Bits von links nach rechts. Das [[Exklusiv-Oder-Gatter]] wird von den beiden hinteren Bits des Registers gefüttert und liefert diesem vorne damit wiederum die Eingabe. Die maximale Ausgabesequenz besteht aus jedem möglichen Zustand mit Ausnahme des Zustands "0000".]]
Ein '''linear rückgekoppeltes Schieberegister''' (engl. {{lang|en|''linear feedback shift register''}}, kurz ''LFSR'') ist ein rückgekoppeltes [[Schieberegister]], das zur Erzeugung von streng deterministischen [[Pseudozufallszahlen]]folgen eingesetzt werden kann. Zur Rückkopplung wird die lineare logische Funktion [[XOR]] verwendet.

Den Startwert bezeichnet man als {{lang|en|''[[Seed key|seed]]''}}. Da die Ausgabe des Registers streng deterministisch ist und vollständig von seinem momentanen Zustand abhängt, das Register jedoch gleichzeitig nur eine endliche Anzahl an Zuständen hat, muss es zwangsläufig irgendwann wieder bei seinem Startwert ankommen. Bei n Bit breiten Schieberegistern ergibt sich damit eine maximale Periodenlänge von 2<sup>''n''</sup>−1. Ab diesem Zeitpunkt wiederholt sich die Ausgabesequenz, das Register befindet sich in einem Wiederholzyklus. Je nach gewählter Implementierung ist diese Sequenz unterschiedlich lang, allerhöchstens können [[Maximum Length Sequence|Folgen maximaler Länge]] erzeugt werden.

Anwendungen liegen neben der Erzeugung von Pseudozufallszahlenfolgen im Bereich schneller digitaler [[Synchronzähler]], da diese Zähler ohne Übertrag arbeiten, im Bereich der Nachrichtentechnik und [[Kryptografie]] bei [[Scrambler (Telekommunikation)|Scramblern]], um Datenfolgen [[Weißes Rauschen (Physik)|spektral weiß]] zu machen, in der Kodierungstheorie bei der Kodierung und Dekodierung von [[Zyklischer Code|zyklischen Codes]], wie beispielsweise bei der [[Zyklische Redundanzprüfung|zyklischen Redundanzprüfung]] (CRC) oder dem [[Hamming-Code]], und im Bereich der digitalen Modulationstechnik bei den [[Codemultiplexverfahren]] (CDMA) und im Bereich der [[Steganographie]].

Linear rückgekoppelte Schieberegister können effizient sowohl direkt in Hardware, wie beispielsweise [[FPGA]]s, als auch in Software implementiert werden. Bei der Softwareimplementierung wird, da die meisten Prozessoren mit Registerbreiten größer als ein Bit arbeiten, typischerweise mit im Voraus berechneten Tabellen gearbeitet, die direkt den inneren Zustand des Schieberegisters abbilden.

== Funktionsweise ==
Ein LFSR ist in der [[Digitaltechnik]] als ein Schieberegister mit ''n'' Speicherelementen realisiert. Die einzelnen Speicherelemente sind typischerweise [[Flipflop#D-Flipflop|D-Flipflops]], welche je ein Bit speichern können. Im Gegensatz zu einem gewöhnlichen [[Schieberegister]] bestehen zwischen bestimmten D-Flipflops Abzweigungen, welche die Rückkopplungen darstellen. Die Anzahl und die Position dieser Abzweigungen in der Registerkette wird zur Erzielung der maximal möglichen Periodenlänge von 2<sup>''n''</sup>−1 durch ein [[primitives Polynom]], das sogenannte Generatorpolynom, bestimmt. ''n'' ist in diesem Fall auch gleich dem [[Grad (Polynom)|Grad]] des Generatorpolynoms.

Ein primitives Polynom als Generatorpolynom ist nicht zwingend notwendig, allerdings ergeben nicht-primitive Polynome kürzere Periodenlängen. Kürzere Periodenlängen sind jedoch auch mit einer geringeren Anzahl von Flipflops und Verwendung eines entsprechenden primitiven Polynoms geringeren Grades erreichbar, weshalb als Generatorpolynome praktisch ausschließlich primitive Polynome Einsatz finden. Die mögliche Gesamtanzahl aller linear rückgekoppelten Schieberegister beträgt 2^(n - 1) - 1, (mindestens ein XOR-Gatter), allerdings sind von dieser Gesamtzahl nur ein kleiner Anteil solche Schieberegister, deren Periodenlänge maximal ist ("m-Sequenz"), also durch ein primitives Polynom bestimmt. Die Anzahl verfügbarer m-Sequenzen für gegebenes n berechnet sich zu φ(2^n - 1)/n. Darin ist φ(x) die sogenannte "Eulerfunktion". Die "On-Line Encyclopedia of Integer Sequences", OEIS, listet die Zahlenfolge dafür unter [[OEIS:A011260|A011260]].

Zur Initialisierung, im Englischen wird dieser Startwert auch als ''seed'' bezeichnet, kann das Schieberegister mit XOR-Rückkopplung mit beliebigen Werten gefüllt werden&nbsp;– bei positiver Logik jedoch nicht nur mit Nullen, da dann das Register aus diesem Zustand niemals herauskäme, das Schieberegister also eine triviale Folge konstanter Nullen generieren würde. Es können statt der XOR-Verknüpfungen auch [[XNOR-Verknüpfung]]en eingesetzt werden (negative Logik); in diesem Fall sind als Startwert alle Werte außer lauter Einsen erlaubt, was auch wieder eine maximale Periodenlänge von 2<sup>''n''</sup>−1 ergibt. Je nach Technologie ist es einfacher, den Zustand mit lauter Nullen als definierten Anfangszustand zu implementieren. Die Verknüpfung mittels XNOR hat hierbei den Vorteil, dass dieser Zustand mit lauter Nullen als Startwert geeignet ist und nicht, wie bei XOR, zu der trivialen konstanten Nullfolge führt.

Ein LFSR kann auch so implementiert werden, dass es die maximale Periodenlänge von 2<sup>''n''</sup> aufweist<ref name="xilinx" />. Hierbei treten nach einem Durchlauf lauter '0' im Schieberegister auf, die als Sonderfall durch eine zusätzliche Logikschaltung erkannt und durch daraufhin aktivierte Invertierung der Rückkopplung kompensiert werden müssen. Diese Möglichkeit besteht analog auch bei XNOR-Verknüpfungen; der Sonderfall ist hierbei stattdessen der Zustand mit lauter Einsen.

Wie jedes andere Schieberegister verfügt auch das LFSR über einen [[Taktsignal|Takteingang]]: Bei jedem Taktimpuls wird in den Folgezustand gewechselt und für einen vollständigen Durchlauf aller Kombinationen sind 2<sup>''n''</sup>−1 Taktimpulse notwendig (sofern, wie oben beschrieben, ein primitives Polynom zum Einsatz kommt und auf das erwähnte „Aufbohren“ der Rückkopplung auf 2<sup>''n''</sup> Zustände verzichtet wurde).

Ein LFSR bildet wegen seiner Linearität der erzeugten Folgen für sich alleine für kryptologische Anwendungen einen schlechten [[Pseudozufallszahlen]]generator. LFSR werden als Grundelement und in Verbindung mit nichtlinearen Funktionen oder als eine Kombination mehrerer LFSR verwendet.

Neben den in digitalen Schaltungen üblichen binären LFSR in [[Endlicher Körper|GF(2)]] existieren auch nichtbinäre LFSR mit einer Anzahl an Elementen ''q'' größer als 2. Die XOR-Operation, sie stellt eine Addition [[modulo]] 2 dar, wird im allgemeinen Fall durch eine Addition modulo ''q'' ersetzt, die Speicherelemente müssen je ''q'' Zustände speichern können.

=== Arten ===
Es gibt in der Realisierung zwei verschiedene Arten von LFSR:

# Fibonacci-LFSR, benannt nach dem italienischen Mathematiker [[Leonardo Fibonacci]], und
# 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 „<math>\oplus</math>“ dargestellt.

[[Datei:LFSR-Fibonacci.svg|mini|zentriert|650px|Fibonacci-LFSR]]
[[Datei:LFSR-Galois.svg|mini|zentriert|650px|Galois-LFSR]]

Die beiden Formen ergeben sich aus dem Umstand, dass jedes primitive Polynom vom Grad ''n''&nbsp;>&nbsp;2 ein „Zwillingspolynom“ besitzt, welches ebenfalls primitiv ist.<ref name="schroeder" /> In den beiden Abbildungen wurde für das Fibonacci-LFSR ein Generatorpolynom vom 8. Grad verwendet:

:<math>p_f(x) = x^8 + x^6 + x^5 + x^4 + 1</math>

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

:<math>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</math>

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-Tabelle]]n, welche vier Eingänge aufweisen, effizient implementieren.

=== Polynomauswahl ===
Neben dem Grad ''n,'' welcher die Periodenlänge festlegt, existieren bei einem bestimmten Grad ''n''&nbsp;>&nbsp;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 [[Scrambler (Telekommunikation)|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 [[Scrambler (Telekommunikation)#Selbstsynchronisierende (multiplikative) Scrambler|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.<ref name="stahnke" /><ref name="xilinx" /> In nachfolgender Tabelle sind einige primitive Polynome mit minimaler Besetzung angeführt:

{| class="wikitable" style="text-align:center"
!Grad !! Exponenten !! !! Grad !! Exponenten
|-
|1  || 1      || || 14 || 14, 13, 11, 9
|-
|2  || 2, 1   || || 15 || 15, 14
|-
|3  || 3, 2   || || 16 || 16, 14, 13, 11
|-
|4  || 4, 3   || || 17 || 17, 14
|-
|5  || 5, 3   || || 18 || 18, 11
|-
|6  || 6, 5   || || 19 || 19, 18, 17, 14
|-
|7  || 7, 6   || || 20 || 20, 17
|-
|8  || 8, 6, 5, 4 || || 21 || 21, 19
|-
|9  || 9, 5   || || 22 || 22, 21
|-
|10 || 10, 7  || || 23 || 23, 18
|-
|11 || 11, 9  || || 24 || 24, 23, 21, 20
|-
|12 || 12, 11, 8, 6  || ||  … || …
|-
|13 || 13, 12, 10, 6 || || 9689 || 9689, 84
|}

=== Programmierung ===
Der folgende [[Quelltext]] implementiert ein Galois-LFSR vom Grad 32 mit Periodenlänge <math>2^{32}-1</math>:
<syntaxhighlight lang="c++">
unsigned lfsr()
{
    static unsigned r = 1;
    unsigned b = r & 1;
    r = (r >> 1) ^ (-b & 0xc3308398);
    return b;
}
</syntaxhighlight>
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:
<syntaxhighlight lang="c++">
#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;
}

int 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
    return 0;
}
</syntaxhighlight>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:

<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>

Entsprechendes Fibonacci-LFSR<ref name="xilinx" /> mit 32 Schritten:

<syntaxhighlight lang="c">
#include <stdint.h>

uint32_t prsg31(uint32_t lfsr) {
    for (int i = 0; i < 32; i++)
        lfsr = lfsr << 1 | ((lfsr>>30 ^ lfsr>>27) & 1);
    return lfsr;
}
</syntaxhighlight>

== Anwendungen ==
Anwendungen von LFSRs liegen, neben den eingangs erwähnten Bereichen, bei [[Modulo]]-[[Zählwerk|Zählern]], welche bis zur Periodenlänge zählen und dann „überlaufen“, also wieder von vorne beginnen. Dies ist deutlich effizienter als ein arithmetischer („echter“) Zähler mit Übertragslogik ''(Carry-Logic),'' da statt einer n-Bit-[[Addition]] lediglich einige Exklusiv-Oder-Verknüpfungen (XOR) notwendig sind. Allerdings lässt sich der aktuelle Zählerstand nicht direkt aus dem Zustand des LFSR ableiten, weshalb sich ein LFSR-Zähler nur für bestimmte Anwendungen eignet, z.&nbsp;B. zur Index-Berechnung bei der Implementierung einer Warteschlange ([[First In – First Out]]) mittels [[Random-Access-Memory]] (RAM).

Im Bereich der digitalen Signalverarbeitung werden LFSR auch nach der Taktgeschwindigkeit in Relation zur Bitrate bzw. [[Symbolrate]] in den Anwendungen unterschieden. Bei einem [[Scrambler (Telekommunikation)|Scrambler]] ist die Bitrate bzw. Symbolrate gleich der Taktgeschwindigkeit des LFSRs. Wird das LFSR zur spektralen Spreizung eingesetzt, ist die Taktrate des LFSR deutlich höher als die Bit- bzw. Symbolrate. Anwendung findet das etwa im Rahmen von [[Direct Sequence Spread Spectrum|Direct-Sequence-Spread-Spectrum]]-Verfahren (DSSS) bzw. –&nbsp;damit verwandt&nbsp;– im Bereich [[Codemultiplexverfahren]] (CDMA). Durch sogenannte ''zusammengesetzte LFSR'' können dann Folgen gebildet werden, wie sie beispielsweise im Rahmen von [[Global Positioning System]] (GPS) zu Navigationszwecken eingesetzt werden.

Mit linear rückgekoppelten Schieberegistern werden bei der [[Signaturanalyse]] komprimierte Bitvektoren zur Überprüfung der Funktion einer Schaltung ermittelt.

== Zusammengesetzte LFSR ==
[[Datei:LFSR-GPS-CA-Goldcode.svg|mini|hochkant=2.5|Zwei kombinierte LFSRs wie sie bei GPS zur Erzeugung der C/A-Codes (Gold-Code) Verwendung finden.]]
Eine Erweiterung stellt die Kombinationen der Datenfolgen verschiedenartiger LFSR dar. Die dabei entstehenden neuen Datenfolgen können andere Eigenschaften aufweisen als die ursprünglichen LFSR. Sie können damit beispielsweise durch eine geringe [[Autokorrelation]] geeigneter für Anwendungen im Bereich Code Division Multiple Access und zur spektralen Spreizung sein.

Die Zusammensetzung der Ausgabedatenfolge aus den einzelnen unabhängigen LFSRs erfolgt mittels [[XOR]]-Verknüpfung der einzelnen Teilfolgen. Weisen die LFSR unterschiedliche Folgenlängen ''L'' = 2<sup>''n''</sup>−1 und unterschiedliche Generatorpolynome auf, lassen sich Codefolgen mit völlig neuen Eigenschaften erzeugen. Im Regelfall weisen diese zusammengesetzten, zyklischen Folgen nicht die maximal mögliche Länge auf. Im Folgenden werden einige wichtige Klassen von aus LFSR-Registern zusammengesetzten Codefolgen dargestellt:

=== Gold-Folgen ===
Gold-Folgen wurden 1967 von Robert Gold vorgestellt und besitzen ebenfalls zwei LFSRs mit unterschiedlichen Generatorpolynomen allerdings von gleicher Länge m.<ref>{{Literatur |Autor=Robert Gold |Titel=Optimal binary sequences for spread spectrum multiplexing |Band=Volume 13 |Auflage=4. |Verlag=IEEE Transactions on Information Theory |Seiten=619–621 |Online= [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1054048 online]}}</ref> Die maximale Codefolgenlänge der Gold-Folge ist daher auch nur 2<sup>''m''</sup>−1. Hält man den Anfangszustand eines LFSR fest und verändert den Anfangszustand („Phasenverschiebung“) des anderen zyklisch, lassen sich 2<sup>''m''</sup>−1 neue Codefolgen erstellen, die alle ein relativ kleines periodisches [[Kreuzkorrelation]]smaximum zueinander aufweisen, d.&nbsp;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 [[WLAN]]s.

=== Kasami-Folgen ===
[[Datei:LFSR-GLONASS-K-Kasamicode.svg|mini|hochkant=2.5|Kasami-Codegenerator wie er bei GLONASS-K Satelliten eingesetzt wird]]
Kasami-Folgen wurden 1966 von [[Tadao Kasami]] vorgestellt und weisen ein relativ kleines periodisches [[Kreuzkorrelation]]smaximum zueinander auf, d.&nbsp;h., sie stehen fast orthogonal zueinander und werden wie die Gold-Folgen im Bereich des [[Codemultiplex]] (CDMA) eingesetzt.<ref>{{Literatur |Autor=Tadao Kasami |Titel=Weight Distribution Formula for Some Class of Cyclic Codes |Reihe=Technical Report Nr. R-285 |Verlag=University of Illinois |Datum=1966}}</ref> 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 <math>a[n]</math> mit <math>n=1..2^N-1</math> erzeugt. Als Einschränkung muss <math>N</math> gerade sein. Ein zweites LFSR, in der Darstellung darüber, erzeugt die Folge <math>b[n] = a[q \cdot n]</math> mit dem Indexfaktor <math>q = 2^{N/2}+1</math>. Die endgültige Kasamifolge <math>k[n]</math> wird dadurch gebildet, indem die beiden Teilfolgen miteinander XOR-verknüpft werden:

:<math>k[n] = a[n] \oplus b[n]</math>

Die Kasami-Folge weist eine Länge von <math>2^N-1</math> 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 <math>\{-1, +1\}</math> repräsentiert wird:

:<math>\left\{ 1, -\frac{1}{N}, -\frac{2^{N/2}-1}{N}, \frac{2^{N/2}-1}{N} \right\}</math>

=== JPL-Folgen ===
JPL-Folgen bestehen aus zwei LFSRs deren Codefolgenlänge ''L''<sub>a</sub> und ''L''<sub>b</sub> teilerfremd ([[relativ prim]]) sein müssen.<ref name="Goiser1" /> In diesem Fall ist die Codefolgenlänge der erzeugten Gesamtfolge ''L''<sub>c</sub> gleich:

:<math>L_c = L_a \cdot L_b = (2^n - 1)(2^m - 1)</math>

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 Laboratory|Jet Propulsion Labs]], wovon sich auch der Name für diese Codefolgen ableitet. Einsatzbereiche sind unter anderem im Bereich der Entfernungsmessung mittels [[Frequenzspreizung|Spread-Spectrum]]-Signalen bei Satelliten und im Bereich der Weltraumtechnik und bei dem militärisch genutzten und genaueren P/Y-Code im [[Global Positioning System|globalen Positionssystem GPS]].

== Siehe auch ==
* [[Maximum Length Sequence]]
* [[Berlekamp-Massey-Algorithmus]]
* [[Pseudozufallsrauschen]]

== Literatur ==
* {{Literatur |Autor=Uwe Meyer-Baese |Titel=Digital Signal Processing with Field Programmable Gate Arrays |Auflage=1. |Verlag=Springer |Datum=2001 |ISBN=3-540-41341-3}}

== Einzelnachweise ==
<references>
<ref name="schroeder">{{Literatur |Autor=Manfred Schroeder |Titel=Number Theory in Science and Communication |Auflage=8. |Verlag=Springer |Datum=2008 |ISBN=978-3-540-85297-1}}</ref>
<ref name="stahnke">{{Literatur |Autor=Wayne Stahnke |Titel=Primitive Binary Polynomials |Sammelwerk=Mathematics of Computation |Datum=1973-10 |DOI=10.2307/2005535 |Seiten=977–980}}</ref>
<ref name="xilinx">{{Literatur |Autor=Peter Alfke |Titel=Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators |Reihe=Xilinx Application Note XAPP052 |Datum=1996 |Online= [http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf online] PDF}}</ref>
<ref name="Goiser1">{{Literatur |Autor=Alois M.J. Goiser |Titel=Handbuch der Spread-Spectrum Technik |Verlag=Springer Verlag |Datum=1998 |ISBN=3-211-83080-4 |Kapitel=Kapitel 4.3: Zusammengesetzte Folgen |Seiten=151 – 152}}</ref>
</references>

{{SORTIERUNG:Linear Ruckgekoppeltes Schieberegister}}

[[Kategorie:Pseudozufallszahlengenerator]]
[[Kategorie:Digitale Schaltungstechnik]]