Verschiedene Shannon-Zerlegungen und deren Leistungsfähigkeit in Benchmarks (PDF)

Masterarbeit aus dem Jahr 2017 im Fachbereich Informatik - Angewandte Informatik, Note: 1.4, FernUniversität Hagen (Fachbereich Mathe, Informatik, E-Technik), Veranstaltung: Abschlussarbeit im MSc Praktische Informatik, Sprache: Deutsch, Abstract: 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. [...]