Die rekursive, also wiederholte Anwendung der Shannon-Zerlegung dient zusammen mit zwischengeschalteten Reduktionsschritten wie der Extraktion doppelter und überdeckter Terme der Minimierung boolscher Funktionen, so dass sich diese durch möglichst einfache Formelausdrücke oder Decision Diagrams darstellen und auf minimaler Chip-Fläche realisieren lassen. Heuristiken sollen dabei Hinweise liefern wo, sprich bei welcher Eingabevariablen, die jeweils nächste Shannon-Zerlegung stattfinden soll. Durch die Shannon-Zerlegung entstehen aus einer Funktion jeweils zwei einfachere Subfunktionen, die eine Eingabevariable weniger besitzen. Die Heuristiken stellen keine exakte Minimierungsmethode dar. Im Gegensatz zur exakten und maximalen Minimierung z.B. nach dem Quine- McCluskey-Algorithmus, erreichen heuristische Verfahren geringere Reduktionsgrade. Zwar werden weniger Terme in den Formeln eingespart, dafür sind die heuristischen Verfahren aber wesentlich schneller und bei vielen Eingabevariablen das einzig Praktikable. Benchmarks in dieser Arbeit bestimmen die Einsparung an Formel-Termen, die Anzahl nötiger Rekursionsschritte und die benötigte Rechenzeit.
Die rekursive Shannon-Zerlegung ist ein sehr altes Verfahren. Das bekannteste Verfahren dazu war der Simplify-Algorithmus mit der Heuristik der Spaltung von Funktionen an der "most-binate" Position, für die die Summe an 0en und 1en einer Eingabespalte einer Wahrheitstafel – genauer: ihrem OnSet – maximal ist. Ein bekannteres heuristisches Verfahren, allerdings mit ganz anderer Vorgehensweise (Komplementbildung, Maximierung von Don't Cares, ...) ist Espresso (II), das auf Simplify folgte und Vorgänger für Verfahren wie SIS und ABC war, in denen es bis heute noch aufrufbar ist. Espresso war wohl auch das erste Verfahren, das im Gegensatz zu Simplify und den Heuristiken, die Gegenstand dieser Arbeit sind, mit Don't Cares in Ausgabevariablen umgehen kann.
Simplify, das in dieser Arbeit in C/C++ neu implementiert und durch Heuristiken 1-3 (Heuristik 0 ist die "most-binate"-Spaltenauswahl des Originals) und Benchmarkprogrammen ergänzt wurde, kennt dagegen nur 1en in den Ausgabevariablen. Es arbeitet also nur mit dem OnSet (denjenigen Zeilen von Wahrheitstafeln mit Ausgabe=1). Bei Heuristik 1 und 2 (2 = zufällig verkleinerter Input, sonst wie Heuristik 1) soll eine der Shannon-Teilfunktionen einen minimalen Definitionsbereich haben. [...]
Inhaltsverzeichnis
- Einleitung
- Grundlagen
- Darstellungen binärer Funktionen
- Shannon Zerlegung/Erweiterung
- Zerlegung und Reduktion boolscher Funktionen
- Benchmarks
- Implementierung
- Simplify-Algorithmus mit Heuristik 0
- Algorithmus im Überblick
- Funktion main()
- Funktionen simplify(), unate() und cofactor()
- Funktionen merge() und intersect()
- Funktion binate_select() zur Spaltenauswahl in Heuristik 0
- Funktionen unate_simplify() und contains()
- Heuristiken 1-3 in Simplify hinzufügen
- Heuristik 1 + 2 mit binate_select_12()
- Heuristik 3 mit binate_select_3(), ttUeberein() und vektorGleich()
- Benchmark-Programme
- Funktionen OnSet() und Offset()
- Funktion ttGen() und dec2bin()
- Funktionen benchmark() und zeit01MS()
- Funktionen write_pla(), read_pla() - eigene und von ABC, SIS
- Programme für Heuristik 2: TeilOnSet02(), benchmark22()
- Prüfung gegen ABC mit Funktion (On)Set Vergleich()
- Simplify-Algorithmus mit Heuristik 0
- Ergebnisse
- Vergleich zu David Eigens Benchmarks mit Heuristik 0
- Benchmarks zu Heuristiken 0, 1 und 3
- Benchmarks zu Heuristiken 2 (und 1)
- Benchmarks mit benchmark2() mit TeilOnSet0()
- Benchmarks mit benchmark22() mit TeilOnSet2()
- Auswertung und Ausblick
Zielsetzung und Themenschwerpunkte
Diese Masterarbeit befasst sich mit der Implementierung und Benchmarking von Heuristiken für die Shannon-Zerlegung von boolschen Funktionen. Ziel ist es, die Effizienz und Performance verschiedener Heuristikansätze in der Praxis zu evaluieren und ihre Stärken und Schwächen zu identifizieren.
- Implementierung und Vergleich von Heuristiken für die Shannon-Zerlegung
- Analyse der Performance und Effizienz verschiedener Heuristikansätze
- Evaluation der Auswirkungen von Heuristiken auf die Minimierung boolscher Funktionen
- Untersuchung der Rechenzeit und des Reduktionsgrades verschiedener Heuristiken
- Bewertung der Praktikabilität und Effektivität von Heuristik-basierten Ansätzen für die Minimierung boolscher Funktionen in realen Anwendungen.
Zusammenfassung der Kapitel
- Einleitung: Die Arbeit führt in das Thema der Minimierung von boolschen Funktionen ein und erläutert die Bedeutung kompakter Darstellungen für die Hardwareimplementierung. Die Shannon-Zerlegung wird als ein Ansatz zur Minimierung von boolschen Funktionen vorgestellt, und es wird erläutert, dass die Reihenfolge der Zerlegungen einen erheblichen Einfluss auf die Größe der resultierenden Funktion hat.
- Grundlagen: Dieses Kapitel behandelt die Grundlagen der Darstellung von binären Funktionen und erläutert die Shannon-Zerlegung sowie deren Anwendung zur Reduktion von boolschen Funktionen. Es werden auch verschiedene Ansätze für Benchmarks zur Evaluierung von Minimierungsverfahren vorgestellt.
- Implementierung: Dieses Kapitel beschreibt die Implementierung des Simplify-Algorithmus, welcher die Heuristik 0 verwendet, sowie die Erweiterung um drei zusätzliche Heuristiken (Heuristiken 1-3). Die Implementierung wird detailliert erläutert, einschließlich der einzelnen Funktionen und Algorithmen.
- Ergebnisse: Dieses Kapitel präsentiert die Ergebnisse der durchgeführten Benchmarks. Die Performance der verschiedenen Heuristiken wird verglichen und analysiert. Die Ergebnisse werden auch im Kontext der Literatur und bekannter Verfahren diskutiert.
Schlüsselwörter
Shannon-Zerlegung, boolsche Funktionen, Minimierung, Heuristiken, Benchmarks, Implementierung, Simplify-Algorithmus, Wahrheitstafeln, Don't Cares, OnSet, Offset, Reduktion, Termbereinigung, Rechenzeit, Hardwareimplementierung.
- Arbeit zitieren
- Rainer Stickdorn (Autor:in), 2017, Verschiedene Shannon-Zerlegungen und deren Leistungsfähigkeit in Benchmarks, München, GRIN Verlag, https://www.grin.com/document/433442
