Linear rückgekoppeltes Schieberegister

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein linear rückgekoppeltes Schieberegister (engl. linear feedback shift register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, das zur Erzeugung von streng deterministischen Pseudozufallszahlenfolgen eingesetzt werden kann. Zur Rückkopplung wird die lineare logische Funktion XOR verwendet.

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 Scramblern, um Datenfolgen spektral weiß zu machen, in der Kodierungstheorie bei der Kodierung und Dekodierung von zyklischen Codes, wie beispielsweise bei der 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 FPGAs, 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.

Funktion[Bearbeiten]

Ein LFSR ist in der Digitaltechnik als ein Schieberegister mit n Speicherelementen realisiert. Die einzelnen Speicherelemente sind typischerweise D-Flipflops welche je ein Bit speichern können. Im Gegensatz zu einem herkömmlichen 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 2n-1 durch ein primitives Polynom, das sogenannte Generatorpolynom, bestimmt. n ist in diesem Fall auch gleich dem 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 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.

Zur Initialisierung, im Englischen wird dieser Startwert auch als seed bezeichnet, kann das Schieberegister mit XOR-Rückkopplung mit beliebigen Werten gefüllt werden, nicht jedoch nur mit Nullen. Als Sonderfall kann ein LFSR auch die maximale Periodenlänge von 2n aufweisen. In diesem Fall treten nach einem Durchlauf lauter '0' im Schieberegister auf, die durch eine zusätzliche Logik erkannt und durch Invertierung der Rückkopplung kompensiert werden müssen. Weiter können statt der XOR-Verknüpfungen auch XNOR-Verknüpfungen eingesetzt werden, in diesem Fall sind als Startwert alle Werte außer lauter Einser erlaubt was auch wieder eine maximale Periodenlänge von 2n-1 ergibt. Auch hierbei besteht die Möglichkeit zur Erzielung der Periodenlänge 2n mit einer Zusatzlogik den „verbotenen“ Zustand mit lauter Einsen zu erkennen und durch eine zusätzliche Invertierung der Rückkopplung zu kompensieren.

Wie jedes andere Schieberegister verfügt auch das LFSR über einen Takteingang: Bei jedem Taktimpuls wird in den Folgezustand gewechselt und für einen vollständigen Durchlauf aller Kombinationen sind 2n-1 Taktimpulse notwendig.

Ein LFSR bildet wegen seiner Linearität der erzeugten Folgen für sich alleine für kryptologische Anwendungen einen schlechten Pseudozufallszahlengenerator. 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 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[Bearbeiten]

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 gleiche 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 „\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:

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:

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 XOR-Gatter mit je zwei Eingängen in der Fibonacci-Struktur zu einem XOR-Gatter mit 4 Eingängen zusammengefasst werden. Diese Form lässt sich in FPGAs mit Lookup-Tabellen welche 4 Eingänge aufweisen effizient implementieren.

Polynomauswahl[Bearbeiten]

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:

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

Anwendungen[Bearbeiten]

Anwendungen von LFSRs liegen, neben den eingangs erwähnten Bereichen, bei Modulo-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 XOR-Verknüpfungen 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. B. zur Index-Berechnung eines FIFOs.

Im Bereich der digitalen Signalverarbeitung werden LFSR auch nach der Taktgeschwindigkeit in Relation zur Bitrate bzw. Symbolrate in den Anwendungen unterschieden. Ist die Bitrate bzw. Symbolrate gleich der Taktgeschwindigkeit des LFSRs liegt ein Scrambler vor. Ist die Taktrate des LFSR deutlich höher als Bit- bzw. Symbolrate, dient das LFSR zur spektralen Spreizung wie es im Rahmen von Direct Sequence Spread Spectrum (DSSS) bzw. damit verwandt im Bereich Codemultiplexverfahren (CDMA) eingesetzt wird. 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[Bearbeiten]

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 = 2n-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[Bearbeiten]

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 2m-1. Hält man den Anfangszustand eines LFSR fest und verändert den Anfangszustand („Phasenverschiebung“) des anderen zyklisch, lassen sich 2m-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-Folgen[Bearbeiten]

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 wird, diese dezimiert wird und die so dezimierte Folge 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 a[n] mit n=1..2^N-1 erzeugt. Als Einschränkung muss N gerade sein. Ein zweites LFSR, in der Darstellung darüber, erzeugt die Folge b[n] = a[q \cdot n] mit dem Indexfaktor q = 2^{N/2}+1. Die endgültige Kasamifolge k[n] wird dadurch gebildet, indem die beiden Teilfolgen miteinander XOR-verknüpft werden:

k[n] = a[n] \oplus b[n]

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

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

JPL-Folgen[Bearbeiten]

JPL-Folgen bestehen aus zwei LFSRs deren Codefolgenlänge La und Lb teilerfremd sein müssen. In diesem Fall ist die Codefolgenlänge der erzeugten Gesamtfolge Lc gleich:

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 in Bereich der Weltraumtechnik und bei dem militärisch genutzten und genaueren P/Y-Code im globalen Positionssystem GPS.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  •  Uwe Meyer-Baese: Digital Signal Processing with Field Programmable Gate Arrays. 1. Auflage. Springer, 2001, ISBN 3-540-41341-3.

Einzelnachweise[Bearbeiten]

  1.  Manfred Schroeder: Number Theory in Science and Communication. 8. Auflage. Springer, 2008, ISBN 978-3-540-85297-1.
  2.  Wayne Stahnke: Primitive Binary Polynominals. Mathematics of Computation, 1973, S. 977 bis 980.
  3.  Peter Alfke: Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators. Xilinx Application Note XAPP052, 1996 (http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf).
  4.  Robert Gold: Optimal binary sequences for spread spectrum multiplexing. IEEE Transactions on Information Theory, Volume 13, Ausgabe 4 (Online).
  5.  Tadao Kasami: Weight Distribution Formula for Some Class of Cyclic Codes. University of Illinois, 1966 (Technical Report Nr. R-285).