FPGA: Pseudo Random Generator (PRNG) von Prof. Dr

Praktikum
Digitaltechnik
FPGA: Pseudo Random Generator (PRNG)
von Prof. Dr.-Ing. Dirk Rabe
Gruppe:
Teilnehmer:
Benutzte Geräte:
Vortestat:
Testat:
1
1
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
1 Einleitung und Überblick
Einleitung und Überblick
Dieser Versuch behandelt drei Themen:
1)
Den Logikanalysator als Messgerät zur Schaltungsanalyse (z.B. Fehleranalyse).
2)
Den Pseudo-Random-Generator (PRNG).
3)
Den Entwurf des PRNG als Repräsentant sequentieller Schaltungen mit VHDL.
Teile dieser Versuchsanleitung entstammen der Versuchsanleitung von Prof. Dr.-Ing. Ingo H.
Karlowsky. Verglichen mit dem bei Herrn Karlowsky durchgeführten Laborversuch wird hier
der Fokus auf die Hardwarerealisierung in einem FPGA gelegt.
V 1.0.1 / 2009-04-29
FPGA-Einführung und Hardwareentwurf mit VHDL
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
2
2
Der Logikanalysator
Logikanalysatoren sind ein sehr nützliches Hilfsmittel bei der Erprobung und Analyse digitaler
Schaltungen. Im Unterschied zu Oszilloskopen sollen sie nicht die Kurvenform der Eingangssignale möglichst authentisch wiedergeben, sondern den zeitlichen Ablauf von Binärsignalen.
Mehrere Binärsignale können als Zahlen dargestellt werden (binär, oktal oder hexadezimal).
Die aufzunehmenden Daten werden typischerweise fortlaufend in Speichern abgespeichert.
Ähnlich wie bei Oszilloskopen können Trigger definiert werden. Die Triggerbedingungen können jedoch wesentlich komplizierter gestaltet werden. Da die Signale fortlaufend gespeichert
werden, ist auch die Historie der Signale darstellbar. Bei Fehleranalysen wird beispielsweise
auf eine Fehlerbedingung getriggert und dann anschließend analysiert wie es zu diesem Fehler
gekommen ist. Hierzu ist die Historie von besonderer Bedeutung.
Die Anzahl der Pins digitaler Schaltungen kann mehrere hundert betragen (z.B. hat das auf
dem Experimentierboard DE2 verwendete FPGA 475 Pins). Die Anzahl der Signale, die
gleichzeitig aufgezeichnet werden können hängt vom Logikanalysator (und damit den
Anschaffungskosten) ab (neben weiteren Parametern wie die maximale Abtastrate und die
Speichertiefe).
Die im Versuch verwendeten Geräte sind eine Kombination aus Oszilloskopen und einfachen
Logikanalysatoren. Professionelle Logikanalysatoren weisen typischerweise wesentlich
umfangreichere Trigger- und Verarbeitungsmöglichkeiten auf.
FPGA-Einführung und Hardwareentwurf mit VHDL
V 1.0.1 / 2009-04-29
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
3 Der Pseudo Random Number Generator (PRNG)
3
3
Der Pseudo Random Number Generator (PRNG)
3.1 Einleitung
Sehr häufig werden in der Technik Zufallszahlen benötigt (z.B. zur Untersuchung von dynamischen Systemen, zum Testen vom RAM-Speichern, für kryptographische Verfahren, ...).
Solche Generatoren lassen sich sehr gut mit rückgekoppelten Schieberegistern (LFSR†) aufbauen. Im folgenden werden 2 prinzipielle Realisierungen unterschieden: Fibonacci- und
Galois-LFSRs .
3.1.1
Fibonacci-LFSR
Abbildung 1 zeigt den Hardwareaufbau eines 4 Bit Fibonacci-LFSRs und die 24-1=15 Bitmuster, die sich durch Taktung des rückgekoppelten Schieberegisters ergeben.
1010
0101
1011
1101
0110
1110
1 3 4
1100
1111
1 0 0 0
1001
0111
0010
0011
0001
1000
0100
Abbildung 1: Sequenz eines 4-Bit Fibonacci-LFSRs (linear Feedback Shift Registers)
Mit jedem Clock(Takt)-Impuls wird der gesamte Inhalt des Schieberegisters um eine Stelle
nach rechts verschoben (Multiplikation mit 2). Das Exklusiv-Oder-Verknüpfte Signal wird
dabei in die Bitposition 1 (SL-Eingang) rückgekoppelt. Der Inhalt der Bitposition 4 (MSB)
geht dabei verloren. Auf diese Weise entsteht mit jedem Taktimpuls ein neues Bitmuster im
Schieberegister. Erst nach 24 - 1 = 15 Taktimpulsen wiederholt sich die ursprüngliche Bitkombination (Pseudo-Zufallszahlen). Für längere Schieberegister mit geeigneter Rückkoppelung
erhöht sich die Anzahl der Bitkombinationen entsprechend (2n-1).
3.1.2
Galois-LFSR
Abbildung 2 zeigt den Hardwareaufbau eines 4 Bit Galois-LFSRs und die 24-1=15 Bitmuster,
die sich durch Taktung des rückgekoppelten Schieberegisters ergeben.
Der Unterschied zum Fibonacci-LFSR liegt in der Art der Rückkopplung. Das am weitesten
rechts befindliche Register wird hier über ein EXOR-Gatter mit Schiebewerten verknüpft. Der
Wert des Schieberegisters 4 wird hier mit dem Schieberegister 1 EXOR-verknüpft und mit der
nächsten steigenden Flanke in das Register 3 übernommen.
†
LFSR: Linear Feedback Shift Register - also auf Deutsch: linear rückgekoppeltes Schieberegister
V 1.0.1 / 2009-04-29
FPGA-Einführung und Hardwareentwurf mit VHDL
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
3.2 Optimale Rückkopplung eines Schieberegisters
4
4 3 1
0111
1110
0
0101
1111
0 0 1
P=x4 + x3 + 1
1010
1011
1101
1001
1000
0011
0100
0110
0010
0001
1100
Abbildung 2: Sequenz eines 4-Bit Galois-LFSRs (linear Feedback Shift Registers)
Auch hier entsteht mit jedem Taktimpuls ein neues Bitmuster im Schieberegister. Erst nach 24
- 1 = 15 Taktimpulsen wiederholt sich die ursprüngliche Bitkombination (Pseudo-Zufallszahlen). Für längere Schieberegister mit geeigneter Rückkoppelung erhöht sich die Anzahl der
Bitkombinationen entsprechend (2n-1).
3.2 Optimale Rückkopplung eines Schieberegisters
Die Darstellung in diesem Abschnitt gilt sowohl für das Fibonacci- als auch für das GaloisLFSR.
Für die gewählte Struktur des LFSRs (Linear Feedback Shift Register - linear rückgekoppeltes
Schieberegister) mit maximaler Periodizität gibt es 2 mögliche Bitfolgesequenzen:
• eine Bitfolgesequenz der Länge 2n-1 (siehe Abb. 1),
• eine Bitfolgesequenz der Länge 1: sämtliche Bits sind ‚0‘.
Den Nullzustand muss man in jedem Fall vermeiden, wenn man ein LFSR mit maximaler Periodizität haben möchte. Bei der Realisierung mit Flipflops sollten damit nicht alle Flipsflops
den Reset-Zustand 0 haben.
Der Zustand des Schieberegisters (also das Bitmuster sämtlicher Register zum aktuellen Zeitpunkt) ist nicht als Pseudozufallszahl zu betrachten. Lediglich das Eingangsbit ist als Zufallsbit zu betrachten. In der Fibonacci-Realisierung wird das Bit von der ersten Position nämlich
einfach bis zur letzten Position des Schieberegisters propagiert. Kennt man also zum Zeitpunkt
t das in den Registern gespeicherte Bitmuster, so wird zum Zeitpunkt t+1 (also nach der nächsten steigenden Taktflanke) dieses Muster lediglich um eine Position weiter geschoben. Dabei
fällt der Wert des höchstwertigen Registers heraus und das niederwertigste Bit wird aus der
Modulo-2-Verknüpfung (EXOR) anderer Register gebildet.
Nun stellt sich die Frage welche Bits man per EXOR zurück koppeln muß, um ein LFSR mit
maximaler Periodizität zu erhalten. Dies kann man mathematisch berechnen (Z-Transformation) oder aus Tabellen entnehmen. Die Rückkoppelungen werden mit einem Rückkopplungspolynom beschrieben. Dies ist in Abbildung 3 für ein 16-Bit Fibonacci-LFSR und in
Abbildung 4 für ein 16-Bit Galois-LFSR mit einer Periodizität von 216-1=65535 beschrieben.
Die ‚1‘ im Polynom kennzeichnet beim Fibonacci-LFSR die Rückkopplung auf das 1.Bit und
FPGA-Einführung und Hardwareentwurf mit VHDL
V 1.0.1 / 2009-04-29
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
3 Der Pseudo Random Number Generator (PRNG)
5
beim Galois-LFSR die Rückkopplung vom 1.Bit. Es ist zu beachten, dass die Numerierung der
Bits in den beiden LFSRs unterschiedlich ist.
1 11 13 14 16
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
P=x16+x14+x13+x11+1
Abbildung 3: 16-Bit-Fibonacci-LFSR maximaler Periodizität und das zugehörige Rückkopplungspolynom P
16 14 13 11 1 0
0
0 1
1
0 0 0 1 0 0 0 1 0 0 0
P=x16+x14+x13+x11+1
Abbildung 4: 16-Bit-Galois-LFSR maximaler Periodizität und das zugehörige Rückkopplungspolynom P
In Tabelle 1 sind für mehrere LFSR-Längen (n) die Rückkoppelungspolynome angegeben, die
eine maximale Periodizität ergeben.
Rückkoppelungspolynom
Periodenlänge
2n − 1
n
4
x4 + x3 + 1
15
5
x5 + x3 + 1
31
6
x6 + x5 + 1
63
7
x7 + x6 + 1
127
8
x8 + x6 + x5 + x4 + 1
255
9
x9 + x5 + 1
511
10
x10 + x7 + 1
1023
Tabelle 1: Rückkoppelungspolynome, die ein LFSR maximaler Periodizität liefern
V 1.0.1 / 2009-04-29
FPGA-Einführung und Hardwareentwurf mit VHDL
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
3.2 Optimale Rückkopplung eines Schieberegisters
Rückkoppelungspolynom
6
Periodenlänge
2n − 1
n
11
x11 + x9 + 1
2047
12
x12 + x11 + x10 + x4 + 1
4095
13
x13 + x12 + x11 + x8 + 1
8191
14
x14 + x13 + x12 + x2 + 1
16383
15
x15 + x14 + 1
32767
16
x16 + x14 + x13 + x11 + 1
65535
17
x17 + x14 + 1
131071
18
x18 + x11 + 1
262143
19
x19 + x18 + x17 + x14 + 1
524287
Tabelle 1: Rückkoppelungspolynome, die ein LFSR maximaler Periodizität liefern
FPGA-Einführung und Hardwareentwurf mit VHDL
V 1.0.1 / 2009-04-29
7
4
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
4 Beschreibung sequentieller Schaltungen in VHDL
Beschreibung sequentieller Schaltungen in VHDL
Im Gegensatz zu den bisher verwendeten kombinatorischen Schaltungen haben sequentielle
Schaltungen ein Gedächtnis (vergleiche auch Automaten). Das Herzstück dieser sequentiellen
Schaltungen sind speichernde Schaltungselemente. Als speichernde Schaltungselemente werden typischerweise taktflankengesteuerte Flipflops verwendet. Es stellt sich nun die Frage wie
man das Verhalten von Flipflops in VHDL beschreiben kann.
Flipflops werden im architecture-body in einem Prozess beschrieben. In Abbildung 5 ist ein DFlipflop mit asynchronem Reset beschrieben. In der Sensitivity-Liste ist das Taktsignal clk und
das Signal für den asynchronen Reset (rst_n) beschrieben. D.h., dass Änderungen am Eingang
d nicht zu einer Neubewertung vom Ausgangssignal q führt. Wenn das Signal rst_n ‚0‘ ist, so
wird der Ausgang q auf ‚0‘ gehalten. Sollte rst_n von ‚1‘ auf ‚0‘ wechseln so wird unabhängig
vom Takt der Ausgang unmittelbar auf ‚0‘ gesetzt. Ist rst_n=‘1‘ so wird bei jeder steigenden
Taktflanke der Eingang D übernommen (elsif clk‘event and clk=‘1‘ - also Signalwechsel an
clk und der neue Wert soll ‚1‘ sein). In dem Bereich zwischen diesem elsif und dem „end if“
wird hier nur d auf q zugewiesen. In diesem Bereich können auch komplexere Ausdrücke stehen. Bei Automaten könnte hier z.B. der Folgezustand kodiert werden. Außerdem können hier
auch mehrere Bits - wie z.B. Vektoren - zugewiesen werden. Beim PRNG kann hier nun die
Schiebefunktion und die Rückkopplung beschrieben werden.
Abbildung 5: Verhaltensbeschreibung eines taktflankengesteuerten D-Flipflops
V 1.0.1 / 2009-04-29
FPGA-Einführung und Hardwareentwurf mit VHDL
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
3.2 Optimale Rückkopplung eines Schieberegisters
8
Auf einzelne Bits eines Signals vom Typ std_ulogic_vector kann durch Angabe der Bit-Position oder des Bit-Bereichs zugegriffen werden. Dies soll durch folgendes Beispiel erklärt werden. Das Signal mysig sei hierbei vom Typ std_ulogic_vector(1 to 10).
mysequentialproc : process...
...
begin
...
elsif clk‘event and clk=‘1‘
mysig(3 to 8) <= mysig(1 to 6); -- schieben um 2 Bit-Positionen
mysig(2) <= mysig(3) xor mysig(2); -- xor-Verknüpfung des alten Werts vom mysig(2) und mysig(3)
end if;
end process mysequentialproc;
FPGA-Einführung und Hardwareentwurf mit VHDL
V 1.0.1 / 2009-04-29
9
5
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
5 Aufgabenstellung
Aufgabenstellung
Es soll ein PRNG in VHDL realisiert werden.
5.1 Vorbereitung (vor dem Praktikumstermin)
Die Antworten sind auf dem Ausdruck handschriftlich zu ergänzen.
1)
Wie lautet ein Polynom P1, das ein 5-Bit-LFSR mit maximaler Periodizität liefert?
2)
Skizzieren Sie die Struktur des Fibonacci- und Galois-LFSR, das dieses Polynom P1 verwendet.
3)
Skizzieren Sie die Struktur des Fibonacci- und Galois-LFSR, das das Polynom
P2=x5+x1+1 verwendet.
4)
Was passiert wenn Sie bei der Verwendung des Polynoms P1 mit der Bitfolgenkombination „00000“ starten?
V 1.0.1 / 2009-04-29
FPGA-Einführung und Hardwareentwurf mit VHDL
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
5.1 Vorbereitung (vor dem Praktikumstermin)
5)
10
Vervollständigen Sie in der folgenden Tabelle die Bitfolgenkombination für die Fibonacci- und Galois-LFSRs, die das Polynom P2 verwenden.
Fibonacci-LFSR
Nr.
Galois-LFSR
1
2
3
4
5
5
4
3
2
1
1
1
1
1
1
1
1
1
1
1
1
2
0
1
1
1
1
1
1
1
1
0
3
1
0
1
1
1
0
1
1
1
1
4
0
1
0
1
1
1
0
1
1
0
10
0
1
1
0
0
1
1
0
0
0
11
0
0
1
1
0
0
1
1
0
0
12
0
0
0
1
1
0
0
1
1
0
15
0
0
1
0
0
0
1
0
0
0
16
0
0
0
1
0
0
0
1
0
0
17
0
0
0
0
1
0
0
0
1
0
18
1
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
1
1
0
1
5
6
7
8
9
13
14
19
20
21
22
23
Tabelle 2: Bitfolge für 5-Bit Fibonacci- und Galois-LFSRs bei Verwendung des Polynoms P2
FPGA-Einführung und Hardwareentwurf mit VHDL
V 1.0.1 / 2009-04-29
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
5 Aufgabenstellung
11
6)
Ermitteln Sie eine weitere Bitfolge-Sequenz, die nicht in der vorherigen Aufgabe enthalten ist und nicht mit „00000“ beginnt. Tragen Sie diese Sequenz in die folgende Tabelle
ein.
Fibonacci-LFSR
Nr.
1
2
3
4
Galois-LFSR
5
5
4
3
2
1
1
2
3
4
5
6
7
8
9
10
Tabelle 3: weitere Bitfolge für 5-Bit Fibonacci- und Galois-LFSRs bei Verwendung des
Polynoms P2
7)
Folgender VHDL-Prozess soll das sequentielle Verhalten des PRNGs beschreiben. Ergänzen Sie den VHDL-Code an den durch Unterstreichung gekennzeichneten Stellen.
-- type
: sequential
-- inputs : clk_i, res_n_i
-- outputs: prng_reg
prng_p: process (___________, ___________)
begin -- process prng_p
if _____________ then
-- asynchronous reset (active low)
prng_reg <= ( others => '___' );
elsif ______________________________________ then
-- prng_reg <= ...
end if;
end process prng_p;
V 1.0.1 / 2009-04-29
-- rising clock edge
FPGA-Einführung und Hardwareentwurf mit VHDL
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
5.2 VHDL-Kodierung, Synthese, FPGA-Programmierung und Erprobung
12
5.2 VHDL-Kodierung, Synthese, FPGA-Programmierung und
Erprobung
8)
Wählen Sie zunächst eine Schieberegisterlänge von 5 Bits.
8.a)
Editieren Sie die Dateien prng.vhd und prng_core.vhd! Versuchen Sie zunächst den
Aufbau des VHDL-Codes zu verstehen!
Hinweis: Über den generischen Parameter reg_width_g können Sie in der entity prng
die Schieberegisterbreite anpassen (Anmerkung: der generische Parameter
reg_width_g in der entity reg_core wird automatisch in der Instanziierung überschrieben).
8.b)
Passen Sie - falls nötig - zunächst in der Datei prng.vhd die Schieberegisterbreite an die
Aufgabenstellung an!
8.c)
Ergänzen Sie die architecture, die das Verhalten von prng.vhd beschreibt! Verwenden
Sie ein Rückkopplungspolynom, so dass ein LFSR mit maximaler Periodizität entsteht
(siehe Aufgabenvorbereitung Punkt 1)! Die Wahl des LFSR-Typs (Fibonacci oder
Galois) wird von der Praktikumsbetreuung für jede Gruppe festgelegt.
8.d)
Stellen Sie sicher, dass in der Top-Level-Architecture der Druckschalter 0 als Takt verwendet wird.
8.e)
Erproben Sie die VHDL-Implementierung auf dem DE2-Board! Überprüfen Sie die
Periodizität des LFSRs.
8.f)
Ändern Sie das Rückkopplungspolynom wie folgt:
- P=x5+x1+1 (vergleiche Versuchsvorbereitung Polynom P2)
- Überprüfen Sie die Periodizität und protokollieren Sie die Bitfolgen bzw. vergleichen
Sie die Sequenz mit Ihren Erwartungswerten aus der Aufgabenvorbereitung!
- Ändern Sie die den Reset-Wert des Schieberegisters, auf eine Bit-Kombination, die
Sie bei diesem Polynom nicht erreichen konnten und die nicht „00000“ ist! Überprüfen
Sie hier die Periodizität und protokollieren Sie die Bitfolgen bzw. vergleichen Sie die
Sequenz mit Ihren Erwartungswerten aus der Aufgabenvorbereitung!
9)
Ändern Sie den VHDL-Code wie folgt:
- Schieberegister mit 15 Flipflops (Rückkopplungspolynom ändern!)
- Verwendung eines auf dem DE2-Board generierten 27MHz Clock
9.a)
Implementieren Sie die Hardware auf das FPGA!
9.b)
Beobachten Sie das Verhalten mit dem Logikanalysator!
9.c)
Triggern Sie auf eine beliebige 15-Bit-Kombination! Welches ist das Vorgänger- und
das Nachfolger-Bitmuster?
Hinweise: Das Pin-Map-File muss die benötigten Pins enthalten!
5.3 Ergänzende Frage zur VHDL-Kodierung im Protokoll
10) Erklären Sie die Verwendung der generischen Parameter in der Entity und bei der Instanziierung (Stichworte Default-Werte und Überschreibung bei...)?
FPGA-Einführung und Hardwareentwurf mit VHDL
V 1.0.1 / 2009-04-29
13
Versuchsanleitung Praktikum Digitaltechnik - Prof. Dr.-Ing. Dirk Rabe
5 Aufgabenstellung
5.4 Hinweise zum Protokoll
Folgende Punkte müssen im Protokoll enthalten sein:
• Dokumentation des Source-Codes
• Antworten zur Frage in Abschnitt 5.3
• Dokumentation des Logikanalysatorbilds
V 1.0.1 / 2009-04-29
FPGA-Einführung und Hardwareentwurf mit VHDL