Schaltnetze und Schaltwerke Quiz

Automaten und Rechnerarchitekturen - Kapitel 2: Schaltnetze

• Sommersemester 2024: Vorlesung zu Automaten und Rechnerarchitekturen, Kapitel 2 befasst sich mit Schaltnetzen als Wiederholung
• Dozenten: Prof. Dr. Uwe Brinkschulte und apl. Prof. Dr. Mathias Pacher
• Inhalt: Definition von Schaltnetzen, Boolesche Funktionen, KV-Diagramme, 2-stufige Normalformen, Minimierung, Zeitverhalten, Hazards und spezielle Schaltnetze in der Rechnerarchitektur

Definition Schaltnetz

• Ein Schaltnetz realisiert eine Boolesche Funktion, enthält keine Rückführungen oder Speicherglieder
• Es hat rein kombinatorischen Charakter

Unterschied zu Schaltwerk

• Ein Schaltwerk realisiert eine Boolesche Funktion, enthält Rückführungen oder Speicherglieder
• Schaltwerke besitzen ein Gedächtnis

Boolesche Funktionen

• Definition: Eine Beziehung zwischen zwei Mengen, die jedem Element der Definitionsmenge genau ein Element des Wertebereichs zuordnet.
• Beispiele verschiedener Boolescher Funktionen einer Variablen (fo, f1, f2, f3) dargestellt in Tabellen und Graphen.
• Literale: x oder ¬x
• Negationen: ¬x = 1-x
• Boolesche Funktionen von zwei Variablen: Darstellung in Wahrheitstafeln, prominente Funktionen (AND, OR, NAND, NOR, Implikation, Äquivalenz, Antivalenz) und deren Infix-Schreibweisen.

Boolesche Funktionen von n Variablen

• Funktionstabelle mit 2n Zeilen, wobei jedes Element der Wahrheitswerte der Funktion entspricht
• Wf,i ∈ {0, 1}

Bemerkungen zu Booleschen Funktionen

• In der Infix-Schreibweise haben die Operatoren unterschiedliche Prioritäten: Negation am höchsten, Konjunktion größer als Disjunktion
• Oft werden Konjunktionsoperatoren in Booleschen Ausdrücken weggelassen (x0 ^ x1 = x0x1)
• Ä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.

Gesetze von DeMorgan

• Formulierung der Gesetze von DeMorgan für die Negation von logischen Operatoren (AND, OR) mit Wahrheitstafeln. Gleichungen für Negationen von Disjunktionen und Konjunktionen

Der Shannon'sche Entwicklungssatz

• Jede Boolesche Funktion kann nach einer Variablen entwickelt werden, indem diese durch Co-Faktoren (Co-Faktoren sind Funktionen, die die jeweilige Variable eliminieren) dargestellt werden.
• Anwendungsbeispiel zur Entwicklung einer Booleschen Funktion nach zwei Variablen (a, b)

Das AND-OR-NOT-System

• Jede Boolesche Funktion kann durch die Kombination der Operatoren AND, OR und NOT dargestellt werden, Antivalenz und Äquivalenz sind Spezialfälle
• Regeln zur Behandlung von Konstanten (x 0 = x, x1 = x)
• Vollständige Operatorsysteme (NAND und NOR)

Gatter

• Symbolische Darstellung von grundlegenden Gattern nach DIN (NOT, AND, NAND, OR, NOR, XOR, XNOR)
• Verwendung zur Realisierung von Schaltnetzen

KV-Diagramme

• Alternative zur Darstellung von Booleschen Funktionen.
• Karnaugh-Veitch-Diagramme, die für bis zu vier Variablen besonders praktikabel sind.
• Graphische Darstellung von Funktionstabellen mit Feldern für die logischen Funktionswerte

Konstruktion von KV-Diagrammen

• Induktive Erstellung für n Variablen durch Verdoppelung der (n-1) KV-Tafel mit Spiegelung
• Zuweisung von 0 oder 1 je nach Variable, die hinzugefügt werden

Konjunktionsterme/Minterme

• Eine konjunktive Verknüpfung von Literalen
• Jede Variable tritt höchstens einmal auf
• Ein Minterm ist ein Konjunktionsterm maximaler Länge (alle Variablen treten einmal auf)
• Es existiert genau eine Belegung, die einen spezifischen Minterm zu 1 macht

Minterme einer Schaltfunktion

• Ein Term M₁ ist ein Minterm einer Booleschen Funktion f, wenn ein bestimmten Belegung den Wert 1 zuweist

Disjunktionsterme/Maxterme

• Eine disjunktive Verknüpfung von Literalen.
• Jede Variable tritt höchstens einmal auf.
• Ein Maxterm ist ein Disjunktionsterm maximaler Länge, dessen inverse Form dem Minterm entspricht 

Implikant und Primimplikant

• Ein Implikant ist ein Konjunktionsterm, der, wenn alle Variablen auf 1 gesetzt werden, die gleiche Ausgabe wie die Funktion liefert.
• Ein Primimplikant ist ein Implikant, der nicht weiter reduziert/vereinfacht werden kann

Zweistufige Normalformen

• Disjunktive Normalform (DNF). Die DNF einer Schaltfunktion ist die Disjunktion aller ihrer Implikanten.
• Konjunktive Normalform (KNF). Die KNF einer Schaltfunktion ist die Konjunktion aller ihrer Implikate.

Optimierung zweistufiger Normalformen mit KV Diagrammen

• Vorgehensweise zur Minimierung von Schaltnetzen mittels KV-Diagrammen:
  • Ermittlung aller Primimplikanten
  • Auswahl minimaler Menge von Primimplikanten, um die Funktion korrekt zu beschreiben

Klassifizierung der Primimplikanten

• Kern-Primimplikanten: Überdecken mindestens einen Minterm, der von keinem anderen Primimplikanten überdeckt wird.
• Absolut eliminierbare Primimplikanten: werden von Kern-Primimplikanten vollständig überdeckt.
• Relativ eliminierbare Primimplikanten: überdecken nur mehrfach überdeckte Minterme.

Zeitliches Verhalten von Schaltnetzen

• Totzeitmodell: Einfaches Modell, das nur die Verzögerungen durch Gatter und Verbindungen berücksichtigt.
• Totzeitglied: Verzögerung an einem Element mit der zeitlichen Verschiebung

Hazards und Hazardfehler

• Hazardfehler: Mehrfache Änderungen des Ausgangssignals während eines Übergangs.
• Hazard: Die logisch-strukturelle Vorbedingung für einen Hazardfehler.
• Einteilung von Hazards in statische, dynamische und Funktions- und Strukturhazards

Verhalten bei Änderung der Eingabebelegung

• Ideales Schaltnetz: Ausgangssignal ändert sich nur einmal
• Reales Schaltnetz: Mehrfache Änderungen des Ausgangssignals sind möglich

Spezielle Schaltnetze

• Multiplexer/Demultiplexer: Datenweiche zur Auswahl von Eingängen.
• Tri-State-Gatter: Darstellung der Ein- und Ausgabe eines Buszuganges zur Steuerung mehrerer Eingaben und Ausgänge.
• unidirektionaler und bidirektionaler Buszugang: Richtung der Übertragung der Datenströme

Vergleicher (Komparator)

• Schaltungen zum Vergleichen von Zahlen (größer, kleiner, gleich).
• Aufbau und Funktion eines 1-Bit-Vergleichers
• Aufbau und Funktionsweise eines Halbaddierers und Volladdierers
• Aufbau und Funktionsweise eines n-Bit Ripple-Carry-Addierers
• Aufbau und Funktionsweise eines Carry-Select-Addierers (optimierter Aufbau für Adders)

Subtrahierer

• Berechnung der Differenz von Dualzahlen mittels 2er-Komplements
• Implementierung eines Subtrahierers mit Multiplexern und Volladdierern
• Genereller Vergleicher für Dualzahlen

Multiplizierer

• Schnelle Multiplikation durch parallele Produktberechnung und Addition
• Aufbau und Funktionsweise eines 3-Bit-Multiplizierers
• Standardbausteine (SN74284, SN74285) für die Multiplikation von Dualzahlen