--- title: "Kapitel 05 - Synchrone Schaltwerke" source: "ti-5-deck.html" generated-by: uni-vault/sync.py --- # Kapitel 05 - Synchrone Schaltwerke ## Title Einführung in die Technische Informatik Prof. Jian-Jia Chen | Dr.-Ing. Christian Hakert | Dr. rer. nat. Marcus Völker RWTH Aachen University ## Kapitel 5: Synchrone Schaltwerke ## Abschnitt 5.1 Einleitung - Sequentielle Schaltungen - Flimmerschaltung - Kreise als Speicher ## Sequentielle Schaltungen **Beobachtung** - Das ist **kein** Schaltnetz - Es ist eine “baubare” Schaltung - **Was passiert in dieser Schaltung?** ## Sequentielle Schaltungen **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** Offensichtlich stabil. \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 ## Eine konkrete sequentielle Schaltung **Was passiert in dieser Schaltung?** \(x\) \(y\) \(x \lor \overline{y}\) 0 0 1 0 1 0 1 0 1 1 1 1 **Beobachtung:** Und immer weiter so … **Natürlich:** In der Realität viel schneller Darum heißt die Schaltung **Flimmerschaltung** ## Bewertung des Effekts **Unkontrolliertes** Flimmern ist sehr **unschön.** **Also Kreise konsequent verbieten?** **Wozu können Kreise gut sein?** - **Beobachtung:** Ausgänge werden zu Eingaben … - **Etwas anders:** Man kann schon Berechnetes noch einmal “sehen”. - **Einsicht:** Das realisiert so etwas wie **Speicher** ## Abschnitt 5.2 Bistabile Kippstufe (engl. Latch) - NAND-Kippstufe - Abhängigkeit von den Schaltzeiten - 1-Bit-Speicher ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 0 1 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 0 1 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 0 1 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 \(\overline{Q_t}\) 1 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 \(\overline{Q_t}\) 1 0 1 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 \(\overline{Q_t}\) 1 0 1 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 \(\overline{Q_t}\) 1 0 1 1 1 \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 \(\overline{Q_t}\) 1 0 1 1 1 \(\overline{Q_t}\) \(Q_t\) \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 \(\overline{Q_t}\) 1 0 1 1 1 \(\overline{Q_t}\) \(Q_t\) \(\overline{Q_t}\) \(Q_t\) \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Ein zweites Beispiel \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 \(\overline{P_t}\) 1 0 1 0 0 1 0 1 1 1 \(P_t\) \(\overline{P_t}\) \(P_t\) \(\overline{P_t}\) \(\Delta\) : Zeit, in der **beide** Gatter **genau einmal** schalten ## Bi-stabile NAND-Kippstufe **Anmerkung:** Heißt auch **Latch** **Positiv:** Kippt, flimmert nicht **Negativ:** Verhalten hängt von Schaltzeiten der beiden Gatter ab **Genauer beobachtet:** Verhalten hängt **manchmal** von Schaltzeiten der beiden Gatter ab ## Analyse der bi-stabilen NAND-Kippstufe **1. Fall:** oberes NAND-Gatter schneller \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 \(\overline{Q_t}\) 1 0 1 1 1 \(\overline{Q_t}\) \(Q_t\) \(\overline{Q_t}\) \(Q_t\) \[P_{t+2\Delta} = \overline{RQ_{t+\Delta}}\] \[\begin{aligned} &= \overline{R} \lor \overline{Q_{t+\Delta}} = \overline{R} \lor \overline{\overline{SP_{t+\Delta}}} = \overline{R} \lor SP_{t+\Delta}\\ &= \overline{R} \lor S\overline{RQ_t} = \overline{R} \lor S(\overline{R} \lor \overline{Q_t}) = \overline{R} \lor S\overline{R} \lor S\overline{Q_t}\\ &= \overline{R} \lor S\overline{Q_t} \end{aligned}\] ## Analyse der bi-stabilen NAND-Kippstufe **2. Fall:** unteres NAND-Gatter schneller \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 \(\overline{P_t}\) 1 0 1 0 0 1 0 1 1 1 \(P_t\) \(\overline{P_t}\) \(P_t\) \(\overline{P_t}\) \[P_{t+2\Delta} = \overline{RQ_{t+2\Delta}}\] \[\begin{aligned} &= \overline{R} \lor \overline{Q_{t+2\Delta}} = \overline{R} \lor \overline{\overline{SP_{t+\Delta}}} = \overline{R} \lor SP_{t+\Delta}\\ &= \overline{R} \lor S\overline{RQ_{t+\Delta}} = \overline{R} \lor S(\overline{R} \lor \overline{Q_{t+\Delta}}) = \overline{R} \lor S\overline{R} \lor S\overline{Q_{t+\Delta}}\\ &= \overline{R} \lor S\overline{Q_{t+\Delta}} = \overline{R} \lor S\overline{\overline{SP_t}} = \overline{R} \lor SSP_t = \overline{R} \lor SP_t \end{aligned}\] ## Fazit zum Ausgang P der bi-stabilen NAND-Kippstufe **1. Fall:** Oberes NAND-Gatter schneller \[P_{t+2\Delta} = \overline{R} \lor S\overline{Q_t}\] **2. Fall:** Unteres NAND-Gatter schneller \[P_{t+2\Delta} = \overline{R} \lor SP_t\] **Beobachtung:** Wenn \(P_t = \overline{Q_t}\) , ist das Verhalten an \(P_t\) **stabil**, also von den Schaltzeiten der Gatter unabhängig. **Was ist mit dem anderen Ausgang?** ## Analyse der bi-stabilen NAND-Kippstufe **1. Fall:** oberes NAND-Gatter schneller \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 \(\overline{Q_t}\) 1 0 1 1 1 \(\overline{Q_t}\) \(Q_t\) \(\overline{Q_t}\) \(Q_t\) \[\begin{aligned} Q_{t+2\Delta} &= \overline{SP_{t+2\Delta}} = \overline{S} \lor \overline{P_{t+2\Delta}} = \overline{S} \lor \overline{\overline{RQ_{t+\Delta}}} = \overline{S} \lor RQ_{t+\Delta}\\ &= \overline{S} \lor R\overline{SP_{t+\Delta}} = \overline{S} \lor R(\overline{S} \lor \overline{P_{t+\Delta}}) = \overline{S} \lor R\overline{S} \lor R\overline{P_{t+\Delta}}\\ &= \overline{S} \lor R\overline{P_{t+\Delta}} = \overline{S} \lor R\overline{RQ_t} = \overline{S} \lor RRQ_t = \overline{S} \lor RQ_t \end{aligned}\] ## Analyse der bi-stabilen NAND-Kippstufe **2. Fall:** unteres NAND-Gatter schneller \(R_t\) \(S_t\) \(P_{t+\Delta}\) \(Q_{t+\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 \(\overline{P_t}\) 1 0 1 0 0 1 0 1 1 1 \(P_t\) \(\overline{P_t}\) \(P_t\) \(\overline{P_t}\) \[\begin{aligned} Q_{t+2\Delta} &= \overline{SP_{t+\Delta}} = \overline{S} \lor \overline{P_{t+\Delta}} = \overline{S} \lor \overline{\overline{RQ_{t+\Delta}}} = \overline{S} \lor RQ_{t+\Delta}\\ &= \overline{S} \lor R\overline{SP_t} = \overline{S} \lor R(\overline{S} \lor \overline{P_t}) = \overline{S} \lor R\overline{S} \lor R\overline{P_t}\\ &= \overline{S} \lor R\overline{P_t} \end{aligned}\] ## Fazit der Analyse der bi-stabilen NAND-Kippstufe **1. Fall:** Oberes NAND-Gatter schneller \[P_{t+2\Delta} = \overline{R} \lor S\overline{Q_t} \qquad Q_{t+2\Delta} = S \lor RQ_t\] **2. Fall:** Unteres NAND-Gatter schneller \[P_{t+2\Delta} = \overline{R} \lor SP_t \qquad Q_{t+2\Delta} = S \lor R\overline{P_t}\] **Also:** Wenn \(Q_t = \overline{P_t}\) , so ist das Verhalten **stabil**, von den Schaltzeiten der Gatter unabhängig. **Also:** **Forderung** \(P_t \ne Q_t\) ## Wertetabelle bi-stabile NAND-Kippstufe oberes Gatter schneller unteres Gatter schneller \(R_t\) \(S_t\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 \(\overline{Q_t}\) \(Q_t\) \(P_t\) \(\overline{P_t}\) ## Wertetabelle bi-stabile NAND-Kippstufe oberes Gatter schneller unteres Gatter schneller \(R_t\) \(S_t\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) **0** **0** **1** **1** **1** **1** 0 1 1 0 1 0 1 0 0 1 0 1 1 1 \(\overline{Q_t}\) \(Q_t\) \(P_t\) \(\overline{P_t}\) **Beobachtung:** Wir müssen nur \(R = S = 0\) ausschließen, damit die Forderung \(P_t \ne Q_t\) gilt. ## Wertetabelle bi-stabile NAND-Kippstufe oberes Gatter schneller unteres Gatter schneller \(R_t\) \(S_t\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) **0** **0** **1** **1** **1** **1** 0 1 1 0 1 0 1 0 0 1 0 1 1 1 \(\overline{Q_t}\) \(Q_t\) \(P_t\) \(\overline{P_t}\) **Beobachtung:** Wir müssen nur \(R = S = 0\) ausschließen. \(R_t\) \(S_t\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 1 1 0 1 0 0 1 1 1 \(P_t\) \(\overline{P_t}\) - \((R, S) = (0, 1)\) setzt \(P = 1\) - \((R, S) = (1, 0)\) setzt \(P = 0\) - \((R, S) = (1, 1)\) lässt \(P\) unverändert **Fazit:** Bi-stabile NAND-Kippstufe realisiert 1-Bit-Speicher! ## Erstes Fazit zu sequentiellen Schaltungen **Bi-stabile NAND-Kippstufe realisiert 1-Bit-Speicher.** **Beobachtung** - Kreise in “Schaltnetzen” manchmal sinnvoll - Neue Funktionalität - Analyse schwierig **Wunsch:** Strukturierter Entwurf ## Abschnitt 5.3 Automaten - Mealy-Automaten - Moore-Automaten - Äquivalenz von Automaten ## Automaten **Wunsch:** Formales **Modell** eines Automaten **Was ist überhaupt ein Automat?** **Beispiele** - Getränke-Automat - Einfache Ampelsteuerung - Steuerung einer Waschmaschine **Gegenbeispiele** - Geldspielautomat (wegen der Zufalls-Komponente) - Computer (zu komplex) - Mensch (für uns nicht formal beschreibbar) ## Automatenmodell **Grobbeschreibung** - Verarbeitet eine Eingabe - Erzeugt eine Ausgabe - Ist in einem Zustand - Arbeitet in Takten - Arbeitet deterministisch (exakt vorhersagbar) **Jetzt:** Exakte, formale Beschreibung ## Definition Mealy-Automat Ein **Mealy-Automat** \(M = (Q, q_0, \Sigma, \Delta, \delta, \lambda)\) ist definiert durch: - Endliche **Zustandsmenge** \(Q\) - **Startzustand** \(q_0 \in Q\) - Endliches **Eingabealphabet** \(\Sigma\) - Endliches **Ausgabealphabet** \(\Delta\) - **Zustandsüberführungsfunktion** \(\delta: Q \times \Sigma \rightarrow Q\) - **Ausgabefunktion** \(\lambda: Q \times \Sigma \rightarrow \Delta \cup \{\epsilon\}\) In einem **Takt** mit aktuellem Zustand \(q\) und Eingabesymbol \(w\) - **schreibt** der Automat \(\lambda(q, w)\) , - **wechselt** der Automat in den Zustand \(\delta(q, w)\) . ## Beispiel Mealy-Automat aktueller Zustand \(q \in Q\) Eingabe \(w \in \Sigma\) Folgezustand \(\delta(q, w)\) Ausgabe \(\lambda(q, w)\) \(q_0\) 0 \(q_1\) \(a\) \(q_0\) 1 \(q_2\) \(c\) \(q_1\) 0 \(q_0\) \(c\) \(q_1\) 1 \(q_2\) \(b\) \(q_2\) 0 \(q_1\) \(a\) \(q_2\) 1 \(q_0\) \(b\) \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;1\;\;0\;\;0\) **Ausgabe:** ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;1\;\;0\;\;0\) **Ausgabe:** ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(\underline{\mathbf{0}}\;\;1\;\;0\;\;0\) **Ausgabe:** ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(\underline{\mathbf{0}}\;\;1\;\;0\;\;0\) **Ausgabe:** ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;\underline{\mathbf{1}}\;\;0\;\;0\) **Ausgabe:** a ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;\underline{\mathbf{1}}\;\;0\;\;0\) **Ausgabe:** a b ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;1\;\;\underline{\mathbf{0}}\;\;0\) **Ausgabe:** a b ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;1\;\;\underline{\mathbf{0}}\;\;0\) **Ausgabe:** a b a ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;1\;\;0\;\;\underline{\mathbf{0}}\) **Ausgabe:** a b a ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;1\;\;0\;\;\underline{\mathbf{0}}\) **Ausgabe:** a b a ## Beispiel Mealy-Automat \(Q = \{q_0, q_1, q_2\}\) \(\Sigma = \{0, 1\}\) \(\Delta = \{a, b, c\}\) **Eingabe:** \(0\;\;1\;\;0\;\;\underline{\mathbf{0}}\) **Ausgabe:** a b a c ## Äquivalenz von Automaten **Definition:** Zwei Mealy-Automaten heißen **äquivalent**, wenn sie für jede Eingabe \(w \in \Sigma^*\) die gleiche Ausgabe \(a \in \Delta^*\) erzeugen. **Beobachtung** - Äquivalente Automaten können unterschiedlich groß sein - Man wünscht sich möglichst kleine Automaten - Komplexer Problemkreis, … umfasst auch effiziente Minimierung von Automaten - … näher i.d. Theoretischen Informatik (GTI) **Hier:** Noch ein anderes (ähnliches!) Automaten-Modell ## Definition Moore-Automat Ein **Moore-Automat** \(M = (Q, q_0, \Sigma, \Delta, \delta, \lambda)\) ist definiert durch: - Endliche **Zustandsmenge** \(Q\) - **Startzustand** \(q_0 \in Q\) - Endliches **Eingabealphabet** \(\Sigma\) - Endliches **Ausgabealphabet** \(\Delta\) - **Zustandsüberführungsfunktion** \(\delta: Q \times \Sigma \rightarrow Q\) - **Ausgabefunktion** \(\lambda: Q \rightarrow \Delta \cup \{\epsilon\}\) (Unterschied zum Mealy-Automat: \(\lambda: Q \times \Sigma \rightarrow \Delta \cup \{\epsilon\}\) ) In einem **Takt** mit aktuellem Zustand \(q\) und Eingabesymbol \(w\) - **schreibt** der Automat \(\lambda(\delta(q, w))\) , - **wechselt** der Automat in den Zustand \(\delta(q, w)\) . ## Mealy- und Moore-Automaten **Beobachtung:** Zu jedem Moore-Automaten gibt es einen äquivalenten Mealy-Automaten. **Denn:** Zu Moore-Automat \(A = (Q, q_0, \Sigma, \Delta, \delta, \lambda)\) - ist Mealy-Automat \(A' = (Q, q_0, \Sigma, \Delta, \delta, \lambda')\) - mit \(\lambda'(q, w) := \lambda(\delta(q, w))\) **Offensichtlich äquivalent** ## Mealy- und Moore-Automaten **Beobachtung:** Zu jedem Mealy-Automaten gibt es einen äquivalenten Moore-Automaten. **Denn:** Zu Mealy-Automat \(A = (Q, q_0, \Sigma, \Delta, \delta, \lambda)\) - ist Moore-Automat \(A' = (Q', q_0', \Sigma, \Delta, \delta', \lambda')\) - mit \(Q' := Q \times (\Delta \cup \{\epsilon\})\) , \(q_0' := (q_0, \epsilon)\) , - \((q, v)\) ist ein Zustand in der Menge \(Q'\) - \(\lambda(\delta(q', w)) = \lambda'((q, v)) := v\) - \(\delta'(q', w) = \delta'((q, v), w) := (\delta(q, w), \lambda(q, w))\) **Äquivalent** ## Einfacher Beispiel-Automat **Aufgabe:** Einfache „Datenglättung“: Filtere isolierte Bits aus Datenstrom aus. **Es gilt:** \(\Sigma := \{0, 1\}, \Delta := \{0, 1\}\) **Mealy-Automat** mit \(Q := \{0, 1, ?\}, q_0 := 0\) ## Äquivalente Automaten „Bit-Filter“ **Mealy-Automat** **Moore-Automat** ## Abschnitt 5.4 Synchrone Schaltwerke - Getaktete Flip-Flops: RS, D, JK, T - Ansteuertabellen - Huffman-Schaltwerk-Modell ## Automaten & Schaltungen: Synchrone Schaltwerke **Erinnerung:** bi-stabile NAND-Kippstufe \(R_t\) \(S_t\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 1 1 0 1 0 0 1 1 1 \(P_t\) \(\overline{P_t}\) \(Q = \{0, 1\}, q_0 = 0\) \(\Sigma = \{01, 10, 11\}\) \(\Delta = \{0, 1\}\) \(R\) : Reset, \(S\) : Set ## Vergleich Automat und NAND-Kippstufe **Nicht getaktet** \(R_t\) \(S_t\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 1 1 0 1 0 0 1 1 1 \(P_t\) \(\overline{P_t}\) **Getaktet** \(Q = \{0, 1\}, q_0 = 0\) \(\Sigma = \{01, 10, 11\}\) \(\Delta = \{0, 1\}\) \(R\) : Reset, \(S\) : Set ## Synchrone Schaltwerke **Ab jetzt:** Getaktete Schaltwerke **Also:** Führe **Taktsignal \(T\) ** ein **Verschiedene technische Möglichkeiten** - **Pegelsteuerung:** Aktiv, wenn 1 anliegt - **Positive Flankensteuerung:** Aktiv, wenn Wechsel von 0 nach 1 - **Negative Flankensteuerung:** Aktiv, wenn Wechsel von 1 nach 0 **Digital-logische Ebene:** Technisches Detail ignorieren ## RS-Flip-Flop \(R\) \(S\) \(Q\) 0 0 \(Q\) 0 1 1 1 0 0 1 1 nicht erlaubt **Zustandstabelle NAND-Kippstufe** \(R_t\) \(S_t\) \(P_{t+2\Delta}\) \(Q_{t+2\Delta}\) 0 0 nicht erlaubt nicht erlaubt 0 1 1 0 1 0 0 1 1 1 \(\overline{Q_t}\) \(Q_t\) **Wertetabelle NAND** \(x\) \(y\) \(\overline{xy}\) 0 0 1 0 1 1 1 0 1 1 1 0 \(R\) : Reset, \(S\) : Set ## D-Flip-Flop \(D\) \(Q\) 0 0 1 1 **Sinnlos?** Verzögerung um 1 Takt **Name:** Delay \(R\) \(S\) \(Q\) 0 0 \(Q\) 0 1 1 1 0 0 1 1 nicht erlaubt ## JK-Flip-Flop \(J\) \(K\) \(R\) \(S\) \(Q\) 0 0 0 0 \(Q\) 0 1 \(Q\) 0 0 1 0 0 \(\overline{Q}\) 1 1 1 \(Q\) \(\overline{Q}\) \(\overline{Q}\) \(R\) \(S\) \(Q\) 0 0 \(Q\) 0 1 1 1 0 0 1 1 nicht erlaubt **Positiv:** Alle Eingaben erlaubt, sinnvolle Funktionalität, vielseitig \(J\) : Jump, \(K\) : Kill ## T-Flip-Flop \(T\) \(Q\) 0 \(Q\) 1 \(\overline{Q}\) **Name:** Toggle \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Flip-Flops **Wir haben:** Also hier 4 verschiedene Flip-Flop-Typen **Wozu brauchen wir eigentlich Flip-Flops?** **Klar:** Realisierung von Speicher **Was müssen wir für den Einsatz als Speicher wissen?** **Klar:** Gezielte Änderung von Speicherinhalten **Also:** Zustandstabellen eigentlich **nicht** interessant **Besser:** **Ansteuertabellen** ## Flip-Flops **Etwas präziser** **Zustandstabelle** Eingabe \(\Rightarrow\) Zustand **Ansteuertabelle** Ist-Zustand, Soll-Zustand \(\Rightarrow\) Eingabe **Anmerkung:** Ansteuertabellen können „don’t care“ enthalten ## Ansteuertabelle D-Flip-Flop **Zustandstabelle** \(D\) \(Q\) 0 0 1 1 **Ansteuertabelle** \(Q_{\text{alt}}\) \(Q_{\text{neu}}\) \(D\) 0 0 0 0 1 1 1 0 0 1 1 1 **Beobachtung:** Ansteuerung \(D\) vom alten Zustand unabhängig ## Ansteuertabelle T-Flip-Flop **Zustandstabelle** \(T\) \(Q\) 0 \(Q\) 1 \(\overline{Q}\) **Ansteuertabelle** \(Q_{\text{alt}}\) \(Q_{\text{neu}}\) \(T\) 0 0 0 0 1 1 1 0 1 1 1 0 **Beobachtung:** Kenntnis des „alten“ Zustands erforderlich ## Ansteuertabelle RS-Flip-Flop **Zustandstabelle** \(R\) \(S\) \(Q\) 0 0 \(Q\) 0 1 1 1 0 0 1 1 nicht erlaubt **Ansteuertabelle** \(Q_{\text{alt}}\) \(Q_{\text{neu}}\) \(R\) \(S\) 0 0 \(*\) 0 0 1 0 1 1 0 1 0 1 1 0 \(*\) **Beobachtung:** Wenn Zustand nicht wechselt, gibt es **Freiheit** in der Ansteuerung ## Ansteuertabelle JK-Flip-Flop **Zustandstabelle** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) **Ansteuertabelle** \(Q_{\text{alt}}\) \(Q_{\text{neu}}\) \(J\) \(K\) 0 0 0 \(*\) 0 1 1 \(*\) 1 0 \(*\) 1 1 1 \(*\) 0 **Beobachtung:** Immer **Freiheit** in der Ansteuerung ## Unvollständig definierte Ansteuerfunktionen **Wir haben:** Für RS-Flip-Flops und JK-Flip-Flops nur partiell definierte Ansteuerfunktionen **Ist das ungünstig?** **Nein!** - **Erinnerung:** Minimalpolynome für partiell definierte Funktionen - **Erinnerung:** Realisierungen können wesentlich einfacher sein - **Erinnerung:** Minimalpolynom für partiell definiertes \(f\) durch PI für \(f_1\) und Überdeckung von \(f_0\) ## Huffman Schaltwerk-Modell Ein allgemeines, formales Schaltwerkmodell **Beobachtung:** Führt Gelerntes über Schaltnetze, Flip-Flops und Automaten **sinnvoll** zusammen ## Huffman Schaltwerk-Modell Etwas detaillierter ## Schaltwerk-Entwurf **Wunsch:** Strukturierter Schaltwerk-Entwurf **Was können wir überhaupt als Schaltwerk realisieren?** **Klar:** Alles, was als Automat beschrieben werden kann **Zum Beispiel** - Getränke-Automat - Ampelsteuerung - Waschmaschinen-Steuerung - … **Anmerkung:** **Heuristiken** und **Erfahrung** sind wichtig ## Abschnitt 5.5 Serienaddierwerke - Schritte beim Schaltwerk-Entwurf - Entwurf eines Serienaddierwerks - Simulation des Serienaddierwerks ## Schritte beim Schaltwerk-Entwurf - **Verstehen** der Aufgabe - Spezifikation des **Verhaltens** (z.B. als Mealy-Automat) - Wahl der **Codierung** von Eingaben, Zuständen, Ausgaben - **Wertetabelle** mit Eingaben, Zustand, Ausgaben, neuem Zustand - Wahl der **Flip-Flop-Typen** - Ergänzung der Wertetabelle um die **Flip-Flop-Ansteuerung** - Entwurf passender **boolescher Funktionen** - Entwurf passender **Schaltnetze** - Entwurf **vollständiges getaktetes Schaltwerk** ## Beispiel zum Schaltwerk-Entwurf **zur Einführung:** ein „**praktisches**“ Beispiel **hilfreich:** besonders gut verstandenes Problem **Aufgabe:** Addition von zwei Betragszahlen **Erinnerung:** wir haben Verfahren Größe Tiefe Schul-Methode \(\approx 5n\) \(\approx 2n\) Carry-Look-Ahead \(\approx n^2\) \(\approx 2\log_2 n\) **jetzt:** klein und flach mit einem Schaltwerk **aber extrem langsam** ## Entwurf Addierwerk: Schritt 0 **Schritt 0:** **Verstehen** der Aufgabe **Wunsch:** - Summanden bitweise eingeben - Summe bitweise erhalten **Offensichtlich:** geht nur von rechts nach links **Was muss man sich merken?** - nur den aktuellen Übertrag - also 1 Bit ## Entwurf Addierwerk: Schritt 1 **Schritt 1:** Spezifikation des **Verhaltens** **Entscheidung:** Beschreibung durch Mealy-Automat - **Eingabealphabet:** \(\Sigma = \{00, 01, 10, 11\}\) - **Ausgabealphabet:** \(\Delta = \{0, 1\}\) (Summenbit) - **Zustandsmenge:** \(Q = \{0, 1\}\) (Übertragsbit) ## Entwurf Addierwerk: Schritt 2 **Schritt 2:** Wahl der Codierung: Eingaben, Zuständen, Ausgaben **Beobachtung:** im Allgemeinen (fast) jede Freiheit **hier:** kanonische Codierung naheliegend **Codierung von \(Q\) ** \(q \in Q\) Codierung 0 0 1 1 **Codierung von \(\Sigma\) ** \(w \in \Sigma\) Codierung 00 00 01 01 10 10 11 11 **Codierung von \(\Delta\) ** \(w \in \Delta\) Codierung 0 0 1 1 ## Entwurf Addierwerk: Schritt 3 **Schritt 3:** **Wertetabelle** Eingaben, Zustand, neuer Zustand, Ausgaben **naheliegend:** Eingaben heißen \(x\) , \(y\) ; alter Zustand heißt \(c_{\text{alt}}\) ; neuer Zustand heißt \(c_{\text{neu}}\) ; Ausgabe heißt \(s\) \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 ## Entwurf Addierwerk: Schritt 4 **Schritt 4:** Wahl der **Flip-Flop-Typen** **Entscheidung:** JK-Flip-Flops **Anmerkung** - nicht viele überzeugende Gründe - weil es besonders viele Freiheiten erlaubt - weil der Zustandswechsel nichts nahelegt - weil es oft benutzt wird ## Entwurf Addierwerk: Schritt 5 **Schritt 5:** Ergänzung der Wertetabelle um **Flip-Flop-Ansteuerung** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) 0 0 0 0 0 0 \(\ast\) 0 0 1 0 1 0 \(\ast\) 0 1 0 0 1 0 \(\ast\) 0 1 1 1 0 1 \(\ast\) 1 0 0 0 1 \(\ast\) 1 1 0 1 1 0 \(\ast\) 0 1 1 0 1 0 \(\ast\) 0 1 1 1 1 1 \(\ast\) 0 **Ansteuertabelle JK-Flip-Flop** \(Q_{\text{alt}}\) \(Q_{\text{neu}}\) \(J\) \(K\) 0 0 0 \(\ast\) 0 1 1 \(\ast\) 1 0 \(\ast\) 1 1 1 \(\ast\) 0 ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) 0 0 0 0 0 0 \(\ast\) 0 0 1 0 1 0 \(\ast\) 0 1 0 0 1 0 \(\ast\) 0 1 1 1 0 1 \(\ast\) 1 0 0 0 1 \(\ast\) 1 1 0 1 1 0 \(\ast\) 0 1 1 0 1 0 \(\ast\) 0 1 1 1 1 1 \(\ast\) 0 ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) 0 0 0 0 0 **0** \(\ast\) 0 0 1 0 1 **0** \(\ast\) 0 1 0 0 1 **0** \(\ast\) 0 1 1 1 0 **1** \(\ast\) 1 0 0 0 1 \(\boldsymbol{\ast}\) 1 1 0 1 1 0 \(\boldsymbol{\ast}\) 0 1 1 0 1 0 \(\boldsymbol{\ast}\) 0 1 1 1 1 1 \(\boldsymbol{\ast}\) 0 ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 0 **0** \(\ast\) **0** **0** **1** 0 1 **0** \(\ast\) **0** **1** **0** 0 1 **0** \(\ast\) **0** **1** **1** 1 0 **1** \(\ast\) **1** **0** **0** 0 1 \(\boldsymbol{\ast}\) 1 **1** **0** **1** 1 0 \(\boldsymbol{\ast}\) 0 **1** **1** **0** 1 0 \(\boldsymbol{\ast}\) 0 **1** **1** **1** 1 1 \(\boldsymbol{\ast}\) 0 ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 0 **0** \(\ast\) **0** **0** **1** 0 1 **0** \(\ast\) **0** **1** **0** 0 1 **0** \(\ast\) **0** **1** **1** 1 0 **1** \(\ast\) **1** **0** **0** 0 1 \(\boldsymbol{\ast}\) 1 **1** **0** **1** 1 0 \(\boldsymbol{\ast}\) 0 **1** **1** **0** 1 0 \(\boldsymbol{\ast}\) 0 **1** **1** **1** 1 1 \(\boldsymbol{\ast}\) 0 ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 0 **0** \(\ast\) **0** **0** **1** 0 1 **0** \(\ast\) **0** **1** **0** 0 1 **0** \(\ast\) **0** **1** **1** 1 0 **1** \(\ast\) **1** **0** **0** 0 1 \(\boldsymbol{\ast}\) 1 **1** **0** **1** 1 0 \(\boldsymbol{\ast}\) 0 **1** **1** **0** 1 0 \(\boldsymbol{\ast}\) 0 **1** **1** **1** 1 1 \(\boldsymbol{\ast}\) 0 ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 0 **0** \(\ast\) **0** **0** **1** 0 1 **0** \(\ast\) **0** **1** **0** 0 1 **0** \(\ast\) **0** **1** **1** 1 0 **1** \(\ast\) **1** **0** **0** 0 1 \(\boldsymbol{\ast}\) 1 **1** **0** **1** 1 0 \(\boldsymbol{\ast}\) 0 **1** **1** **0** 1 0 \(\boldsymbol{\ast}\) 0 **1** **1** **1** 1 1 \(\boldsymbol{\ast}\) 0 \(J(c_{\text{alt}}, x, y) = x\,y\) ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 0 0 \(\boldsymbol{\ast}\) **0** **0** **1** 0 1 0 \(\boldsymbol{\ast}\) **0** **1** **0** 0 1 0 \(\boldsymbol{\ast}\) **0** **1** **1** 1 0 1 \(\boldsymbol{\ast}\) **1** **0** **0** 0 1 \(\ast\) **1** **1** **0** **1** 1 0 \(\ast\) **0** **1** **1** **0** 1 0 \(\ast\) **0** **1** **1** **1** 1 1 \(\ast\) **0** \(J(c_{\text{alt}}, x, y) = x\,y\) ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 0 0 \(\boldsymbol{\ast}\) **0** **0** **1** 0 1 0 \(\boldsymbol{\ast}\) **0** **1** **0** 0 1 0 \(\boldsymbol{\ast}\) **0** **1** **1** 1 0 1 \(\boldsymbol{\ast}\) **1** **0** **0** 0 1 \(\ast\) **1** **1** **0** **1** 1 0 \(\ast\) **0** **1** **1** **0** 1 0 \(\ast\) **0** **1** **1** **1** 1 1 \(\ast\) **0** \(J(c_{\text{alt}}, x, y) = x\,y\) ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 0 0 \(\boldsymbol{\ast}\) **0** **0** **1** 0 1 0 \(\boldsymbol{\ast}\) **0** **1** **0** 0 1 0 \(\boldsymbol{\ast}\) **0** **1** **1** 1 0 1 \(\boldsymbol{\ast}\) **1** **0** **0** 0 1 \(\ast\) **1** **1** **0** **1** 1 0 \(\ast\) **0** **1** **1** **0** 1 0 \(\ast\) **0** **1** **1** **1** 1 1 \(\ast\) **0** \(J(c_{\text{alt}}, x, y) = x\,y\) \(K(c_{\text{alt}}, x, y) = \overline{x}\,\overline{y}\) ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 **0** 0 \(\ast\) **0** **0** **1** 0 **1** 0 \(\ast\) **0** **1** **0** 0 **1** 0 \(\ast\) **0** **1** **1** 1 **0** 1 \(\ast\) **1** **0** **0** 0 **1** \(\ast\) 1 **1** **0** **1** 1 **0** \(\ast\) 0 **1** **1** **0** 1 **0** \(\ast\) 0 **1** **1** **1** 1 **1** \(\ast\) 0 \(J(c_{\text{alt}}, x, y) = x\,y\) \(K(c_{\text{alt}}, x, y) = \overline{x}\,\overline{y}\) ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 **0** 0 \(\ast\) **0** **0** **1** 0 **1** 0 \(\ast\) **0** **1** **0** 0 **1** 0 \(\ast\) **0** **1** **1** 1 **0** 1 \(\ast\) **1** **0** **0** 0 **1** \(\ast\) 1 **1** **0** **1** 1 **0** \(\ast\) 0 **1** **1** **0** 1 **0** \(\ast\) 0 **1** **1** **1** 1 **1** \(\ast\) 0 \(J(c_{\text{alt}}, x, y) = x\,y\) \(K(c_{\text{alt}}, x, y) = \overline{x}\,\overline{y}\) ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) **0** **0** **0** 0 **0** 0 \(\ast\) **0** **0** **1** 0 **1** 0 \(\ast\) **0** **1** **0** 0 **1** 0 \(\ast\) **0** **1** **1** 1 **0** 1 \(\ast\) **1** **0** **0** 0 **1** \(\ast\) 1 **1** **0** **1** 1 **0** \(\ast\) 0 **1** **1** **0** 1 **0** \(\ast\) 0 **1** **1** **1** 1 **1** \(\ast\) 0 \(J(c_{\text{alt}}, x, y) = x\,y\) \(K(c_{\text{alt}}, x, y) = \overline{x}\,\overline{y}\) \[\begin{aligned} s(c_{\text{alt}}, x, y) = {} & \overline{c_{\text{alt}}}\,\overline{x}\,y \vee \overline{c_{\text{alt}}}\,x\,\overline{y}\\ & \vee c_{\text{alt}}\,\overline{x}\,\overline{y} \vee c_{\text{alt}}\,x\,y \end{aligned}\] ## Entwurf Addierwerk: Schritt 6 **Schritt 6:** Entwurf passender **boolescher Funktionen** \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) 0 0 0 0 0 0 \(\ast\) 0 0 1 0 1 0 \(\ast\) 0 1 0 0 1 0 \(\ast\) 0 1 1 1 0 1 \(\ast\) 1 0 0 0 1 \(\ast\) 1 1 0 1 1 0 \(\ast\) 0 1 1 0 1 0 \(\ast\) 0 1 1 1 1 1 \(\ast\) 0 \(J(c_{\text{alt}}, x, y) = x\,y\) \(K(c_{\text{alt}}, x, y) = \overline{x}\,\overline{y}\) \(s(c_{\text{alt}}, x, y) = c_{\text{alt}} \oplus x \oplus y\) ## Entwurf Addierwerk: Schritt 7 **Schritt 7:** Entwurf passender **Schaltnetze** \(J(c_{\text{alt}}, x, y) = x\,y\) \(K(c_{\text{alt}}, x, y) = \overline{x}\,\overline{y}\) \(s(c_{\text{alt}}, x, y) = c_{\text{alt}} \oplus x \oplus y\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** \(J\) \(K\) \(Q\) 0 0 \(Q\) 0 1 0 1 0 1 1 1 \(\overline{Q}\) ## Entwurf Addierwerk: Schritt 8 **Schritt 8:** Entwurf des **vollständigen Schaltwerks** **Beobachtung:** Eingabe (0,0) im letzten Takt wichtig **Initialisierung?** Eingabe (0,0) ## Initialisierung **Initialisierung:** Eingabe (0,0) **Ziel:** Löschen des Übertrags \(Q_{neu}\) - \(Q_{neu}=0\) für \((J,K)=(0,*)\) oder \((J,K)=(*,1)\) \(\Rightarrow (J,K)=(0,1)\) - \((J,K)=(0,1)\) \(\Rightarrow\) \((x,y)=(0,0)\) \(c_{\text{alt}}\) \(x\) \(y\) \(c_{\text{neu}}\) \(s\) \(J\) \(K\) 0 0 0 0 0 0 \(*\) 0 0 1 0 1 0 \(*\) 0 1 0 0 1 0 \(*\) 0 1 1 1 0 1 \(*\) 1 0 0 0 1 \(*\) 1 1 0 1 1 0 \(*\) 0 1 1 0 1 0 \(*\) 0 1 1 1 1 1 \(*\) 0 \(Q_{\text{alt}}\) \(Q_{\text{neu}}\) \(J\) \(K\) 0 0 0 \(*\) 0 1 1 \(*\) 1 0 \(*\) 1 1 1 \(*\) 0 ## Unser Addierwerk: Serien-Addierer **Fazit** - addiert beliebig lange Betragszahlen - ist sehr klein und flach - ist sehr leicht zu initialisieren - **ist extrem langsam** **Warum ist das Schaltwerk so langsam?** **bereits bekannt:** wegen der Überträge **Müssen Überträge so lange dauern?** **bekannt:** im Allgemeinen nicht (siehe Addierer) **aber:** Bei bit-weiser Eingabe schon! ## Über unsere Modelle **Wir wissen schon:** Überträge werden **nur manchmal** lange weitergereicht. **Kann man ein Schaltwerk bauen, das nur manchmal langsam ist?** **Problem:** unsere Automaten können das zunächst nicht **Beobachtung:** bei Mealy- und Moore-Automat bestimmt Länge der Eingabe die Anzahl der Rechentakte **darum Modifikation des Automatenmodells** ## Über unsere Modelle **darum Modifikation des Automatenmodells** **neu:** Erlaube leere Eingabe \(\varepsilon\) und signalisiere Ende der Rechnung durch Rechenende-Zeichen **Beobachtung:** Das ist **fundamental neu** für uns. Rechenzeit kann von der Eingabe abhängen (nicht nur von der Eingabelänge). ## Auf dem Weg zum besseren Addierwerk **Wie wollen wir vorgehen?** **Beobachtung:** Eingaben müssen sofort ganz zur Verfügung stehen, sonst kann man nicht schneller sein **also:** Eingabealphabet \(\Sigma=\{0,1\}^{2n}\) **Eingabe:** \(x_{n-1}x_{n-2}\cdots x_1x_0y_{n-1}y_{n-2}\cdots y_1y_0 \in \{0,1\}^{2n}\) **interpretieren als:** \(\begin{array}{ccccc} & x_{n-1} & x_{n-2} & \cdots & x_0\\ + & y_{n-1} & y_{n-2} & \cdots & y_0\\ \hline \end{array}\) **bekannte Idee zur Lösung:** Ersetze \(x\) und \(y\) durch \(x'\) und \(y'\) mit \(x+y=x'+y'\) so lange, bis \(y'=0\) gilt. ## Eine gute Idee verallgemeinern **Erinnerung:** Wir kennen das schon vom Halbaddierer… mit \(x+y=2c+s=(c0)_2+s\) **Klar:** Das funktioniert auch für alle \(n\) Stellen parallel. \(\begin{array}{rcl} x_3'\,x_2'\,x_1'\,x_0' & = & s_3\,s_2\,s_1\,s_0\\ \text{Ü}\;y_3'\,y_2'\,y_1'\,y_0' & = & c_3\,c_2\,c_1\,c_0\,0 \end{array}\) **Fortschritt?** in \(y\) hinten „neue“ 0, **also** nach \(\le n\) Takten \(y = 0\) ## Noch offene Fragen **Was ist mit dem Ü?** **klar:** potenziell kann in jedem Takt vorne ein Überlauf entstehen **Also bis zu n Überläufe speichern?** **zum Glück:** nein **Wir wissen:** höchstens 1 Überlauf insgesamt **Wann ist die Rechnung fertig?** **klar:** Rechnung fertig, \(y = 0\) **Also:** „done“ \(d=\overline{y_0\lor y_1\lor\dots\lor y_{n-1}}=\neg\bigvee_{i=0}^{n-1}y_i\) **jetzt:** unsere Ideen zusammensetzen ## Das von Neumann-Addierwerk Das von Neumann-Addierwerk nach John von Neumann (1903–1957) **Ideen** - Schaltwerk bekommt direkt Summanden komplett - Eingabe \(\varepsilon\) wird erlaubt - Rechenende-Zeichen signalisiert Ende der Rechnung - in jedem Takt ersetze \(x\) , \(y\) durch \(x'\) , \(y'\) mit \(x+y=x'+y'\) - Ersetzung stellenweise mit Halbaddierern **Hoffnung:** Addierwerk ist oft schnell ## Schematische Darstellung Schematische Darstellung von Neumann-Addierwerk für \(n = 3\) Die \(x_i\) und \(y_i\) und Ü (in der Abbildung mit \(o\) bezeichnet) sind Speicher, die mit Flip-Flops realisiert werden ## Ist das Addierwerk denn jetzt wirklich schnell? **Frage:** Welche Eingaben dauern lange? **1. Versuch:** viele Überträge exemplarisch für \(n = 6\) : 111111 + 111111 Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) 0 1 1 1 1 1 1 1 1 1 1 1 1 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) 1 0 0 0 0 0 0 1 1 1 1 1 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) 1 1 1 1 1 1 0 0 0 0 0 0 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) **Beobachtung:** nach nur zwei Takten fertig \(\rightarrow\) **schnell** **Erinnerung:** bzgl. Übertrag schwierig: 0 + 1, 1 + 0 ## Ist das Addierwerk denn jetzt wirklich schnell? **Frage:** Welche Eingaben dauern lange? **2. Versuch:** 0+1, 1+0 exemplarisch für \(n = 6\) : 000000 + 111111 Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) 0 0 0 0 0 0 0 1 1 1 1 1 1 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) 0 1 1 1 1 1 1 0 0 0 0 0 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) **Beobachtung:** nach nur einem Takt fertig \(\rightarrow\) **sehr schnell** **Offensichtlich:** 111111 + 000000 wäre sofort fertig **Vermutung:** Überträge mit langen Wegen dauern lange **Frage:** Was ist die “**worst case**” Eingabe? ## “worst case”-Eingabe “**worst case**” Eingabe für das von Neumann Addierwerk Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) 0 1 1 1 1 1 1 0 0 0 0 0 **1** \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) 0 1 1 1 1 1 0 0 0 0 0 **1** 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) 0 1 1 1 1 0 0 0 0 0 **1** 0 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) 0 1 1 1 0 0 0 0 0 **1** 0 0 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) 0 1 1 0 0 0 0 0 **1** 0 0 0 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) 0 1 0 0 0 0 0 **1** 0 0 0 0 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) Ü \(x_5\) \(x_4\) \(x_3\) \(x_2\) \(x_1\) \(x_0\) \(\Longrightarrow\) **1** 0 0 0 0 0 0 0 0 0 0 0 0 \(y_5\) \(y_4\) \(y_3\) \(y_2\) \(y_1\) \(y_0\) **extrem langsam** ## Analyse des von Neumann-Addierwerks **Beobachtung:** \(111\cdots111 + 000\cdots000 \Longrightarrow 0\) Takte: **extrem schnell** **Beobachtung:** \(111\cdots111 + 000\cdots001 \Longrightarrow n\) Takte: **extrem langsam** **Ist das von Neumann-Addierwerk schnell oder langsam?** - Best Case: schnell (0 Takte) - Worst Case: langsam ( \(n\) Takte) - 0 Takte: Glücklicher Zufall? - \(n\) Takte: Seltenes Unglück? **Was ist typisch?** - Antwort Average-Case-Analyse - d. h. durchschnittliche Rechenzeit - Problem: Welche Verteilung über die Eingaben nehmen wir an? ## Average-Case-Analyse Average-Case-Rechenzeit **durchschnittliche Rechenzeit** - bei Gewichtung der Eingaben - nach ihrer Wahrscheinlichkeit bei gegebener - Wahrscheinlichkeitsverteilung über den Eingaben **Problem:** Welche Verteilung ist angemessen? - meist betrachtet **Gleichverteilung** - **Vorsicht:** reale Daten fast nie gleichverteilt - trotzdem hier Annahme Gleichverteilung **Gleichverteilung** bedeutet - alle Eingaben gleichwahrscheinlich - an jeder Position 0 und 1 mit Wahrscheinlichkeit \(\frac{1}{2}\) - alle Positionen unabhängig ## Average-Case-Analyse (ungenau!) **Start:** *Typische* Eingabe der Länge \(2n\) bei Gleichverteilung: - je 50% 0- und 1-Stellen - d.h. \(n/2\) 1-en pro Summand **Verarbeitung:** nach 1 Takt … - **Überträge ( \(y\) ):** Wir erwarten 1 an \(y_{i+1}\) , wenn vorher 1 sowohl an \(x_i\) als auch an \(y_i\) , d.h. mit Wahrscheinlichkeit \(1/4\) \(\Rightarrow\) **Erwarten nach 1 Takt \(n/4\) 1-en in \(y\) ** - **Ergebnis ( \(x\) ):** Wir erwarten 1 in \(x_i\) , wenn vorher 01 oder 10 in \(x_i\) , \(y_i\) , d.h. in 50% der Fälle \(\Rightarrow\) **Erwarten nach 1 Takt weiterhin \(n/2\) 1-en in \(x\) ** - \(\Rightarrow\) **Erwarten: Anzahl 1-en in \(y\) halbiert sich je Takt (in \(x\) unverändert)** **Fazit:** Erwarten Rechenende nach \(\log_2(n)\) Takten ## Moore-Automat zum von Neumann-Addierwerk **Ziel:** Beschreibung eines Moore-Automaten zum von Neumann-Addierwerk zur Addition von zwei n-Bit-Zahlen Erweiterung des Automatenmodells um ** \(\varepsilon\) -Eingaben** im folgenden Sinn - bei Eingabe von \(xy\) wird aktuelle **Rechnung unterbrochen** und mit **Berechnung** von \(x+y\) **begonnen** - bei Eingabe von \(\varepsilon\) wird aktuelle **Rechnung fortgesetzt** - Ausgabe ist “ \(-\) ”, falls Rechnung noch **nicht beendet** - Ausgabe ist Summe der Eingabezahlen, wenn **fertig berechnet** ## Schematische Darstellung Schematische Darstellung von Neumann-Addierwerk für \(n = 3\)