Schaltnetze und Boolesche Funktionen

Automaten und Rechnerarchitekturen - Kapitel 2: Schaltnetze (Wiederholung)

• Das Kapitel behandelt Schaltnetze, welche Boolesche Funktionen realisieren, die keine Rückführungen oder Speicherglieder enthalten. Schaltnetze haben einen rein kombinatorischen Charakter. Schaltwerke hingegen realisieren Boolesche Funktionen mit Rückführungen und Speichergliedern und verfügen über ein Gedächtnis.

• Der Inhalt des Kapitels umfasst die Definition von Schaltnetzen, Boolesche Funktionen, KV-Diagramme, 2-stufige Normalformen, Minimierung, Zeitverhalten, Hazards und spezielle Schaltnetze (z. B. Multiplexer/Demultiplexer) für die Rechnerarchitektur.

Boolesche Funktionen

• Eine Funktion ist eine Beziehung zwischen zwei Mengen, die jedem Element der Definitionsmenge genau ein Element des Wertebereiches zuordnet.

• Alle Booleschen Funktionen einer einzelnen Variablen sind aufgelistet (fo, f1, f2, f3).

• Literale sind Variablen in der Booleschen Algebra.

Boolesche Funktionen von zwei Variablen

• Eine Tabelle aller Booleschen Funktionen von zwei Variablen (x0, x1) und deren Beziehungen ist aufgeführt (fo bis f15).

• Es werden prominente Funktionen von zwei Variablen mit ihrer Bedeutung und ihrer Infix-Schreibweise aufgeführt (z. B. Konjunktion, Disjunktion, NAND, NOR, Implikation, Äquivalenz, Antivalenz).

Bemerkungen zu Booleschen Funktionen

• Die in der Infix-Schreibweise verwendeten Booleschen Operatoren entstammen der Booleschen Algebra.

• Die Negation besitzt die höchste Priorität, gefolgt von der Konjunktion und dann der Disjunktion.

• Oft wird der Konjunktionsoperator in Booleschen Ausdrücken weggelassen.

Boolesche Funktionen von n Variablen

• Zur Darstellung Boolescher Funktionen in n Variablen können Funktionstafeln verwendet werden.

• Eine Funktionstabelle hat 2ⁿ Zeilen.

Bemerkungen

• Es existieren 2ⁿ verschiedene Funktionen von n Variablen, wobei jede Funktionsspalte 2n Zeilen hat.

Boolesche Algebra

• Die Axiome der Booleschen Algebra, wie z. B. Kommutativgesetz, Assoziativgesetz und Distributivgesetz, sind aufgeführt.

• Identityelemente und Inverselemente und Folgerungen sind ebenfalls aufgeführt.

Gesetze von DeMorgan

• Die Gesetze von DeMorgan zur Umformung von Booleschen Ausdrücken sind aufgelistet.

Der Shannon'sche Entwicklungssatz

• Jede Boolesche Funktion kann durch eine Variable und die entsprechenden Co-Faktoren dargestellt werden.

Das AND-OR-NOT-System

• Jede Boolesche Funktion kann mittels der Operatoren AND, OR und NOT dargestellt werden.

Vollständige Operatorsysteme

• Neben AND-OR-NOT gibt es weitere vollständige Operatorsysteme, die alle Booleschen Funktionen darstellen können, z. B. NAND und NOR.

Gatter

• Für die Implementierung von Booleschen Funktionen gibt es Gatter mit entsprechenden DIN-Symbolen.

KV-Diagramme

• KV-Diagramme (Karnaugh-Veitch-Diagramme) sind eine graphische Darstellung von Booleschen Funktionen, die zur Optimierung verwendet werden (für bis zu 4 Variablen).

Konstruktion von KV-Diagrammen

• Die Konstruktion von KV-Diagrammen erfolgt induktiv durch Verdopplung und Spiegelung.

Konjunktionsterme

• Konjunktionsterme sind konjunktive Verknüpfungen von Literalen.

• Jedes Literal taucht höchstens einmal auf.

Minterm

• Ein Minterm ist ein Konjunktionsterm maximaler Länge.

• Es kommt in Booleschen Funktionstafeln und KV-Diagrammen vor. In einer Funktionstabelle und im KV-Diagramm ist jedem Minterm genau eine Zeile oder ein Feld zugeordnet.

Minterme einer Schaltfunktion

• Ein Term Mi ist ein Minterm einer Booleschen Funktion, wenn für die Belegung, für die auch M_i den Wert 1 annimmt.

Minterme

• Minterme sind in Funktionstafeln und KV-Diagrammen notiert.

• Die duale Interpretation der 1-Belegung entspricht der Zeilennummer in der Funktionstabelle.

Disjunktionsterme

• Disjunktionsterme sind disjunktive Verknüpfungen von Literalen.

• Jede Variable taucht höchstens einmal auf.

Maxterm

• Ein Maxterm ist ein Disjunktionsterm maximaler Länge (analog zum Minterm).

Minterme und Maxterme in einer Funktionstabelle

• Beispiele für Minterme und Maxterme in einer Funktionstabelle.

Implikant und Primimplikant

• Ein Implikant ist ein Konjunktionsterm, der die Funktion impliziert.

• Ein Primimplikant ist ein Implikant, der nicht mehr verkürzbar ist.

Beispiel

• Beispiele illustrieren die Anwendung der Prinzipien.

Implikat und Primimplikat

• Ein Implikat von f ist ein Disjunktionsterm, der f impliziert. (I = 0 => f = 0)

• ein Primimplikat ist ein Implikant von , der nicht mehr verkürzbar ist.

Zweistufige Normalformen

• Disjunktive Normalform (DNF): Die DNF einer Schaltfunktion ist die Disjunktion von Konjunktionstermen.

• Konjunktive Normalform (KNF): Die KNF einer Schaltfunktion ist die Konjunktion von Disjunktionstermen.

Optimierung zweistufiger Normalformen mit KV-Diagrammen

• Die Methode zur Minimierung von Schaltnetzen basiert stark auf der Intuition des Schaltungsentwicklers.

Klassifizierung der Primimplikanten

• Kern-Primimplikanten
• Absolut eliminierbare Primimplikanten
• Relativ eliminierbare Primimplikanten

Minimale Normalform

• Satz: Die minimale Normalform besteht nur aus Kern- und relativ eliminierbaren Primimplikanten.

Beispiel – Minimale Normalform

• Beispiele veranschaulichen die Minimierung von Schaltnetzen anhand des KV-Diagramms.

Zeitliches Verhalten von Schaltnetzen

• Einfaches Modell: Totzeitmodell, das Verzögerungen durch Gatter und Leitungen berücksichtigt.

Totzeitglied

• Das Verhalten einer binären Größe hinter einem Totzeitglied ist zeitlich um die Totzeit verschoben.

Totzeitmodell eines Inverters

• Beispiele erläutern das Totzeitmodell anhand eines Inverters.

Eigenschaften von Totzeiten

• Addierbarkeit und Durchschiebbarkeit von Totzeiten.

Trennung von Verknüpfungs- und Verzögerungsteil

• Trennung von Verknüpfungs- und Verzögerungseffekten in Schaltnetzen.

Pfadvektor und Strukturausdruck

• Pfadvektor und Strukturausdruck.

Alternative Methode zu Pfadvektor und Strukturausdruck

• Alternative Methode zur Darstellung von Schaltnetzstrukturen.

Hazards und Hazardfehler in Schaltnetzen

• Hazardfehler in Schaltnetzen.

Verhalten bei Änderung der Eingabebelegung

• Verhalten von Ideal- und Real-Schaltnetzen bei Änderungen der Eingabe.

Hazardfehler - Hazard

• Hazardfehler und Hazard, als logisch-strukturelle Bedingungen anhand der Funktion und der Struktur des Schaltnetzes.

Beispiel

• Beispiele für Hazards und deren Analyse.

Funktionshazards-Definition

• Definition von statischen Hazards.
• Definition von dynamischen Hazards.

Funktionshazard

• Erklärung und Beispiele von Funktionshazards.

Analyse von Hazards

• Methode für die Analyse von Hazards in KV-Diagrammen.

Erkennen eines Funktionshazards

• Vorgehensweise zur Hazardanalyse anhand des KV-Diagramms.

Erkennen eines Strukturhazards

• Vorgehensweise zur Erkennung von Strukturhazards anhand des Schaltnetzes, in Bezug auf die Pfade.

Beispiel

• Beispiele für die Anwendung der Hazardanalyse.

Zeitbedingungen für Hazardfehler

• Beispiele und Bedingungen, dass der Hazardfehler auftritt.

Beheben von Hazards

• Möglichkeiten zur Behebung von Funktions- und Strukturhazards.

Spezielle Schaltnetze für die Rechnerarchitektur

• Multiplexer und Demultiplexer als Datenweichen.

Multiplexer/Demultiplexer

• Funktionsweise und deren Verwendung.

Multiplexer/Demultiplexer – Datenwegschaltungen

• Funktion und Verwendung von Multiplexern und Demultiplexern in Datenwegschaltungen.

Multiplexer/Demultiplexer – Anwendung

• Anwendungsverispiele für Multiplexer und Demultiplexer, z. B. in Rechnerarchitekturen.

Alternative: Busbasiert

• Beschreibung der Busbasierten Datenverarbeitung.

Buszugang

• Tri-State-Gatter
• Unidirektionaler Buszugang
• Bidirektionaler Buszugang

Vergleicher (Komparator)

• Funktion und Verwendung von Vergleichern.

Addierer

• Halbaddierer und Volladdierer
• Arithmetische Operationen

Subtrahierer

• Subtraktion durch 2er Komplement
• Weitere Verfahren (wie Addierer/Subtrahierer)
• Allgemeine Vergleicher

Multiplizierer

• Schnelle Multiplizierer

• 3-Bit Multiplizierer

• Beispiele und Standardbausteine.

In diesem Quiz werden grundlegende Konzepte von Schaltnetzen und Schaltwerken behandelt. Es wird auch auf Boolesche Funktionen und ihre Minimierung mittels KV-Diagrammen eingegangen. Testen Sie Ihr Wissen über verschiedene Operatoren und Grundfunktionen in der digitalen Logik.