Praktikum
Grundlagen von Hardwaresystemen
Sommersemester 2013
Versuch 4: Endliche Automaten
10. Juni 2013
Fachbereich 12: Informatik und MathematikInstitut fur Informatik
Professur fur Eingebettete SystemeProf. Dr. Uwe Brinkschulte
unter Mitarbeit vonMichael BauerDaniel Lohn
Benjamin BettingManuel Penschuck
Johann Wolfgang Goethe-UniversitatFrankfurt am Main
Inhaltsverzeichnis
1 Einleitung 2
2 Grundlagen 32.1 Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Formale Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1.2 Graphische Reprasentation . . . . . . . . . . . . . . . . . . . . . . . . 42.1.3 Implementation in Hardware . . . . . . . . . . . . . . . . . . . . . . . 52.1.4 Implementation in VHDL . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.5 Definition der Ubergangs- und Ausgabefunktion . . . . . . . . . . . . 62.1.6 Endliche Automaten mit Datenpfad . . . . . . . . . . . . . . . . . . . 7
2.2 Hardware Informationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2.1 7-Segment-Anzeige . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2.2 Taster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Anmerkungen und Tipps 10
4 Vorbereitungsaufgaben 11
5 Praktikumsaufgaben 14
1
Kapitel 1
EinleitungDieser Versuch stellt den Hardware-Entwurf mit Hilfe von endlichen Automaten vor. Hierzuwerden zunachst Grundlagen aus den Vorlesungen Diskrete Modellierung und Hardware 2aufgefrischt, und dann konkret auf die Verhaltensbeschreibung angewendet.
Um den Umgang mit dieser zunachst recht abstrakten Modellierungsform zu uben, wirdeine Eieruhr (also ein einstellbarer Timer) implementiert. Strukturell handelt es sich um einenfest programmierten Prozessor, dessen Konzepte sich leicht auf die eines frei programmierba-ren Mikrocontrollers ubertragen lassen.
Um den Umgang mit Automaten zu vereinfachen, werden in VHDL Aufzahlungstypen unddas case-when-Sprachkonstrukt eingefuhrt, sowie die Verwendung von process-Umgebungenvertieft.
Bitte beachten Sie die Vorbereitungsaufgaben. Die Praktikumsaufgaben bauen di-rekt auf diesen auf, und setzen deren Bearbeitung aus Zeitgrunden voraus.
2
Kapitel 2
Grundlagen2.1 Automaten
2.1.1 Formale Definition
Automaten sind eines der Werkzeuge, die sich gleichzeitig fur theoretische Betrachtungensowie praktische Modellierung eignen. Sie werden intensiv in Grundvorlesungen analysiertund sollen daher an dieser Stelle nur auffrischend behandelt werden. Fur weitere Informa-tionen sei etwa auf die Veranstaltungen Diskrete Modellierung, Hardwarearchitekturen undRechensysteme, Hardware 2, sowie Formale Sprachen und Berechenbarkeit (GL-2) verwiesen.
Man unterscheidet zwischen deterministischen und nicht-deterministischen Automaten,wobei wir im Folgenden ausschließlich die deterministischen Vertreter diskutieren wollen. Einsolcher DFA1 besteht aus einer endlichen Menge von Zustanden und zeichnet sich dadurchaus, dass der aktuelle Zustand zu jedem Zeitpunkt exakt definiert ist. Vom ausgewiesenenStartzustand aus beginnend konsumiert ein DFA seine Eingabe zeichenweise, wobei in jedemSchritt der Folgezustand in Abhangigkeit vom gegenwartigen Zustand sowie dem gelesenemZeichen ausgewahlt wird.
Solch eine Maschine lasst sich mittels des 5-Tupels (Σ, Q, q0, δ, F ) formalisieren, wobei dieeinzelnen Symbole wie folgt definiert sind:
Σ Das Eingabealphabet, d.h. ein Automat arbeitet auf Eingaben aus Σ∗.Q Eine nicht-leere Zustandsmenge. Die Eintrage sind symbolischer Natur – es kann
sich um Namen, Zahlen und andere unterscheidbare Reprasentanten handeln.q0 ∈ Q Der Startzustand, der vor dem Lesen des ersten Zeichens angenommen wird.δ(q, w) Die totale Transitionsfunktion δ : Q × Σ → Q. Sie beschreibt das Verhalten
und kann als das Programm eines DFA interpretiert werden.F ⊆ Q Die Menge an akzeptierenden Zustanden. Erreicht der DFA das Ende der Ein-
gabe, wahrend er sich in einem Zustand aus F befindet, wird die Eingabe ak-zeptiert, andernfalls verworfen.
Die Frage der Akzeptanz ist besonders fur theoretische Analysen wichtig, da so gezeigtwerden kann, dass ein DFA genau die Zugehorigkeit eines Wortes zu einer Chomsky-Typ3-Sprache, d.h. einer regularen Sprache, entscheiden kann.
In der technischen Informatik spielen diese Uberlegungen jedoch eine untergeordnete Rolle.Viel mehr werden Automaten hier dazu verwendet, das Verhalten von Maschinen zu model-lieren – etwa die Reaktion eines Kaffeeautomaten auf einen Tastendruck oder das Steuerwerkeines Prozessors, der ein Programm ausfuhrt. Ereignisse in der Umwelt werden dabei alsZeichen der Eingabe an die Maschine kommuniziert – beim Kaffeeautomaten konnte das Ein-gabealphabet etwa als Σ = Nichts-Gedruckt,Kaffee-Taste,Espresso-Taste definiert sein.
Dabei ist anzumerken, dass wir in der Regel eine unendliche Laufzeit beschreiben: Es ware
1Deterministic Finite Automata
3
KAPITEL 2. GRUNDLAGEN 4
wenig sinnvoll, wenn der Kaffeeautomat einen Tastendruck erkennt und danach terminiert.Dies zwingt uns jedoch auch, das Ausgabeschema zu generalisieren, denn bisher trifft derDFA nur dann eine Entscheidung, wenn er terminiert. Man spricht in diesem Fall von einemAkzeptor. Dem gegenuber steht ein Transduktor, der in jedem Schritt auch eine Ausgabeproduziert. Zwei gebrauchliche Ansatze sind die sog. Moore- und Mealy-Automaten.
Beide Typen erweitern das vorher definierte 5-Tupel durch Hinzunahme eines Ausgabeal-phabetes Ω und einer Ausgabefunktion λ. Der Unterschied liegt darin, wann ein neuer Wertberechnet wird:
Die Ausgabe des Moore-Automaten hangt nur vom aktuellen Zustand ab.Die Ausgabefunktion hat daher die Signatur λ : Q → Ω.
Ein Mearly Automat berucksichtigt zusatzlich noch die gegenwartige Eingabe, somitmuss die Signatur auf λ : Q× Σ → Ω erweitert werden.
In diesem Versuch beschranken wir uns auf Moore-Automaten, da diese eine einfachereStruktur und bessere Timing-Eigenschaften aufweisen.
2.1.2 Graphische Reprasentation
In der Literatur werden Moore-Automaten haufig mittels eines gerichteten Graphen beschrie-ben: Die Knoten entsprechen den Zustanden, die Kanten den Zustandsubergangen. Knotenverfugen uber zwei Beschriftungsteile, getrennt durch eine horizontale Linie: Im oberen Be-reich steht der Name des Zustandes, im unteren die Werte der Ausgange. Kanten trageneine boolesche Formel als Beschriftung. Nur wenn diese erfullt ist, wird der durch die Kantebeschriebene Zustandsubergang vorgenommen.
Da wir uns in dieser Aufgabe nur mit deterministischen Automaten beschaftigen, mussfur jede mogliche Eingabe und jeden Zustand genau eine ausgehende Kante existieren, derenFormel erfullt ist. Um die Darstellung zu vereinfachen, definieren wir, dass Eigenkanten nichtexplizit angegeben werden mussen: Sind keine anderen Ubergange verfugbar, verbleibt derAutomat im gegenwartigen Zustand.
Wir mochten uns nun einem konkreten Problem zuwenden. Es gilt das Verhalten eineselektrischen Garagentoroffners zu beschreiben. Das System verfugt uber die folgenden Kom-ponenten:
Ein Motor, der uber die Signal motorAuf und motorZu angesteuert wird. Ein Uberlastkontrolle blockiert: Blockiert etwas das Tor (im schlimmsten Fall z.B. ein
Mensch) steigt der Stromverbauch des Motors. Die Bewegung sollte gestoppt werden,um Beschadigungen des Gerate oder Dritter vorzubeugen.
Ein Raumlicht licht, das ausgeschaltet wird, sobald das Tor geschlossen ist. Zwei Sensoren, welche die Endpositionen des Tors erkennen: sensorAuf und sensorZu. Ein Taster taster, der vom Benutzer zum Betatigen des Tors genutzt werden kann.
Alle Signale sind boolesch. Die drei Ausgange werden nun als Tupel(motorAuf, motorZu, licht) notiert. Mit (1, 0, 1) meinen wir also: Das Tor wird geoffnet unddas Licht ist angeschaltet.
KAPITEL 2. GRUNDLAGEN 5
Zu
(0, 0, 0)
Stop 1
(0, 0, 1)
Offnen
(1, 0, 1)
Schließ.
(0, 1, 1)
Offen
(0, 0, 1)
Stop 2
(0, 0, 1)
taster
tastersensorZu
sensorAuf
taster ∨blockiert
taster
taster
sensorZu
taster ∨ blockiert
Abbildung 2.1: Endlicher Moore-Automat am Bespiel eines Garagentors. Welche Zustandesind redundant und konnen minimiert werden?
2.1.3 Implementation in Hardware
Einer der wichtigsten Schritte nach dem Aufstellen eines Automaten ist dessen Minimierung.So konnen aquivalente Zustande verschmolzen werden und so bei unveranderter Aussage derMaschine auf einfachere Kodierungunge zuruck gegriffen werden. Hierbei handelt es sich umein einfaches Problem mit effizienter algorithmischer Losung (siehe z.B. Vorlesung FormaleSprachen und Berechenbarkeit). Sie wird daher von einigen Synthesewerkzeugen automatischdurchgefuhrt.
Die Implementierung eines Moore-Automaten in Hardware orientiert sich dann i.d.R. ander formalen Definition: Der Automat wird hauptsachlich mittels der Ubergangsfunktion δund der Ausgangsfunktions λ definiert. Konnen wir diese beiden Abbildungen als Schaltnetzoder uber eine Look-Up-Table (z.B. als ROM oder PLA) realisieren, ist das Grobste auchschon gelost.
Da wir bereits von booleschen Eingangen ausgehen, muss nur noch die Zustandsmen-ge Q auf geeignete Weise binar kodiert werden: Gesucht ist also eine injektive Abbildungϕ : Q→ 0, 1∗. Offensichtlich kann die Wahl von ϕ die Komplexitat der Implementierungenvon δ und λ stark beeinflussen. Es lasst sich aber zeigen, dass das Problem der Optimierung furallgemeine Schaltnetze NP-vollstandig ist. Daher werden i.d.R. Approximationsalgorithmenverwendet. Ein bekanntes heuristisches Verfahren ist MUSTANG.
Fur die Implementierung von DFAs auf FPGAs bietet sich haufig die sog. 1-hot-encoding an, bei der die Zustande Q uber dem Raum 0, 1|Q| beschrieben werden und je-der Zustand q ∈ Q einem Vektor der kanonischen orthonormalen Basis (d.h. in der Form(0, . . . , 0, 1, 0, . . . , 0)) zugewiesen wird.
Haben wir ein ϕ gefunden, konnen wir δ und λ in Hardware umsetzen. Wir mussen dahernur noch die einzelnen Bausteine zusammensetzen: Aufgrund von Hazards und Glitches istes nicht sinnvoll, DFAs rein kombinatorisch zu losen. Man verwendet daher einen Takt mitdem die Eingaben gelesen und die Zustandsubergange ausgefuhrt werden. Die vollstandigeImplementierung hat dann die in Abbildung 2.2 dargestellte Form.
KAPITEL 2. GRUNDLAGEN 6
Abbildung 2.2: Schematische Darstellung einer Implementation eines Moore-Automaten.
2.1.4 Implementation in VHDL
Definition der Zustandmenge
Wie bereits diskutiert, stellen wir – mit Ausnahme der Unterscheidbarkeit – formal keine An-forderungen an die Benennung der Zustande. Es konnen also beispielsweise binare Vektorenverwendet werden. Allerdings ist es im Sinne der Lesbarkeit des Codes sowie der automati-schen Optimierung hilfreich, abstrakte Namen zu nutzen. VHDL ermoglicht dies durch dieDefinition eigener Aufzahlungstypen. Diese lassen sich mit dem Schlusselwort type etwa imKopf einer architecture definieren. Die Syntax lautettype type-name is ( [Komma-separierte Liste von Werten] );.
1 type FSM_STATES_TYPE is (FSM_GESCHLOSSEN , FSM_OFFEN , FSM_HALB_GESCHLOSSEN ,
2 FSM_HALB_GEOEFFNET , FSM_SCHLIESSEN , FSM_OEFFNEN );
3 signal fsm_state_i , fsm_next_state_i : FSM_STATES_TYPE;
Auch wenn nicht notig, ist es i.d.R. sinnvoll alle Bezeichner mit einem gemeinsamen Prafixzu versehen und bei Definition mehrerer Typen unterschiedliche Bezeichner zu nutzen. DerTypname darf im Scope noch nicht existieren – eine Neudefinition vorhandener Typen ist alsonicht moglich. Weiter gelten fur Typnamen und Werte die ublichen Regeln fur Bezeichner.
2.1.5 Definition der Ubergangs- und Ausgabefunktion
Die beiden Funktionen lassen sich algorithmisch auf einer hohen Abstraktionsebene beschrei-ben. Bei der Synthese entstehen optimierte Schaltnetze. Da wir die Zustandsmenge abstraktbeschreiben, aber meist keine Kodierung wahlen, kann der Compiler hier (semi-)automatischweitere Verbessungen vornehmen.
Da bei der Definition von FSM meist viele verschiedene Zustande abgefragt werdenmussen, werden lange if-Abfragen unubersichtlich. Daher kann die case-when-Struktur, wiein Listing 2.1 gezeigt, verwendet werden.
Um die Hardware nach dem Einschalten in eine definierte Betriebsart zu versetzen, werdenhaufig explizite Reset Eingange verwendet. Das gezeigte Beispiel nutzt einen synchronen,high-aktiven Reset (Warum handelt es sich um einen synchronen Reset?).
1 -- Synchroner Prozess: Erzeugt ausschließlich die Register, d.h. D-Flip-Flops zum Ubernehmen der uber
2 -- delta berechneten Zustandswerte.
3 proc_sync: process is begin
4 wait until rising_edge(clk);
5 fsm_state_i <= fsm_next_state_i;
6 end process;
KAPITEL 2. GRUNDLAGEN 7
7 -- Kombinatorischer Prozess: Erzeugt ein reines Schaltnetz zum Berechenen der neuen Zustande/Ausgabe
8 proc_comb: process(fsm_state_i , taster_in , blockiert_in , sensorAuf_in , sensorZu_in)
9 is begin
10 -- Transition Function
11 fsm_next_state_i <= fsm_state_i; -- implizite Eigenkante
12 case fsm_state_i is
13 when FSM_GESCHLOSSEN =>
14 if taster_in = ’1’ then
15 fsm_next_state_i <= FSM_OEFFNEN;
16 end if;
17 when FSM_HALB_GESCHLOSSEN => ...
18 when FSM_OFFEN | FSM_HALB_OFFEN => ...
19 when FSM_OEFFNEN => ...
20 when FSM_SCHLIESSEN =>
21 if sensorZu_in = 1 then
22 fsm_next_state <= FSM_ZU;
23 elif (taster_in or blockiert_in) = ’1’ then
24 fsm_next_state_i <= FSM_OFFEN;
25 end if;
26 end case;
2728 if reset_in = ’1’ then
29 fsm_next_state_i <= FSM_HALB_GESCHLOSSEN;
30 end if;
3132 -- Output Function
33 licht <= ’1’; -- Standardwerte fur die Ausgange. Wir mussen
34 motorAuf <= ’0’; -- daher nur die Zustande auffuhren, die diese
35 motorZu <= ’0’; -- uberschreiben.
3637 case fsm_state_i is
38 when FSM_GESCHLOSSEN => licht <= ’0’;
39 when FSM_OEFFNEN => motorAuf <= ’1’;
40 when FSM_SCHLIESSEN => motorZu <= ’1’;
41 when others => null;
42 end case;
43 end process;
Listing 2.1: Partielle Implementierung des in Abbildung 2.1 gezeigten Automaten.
2.1.6 Endliche Automaten mit Datenpfad
Der bisher definierte Moore-Automat unterstutzt keine arithmetischen Operationen: Wirkonnen z.B. nicht einfach einen Zahler implementieren, ohne fur jede Zahl einen Zustandzu benutzen. Durch Hinzunahme eines Datenpfades konnen wir dieses Problem auflosen.
Diese Idee fuhrt etwa zur Trennung eines Prozessors in ein Steuerwerk, den Automaten,und eine Arithmetische Einheit (ALU), den Datenpfad. Bei einem frei progammierbaren Pro-zessor verfugt eine ALU in der Regel uber mindestens zwei Operanden- A und B sowie einenInstruktions-Eingang mit Hilfe dessen die Operation ausgewahlt werden kann, z.B. A + Boder A−B.
Am Design des Automaten andert sich hier nichts: Die Ausgange zum Steuern des Daten-pfades werden einfach zur Ausgabefunktion hinzugefugt. Statusinformationen, die ggf. vomDatenpfad produziert werden, konnen als normale Eingange des Automaten behandelt wer-den.
KAPITEL 2. GRUNDLAGEN 8
2.2 Hardware Informationen
2.2.1 7-Segment-Anzeige
Das FPGA-Board verfugt uber eine vierstellige 7-Segment-Anzeige. Wie in Abbildung 2.3dargestellt, entsteht jede Ziffer durch das Steuern von sieben Segmenten, welche in drei Zeilenund zwei Spalten mit je zwei Elementen angeordnet sind. Fur die gesamte Anzeige mussendemnach 28 Leuchtdioden koordiniert werden.
Um die Anzahl der Steuerleitungen zwischen Anzeige und Controller gering zu halten,kommt eine Ansteuerung zum Einsatz, die es erlaubt, eine Leitung fur mehrere Ziffern zuverwenden. Bei diesem sog. Multiplexing handelt es sich um ein Time-Sharing-Verfahren: Dieinteressante Ressource, in diesem Fall eine Leitung, wird zwischen verschiedenen Elementengeteilt, steht aber zu einem gegebenen Zeitpunkt einer Ziffer exklusiv zur Verfugung:
Ahnlich der chip-select Leitung eines Datenbusses verfugt jede Ziffer uber eine Steuerlei-tung, die die gerade aktive Stelle auswahlt. In der vorliegenden Anzeige werden hierfurdie Anoden der sieben LEDs uber einen gemeinsamen Pin herausgefuhrt.
Die Datenleitungen, welche die Segmente aufleuchten lassen, hangen parallel an allenZiffern.
Um eine mehrstellige Anzeige zu realisieren, wird nun zunachst die uber die sog. commonanode die erste Stelle selektiert und die gewunschten Segmente aktiviert: Die erste Zifferleuchtet, die restlichen bleiben deaktiviert. Nach einer kurzen Zeit (typischerweise 0.1 ms bis1 ms) wiederholt sich der Vorgang fur die nachste Stelle. Bei der letzten angekommen, wirdwieder von vorn begonnen. Da das menschliche Auge nicht in der Lage ist Frequenzen oberhalbvon ca. 1 KHz bewusst aufzulosen2, konnen die Schaltvorgange nicht wahrgenommen werden.
Der oben beschriebene Algorithmus ist in der Entity DISPLAY implementiert und kannzur Bearbeitung der Aufgaben verwendet werden. Als Dateneingange kommen die Vektorendata in, highlight in und dots in zum Einsatz. Mittels des dritten Signals lassen sich dieDezimalpunkte des Displays steuern. Eine 1 im i-ten Bit aktiviert den i-ten Punkt von rechts.
Bei data in handelt es sich um einen 16-bit Vektor, der sich durch eine 4-stellige Hexa-dezimal vollstandig reprasentieren lasst und so auf der Anzeige ausgegeben wird. Das most-significant-digit steht – wie auch in der normalen Zahlendarstellung – links. Der 4-bit breitehighlight in Vektor steuert die Helligkeit jeder Ziffer. Eine 0 lasst die Ziffer dunkler leuch-ten.
Abbildung 2.3: Nexys3 Manual, http://www.digilentinc.com/Data/Products/NEXYS3/Nexys3_rm.pdf, 19.04.2013
2Tipp: Bewegen Sie Ihre Hand/Ihren Kopf schnell vor dem Display hin und her. Was fallt Ihnen auf?
KAPITEL 2. GRUNDLAGEN 9
2.2.2 Taster
Abbildung 2.4: Exemplarische Messung des Signalverlauf beim Loslassen eines Tasters. Wieim oberen Bildbereich aufgefuhrt, entspricht ein horizontaler Abschnitt 50µs, ein vertikaler0.5 V. Das Signal wird in diesem Fall erst nach rund 250 us stabil.
In bisherigen Versuchen verwendeten wir Taster, um Eingange von Schaltnetzen zu steu-ern. Hierbei war das Flankenverhalten der Schalter nur von kleiner Bedeutung und wurdeals einzelne Flanke modelliert. Abbildung 2.4 zeigt den tatsachlichen zeitlichen Verlauf ei-nes Schaltvorgangs: Statt einer exakt definierten Schaltflanke, offnet und schließt der Tastermehrfach, bevor ein stabiler Zustand erreicht wird. Ursache hierfur sind Federungen der Kon-takte, die beim Betatigen zu elastischen Stoßen und somit zu stark gedampften Schwingungenfuhren.
Anders als bei einem einfachen Schaltnetz, kann dieses sog. Prellen bei sequentiellenSchaltungen zu ungewunschten Effekten fuhren. So kann etwa ein einzelner Tastendruck alsmehrfache Betatigung interpretiert werden. Das Prellen hat daher Auswirkungen, die mitdenen eines Harzards oder Glitches vergleichbar sind.
Um dem entgegenzuwirken, gibt es diverse Ansatze – z.B. die Verwendung eines spe-ziell konstruierten Wechslers, eines elektronischen Tiefpasses (mittels RC-Glied) oder einerSoftware-Losung, die einen Zustandswechsel erst nach einer sog. Entprelldauer akzeptiert.
Wir orientieren uns an der Software-Losung und fordern, dass ein Signal fur einige Mil-lisekunden stabil ist. Im Vergleich zu den Storungen in den aufgezeichneten Signalverlaufenist das lange, fur den Benutzer erscheint es jedoch immer noch als sofortige Reaktion. Eineentsprechende Entprell-Einheit (engl. debouncer) wird wir im Zuge dieses Versuchs komplet-tiert.
Kapitel 3
Anmerkungen und Tipps1. Um das Testen auf der Hardware zu vereinfachen, kann der clk10hz in Takt um den
Faktor 10 beschleunigt werden. Schieben Sie hierfur den Schalter SW7 (links) auf dieobere Position. Hierdurch sollte eine Minute des Timers in 6 s ablaufen.
2. Zum Entwurf des Timers gibt es diverse Moglichkeiten. Ein Ansatz, der bisher nur dieAusgange (disp highlight out, alu instruction out) berucksichtig, sieht wie folgtaus (es fehlen noch viele Zustande und Transitionen):
IDLE
”1111”,ALU NONE
SEL MIN
”1000”,ALU NONE
INC MIN
”1000”,ALU SINGLE
INC MIN
DEC MIN
”1000”,ALU SINGLE
DEC MIN
START
”1111”,ALU STORE
WAIT 10HZ
”1111”,ALU NONE
...
...
keySet in
keyUp in ∨keyDown in ∨keyLeft in ∨keyRight in
keyUp in
keyDown in
keyRight in
keyLeft in
clk10hz in
10
Kapitel 4
VorbereitungsaufgabenAufgabe 1. Machen Sie sich mit der case-when Sprachstruktur in VHDL vertraut. Wie lautet die
Syntax? Welche Regeln zur Wertebereichsuberdeckung mussen beachtet werden? Wielassen sich mehrere Falle in einer Abfrage kombinieren? In welcher Umgebung darfdieser Ausdruck verwendet werden?
Aufgabe 2. Wie lassen sich in VHDL Aufzahlungstypen erstellen? Wie definiert man ein Signalampel, welches die Werte Rot, RotGelb, Gelb, Gruen annehmen kann? Wie lasst sich mit-tels case-when-Konstrukt das Signal dekodieren, um etwa die Ausgange rot o, gelb o
und gruen o der aktuellen Belegung von ampel entsprechend zu steuern.
Aufgabe 3. In Abschnitt 2.1.3 wird die Kodierung der Zustandsmenge angerissen, und angefuhrt,dass die 1-hot-encoding haufig eine gute Heuristik fur die FPGA-Synthese darstellt. Wes-halb verwendet man diesen hoch-dimensionalen Ansatz, der Ω(|Q|) Flip-Flops benotigt,wenn man mittels binaren Zahlens auch mit Ω(log2 |Q|) Speicherzellen auskommenkonnte? Tipp: Beachten Sie die Struktur von Logik-Zellen in einem FPGA (insb. dieAnzahl der Eingange und der Position von Flip-Flops).
Aufgabe 4. Rekapitulieren Sie die process-Umgebung zum Hardware-Entwurf auf algorithmischerEbene. Welche Bedeutung hat die Sensitivitatsliste? Geben Sie je ein minimales Code-Beispiel fur eine rein kombinatorische Schaltung (etwa ein And-Gatter) mit Sensiti-vitatsliste. Geben Sie zwei weitere Beispiele fur eine sequentielle Schaltung (z.B. einD-Flip-Flop) je mit und ohne Sensitivitatsliste an.
Aufgabe 5. Vergleichen Sie die folgenden Prozesse (einziger Unterschied in Zeile 7). Beide beschrei-ben ein unterschiedliches Verhalten, das jedoch fur Schaltungen mit entsprechendendon’t care Werten kompatibel sein kann. Welche der beiden Schaltungen benotigt beioptimaler Synthese mehr Hardware? Warum? Es kann hilfreich sein, die Schaltungenauf Gatterebene zu skizzieren.
1 proc1: process(input) is begin
2 if input = "00" then output <= ’0’;
3 elsif input = "01" then output <= ’1’; end if;
4 end process;
56 proc2: process(input) is begin
7 output <= ’1’;
8 if input = "00" then output <= ’0’;
9 elsif input = "01" then output <= ’1’; end if;
10 end process;
Aufgabe 6. In Listing 2.1 werden zunachst Standardwerte definiert, die dann abhangig vom ak-tuellen Zustand ggf. uberschrieben werden. Verursacht dieser Ansatz im Vergleich zur
11
KAPITEL 4. VORBEREITUNGSAUFGABEN 12
einmaligen Zuweisung des Wertes (etwa durch mehrere ifs) zusatzliche Glitches? Be-grunden Sie Ihre Antwort.Tipp: Bedenken Sie Ihre Antwort fur die vorherige Aufgabe.
Aufgabe 7. Wir mochten einen einfachen Count-Down-Timer, im Sinne einer Eieruhr implementie-ren. Hierbei stellt der Benutzer eine Zeitspanne in Minuten und Sekunden ein. Nach demStarten beginnt der Count-Down und halt, sobald 0:00.0 erreicht wurde. Die Steue-rung soll uber das Tasten-Kreuz des FPGA-Boards implementiert werden. Im Folgendenbezeichnen wir die Tasten mittels oben, unten, links, rechts, set (mittlere Taste).
Die Uhr soll folgendes Verhalten haben:
Der aktuelle Zahlerstand wird zu jedem Zeitpunkt auf der 7-Segment-Anzeige imFormat m.ss.z dargestellt, wobei m den Minuten, s den Sekunden und z denZehnteln-Sekunden entspricht. Die Punkte sollen angezeigt werden.
Nach dem Einschalten (bzw. nach einem Reset) wird ein Ruhezustand eingenom-men. Das voreingestellte Zeitintervall betragt 1 min. Durch Drucken von set lasstsich der Wert andern, jede andere Taste startet den Count-Down.
Wahrend der Count-Down lauft, soll die verbleibende Zeit dem Benutzer im o.g.Format angezeigt werden. Durch Drucken einer beliebigen Taste soll der Zahler aufden Startwert zuruck gesetzt und der Ruhezustand eingenommen werden.
Nach Ablauf des Zahlers bleibt dieser mit der Anzeige 0.00.0 stehen. Zusatzlichsollen die Leds auf dem Board dauerhaft bis zum nachsten Tastendruck eingeschal-tet bleiben. Die Tasten werden wie im Ruhezustand behandelt.
Das Einstellen eines neuen Wertes geschieht ziffernweise. Die aktuelle Auswahlwird hell dargestellt, alle anderen abgedunkelt. Mittels der Tasten oben und unten
wird die aktuelle Ziffer erhoht bzw. verringert. Bei einem Uberlauf wird die Zifferauf 0, bei einem Unterlauf auf die großt mogliche Zahl gesetzt. Dies hat keineAuswirkungen auf benachbarte Werte.
Mittels der Taste rechts werden die Ziffern in der Reihenfolge Minute, Sekunden-Zehner, Sekunden-Einer durchgegangen. Die Zehntel-Sekunden konnen nicht bear-beitet werden, und werden auf 0 gesetzt. Ein weiteres Drucken startet den Count-Down. Die Taste links soll genutzt werden, um wieder eine Ziffer nach links zulaufen; sind gerade Minuten selektiert, wird die Taste ignoriert.
Dies soll uber einen Moore-Automaten implementiert werden. Dieser ist in der EntitatCONTROLLER gekapselt. Sie wird von TIMER SOC instantiiert und mit den anderen Modu-len verbunden. Alle arithmentischen Operationen auf dem Timer-Wert sind bereits imModul ALU implementiert und mussen nur durch den Automaten gesteuert werden. DieAusgabe des Datenpfades ist weiterhin bereits mit dem Display verbunden. Sie mussendaher nur die folgende IO/s verwenden:
Der Eingang sysclk in arbeitet mit 100 MHz und soll die FSM takten.
Der Eingang clk10hz in kann fur den Count-Down benutzt werden. Er liefert proSekunde zehn sehr kurze Pulse, die jeweils fur nur einen Systemtakt 1 sind. Diesesollten also zu einem Dekrementieren des Timers fuhren.
KAPITEL 4. VORBEREITUNGSAUFGABEN 13
Der Eingang reset in ist nach dem Einschalten des FPGAs aktiv (= 1) und sollden zuvor definierten Initialzustand herstellen.
Die Eingange keyUp in, keyDown in, keyLeft in, keyRight in, keySet in sindmit den entprellten Tasten verbunden. Beim Drucken einer Taste geht das entspre-chende Signal fur einen Takt auf 1. Erst nach einem erneuten Drucken wird eineweitere 1 erzeugt. Es ist realisitsch davon auszugehen, dass gleichzeitig nur eineTaste gedruckt wird.
Der Ausgang disp highlight out(3 downto 0) ist mit der 7-Segment-Anzeigeverbunden. Eine 1 bewirkt, dass die entsprechende Ziffer hell leuchtet, eine 0 fuhrtzur Abdunkelung. Standardmaßig sollten alle Ziffern hell leuchten. Details sieheKapitel 2.2.1.
Der high-aktive Ausgang alarm out, steuert die verbleibenden Leds des Boardsan. Dieser soll beim Ablauf des Count-Downs aktiviert werden.
Der Eingang timer is zero in wird 1, wenn auf dem Display 0.00.0 erscheint.Der Count-Down sollte in diesem Fall beendet werden.
Der Ausgang alu instruction out steuert den Datenpfad. Es werden folgendeBefehle unterstutzt:
Befehl Beschreibung
ALU NONE Keine Aktion
ALU STORE Speichert den aktuellen Zahlerwert. Dieser kannmit dem nachsten Befehl wieder hergestellt werden.Nutzlich nach dem Ablauf eines Count Downs wiedervon vorn zu starten.
ALU LOAD Stellt den gespeichert Wert wieder her (s.o.).
ALU DEC TIMER Verringert den Zahlerwert um 0.1 s. Aus der Anzeige1.00.0 wird so 0.59.9.
ALU SINGLE INC MIN Erhoht die Minutenstelle um 1. Ist der Wert gerade9, so wird er auf 0 gesetzt. Andere Ziffern werdennicht verandert. Nutzlich um das Einstellen des Timer-Wertes zu implementieren.
ALU SINGLE DEC MIN Verringert die Minutenstelle um 1. Ist der Wert gera-de 0, so wird er auf 9 gesetzt. Andere Ziffern werdennicht verandert. Nutzlich um das Einstellen des Timer-Wertes zu implementieren.
ALU SINGLE INC SEC10 Siehe ALU SINGLE INC MIN, nur auf die Sekunden-Zehner.
ALU SINGLE DEC SEC10 Siehe ALU SINGLE DEC MIN, nur auf die Sekunden-Zehner.
ALU SINGLE INC SEC Siehe ALU SINGLE INC MIN, nur auf die Sekunden-Einer.
ALU SINGLE DEC SEC Siehe ALU SINGLE DEC MIN, nur auf die Sekunden-Einer.
Entwerfen Sie graphisch einen Moore-Automaten, der das o.g. Verhalten implemen-tiert. Dieser wird wahrend des Praktikums implementiert werden. Ein moglicher Ansatzist in den Tipps beschrieben.
Kapitel 5
PraktikumsaufgabenAufgabe 0. Laden Sie den der Aufgabe beliegenden Code herunter, erstellen Sie ein neues Projekt
und importieren Sie alle VHDL-Files. Als Top-Entitat soll TIMER SOC ausgewahlt sein.
Aufgabe 1. Wie in Kapitel 2.2.2 beschrieben, ist es empfehlenswert von Tastern erhaltenen Werte zuentprellen. Wir erstellen dafur eine Entitat debouncer, die einen Tiefpass implementiertund an dem Ausgang button out den geglatteten Zustand des Tasters ausgibt. Daruberhinaus erkennt das Modul noch den Zeitpunkt zu dem der Taster gedruckt/gelost wird.Obwohl diese Erkennung mittels eines Flip-Flop und eines kleinen Schaltnetzes kombi-natorisch leicht zu beschreiben ist, mochten wir die Zustande einer Taste systematischmit dem nachfolgend dargestellten Automaten nachbilden:
Released
(0, 0, 0)
Down
(1, 1, 0)
Up
(0, 0, 1)
Pressed
(1, 0, 0)
stable
high i=1
stable
lowi=1
Abbildung 5.1: Moore-Automat zur Tastendruck-Erkennung. Ausgabetupel hat dieForm (button out, pressed out, released out).
Vervollstandigen Sie die Entitat debouncer, in dem Sie den dargestellten Automatenimplementieren. Definieren Sie dazu – wie im Theorieteil beschrieben – zunachst einenDatentyp zur Darstellung der Zustandsmenge. Beschreiben Sie dann mittels eines Pro-zesses ein Schaltnetz, welches die Ubergangs- und Ausgabefunktion umsetzt. Legen Sieabschließend einen zu sysclk in synchronen Prozess an, welcher dem in Abbildung 2.2dargestellten Register entspricht.
Eine Logik, welche die letzten n Zustande des Tasters uberwacht, ist bereits angelegt. Sieerzeugt zwei Ausgange stable low i und stable high i. Ersterer wird auf 1 gesetzt,wenn zuruckliegende Messungen durchgangig high ergaben, umgekehrt wird der zweiteAusgang 1, wenn der Eingang durchgangig low war. Beide Signale schließen sich aus,wobei es durchaus moglich ist, dass beide 0 sind.
14
KAPITEL 5. PRAKTIKUMSAUFGABEN 15
Aufgabe 2. Implementieren Sie einen Testbench, der die Entprelleinheit uberpruft. Sie konnen dafurdie Vorlage TB DEBOUNCER nutzen. Diese enthalt bereits die Instantiierung der Einheitund generiert zwei Takte (Sytemtakt: 50 KHz, Abtasttakt: 5 KHz), ein Reset-Signal,sowie einen idealen Tastendruck. Der Testbench weist die Entprelleinheit an, die letz-ten zehn Abtastungen zu uberwachen. Passen Sie die Zuweisungen fur button in an,um mindestens einen realistischen Tastendruck zu simulieren, der an beiden FlankenStorungen von einigen 100 us enthalt. Beachten Sie bei der Simulation die Zeitskalen!
Aufgabe 3. Implementieren Sie den in den Vorbereitungsaufgaben entworfenen Automaten. NutzenSie hierzu die Entitat CONTROLLER und verandern Sie deren Port nicht.
Aufgabe 4. Implementieren Sie einen Testbench, der das Einstellen einer neuen Zeit, sowie einenCount-Down testet. Nutzen Sie hierzu die Entitat TB CONTROLLER. Dieses Templateenthalt bereits die zwei Takte. Da die Simulation der Schaltung uber Sekunden sehraufwendig ist, wurde der clk10hz in Takt auf 10 MHz beschleunigt (er lauft also umden Faktor 106 schneller). Ein Count-Down von 1 min benotigt daher in der Simulationnur 60 ns.
Aufgabe 5. Synthetisieren Sie den Entwurf und testen Sie ihn auf dem FPGA-Board. Beachten Siehierbei, dass der Schalter SW7 (links) genutzt werden kann, um den clk10hz in Taktum den Faktor 10 zu beschleunigen (obere Position).
