Kap2 - Schaltnetze - Vorlesungsskript PDF

Sommersemester 2024 Automaten und Rechnerarchitekturen Kapitel 2: Schaltnetze (Wiederholung) Prof. Dr. Uwe Brinkschulte apl. Prof. Dr. Mathias Pacher Inhalt Definition Schaltnetz Boolesche Funktionen KV Diagramme 2 stufige Normalformen Minimierung Ze...

Sommersemester 2024 Automaten und Rechnerarchitekturen Kapitel 2: Schaltnetze (Wiederholung) Prof. Dr. Uwe Brinkschulte apl. Prof. Dr. Mathias Pacher Inhalt Definition Schaltnetz Boolesche Funktionen KV Diagramme 2 stufige Normalformen Minimierung Zeitverhalten Hasards Spezielle Schaltnetze für die Rechnerarchitektur Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 1 Definition Schaltnetz Ein Schaltnetz ist die Realisierung einer Booleschen Funktion, welche keinerlei Rückführungen oder Speicherglieder enthält => ein Schaltnetz hat rein kombinatorischen Charakter Unterschied zum Schaltwerk Ein Schaltwerk ist die Realisierung einer Booleschen Funktion, welche Rückführungen oder Speicherglieder enthält => Ein Schaltwerk besitzt ein Gedächtnis Wiederholung der wichtigsten Grundlagen von Schaltnetzen, welche wir für Schaltwerke und Rechnerarchitektur benötigen Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 2  Boolesche Funktionen Reelle Funktionen einer Variablen: y f x Funktion: eine Beziehung zwischen zwei Mengen, die jedem Element der einen Menge (Definitionsmenge) genau ein Element der anderen Menge (Wertebereich) zuordnet. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 3 Boolesche Funktion einer Variablen Alle Booleschen Funktionen einer Variablen: f y f y 0 1 1 1 0 x 0 x 0 1 0 1 f y f y 2 3 1 1 0 x 0 x 0 1 0 1 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 4 Boolesche Funktionen einer Variablen heißt Negation von. Bei analoger Interpretation des Minuszeichens wäre die Schreibweise ebenfalls erlaubt. Für Funktionen gilt entsprechend: Literal: Die Größe heißt Literal. Literale sind als Quasivariable zu verstehen. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 5 Boolesche Funktionen von zwei Variablen Alle Booleschen Funktionen von zwei Variablen: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 6 Boolesche Funktionen von zwei Variablen Prominente Funktionen zweier Variablen: In der Praxis kommen NAND- und NOR-Gatter häufig vor, weil sie technologisch einfach zu realisieren sind. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 7 Bemerkungen zu Booleschen Funktionen  Die in der Infix-Schreibweise verwendeten Booleschen Operatoren entstammen der Booleschen Algebra.  Die Negation besitzt die höchste Priorität.  Die Konjunktion () besitzt eine höhere Priorität als die Disjunktion ().  Oft wird in Booleschen Ausdrücken der Konjunktionsoperator () weggelassen.  Die Äquivalenz entspricht der Negation der Antivalenz.  Die Antivalenz entspricht der einstelligen dualen Addition.  Die Konjunktion entspricht dem Übertrag der einstelligen Addition.  Gleichheit und Äquivalenz sollten nicht verwechselt werden. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 8 Boolesche Funktionen von n Variablen  Zur Darstellung Boolescher Funktionen eignen sich zum einen Funktionstafeln, in denen für jede Eingangsbelegung x der zugehörige Funktionswert notiert wird.  Die Funktionstafel einer Booleschen Funktion in n Variablen hat genau 2n Zeilen. Funktionstafel: sind die Wahrheitswerte der Funktion. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 9 Bemerkungen n  Es existieren 22 verschiedene Funktionen von n Variablen. Eine Funktionsspalte hat 2n Zeilen. Die Werte können als Dualzahl der Länge 2n interpretiert werden. Eine Dualzahl der Länge l kann aber 2l verschiedene Werte annehmen.  Sind zwei Funktionen f1 und f2 voneinander verschieden, so sind auch deren Inverse voneinander verschieden. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 10 Boolesche Algebra Axiome: 1. Kommutativgesetz der Konjunktion: ab=ba 2. Kommutativgesetz der Disjunktion: ab=ba 3. Assoziativgesetz der Konjunktion: (a  b)  c = a  (b  c) 4. Assoziativgesetz der Disjunktion: (a  b)  c = a  (b  c) 5. Erstes Distributivgesetz: a  (b  c) = (a  b)  (a  c) 6. Zweites Distributivgesetz: a  (b  c) = (a  b)  (a  c) 7. Identitätselement der Konjunktion: 1a=a 8. Identitätselement der Disjunktion: 0a=a 9. Inverses Element der Konjunktion: aa=0 10. Inverses Element der Disjunktion: aa=1 Folgerungen: 11. Idempotenzgesetz der Konjunktion: aa=a 12. Idempotenzgesetz der Disjunktion: aa=a 13. Reduktionsgesetz der Konjunktion: a0=0 14. Reduktionsgesetz der Disjunktion: a1=1 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 11  Gesetze von DeMorgan Gesetze: Wahrheitstafel: Diese beiden Regeln haben große Bedeutung für die Umformung von Booleschen Ausdrücken. Sie lassen sich auf beliebige Variablenzahl verallgemeinern: Die Negation einer Disjunktion von Die Negation einer Konjunktion von Literalen ist identisch zur Konjunktion der Literalen ist identisch zur Disjunktion der negierten Literale negierten Literale Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 12 Der Shannon'sche Entwicklungssatz Jede Boolesche Funktion kann durch eine Variable xi und die entsprechenden Co-Faktoren dargestellt werden: Beispiel: Entwicklung nach den Variablen a und b Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 13 Das AND-OR-NOT-System Jede Boolesche Funktion kann ausnahmslos durch alleinige Verwendung der Operatoren AND, OR und NOT dargestellt werden. Ist eine Boolesche Funktion durch einen Booleschen Ausdruck gegeben, so liefert n-maliges Anwenden des Entwicklungssatzes einen Booleschen Ausdruck für f im AND-OR- NOT-System. Bei Konstanten können hierbei folgende Regeln angewandt werden: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 14 Vollständige Operatorsysteme Neben dem AND-OR-NOT-System gibt es noch andere so genannte vollständige Operatorsysteme. Vollständig weist auf die Darstellbarkeit jeder denkbaren Booleschen Funktion hin. Zum Nachweis der Vollständigkeit eines Operatorsystems genügt es zu zeigen, dass die Grundfunktionen AND, OR und NOT darstellbar sind. Das NAND-System: Das NOR-System: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 15 Gatter Zur Realisierung Boolesche Funktionen (Schaltnetze) gibt es eine Reihe von Gattern, welche die Grundfunktionen implementieren. Symbole der grundlegenden Gatter nach DIN: Damit können nun Schaltbilder von booleschen Funktionen gezeichnet werden. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 16 KV-Diagramme KV-Diagramme sind eine Alternative für die Funktionstabelle einer Booleschen Funktion. Karnaugh-Veitch-Diagramme sind spezielle Venn-Diagramme (bekannt aus der Mengenalgebra), die zur Darstellung und insbesondere auch zur Minimierung Boolescher Funktionen verwendet werden, wenn die Zahl der Variablen nicht größer als 4 ist. Ein KV-Diagramm für eine Boolesche Funktion ist eine quadratische oder eine rechteckige (bestehend aus zwei Quadraten) Tafel, die aus Feldern zusammengesetzt wird, in die die Funktionswerte der Booleschen Funktion eingetragen werden. Definition: Ein KV-Diagramm von ist eine graphische Darstellung der Funktionstabelle von f , wobei jeder Zeile der Tabelle genau ein nummeriertes Feld im KV-Diagramm entspricht. Die Feldnummer entspricht der Zeilennummer, wenn die Variablen mit fallendem Index notiert werden. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 17 Konstruktion von KV-Diagrammen Ein KV-Diagramm für eine Funktion in n Variablen entsteht induktiv durch eine Verdopplung einer KV-Tafel für n-1 Variablen durch Spiegelung. Die jeweils neu hinzukommende Variable hat in der alten Tafel den Wert 0, in der neuen den Wert 1. x0 x0 x1 x1 x2 x0 x0 x3 x1 x1 x2 x3 x2 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 18 Konstruktion von KV-Diagrammen Bei 5 Variablen muss man sich auch benachbarte Felder in der 3. Dimension vorstellen, daher sind die Diagramme mit 5 Variablen zwar möglich aber nicht mehr sehr anschaulich. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 19 Beispiel: KV-Diagramm für die 2-von-3 Funktion x0 0 0 1 0 0 1 1 1 x1 x2 x 2x 0 x0 0 0 1 0 0 1 1 1 x1 x2 x 1x 0 x 2x 1 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 20 Konjunktionsterme Konjunktionsterm: Ein Konjunktionsterm ist eine konjunktive Verknüpfung von Literalen. Jede Variable tritt höchstens einmal auf. Minterm: Ein Minterm Mi ist ein Konjunktionsterm maximaler Länge, d.h. es kommen sämtliche Literale genau einmal in Mi vor. Es existiert genau eine Belegung der Literale in Mi, mit der Mi den Wert 1 annimmt. Minterm einer Schaltfunktion: Ein Term Mi ist Minterm einer Booleschen Funktion f , wenn f für die Belegung den Wert 1 annimmt, für die auch Mi den Wert 1 annimmt. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 21 Minterme Minterme einer Booleschen Funktion f entsprechen umkehrbar eindeutig 1. denjenigen Zeilen der Funktionstabelle, die als Funktionswert die 1 haben. 2. denjenigen Quadraten des KV-Diagramms dieser Funktion, die den Wert 1 tragen Bemerkung: Minterme werden mit fallenden Indizes notiert die duale Interpretation der 1-Belegung eines Minterms entspricht exakt der Zeilennummer seiner Position in der Funktionstabelle Beispiel: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 22 Disjunktionsterme Disjunktionsterm: Ein Disjunktionsterm ist eine disjunktive Verknüpfung von Literalen. Jede Variable tritt höchstens einmal auf. Maxterm: Ein Maxterm ist ein Disjunktionsterm maximaler Länge (analog Minterm). Im KV-Diagramm stellt sich der Maxterm als genau eine 0 dar. Die restlichen Felder sind mit 1 belegt (invers zum KV- Diagramm eines Minterms). Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 23 Minterme und Maxterme in einer Funktionstabelle Beispiel: x2x1x0 y 0 0 0 0 Maxterm x2  x1  x0 0 0 1 0 Maxterm x2  x1  x0 0 1 0 1 Minterm x2  x1  x0 0 1 1 1 Minterm x2  x1  x0 1 0 0 0 Maxterm x2  x1  x0 1 0 1 1 Minterm x2  x1  x0 1 1 0 1 Minterm x2  x1  x0 1 1 1 0 Maxterm x2  x1  x0 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 24 Implikant und Primimplikant Implikant Ein Implikant I von f ist ein Konjunktionsterm, der f impliziert. I=1f=1 Für jede Belegung, bei der I den Wert 1 annimmt, nimmt auch f den Wert 1 an. Primimplikant Ein Primimplikant ist ein Implikant von f , der nicht mehr verkürzbar ist. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 25 Beispiel Funktion: KV-Diagramm: a 1 1 Primimplikanten: b 1 1 1 1 d 1 1 1 1 c Vereinfachte Funktion: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 26 Implikat und Primimplikat Implikat Ein Implikat I von f ist ein Disjunktionsterm, der von f impliziert wird. I=0f=0 Für jede Belegung, bei der I den Wert 0 annimmt, nimmt auch f den Wert 0 an. Primimplikat Ein Primimplikat ist ein Implikat von f , der nicht mehr verkürzbar ist. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 27 Zweistufige Normalformen Disjunktive Normalform (DNF): Die DNF einer Schaltfunktion f ist die Disjunktion von Konjunktionstermen, die Implikanten dieser Funktion sind. Konjunktive Normalform (KNF): Die KNF einer Schaltfunktion f ist die Konjunktion von Disjunktionsstermen, die Implikate dieser Funktion sind.. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 28 Optimierung zweistufiger Normalformen mit KV Diagrammen Bei der graphischen Methode zur Minimierung von Schaltnetzen ist vor allem die Intuition des Schaltungsentwicklers gefragt, da es auf das Erkennen von Symmetrien ankommt. Diese Vorgehensweise ist nur für Schaltungen geringer Komplexität geeignet. Vorgehensweise: 1. Ermittlung aller Primimplikanten P( f ) einer Funktion f 2. Auswahl derjenigen {p1, p2, … , pk}  P(f), für die (a) NF(f) = p1 p2  …  pk = f (b) Kosten = min Die Menge P( f ) läßt sich direkt aus dem KV-Diagramm entnehmen. Die Suche nach NFmin( f ) läßt sich durch Klassifizierung der Primimplikanten erleichtern. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 29 Klassifizierung der Primimplikanten Kern-Primimplikant PK: Ein Primimplikant p ist ein Kern-Primimplikant, d.h. p  PK, falls p von der Disjunktion aller übrigen p  P( f ) nicht überdeckt wird. Bemerkung: Ein Kern-Primimplikant überdeckt mindestens einen Minterm, der von keinem anderen Primimplikanten überdeckt wird. Absolut eliminierbare Primimplikanten PA: Ein Primimplikant p ist ein absolut eliminierbarer Primimplikant, d.h. p  PA, falls p von der Disjunktion aller PK überdeckt wird. Bemerkung: Ein absolut eliminierbarer Primimplikant wird vollständig von Kern-Primimplikanten überdeckt. Relativ eliminierbare Primimplikanten PR: Ein Primimplikant p ist ein relativ eliminierbarer Primimplikant, d.h. p  PR, falls p von der Disjunktion von P( f ) - PA überdeckt wird. Bemerkung: Ein relativ eliminierbarer Primimplikant überdeckt nur mehrfach überdeckte Minterme, wobei nicht alle von Kern- Primimplikanten überdeckt werden. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 30 Minimale Normalform Satz: Die minimale Normalform NFmin( f ) besteht nur noch aus den Kern- Primimplikanten PK und einer Auswahl relativ eliminierbarer Primimplikanten p  PR derart, dass kein Primimplikant von der Disjunktion der übrigen p  NFmin( f ) überdeckt wird. Im allgemeinen erfüllen für eine gegebene Funktion f mehrere NF diese Bedingung. Von ihnen wird diejenige ausgewählt, für die der Kostenwert minimal ist. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 31  Beispiel – Minimale Normalform a a a 1 1 1 1 1 1 1 1 1 1 1 1 b b b 1 1 1 1 1 1 1 1 1 1 1 1 d d d 1 1 1 1 1 1 c c c Primimplikanten irredundante NF irredundante und minimale NF Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 32  Zeitliches Verhalten von Schaltnetzen Um die Effekte auf der annähernd Gatterebene zu beschreiben, gibt es eine Reihe verschieden komplexer Modelle. Einfachstes Modell: Totzeitmodell Es werden lediglich die durch Gatter und Leitungen entstehenden Verzögerungen berücksichtigt. Ein reales Verküpfungsglied (Gatter) wird modelliert durch: - ein ideales Verknüpfungsglied ohne Verzögerung - ein Totzeitglied als reines Verzögerungsglied (steht für die Schaltzeit des Gatters und ggf. für Leitungsverzögerungen).  Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 33  Totzeitglied Das zeitliche Verhalten einer binären Größe hinter einem Totzeitglied ist dasselbe wie dasjenige vor dem Totzeitglied, aber um die Zeit t versetzt. a(t)  b(t) = a(t-) Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 34 Totzeitmodell eines Inverters x(t) x y 1  y(t)   Mit Hilfe dieses einfachen Modells lassen sich Laufzeiteffekte bereits sehr gut modellieren. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 35  Eigenschaften von Totzeiten Addierbarkeit: zwei hintereinanderliegende Totzeiten können durch ihre Summe ersetzt werden 1 b(t) 2 a(t) c(t) = a(t) 1 + 2 c(t) Durchschiebbarkeit: Ein Totzeitglied in diesem Totzeitmodell, welches hinter einem Gatter mit beliebiger Verknüpfungsfunktion f liegt, kann durch das Gatter hindurch in alle Eingänge vorgeschoben werden. a1(t-  ) a (t ) a1(t)  1 y´ (t ) f  y (t ) = f y(t) an(t)  a (t ) n an(t-  ) Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 36 Trennung von Verknüpfungs- und Verzögerungsteil Alle Verzögerungszeiten sukzessive zum Eingang des Schaltnetzes verschieben und aufaddieren. e1 1  &  e 2 1  a & 3 e3 Beispiel: gemischte Verknüpfungen und Verzögerungen Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 37 Trennung von Verknüpfungs- und Verzögerungsteil e11 e1 3 1 & e21 e2 2 e12 11 4 a e31 & e3 4 Verzögerungsteil Verknüpfungsteil Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 38 Pfadvektor und Strukturausdruck e11 e1 3 1 & e21 e2 2 e12 4 11 a e31 & e3 4 Pfadvektor: (alle Pfadvariable) Strukturausdruck: e11 e21  e12 e31 (beschreibt die Struktur der Funktion) Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 39  Alternative Methode zu Pfadvektor und Strukturausdruck - Man schreibt die der Schaltnetzstruktur entsprechende algebraische Darstellungsform auf. - Hierbei versieht man jede Eingangsvariable bei ihrem ersten, zweiten, dritten … Auftreten mit dem zusätzlichen Index 1, 2, 3,... Beispiel: e1 & e2 1 1 a e & 3 Algebraische Darstellungsform: e 1 e2  e2 e3 Strukturausdruck mit Pfadvariablen: e11 e21  e22 e31 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 40 Hazards und Hazardfehler in Schaltnetzen Gegeben: e 1 a 1 a=ee=1 Beide Gatter haben eine Verzögerung von 1 ns Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 41 Hazards und Hazardfehler in Schaltnetzen e 0 11 0 0 0 1 11 1 0 1 1  a 1  1 10 0 1 1 Zeitdiagramm: e a 1 2 3 4 5 6 7 8 9 10 11 12 t/ns Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 42 Verhalten bei Änderung der Eingabebelegung Ideales Schaltnetz: - Das Ausgangssignal ändert sich nicht, wenn alte und neue Belegung denselben logischen Verknüpfungswert liefern. - Das Ausgangssignal ändert sich genau einmal, wenn alte und neue Belegung verschiedene logische Verknüpfungswerte liefern. Reales Schaltnetz: - Die Änderung läuft auf verschieden langen Wegen mit verschiedenen Verzögerungen durch das Schaltnetz. => Mehrfache Änderungen des Ausgangssignals sind möglich, bis sich der stabile Endwert einstellt: => Hazardfehler Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 43 Hazardfehler - Hazard Ein Hazardfehler ist eine mehrmalige Änderung der Ausgangsvariablen während eines Übergangs. Ein Hazard ist die durch das Schaltnetz gegebene logisch-strukturelle Vorbedingung für einen Hazardfehler, ohne Berücksichtigung der konkreten Verzögerungswerte. Ein Hazard ist die Eigenschaft eines bestimmten Übergangs im Schaltnetz. Zur Betrachtung, ob ein Übergang hazardbehaftet ist, interessieren nur die Funktion und die Struktur des Schaltnetzes, nicht die konkreten Verzögerungswerte Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 44 Hazardfehler - Hazard Tritt in einem konkreten Schaltnetz bei einem bestimmten Übergang ein Hazardfehler auf, so ist dieser Übergang hazardbehaftet, also: Hazardfehler => Hazard Die Umkehrung gilt jedoch nicht: Ist ein Übergang hazardbehaftet, so folgt hieraus nicht notwendigerweise das Eintreten eines Hazardfehlers. Hazard ∧ ungünstige Verzögerungswerte => Hazardfehler Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 45 Beispiel x1 e1 1  x2 &  e2 x3 1  a & 3 e3 e 1 1 1 1 1 e 2 a = e1 e2  e1 e3 e 3 Es soll der folgenden Eingabewechsel betrachtet werden: Die Eingänge e2 und e3 seien konstant 1, der Eingang e1 wechsle von 0 auf 1 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 46 Beispiel Funktionswerte bei dem Übergang: e 1 1 (e3,e2,e1) = (1,1,0) => a = 1 1 1 1 e (e3,e2,e1) = (1 1 1) => a = 1 2 e 3 - korrektes Verhalten bei den Übergängen: bei beiden Übergängen darf sich der Wert von a nicht ändern. Er muss konstant 1 bleiben. Genau dieses Verhalten kann jedoch nicht garantiert werden ! Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 47 Verhalten anhand des Totzeitmodells t0 1 e1 0 1 x1 e2 0 e1 1   1 & x2 e3 0 e2  1 x1 0 1  a  x3 & 3 x2 1 0 e3 3  1 x3 0   1 a 0 Hazardfehler => Hazard Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 48 Verhalten anhand des Totzeitmodells t0 x1 e1 1  e1 1 0 &  x2 1 e2 0 1 e3 0 e2  1 x1  0 x3 1  a x2   1 0 & 3 1 e3 x3   0 1 a 0 Kein Hazardfehler, aber Veränderung der Totzeit 3 auf  trotzdem Hazard Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 49  Definitionen Statischer Hazard: Hazard bei statischem Übergang des Ausgangssignals, d.h. Anfangs- und Endwert des Ausgangssignals sind gleich => Statischer 0-Hazard, Statischer 1-Hazard Dynamischer Hazard: Hazard bei dynamischen Übergang des Ausgangssignals, d.h. Anfangs- und Endwert des Ausgangssignals sind ungleich => Dynamischer 01- Hazard, Dynamischer 10-Hazard Funktionshazard: Hazard, dessen Ursache in der zu realisierenden Funktion liegt. Er tritt in jeder möglichen Schaltnetzrealisierung für diese Funktion auf. Er kann somit nicht behoben werden. Nur das Auftreten des Hazardfehlers kann durch günstige Wahl der Verzögerungen vermieden werden. Strukturhazard: Hazard, dessen Ursache in der Struktur des realisierten Schaltnetzes liegt. Er kann durch Änderung der Schaltnetzstruktur bei gleicher Schaltfunktion behoben werden. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 50 Analyse von Hazards Methode: Alle möglichen Wege eines Übergangs werden im KV- Diagramm untersucht Erkennen eines Funktionshazards Vorgehensweise:  Man stellt das KV-Diagramm der Funktion auf und markiert das Feld der Anfangsbelegung und das der Endbelegung des betrachteten Eingabewechsels.  Nun betrachtet man alle Wege, die der Übergang nehmen kann. Hierzu stellt man zunächst fest, welche Eingangsvariablen am Eingabewechsel beteiligt sind.  Nacheinander muss dann jeweils genau einmal an allen Achsen dieser Eingangsvariablen gespiegelt werden, um einen Weg von der Anfangsbelegung bis zur Endbelegung zu erhalten. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 51 Erkennen eines Funktionshazards  Mit m Eingangsvariablen, die am Wechsel beteiligt sind, gibt es m! mögliche Wege, da jede mögliche Reihenfolge der m Spiegelungen berücksichtigt werden muss.  Der Übergang ist genau dann funktionshazardbehaftet, wenn es mindestens einen Weg gibt, für den die Folge der zugehörigen Funktionswerte (0 oder 1 im KV-Diagramm) nicht monoton ist, d. h. in der mindestens zweimal der Funktionswert wechselt. Beispiele monotoner Folgen von Funktionswerten: 0 0 0 0, 0 0 1 1, 1 1 1 0, 1 1 1 1. Beispiele nicht monotoner Folgen von Funktionswerten: 0 0 1 0, 0 1 0 1, 1 0 1 0, 1 0 0 1. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 52 Erkennen eines Funktionshazards  Es ist leicht einzusehen, dass jeder ermittelte Weg eine mögliche Übergangsfolge im Schaltnetz darstellt.  Welcher Weg eingeschlagen wird, hängt von den Verzögerungszeiten ab.  Ist mindestens ein nichtmonotoner Weg dabei, so kann dieser bei ungünstigen Verzögerungswerten auch eingeschlagen werden  Bereitschaft zum Hazardfehler Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 53  Beispiel Übergang (e3, e2, e1): (0,1,0) (1,1,1), im KV-Diagramm: e1 1 1 1 1 e2 e3 Hier sind die Variablen e1 und e3 am Übergang beteiligt. Es gibt 2 Wege: e1 e1 1 1 1 1 1 e2 1 1 1 e2 e3 e3 (0,1,0) (0,1,1) (1,1,1) (0,1,0) (1,1,0) (1,1,1) 1 0 1 1 1 1 14. April 2024 54  Erklärung zum Beispiel Der erste dieser Wege liefert als Folge der Funktionswerte die nicht monotone Folge 10 1.  Der Übergang ist mit einem Funktionshazard behaftet. Bereits eine nicht monotone Folge ist dafür hinreichend. Dass der zweite Weg eine monotone Folge liefert, spielt keine Rolle mehr. Es handelt sich um einen statischen 1-Funktionshazard. 14. April 2024 55  Beispiel 2 Übergang (e3, e2, e1): (1,1,0) (1,1,1) im KV-Diagramm: e 1 1 1 1 1 e 2 e 3 Es ändert sich nur die Variable e1. Es gibt daher nur einen Weg, der aus Anfangs- und Endwert des Übergangs besteht. Die Folge der dazugehörigen Funktionswerte muss monoton sein. Die Folge heißt hier 11.  Dieser Übergang enthält also keinen Funktionshazard. Ein Übergang, bei welchem nur eine Eingangsvariable wechselt, kann keinen Funktionshazard enthalten. Da wir jedoch von vorher wissen, dass der Übergang hazardbehaftet ist, muss es sich hierbei um einen Strukturhazard handeln. 14. April 2024 56  Erkennen eines Strukturhazards Ähnlich wie bei Funktionshazards kann man Strukturhazards mit Hilfe des KV-Diagramms erkennen. Da ein Strukturhazard eine Eigenschaft eines Übergangs in einem Schaltnetz bestimmter Struktur ist, muss man hier diese Struktur in die Überlegungen einbeziehen. Die Struktur des Schaltnetzes liefert Information darüber, über wie viele und welche Pfade sich Änderungen der Eingangsvariablen auf den Ausgang auswirken.  Ausgangspunkt ist der Strukturausdruck des Schaltnetzes 14. April 2024 57  Erkennen eines Strukturhazards Für den Strukturausdruck des Schaltnetzes stelle man das KV- Diagramm auf. Anstelle der Eingangsvariablen treten hier die Pfadvariablen. Man markiere wieder die beiden Felder der Anfangs- und der Endbelegung. In diesen müssen die Werte aller Pfadvariablen einer Eingangsvariablen gleich sein. Man betrachtet alle möglichen Wege von der Anfangs- zur Endbelegung. Der Übergang ist genau dann strukturhazard-behaftet, wenn es mindestens einen Weg mit nicht-monotoner Folge gibt 14. April 2024 58  Beispiel Schaltfunktion: a = e1e2  e1e3 Totzeitmodell: e11 e1 3 1 & e21 e2 2 e12 4 1 a e31 & e3 4 Strukturausdruck: a = e11e21  e12e31 14. April 2024 59  Strukturspezifisches KV-Diagramm Man sieht: Änderungen von e2 bzw. e3 breiten sich nur über einen Pfad aus. Änderungen von e1 breiten sich hingegen über zwei Pfade aus. e11 Strukturausdruck: 1 a = e11e21  e12e31 1 e12 1 1 1 1 e31 1 e21 Graue Felder: können nur während des Übergangs (e11  e12) eingenommen werden Weiße Felder: Felder der Funktion 14. April 2024 60  Strukturspezifisches KV-Diagramm Übergang (e3, e2, e1) : (1,1,0) (1,1,1) Mit Hilfe der Pfadvariablen ausgedrückt lautet dieser Übergang: (e31, e21, e12, e11) : (1,1,0,0) (1,1,1,1) Übergang wird im KV-Diagramm eingezeichnet: e11 e1 1 1 1 e 1 1 1 e 1 1 1 1 12 2 e31 e 1 3 e 21 14. April 2024 61  Strukturspezifisches KV-Diagramm Hier kann man die schon bei den Funktionshazards erprobte Methode zur Hazardbestimmung anwenden: Es sind zwei mögliche Wege zu erkennen, die eingeschlagen werden können: e11 e11 1 1 1 1 e12 e12 1 1 1 1 1 1 1 1 e31 e31 1 1 e21 e21 Kein Hazardfehler! Hazardfehler! => der Übergang ist hazardbehaftet (wie schon früher festgestellt) 14. April 2024 62  Zeitbedingungen für Hazardfehler e e11 11 1 1 1 1 e12 e12 1 1 1 1 1 1 1 1 e 31 e 31 1 1 Weg 2 e 21 Weg 1 e21 Es existieren 2 Wege. Weg 2 erzeugt einen Hazardfehler. Dieser Weg wird eingeschlagen, wenn sich erst e11 und dann e12 ändert => Der Hazardfehler tritt auf, wenn die Totzeit in Pfad e11 kleiner als die Totzeit in Pfad e12 ist. 14. April 2024 63  Zeitbedingungen für Hazardfehler Der Hazardfehler tritt auf, wenn die Totzeit in Pfad e11 kleiner als die Totzeit in Pfad e12 ist. e11 e1 3 1 & e21 e2 2 e12 4 1 a e31 & e3 4 Aus dem Totzeitmodell folgt: Totzeit e11: 3t Totzeit e12: 4t => Der Hazardfehler tritt immer auf 14. April 2024 64  Beheben von Hazards Funktionshazards: Funktionshazards können nicht behoben werden, da sie in der Schaltfunktion begründet sind. Einzige Möglichkeit: Vermeidung des Hazardfehlers durch die Wahl geeigneter Verzögerungszeiten. Strukturhazards: Strukturhazards können durch geeignete Veränderung der Struktur bei gleicher Schaltfunktion behoben werden. Behebung statischer Strukturhazards: Prinzip: Die beim Übergang konstant bleibenden Eingangsvariablen müssen in die Lage versetzt werden, das Ausgangssignal konstant zu halten. 14. April 2024 65  Beheben von Hazards Dies wird am einfachsten gewährleistet durch den Satz von Eichelberger: Ein Schaltnetz, das durch die Disjunktion aller Primimplikanten oder die Konjunktion aller Primimplikate einer gegebenen Funktion realisiert wird, ist frei von allen statischen Strukturhazards allen dynamischen Strukturhazards, falls nur eine Eingabevariable wechselt. Die Behebung dynamischer Strukturhazards mit Mehrvariablenwechsel ist erheblich schwieriger als die Behebung statischer Strukturhazards ! Problem: Die Behebung eines dynamischen Strukturhazards für einen Übergang kann einen Strukturhazard für einen anderen Übergang erzeugen. 14. April 2024 66  Spezielle Schaltnetze für die Rechnerarchitektur Ein Multiplexer/Demultiplexer ist ein Schaltnetz, welches eine Datenweiche darstellt. Multiplexer: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 67 Multiplexer/Demultiplexer Beispiel: 2:1 Multiplexer Funktionstafel: KV-Diagramm: e0 0 0 1 1 sel 0 1 1 0 e1 Schaltplan: Funktion: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 68 Multiplexer/Demultiplexer Demultiplexer arbeiten invers zu den Multiplexern. Sie verteilen einen Datenstrom auf mehrere auswählbare Kanäle. Demultiplexer finden oftmals Anwendung, um die Zahl der Anschlußpins zu begrenzen. In DRAMs beispielsweise wird der höherwertige und der niederwertige Teil der Adresse nacheinander auf den Adreßbus gelegt. Der Baustein muß dann die Signale intern demultiplexen und dem Spalten- bzw. Zeilendekoder zuführen. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 69 Multiplexer/Demultiplexer Beispiel: 1:2 Demultiplexer Funktionstafel: KV-Diagramm: e e 0 1 1 1 sel 1 1 sel 0 1 f0 f1 Schaltplan: Funktion: Der nicht beschaltete Ausgang wird mit dem Wert 1 belegt! Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 70 Multiplexer/Demultiplexer Datenwegschaltungen Multiplexer: 0 Eingangs- Datenweg- Ausgangs- datenwege n-1 schaltung datenweg Steuereingänge Decoder Demultiplexer: 0 Eingangs- Datenweg- Ausgangs- datenweg schaltung n-1 datenwege Steuereingänge Decoder Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 71 Multiplexer/Demultiplexer Anwendung: Ansteuerung Akku- Register 1 Register Register 2 ALU Register 3 Multiplexer Ansteuerung Demultiplexer Ergebnis- Ergebnis- register 1 register 2 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 72 Alternative: Busbasiert Datenbus Akku- Hilfs- Register register Multiplizierer Puffer- ALU register Ansteuerung Ergebnisbus Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 73 Buszugang Tri-State-Gatter: Ein Tri-State-Gatter besitzt die drei definierten Ausgangszustände 0,1 (abhängig vom Eingangssignal e) und einen hochohmigen Zustand z. Der Zustand z wird durch Aktivierung des Sperreingangs i (inhibit) erreicht. Funktionstafel: Schaltplan: e 1 a i Tri-State-Gatter werden immer dann verwendet, wenn mehrere Ausgänge, von denen nur einer aktiv sein darf, an eine Leitung angeschlossen werden sollen (z.B. Busleitungen). Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 74 Buszugang Unidirektionaler Buszugang i i 1 1 Daten- Daten- sender empfänger 1 1 i i 1 1 Daten- Daten- empfänger sender 1 1 Bus Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 75 Buszugang Bidirektionaler Buszugang Funktionstafel: Schaltplan: Tri-State-Gatter ae e 1 d a 1 i r & & d i 1 Schaltsymbol r 1 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 76 Buszugang Bidirektionaler Buszugang Einheit 1 Einheit 3 i i r r bidirektionaler Datenbus i r Einheit 2 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 77 Vergleicher (Komparator) Vergleicher sind Schaltungen, die insbesondere in Mikroprozessoren Verwendung finden um beispielsweise den notwendigen Vergleich für bedingte Sprunganweisungen durchzuführen. Vergleicher werden aber auch integriert in Schaltungen eingesetzt, z.B. zur Speicherauswahl oder für die Selektion von Ein-/Ausgabe-Geräten. Vergleich der 2 Booleschen Tupel X und Y: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 78 Vergleicher (Komparator) 1 Bit Vergleicher für Dualzahlen Der größer als bzw. kleiner als Vergleicher ist schaltungstechnisch aufwendiger als der Vergleich auf Identität. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 79 Addierer Ein Halbaddierer berechnet aus zwei 1-Bit Zahlen die Summen Si und den Übertrag Ci+1. Funktionstafel: Schaltplan: Funktionen: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 80 Addierer Ein Volladdierer berechnet aus drei 1-Bit Zahlen die Summe Si und den Übertrag Ci+1. Funktionstafel: Schaltplan: Funktionen: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 81  Addierer Ein n-Bit Ripple-Carry-Addierer entsteht durch die Kaskadierung von n-1 Volladdierern und einem Halbaddierer. Im schlimmsten Fall müssen für die Addition zweier n-Bit Zahlen alle Addierer nacheinander durchlaufen werden, bis der Übertrag Sn vorliegt. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 82  Addierer Carry-Select Addierer an-1 bn-1 an/2 bn/2 Ziel: Beschleunigung der Durchlaufzeit 0 n/2-Bit-Addierer an/2-1 bn/2-1 a0 b0 cn 0 s‘n-1 s‘n/2 an-1 bn-1 an/2 bn/2 n/2-Bit-Addierer 1 n/2-Bit-Addierer sn/2-1 s0 cn s“n-1 s“n/2 cn/2 sn-1 sn/2 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 83  Subtrahierer Die Differenz A-B (A,B  0) wird durch die Addition des 2-er Komplements B von B erreicht (A+( B)), welches auf die bitweise Negation von B zurückgeführt wird: Auftretende Überträge werden nicht berücksichtigt. Beispiel: 4-Bit (Vorzeichen und 3-Bit für die Zahlendarstellung) 0000 0 1111 -1 1110 -2...... 1001 -7 1000 -8 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 84 Subtrahierer Addierer/Subtrahierer (aus Volladdierern): Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 85  Subtrahierer Allgemeiner Vergleicher für Dualzahlen Der größer als bzw. kleiner als Vergleicher basiert auf einem Subtrahierer. Integrierter Vergleicher (Komparator) SN7485: a0 COMP a1 0 s0 a2 a0 a3 n-Bit-Subtrahierer b0 ≥1 & AB b0 b1 an-1 sn-1 b2 & A>B b3 bn-1 cn Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 86 Multiplizierer Schnelle Multiplizierer werden durch parallele Berechnung sämtlicher (dualer) Produktterme und anschließender Addition der Terme mit den richtigen Wertigkeiten implementiert. 𝑎 𝑏 ∗2 Es werden m2 viele AND-Gatter für die Bildung der Produktterme und m Addierer benötigt. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 87 Multiplizierer Beispiel: 3-Bit Multiplizierer Eingaben: Faktoren a und b Ausgabe: Produkt p = a  b Anschauliche Darstellung: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 88 Multiplizierer a 2 a 1 a 0 3-Bit Multiplizierer b 0 & & & Addierer b 1 & & & VA VA HA Addierer b 2 & & & VA VA HA Addierer p 5 p 4 p 3 p 2 p 1 p 0 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 89  Multiplizierer Für die Multiplikation zweier 4-Bit Dualzahlen existieren die beiden Standardbausteine SN74284 und SN74285. Der Baustein SN74285 berechnet den niederwertigen 4-stelligen Teil des Produktes, der SN74284 den höherwertigen Teil. Multiplikand Multiplikator 23 22 21 20 23 22 21 20 2D 2C 2B 2A 1D 1C 1B 1A 2D 2C 2B 2A 1D 1C 1B 1A SN74284 SN74285 z7 z6 z5 z4 z3 z2 z1 z0 27 26 25 24 23 22 21 20 Produkt Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 90