Sie sind hier
E-Book

Verschiedene Shannon-Zerlegungen und deren Leistungsfähigkeit in Benchmarks

Shannon-Zerlegung, Benchmarks für verschiedene heuristische Verfahren zur Vereinfachung von boolschen Funktionen

AutorRainer Stickdorn
VerlagGRIN Verlag
Erscheinungsjahr2018
Seitenanzahl93 Seiten
ISBN9783668755109
FormatPDF
Kopierschutzkein Kopierschutz
GerätePC/MAC/eReader/Tablet
Preis36,99 EUR
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. [...]

Kaufen Sie hier:

Horizontale Tabs

Blick ins Buch

Weitere E-Books zum Thema: Programmiersprachen - Softwareentwicklung

ASP.NET Shortcut

E-Book ASP.NET Shortcut
Format: PDF

Shortcut-Tipps für ASP.NET-Profis Die neue .NET-Version der Active Server Pages stellt eine Umgebung zur Entwicklung von Web-Applikationen im .NET-Framework bereit. Viele aus der Desktop-…

ASP.NET Shortcut

E-Book ASP.NET Shortcut
Format: PDF

Shortcut-Tipps für ASP.NET-Profis Die neue .NET-Version der Active Server Pages stellt eine Umgebung zur Entwicklung von Web-Applikationen im .NET-Framework bereit. Viele aus der Desktop-…

ASP.NET Shortcut

E-Book ASP.NET Shortcut
Format: PDF

Shortcut-Tipps für ASP.NET-Profis Die neue .NET-Version der Active Server Pages stellt eine Umgebung zur Entwicklung von Web-Applikationen im .NET-Framework bereit. Viele aus der Desktop-…

Programmieren lernen in PHP 5

E-Book Programmieren lernen in PHP 5
Format: PDF

Mit der Version 5 erreicht PHP einen bemerkenswerten Reifegrad, der PHP zu einer festen Größe in der Welt der Webprogrammierung macht. Gerade die leichte Erlernbarkeit macht PHP zur idealen…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Weitere Zeitschriften

BEHINDERTEPÄDAGOGIK

BEHINDERTEPÄDAGOGIK

Für diese Fachzeitschrift arbeiten namhafte Persönlichkeiten aus den verschiedenen Fotschungs-, Lehr- und Praxisbereichen zusammen. Zu ihren Aufgaben gehören Prävention, Früherkennung, ...

BONSAI ART

BONSAI ART

Auflagenstärkste deutschsprachige Bonsai-Zeitschrift, basierend auf den renommiertesten Bonsai-Zeitschriften Japans mit vielen Beiträgen europäischer Gestalter. Wertvolle Informationen für ...

Computerwoche

Computerwoche

Die COMPUTERWOCHE berichtet schnell und detailliert über alle Belange der Informations- und Kommunikationstechnik in Unternehmen – über Trends, neue Technologien, Produkte und Märkte. IT-Manager ...

die horen

die horen

Zeitschrift für Literatur, Kunst und Kritik."...weil sie mit großer Aufmerksamkeit die internationale Literatur beobachtet und vorstellt; weil sie in der deutschen Literatur nicht nur das Neueste ...

building & automation

building & automation

Das Fachmagazin building & automation bietet dem Elektrohandwerker und Elektroplaner eine umfassende Übersicht über alle Produktneuheiten aus der Gebäudeautomation, der Installationstechnik, dem ...

Evangelische Theologie

Evangelische Theologie

Über »Evangelische Theologie« In interdisziplinären Themenheften gibt die Evangelische Theologie entscheidende Impulse, die komplexe Einheit der Theologie wahrzunehmen. Neben den Themenheften ...