Kapitel 2 - Schaltungstechnik II

Wir lernen zunächst zwei Verfahren kennen, um minimale Darstellungen von Booleschen Funktionen als Sum-of-Products oder Product-of-Sums zu finden. Karnaugh-Veitch-Diagramme bieten dabei eine eher visuell-anschauliche Methode, die sich aber nur für bis zu maximal sechs, eher vier Variablen gut eignet. Das Verfahren nach Quine-McCluskey ist systematischer, aber auch weniger gut lesbar, dafür algorithmisch direkt umsetzbar. Zur Realisierung der SOP-Darstellungin Hardware können z.B. programmierbare Logikarrays verwendet werden, um mehrere solche Funktionen in einem Chip unterzubringen. Wir schauen uns daher die Funktionsweise eines solchen Bauteils bis hin zur Transistorebene an. Schließlich geben wir einen Überblick der Hardware-Beschreibungssprache (HDL) der Hack-Architektur, unserer Simulationsumgebung für Experimente mit Logikgattern.

Inhalt

Abschnitt 1 - Minimierung Boolescher Funktionen mit Karnaugh-Veitch-Diagrammen

Folien 1-29

Ziel des ersten Vorlesungsdrittels ist es, einen möglichst einfachen äquivalenten Ausdruck für eine gegebene Boolesche Funktion zu gewinnen. Wir zeigen zunächst, daß man Äquivalenz sowohl durch Umformungen in der Booleschen Algebra (syntaktisch) als auch durch Vergleich der Wertetabellen (semantisch) zeigen kann. Die Suche nach einer minimalen Form durch syntaktische Vereinfachungen hat den Nachteil, daß es nicht systematisch ist und nicht garantiert ist, daß man das Ziel erreicht. In diesem Abschnitt wird das Verfahren von Karnaugh-Veitch vorgestellt, daß eine "graphisch-visuelle Minimierung" durch eine geeignete Anordnung der Wertetabelle ermöglicht.

Wir zeigen, dass bei einer Anordnung der Variablenbelegungen nach einem Gray-Code das Zusammenfassen von $2^k$ Einsen dazu führt, daß in dem entsprechenden Term $k$ Variablen eliminiert werden. Eine minimale Überdeckung aller Einsen durch maximale Zusammenfassungen dieser Art liefert den minimierten Ausdruck für die Funktion. Mit Hilfe der Dualität der Gleichungen in der Booleschen Algebra kann stattdessen auch eine minimale Überdeckung der Nullen in der Ausgabe durch maximale Zusammenfassungen von Nullen gewählt werden. Als abschließendes Beispiel aus der Praxis schauen wir uns die Minimierung der Ansteuerungsfunktionen für eine Sieben-Segment-Anzeige an.


Index

00:00 Einleitung, Kapitelüberblick
05:10 Vorbemerkung: Semantische und syntaktische Äquivalenz
14:30 Minimierung von Ausdrücken durch geschickte Äquivalenzumformungen
17:00 Konstruktion des Karnaugh-Veitch Diagramms, Gray-Code
28:00 Zusammenfassen von zwei benachbarten Einsen eliminiert eine Variable
35:11 Optional: Bemerkungen zur Topologie
39:24 Zusammenfassen von $2^k$ Einsen eliminiert $k$ Variablen
45:19 Bedingungen an die Zusammenfassungen (Kantenlänge ist Zweierpotenz, Maximalität)
47:50 Karnaugh-Veitch Minimierungsalgorithmus
55:55 Duale Konstruktion der Minimierung durch Zusammenfassen von Nullen
62:10 Praktisches Beispiel: Sieben-Segment-Anzeige
66:45 Minimierung der Funktion für das Segment $a$ der Anzeige mit Karnaugh-Veitch
70:33 Mehrstellige Anzeige, Notwendigkeit von Minimierungsverfahren für mehr Variablen


Abschnitt 2 - Minimierung Boolescher Funktionen nach Quine-McCluskey

Folien 29-40

Im Vergleich zu Karnaugh-Veitch ist das Minimierungsverfahren von Quine-McCluskey deutlich systematischer und funktioniert für eine beliebige Anzahl Variablen. Die Terme der Normalform werden in einer Tabelle nach und nach zu sogenannten Implikanten zusammengefasst. An die Stelle der maximalen Vereinigungen treten die Primimplikanten, welches Implikanten sind, die nicht mehr zusammengefasst werden können. Schließlich sucht man eine Auswahl von Primimplikanten, welche alle Minterme der Normalform abdecken, entsprechend der Abdeckung aller Einsen im Karnaugh-Veitch Diagramm. Wir lernen schließlich noch Petricks Algorithmus kennen, welcher helfen kann, eine minimale Abdeckung durch Primimplikanten mit Hilfe einer Heuristik näherungsweise zu finden. Dies ist allerdings im Allgemeinen ein Problem, das nur durch vollständige Suche gelöst werden kann.


Index

00:00 Idee des Verfahrens
04:40 Aufstellen der Tabellen mit den Implikanten
12:40 Markieren der Primimplikanten
17:45 Primimplikantentabelle, Abdeckung der Minterme und Ergebnis
26:30 Vergleich mit Karnaugh-Veitch am Beispiel
29:10 Petricks Algorithmus zur Suche einer minimalen Abdeckung durch Primimplikanten


Abschnitt 3 - Programmierbare Logikarrays (PLAs)

Folien 41-53

PLAs stellen eine bestimmte Hardwarestruktur bereit, welche fest programmiert werden kann, um bestimmte boolesche Funktionen zu implementieren. Diese müssen zunächst als Sum of Products (SOP), also z.B. in der disjunktiven Normalform gegeben sein. Das PLA wird dann durch Trennen der nicht verwendenten Literale und Konjunktionen eingerichtet. In CMOS-Hardware wird üblicherweise mit NOT/NOR oder NAND/NOR-Logik gearbeitet. Wir schauen uns daher an, wie man die SOP-Darstellung entsprechend umwandeln kann, und wie die eigentliche Hardware dann auf Transistorebene aussieht.


Index

00:00 Einleitung, Idee und Struktur der PLAs
02:30 Beispiel: zu implementierende Funktion und Minimierungsergebnis
07:05 Implementation durch spezialisierte Gatter vs. Standardstruktur
09:55 Programmierung durch Trennen von Verbindungen, mehrere Outputs
17:30 Umwandlung der SOP in NOR-NOT-Darstellung
25:10 Realisierung in der CMOS-Technik
34:35 Beispiel für einen komkreten Chip, moderne Erweiterungen


Abschnitt 4 - Hardware-Beschreibungssprache (HDL) der Hack-Plattform

Folien 54-68

Wir schauen uns im Überblick die Elemente der Hardware-Beschreibungssprache der Hack-Plattform an. Diese kurze Tour kann jedoch natürlich nicht die Beschäftigung mit der Dokumentation und der bereitgestellten Software ersetzen.


Index

00:00 Motivation: Manuelle Hardware-Experimente vs. Hardware-Simulation
06:45 Beschreibung der Schnittstelle und Implementation eines AND-Gatters in HDL
13:00 Zweites Beispiel für die Gatterimplementation: XOR-Gatter in HDL
15:37 Simulation der Gatter in der grafischen Benutzeroberfläche des Hardware-Simulators
16:35 Erinnerung: Begleitbuch und Links auf die Software
18:05 Kapitelzusammenfassung und Ausblick
19:41 Vortrag zu Ende, aber Rest versehentlich nicht geschnitten