Elementare kombinatorische Automaten

 Documents

 20 views
of 17
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Universität Bielefeld Technische Fakultät Technische Informatik I Schaltnetze und Schaltwerke I Sommersemester 2001 Tim Köhler…
Share
Transcript
Universität Bielefeld Technische Fakultät Technische Informatik I Schaltnetze und Schaltwerke I Sommersemester 2001 Tim Köhler tkoehler@techfak.uni-bielefeld.de Übersicht  Schaltnetze  Beispiele: Schaltnetze zur Arithmetik  Schaltwerke  Speicher  Taktsteuerung  Beispiele zu Schaltwerken 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 2 Kombinatorischer Automat 1/3  Kombinatorische Automaten sind Schaltnetze die eine Menge von Eingangswertkombinationen (Eingaben) auf eine Menge von Ausgangswertkombinationen (Ausgaben) abbilden  Die Verknüpfungen UND, ODER, NICHT (AND,OR,NOT/٨,٧,¬) heißen elementare kombinatorische Automaten 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 3 Kombinatorischer Automat 2/3 x1 y1 • Kombinatorischer Automat x2 y2 A = (X, Y, Φ) Φ ... ... • Eingabealphabet X=Bn={0,L}n xn ym mit den Buchstaben x = (x1, x2,...,xn) Kombinatorischer Automat • Ausgabealphabet Y=Bm mit den Buchstaben y=(y1,y2,...,ym) x1 • Alphabetabbildung x2 φ y Φ : X→Y, φ : X → B ... xn Φ(x) = y Φ(x1,x2,...,xn)= (y1,y2,...,ym) Einfacher kombinatorischer Automat • Einfacher kombinatorischer Automat A = (X,B,φ) • Elementare kombinatorische Elementare kombinatorische Automaten Automaten AND, OR, NOT 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 4 Kombinatorischer Automat 3/3  Jeder einfache kombinatorische Automat läßt sich aus Elementarautomaten (elementare kombinatorische Automaten) aufbauen (Beweis über DNF)  Jeder kombinatorische Automat läßt sich aus m einfachen kombinatorischen Automaten aufbauen: 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 5 Beispielschaltnetze 1/2  Exklusiv-Oder (Antivalenz) Hier: Eingabealphabet X=B2 Ausgabealphabet Y=B y = φ(x1,x2) = (x1 xor x2) = (x1 ≡ x2) = (x1 x2) = ((x1 ٨ ¬x2) ٧ (¬ x1 ٨ x2)) 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 6 Beispielschaltnetze 2/2  Halbaddierer Schaltung zur Addition zweier einstelliger Dualzahlen (X=B2) mit Ausgabe des zweistelligen Ergebnisses (Summe und Übertrag, Y=B2) x2 x1 y2 y1 y1 = (x1 ٨ ¬x2) ٧ (¬x1 ٨ x2) = x1 xor x2 y2 = (x1 ٨ x2) 0 0 0 0 0 L 0 L L 0 0 L L L L 0 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 7 Sequentielle Automaten  Beim Schaltnetz y zum Zeitpunkt t nur abhängig von x(t) : y(x(t))  Feste Zuordnung zwischen x und zugehörigem y  Beim sequentiellen Automaten (Schaltwerk) y auch abhängig von (allen) früheren Eingaben: y(x(t), x(t - T1), x(t - T2),...) mit T1 < T2 < T3 ...  Schaltwerk muß frühere Eingaben speichern können  Sequentielle Automaten bestehen aus kombinatorischen Automaten und Speichern  Zustand eines Schaltwerks (jeweiliger Inhalt aller Speicher) y(t) = y(x(t),z(t)), z(t) = z(x(t-T), z(t-T)) 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 8 Speicher 1/4  Eingabealphabet = Ausgabealphabet  In dieser Vorlesung X=Y=B (einstellig) : x Speicher y  Ausgabe ist verzögerte Eingabe. Speicher daher auch „Verzögerungsglied“ genannt.  Speicher merkt sich Eingabe x für die Dauer T 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 9 Speicher 2/4 x Speicher y c  Meistens zusätzlicher Takt (Clock) oder Trigger-Eingang c (binär, einstellig)  Eingang c steuert das Speichern von x, bzw. das Ändern von y  Alternativ auch Speicherzeitpunkt aus x ableitbar oder mit internem Takt gesteuert 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 10 Speicher 3/4  Für die Zeit T zwischen zwei Speichervorgängen jeder Wert > 0 möglich  Aber jetzt: Signallaufzeit wird beachtet! → T deutlich größer als Einspeicherungszeit  Meistens T konstant (feste Taktfolge, Taktfrequenz f = 1/T, [Hz]). Dann Taktverhältnis: Verhältnis Dauer „1“ zu Dauer „0“ (“H“:“L“, “L“:“0“). Meistens 1:1 bzw. 50:50  Alle Zustandsänderungen in fest definiertem Zeitraster (als „synchron“ bezeichnet).  „Asynchrone“ Schaltwerke auch möglich (Bezeichnung nicht ganz korrekt: Eigentlich auch synchron) 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 11 Speicher 4/4  Bei konstantem T auch Zeitindex-Schreibweise üblich: y(k)=x(k-1), Zeitindex k: t=k*T t/T = k 0 1 2 ... k k +1 x x(0) x(1) x(2) ... x(k) x(k+1) y y(0) x(0) x(1) ... x(k-1) x(k)  Durch diese Verzögerung sind nun auch Rückkopplungen möglich (Beispiel Takthalbierer). Bei „asynchronen“ Schaltnetzen könnten diese zu Instabilitäten führen (Flimmerschaltungen). 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 12 Vorteile von Schaltwerken  Komplexere Problemstellungen möglich (Beispiel Cola-Automat)  Vermeiden/Herausfiltern von Störungen zwischen den Schaltnetzen  Vermeiden/Herausfiltern von unterschiedlichen Laufzeiten innerhalb der Schaltnetze 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 13 Beispielschaltung 1/2 1. x1 sei am Ende von Netz 1 direkt mit x2 verbunden. Zum Zeitpunkt t=0 springt x1 (und somit auch x2) von H nach L 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 14 Beispielschaltung 2/2 2. Durch den gemeinsamen Takt (und T genügend groß) werden Schalt- und Laufzeiteffekte herausgefiltert 3. Auch wenn jetzt x1 und x2 unterschiedlich schnell schalten, kommt es zu keinen Fehlern mehr. 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 15 Taktsteuerungen  Taktzustandssteuerung: Solange Steuerleitung c in einem Zustand ist, folgt der Ausgang dem Eingang, im anderen Zustand wird Eingabe gespeichert. Meistens realisiert durch konjunktive (selten auch: disjunktive) Verknüpfung von c mit Eingangssignalen  Taktflankensteuerung: Solange Steuerleitung c konstant H oder L ist, wird Ausgabe nicht verändert (=gespeicherter Wert). Wechselt c (zum Beispiel von L nach H) wird aktuelle Eingabe gespeichert und ausgegeben.  Zweizustands-/Zweiflankensteuerung: Aufeinander folgende Speicher werden mit zeitversetzten oder mit unterschiedlichen Flanken des gleichen Taktes gesteuert. 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 16 Ausblick: Nächste Vorlesung  Beispielschaltwerke  Allgemeines zu sequentiellen Automaten  Mealy- und Moore-Automat  Beispielschaltwerk zur Steuerung einer Ampelanlage 16 May, 2016 Vorlesung 5 : Schaltnetze und Schaltwerke 17
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks