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

ti-5-deck-code-ee358a5c.tex.svg

Beobachtung

  • Das ist kein Schaltnetz
  • Es ist eine “baubare” Schaltung
  • Was passiert in dieser Schaltung?

Sequentielle Schaltungen

Was passiert in dieser Schaltung?

ti-5-deck-code-ee358a5c.tex.svg
\(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?

ti-5-deck-code-b6bc3346.tex.svg
\(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?

ti-5-deck-code-1421d7a4.tex.svg
\(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.

ti-5-deck-code-c61bcd8e.tex.svg
\(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?

ti-5-deck-code-f68d6aa4.tex.svg
\(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?

ti-5-deck-code-12cd79ca.tex.svg
\(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?

ti-5-deck-code-6557bead.tex.svg
\(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?

ti-5-deck-code-8117adc3.tex.svg
\(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?

ti-5-deck-code-f68d6aa4.tex.svg
\(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?

ti-5-deck-code-12cd79ca.tex.svg
\(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?

ti-5-deck-code-6557bead.tex.svg
\(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

ti-5-deck-code-e479a933.tex.svg
\(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

ti-5-deck-code-a18cbc9d.tex.svg
\(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

ti-5-deck-code-a309e74b.tex.svg
\(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

ti-5-deck-code-a309e74b.tex.svg
\(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

ti-5-deck-code-e3e77f70.tex.svg
\(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

ti-5-deck-code-32deb69a.tex.svg
\(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

ti-5-deck-code-7ac3de60.tex.svg
\(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

ti-5-deck-code-b9e604d0.tex.svg
\(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

ti-5-deck-code-b9e604d0.tex.svg
\(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

ti-5-deck-code-32deb69a.tex.svg
\(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

ti-5-deck-code-e65fa9b0.tex.svg
\(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

ti-5-deck-code-c96a53a0.tex.svg
\(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

ti-5-deck-code-6c406f3c.tex.svg
\(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

ti-5-deck-code-f11641b4.tex.svg
\(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

ti-5-deck-code-6617c41c.tex.svg
\(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

ti-5-deck-code-67ae7b2c.tex.svg
\(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

ti-5-deck-code-67ae7b2c.tex.svg
\(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

ti-5-deck-code-7f7811a0.tex.svg
\(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

ti-5-deck-code-e479a933.tex.svg

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\)
ti-5-deck-code-e479a933.tex.svg

\[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}\)
ti-5-deck-code-e479a933.tex.svg

\[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\)
ti-5-deck-code-e479a933.tex.svg

\[ \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}\)
ti-5-deck-code-e479a933.tex.svg

\[ \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

ti-5-deck-code-9c650ed1.tex.svg

\(Q = \{q_0, q_1, q_2\}\)

\(\Sigma = \{0, 1\}\)

\(\Delta = \{a, b, c\}\)

Eingabe: \(0\;\;1\;\;0\;\;0\)

Ausgabe:

Beispiel Mealy-Automat

ti-5-deck-code-5f399254.tex.svg

\(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

ti-5-deck-code-84c80e31.tex.svg

\(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

ti-5-deck-code-cee54c69.tex.svg

\(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

ti-5-deck-code-702bb657.tex.svg

\(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

ti-5-deck-code-2cfd6c09.tex.svg

\(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

ti-5-deck-code-fc901ace.tex.svg

\(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

ti-5-deck-code-cee54c69.tex.svg

\(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

ti-5-deck-code-f31402c2.tex.svg

\(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

ti-5-deck-code-5f399254.tex.svg

\(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

ti-5-deck-code-df428276.tex.svg

mit \(Q := \{0, 1, ?\}, q_0 := 0\)

Äquivalente Automaten „Bit-Filter“

Mealy-Automat

ti-5-deck-code-df428276.tex.svg

Moore-Automat

ti-5-deck-code-46cffb29.tex.svg

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

ti-5-deck-code-b8914bde.tex.svg
\(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}\)
ti-5-deck-code-e5859e51.tex.svg

\(Q = \{0, 1\}, q_0 = 0\)

\(\Sigma = \{01, 10, 11\}\)

\(\Delta = \{0, 1\}\)

\(R\): Reset, \(S\): Set

Vergleich Automat und NAND-Kippstufe

Nicht getaktet

ti-5-deck-code-b8914bde.tex.svg
\(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

ti-5-deck-code-e5859e51.tex.svg

\(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

ti-5-deck-code-32f7abe9.tex.svg
\(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

ti-5-deck-code-76cf6a70.tex.svg
\(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

ti-5-deck-code-d61bf9ce.tex.svg
\(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

ti-5-deck-code-6224a44e.tex.svg
\(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

ti-5-deck-code-241f705e.tex.svg

Beobachtung: Führt Gelerntes über Schaltnetze, Flip-Flops und Automaten sinnvoll zusammen

Huffman Schaltwerk-Modell

Etwas detaillierter

ti-5-deck-code-d77ca0af.tex.svg

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

  1. Verstehen der Aufgabe
  2. Spezifikation des Verhaltens (z.B. als Mealy-Automat)
  3. Wahl der Codierung von Eingaben, Zuständen, Ausgaben
  4. Wertetabelle mit Eingaben, Zustand, Ausgaben, neuem Zustand
  5. Wahl der Flip-Flop-Typen
  6. Ergänzung der Wertetabelle um die Flip-Flop-Ansteuerung
  7. Entwurf passender boolescher Funktionen
  8. Entwurf passender Schaltnetze
  9. 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)
ti-5-deck-code-7e4f6158.tex.svg

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
ti-5-deck-code-8d7c5bb7.tex.svg

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
ti-5-deck-code-38248f63.tex.svg

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
ti-5-deck-code-7fbf4b99.tex.svg

\(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
ti-5-deck-code-8d7c5bb7.tex.svg

\(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
ti-5-deck-code-77f08d65.tex.svg

\(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
ti-5-deck-code-912f57e6.tex.svg

\(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
ti-5-deck-code-8d7c5bb7.tex.svg

\(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
ti-5-deck-code-490da380.tex.svg

\(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
ti-5-deck-code-a46c44ae.tex.svg

\(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
ti-5-deck-code-8d7c5bb7.tex.svg

\(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

ti-5-deck-code-1fea1ebd.tex.svg

\(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

ti-5-deck-code-3761f0be.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-3761f0be.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-6a4ff1bf.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-3761f0be.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-789dd3b3.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-9cee9f5d.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-789dd3b3.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-bde4d5ba.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-789dd3b3.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-70df436c.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-d55c1f7c.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-f1665d94.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-58f0e2dc.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-e4239c8b.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-58f0e2dc.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-70df436c.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-70f44696.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-bfaba817.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-3d704637.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-c3105e1d.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-3d704637.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-70df436c.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-eb741017.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-37f92287.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-66d8edb7.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-ba93542b.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-66d8edb7.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-95050b35.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-69f41e8c.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-9cee9f5d.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-7f50e26e.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-bde4d5ba.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-7f50e26e.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-70df436c.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-0bfe70ad.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-37f92287.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-86528d0d.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-ba93542b.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-86528d0d.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-95050b35.tex.svg
\(J\) \(K\) \(Q\)
0 0 \(Q\)
0 1 0
1 0 1
1 1 \(\overline{Q}\)
ti-5-deck-code-b72238db.tex.svg

Entwurf Addierwerk: Schritt 8

Schritt 8: Entwurf des vollständigen Schaltwerks

ti-5-deck-code-95050b35.tex.svg
ti-5-deck-code-35930b29.tex.svg

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
ti-5-deck-code-3761f0be.tex.svg

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…

ti-5-deck-code-e524d176.tex.svg

mit \(x+y=2c+s=(c0)_2+s\)

Klar: Das funktioniert auch für alle \(n\) Stellen parallel.

ti-5-deck-code-7d751e6a.tex.svg

\(\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\)

ti-5-deck-code-eb2616ba.tex.svg

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\)

ti-5-deck-code-eb2616ba.tex.svg