Verschiedene Shannon-Zerlegungen und deren Leistungsfähigkeit in Benchmarks

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. Esp