Verschiedene Shannon-Zerlegungen und deren Leistungsfähigkeit in Benchmarks

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()
• 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.