Logikgatter, Teil 2: Speicher und Automaten

In Teil 1 berechnete jede Schaltung ihren Ausgang allein aus ihren Eingängen: Ändern sich die Eingänge, folgt der Ausgang. Das genügt, um Zahlen zu addieren, aber nicht, um zu zählen, sich Eingaben zu merken oder ein Programm Schritt für Schritt auszuführen. Dafür braucht eine Schaltung ein Gedächtnis. Dieser Teil zeigt, woher Speicher kommt, wie ein Takt für Ordnung sorgt und wie Speicher und Logik zusammen zu Automaten werden. Wie zuvor gibt es zu jedem Schritt etwas zum Anklicken.

Schaltungen, die sich etwas merken

Logikblöcke gibt es in zwei Arten, je nachdem, ob sie Speicher enthalten. In einem kombinatorischen Block hängt der Ausgang nur von der aktuellen Eingabe ab. In einem Block mit Speicher können die Ausgänge auch vom gespeicherten Wert abhängen, dem Zustand des Blocks [1]. Solche Blöcke heißen sequentiell: Was sie ausgeben, hängt von der gesamten bisherigen Folge der Eingaben ab.

George H. Mealy formulierte es 1955 genau: In seinem Modell bestimmen die aktuelle Eingabe und der aktuelle Zustand die aktuelle Ausgabe und den nächsten Zustand einer Schaltung. Eine Schaltung mit nur einem inneren Zustand ist kombinatorisch, jede andere sequentiell [2, S. 1050]. Alles in Teil 1 war kombinatorisch. Teste dein Gespür:

Das SR-Latch

Speicher braucht eine Schleife: ein Signal, das in das Gatter zurückführt, das es erzeugt hat. Das einfachste Speicherelement verbindet zwei NOR-Gatter zu einem Ring, sodass der Ausgang des einen ein Eingang des anderen ist. Das ist das SR-Latch, mit S für Setzen (set) und R für Rücksetzen (reset) [1].

S = 1 setzt den Ausgang Q auf 1, R = 1 setzt ihn auf 0 zurück. Spannend wird es, wenn beide wieder 0 sind: Nichts drückt auf das Latch, und die beiden Gatter halten sich gegenseitig fest. Das Latch merkt sich, welcher Eingang zuletzt aktiv war. S und R dürfen nicht gleichzeitig 1 sein: Dann sind beide Ausgänge 0, und werden beide Eingänge im selben Moment losgelassen, entscheidet ein Wettlauf, welches Gatter gewinnt.

Takt, Latch und Flipflop

Ein SR-Latch reagiert in jedem beliebigen Moment. In einer größeren Schaltung ist das ein Problem: Signale kommen zu leicht unterschiedlichen Zeiten an, und bis ein Addierer stabil ist, können seine Ausgänge falsch sein, wie der Ripple-Carry-Addierer in Teil 1 zeigt. Synchrone Schaltungen haben deshalb einen Takt, ein Signal, das in festem Rhythmus zwischen 0 und 1 wechselt, und lassen ihre Speicherelemente nur im Gleichschritt damit umschalten. Schon Mealy nannte den Takt, der Zeitimpulse liefert, als Merkmal synchroner Schaltungen [2, S. 1047].

Patterson und Hennessy unterscheiden zwei getaktete Speicherelemente [1]. Ein D-Latch speichert seinen Dateneingang D: Solange der Takt 1 ist, folgt sein Ausgang D, und solange der Takt 0 ist, hält er seinen Wert. Ein D-Flipflop ändert sich nur an einer Taktflanke, hier in dem Moment, in dem der Takt von 0 auf 1 steigt; zu allen anderen Zeiten darf sich D ändern, wie es will. Ein Flipflop lässt sich aus zwei Latches bauen, von denen eines offen ist, solange der Takt 0 ist, und das andere, solange er 1 ist.

Darum bestehen Prozessoren aus Flipflops: An jeder Taktflanke übernehmen alle im selben Moment ihre neuen Werte, und zwischen zwei Flanken hat die kombinatorische Logik Zeit, sich einzuschwingen.

Register und Zähler

Eine Reihe von Flipflops mit gemeinsamem Takt ist ein Register: Es hält eine Zahl von einer Taktflanke bis zur nächsten. Verbindet man ein Register mit einem Addierer, der 1 addiert, und führt die Summe zurück ins Register, hat man einen Zähler. Der Addierer ist kombinatorisch und zeigt schon den nächsten Wert; das Register ist sequentiell und wartet auf die Taktflanke.

Automaten

Der Zähler ist bereits ein kleiner endlicher Automat (englisch finite-state machine): ein in Flipflops gespeicherter Zustand und kombinatorische Logik, die daraus den nächsten Zustand berechnet. Allgemein hat ein solcher Automat drei Teile: eine Übergangslogik, die aus Zustand und Eingaben den nächsten Zustand berechnet, ein Zustandsregister, das den Zustand speichert, und eine Ausgabelogik, die die Ausgaben berechnet [1].

Die Automatentypen unterscheiden sich darin, worauf die Ausgabelogik schauen darf. In Edward F. Moores Automaten hängt die aktuelle Ausgabe nur vom aktuellen Zustand ab [3, S. 129]. In Mealys Modell hängt sie vom aktuellen Zustand und von der aktuellen Eingabe ab [2, S. 1050]. Und gibt es gar keine Ausgabelogik, weil die Zustandsbits selbst die Ausgabe sind, heißt der Automat Medwedew-Automat, nach Ju. T. Medwedew, der 1956 über endliche Automaten veröffentlichte [4].

Moore und Mealy

Beide Arten können dieselben Aufgaben lösen. Nimm eine einfache: Eine Lampe soll leuchten, sobald die Eingabe in zwei Takten hintereinander 1 war. Ein Moore-Automat braucht dafür drei Zustände, „noch keine 1“, „eine 1“ und „zwei oder mehr Einsen“, und die Lampe gehört zum letzten. Ein Mealy-Automat kommt mit zwei Zuständen aus, „letzte Eingabe 0“ und „letzte Eingabe 1“, weil seine Ausgabe auf die aktuelle Eingabe schauen darf: Er schaltet die Lampe ein, wenn in „letzte Eingabe 1“ noch eine 1 kommt.

Mealy zeichnete seine Automaten als Zustandsdiagramme: Kreise für die Zustände und Pfeile für die Übergänge, jeder Pfeil beschriftet mit seiner Eingabe und Ausgabe [2, S. 1052]. Stelle unten die Eingabe x ein, beobachte die beiden Lampen und gib dann einen Takt. Die Mealy-Ausgabe reagiert, sobald sich x ändert, die Moore-Ausgabe erst nach der nächsten Taktflanke. Mealy-Automaten reagieren also früher; Moore-Ausgaben ändern sich nur mit dem Takt, was sie ruhiger macht.

Medwedew: Der Zustand ist die Ausgabe

In einem Medwedew-Automaten steht nichts zwischen Zustandsregister und Ausgängen. Das funktioniert immer dann, wenn die Ausgaben selbst als Codes der Zustände taugen. Eine Ampel ist ein gutes Beispiel: Mit einem Flipflop pro Lampe ist der Zustand „Rot und Gelb“ einfach der Code 110, und die Lampen hängen direkt an den Flipflops. Nur die Übergangslogik bleibt zu entwerfen. Die Ampel unten folgt der deutschen Reihenfolge: Rot, Rot und Gelb, Grün, Gelb.

Wie es weitergeht

Register, ein Takt und Automaten machen aus der ALU von Teil 1 einen Prozessor: Register halten die Operanden, und das Steuerwerk, das Schritt für Schritt entscheidet, was der Prozessor tut, ist selbst ein Automat. Wie solche Automaten entworfen und getaktet werden, behandelt der Anhang „The Basics of Logic Design“ in Pattersons und Hennessys Computer Organization and Design [1]. Und wie man all das schnell macht, mit Pipelines, Caches und parallelen Einheiten, ist das Thema von Hennessys und Pattersons Computer Architecture: A Quantitative Approach [5].

Zurück zu Teil 1: vom Schalter bis zur ALU.

Quellen

1. D. A. Patterson und J. L. Hennessy, Computer Organization and Design RISC-V Edition: The Hardware/Software Interface, 2. Aufl. Morgan Kaufmann (Elsevier), 2020. ISBN 978-0-12-820331-6. Anhang A: “The Basics of Logic Design.” Verlagsseite
2. G. H. Mealy, “A Method for Synthesizing Sequential Circuits,” The Bell System Technical Journal, Bd. 34, Nr. 5, S. 1045–1079, 1955. doi:10.1002/j.1538-7305.1955.tb03788.x. Freier Scan im Internet Archive
3. E. F. Moore, “Gedanken-Experiments on Sequential Machines,” in C. E. Shannon und J. McCarthy (Hrsg.), Automata Studies (Annals of Mathematics Studies 34). Princeton University Press, 1956, S. 129–153. doi:10.1515/9781400882618-006
4. Ju. T. Medwedew, “О классе событий, допускающих представление в конечном автомате” [Über eine Klasse von Ereignissen, die sich in einem endlichen Automaten darstellen lassen], in Avtomaty. Moskau: Izdatel'stvo Inostrannoj Literatury, 1956, S. 385–401. Englische Übersetzung in E. F. Moore (Hrsg.), Sequential Machines: Selected Papers. Addison-Wesley, 1964. Besprechung im Journal of Symbolic Logic
5. J. L. Hennessy und D. A. Patterson, Computer Architecture: A Quantitative Approach, 6. Aufl. Morgan Kaufmann (Elsevier), 2017. ISBN 978-0-12-811905-1. Verlagsseite