Kompakte Darstellung und effiziente Manipulation Boolescher Funktionen ist in vielen Anwendungen, insbesondere des computergestützten Schaltkreisentwurfes, eine zentrale Aufgabe. Im Hinblick auf Anwendungen ist es dabei von großem Interesse, einen guten Kompromiß zwischen oben angesprochener Kompaktheit und Effizienz zu finden. Besonderes Interesse finden in diesem Zusammenhang die von Bryant 1985 eingeführten Ordered Binary Decision Diagrams (OBDDs): Sie werden insbesondere in den Bereichen Verifikation und Logiksynthese auch industriell erfolgreich eingesetzt. Mit wachsender Zahl von Anwendungen sind auch inhärente Nachteile sichtbar geworden und haben insbesondere in den letzten drei Jahren zu Weiterentwicklungen des Basiskonzeptes geführt. Dabei hat sich eine ganze Familie von graphenbasierten Funktionsdarstellungen entwickelt, die je nach Anwendungsgebiet Vorteile gegenüber den klassischen OBDDs bieten. In diesem Buch wird eine Klassifizierung der verschiedenen Ansätze sowohl aus theoretischer wie auch praktischer Sicht gegeben. Es werden diverse Datenstrukturen für Boolesche (und ganzzahlige) Funktionen vorgestellt und deren Vor- und Nachteile untersucht. Das Buch wendet sich sowohl an den Einsteiger als einführende Darstellung als auch an den erfahrenen Benutzer. Es werden verschiedene Anwendungen diskutiert, die dem Leser ein tieferes Verständnis der Materie ermöglichen. "... The monograph is well written and the reader gets a good introduction into the subject." I.Wegener. Statistics & Decisions, München

Autorentext
Prof. Dr. Bernd Becker ist Inhaber des Lehrstuhls für Rechnerarchitektur an der Albert-Ludwigs-Universität Freiburg. Seine Hauptarbeitsgebiete sind Entwurf, Verifikation und Test von Schaltungen und Systemen. Seine Arbeiten werden unterstützt durch umfangreiche Drittmittelprojekte sowohl von DFG, BMBF als auch von Geldgebern direkt aus der Industrie. Zur Zeit ist er stellvertretender Sprecher des SFB Transregios der DFG Automatic Verification and Analysis of Complex Systems.

Klappentext

Integrierte Schaltkreise haben in den vergangenen Jahren massiv unsere Umwelt verandert. Der Computer hat in vielen Lebensbereichen Zugang gefunden und ist dort inzwischen unersetzlich. Auch bei vielen Dingen des taglichen Lebens, wie z.B. Fernsehern, Radios und Kiichengeraten, werden Mikrochips verstarkt einge setzt. Die damit verbundenen "Bequemlichkeiten" werden als selbstverstandlich angenommen und fiir die nachste Generation werden weitere Fortschritte gefor dert bzw. fast zwingend erwartet. Dieser Trend verstarkt sich, wenn man an sogenannte High Tech-Bereiche denkt, wie sie sich z.B. hinter Schlagworten wie Video Conferencing, Virtual Reality, Information Highways und Globale K ommu nikationsnetzwerke verbergen. Allgemein sind Steigerung der Rechenkapazitaten und Performanzoptimierung in VLSI-Systemen typische Anforderungen, die von Seiten der Nutzer und Anwender an die Systementwickler gestellt werden. Durch technologische Fortschritte in den vergangenen Jahren sind diese Wiinsche prinzipiell erfiillbar. Allerdings konnen die Moglichkeiten nur umgesetzt werden, wenn parallel mit steigender Integrationsdichte auch die "Fahigkeiten" der Werk zeuge wachsen, die den Chipentwurf notwendigerweise unterstiitzen miissen. In diesem Zusammenhang sei die Entwicklung der Intel-Prozessoren angefiihrt: Der Intel 8080-Prozessor aus dem Jahre 1970 bestand aus nur 5.000 Transistoren. Der von Intel im Jahre 1995 vorgestellte Prozessor PENTIUM PRO hatte schon mehr als 5 Millionen Transistoren. Diese Zahlen verdeutlichen die gestiegenen Anforde rungen einerseits und die Notwendigkeit von Werkzeugen, die den Systementwurf unterstiitzen, andererseits. Es ist nicht moglich, ein Design von mehr als 5 Mil lionen Komponenten ohne (maschinelle) Entwurfsunterstiitzung zu iiberblicken.

Inhalt
1 Einleitung.- 2 Decision Diagrams.- 2.1 Einleitung.- 2.2 Boolesche Funktionen, Pseudo-Boolesche Funktionen.- 2.3 Grundlagen.- 2.4 Restriktionen.- 2.5 Reduktion.- 2.6 Aufgaben.- 3 Bit-level Decision Diagrams.- 3.1 Einleitung.- 3.2 Allgemeine Bemerkungen.- 3.3 Binary Decision Diagrams.- 3.4 Functional Decision Diagrams.- 3.5 Kronecker Functional Decision Diagrams.- 3.6 Komplementierte Kanten.- 3.7 Aufgaben.- 4 Word-level Decision Diagrams.- 4.1 Einleitung.- 4.2 Kantengewichte.- 4.3 Multi-Terminal Binary Decision Diagrams.- 4.4 Edge-Valued Binary Decision Diagrams.- 4.5 Multiplicative Binary Moment Diagrams.- 4.6 Kronecker Multiplicative Binary Moment Diagrams.- 4.7 Aufgaben.- 5 Darstellungsgröße von Decision Diagrams.- 5.1 Einleitung.- 5.2 Bit-level Decision Diagrams.- 5.3 Word-level Decision Diagrams.- 5.4 Überblick.- 5.5 Aufgaben.- 6 Algorithmen für Decision Diagrams.- 6.1 Einleitung.- 6.2 Auswertung und Erfüllbarkeit.- 6.3 Syntheseoperationen.- 6.4 Minimieren von DDs.- 6.5 Aufgaben.- 7 Implementierung.- 7.1 Einleitung.- 7.2 Ein einfaches BDD-Paket.- 7.3 Speicherverwaltung.- 7.4 Verfügbare Pakete.- 7.5 Aufgaben.- 8 Experimentelle Ergebnisse.- 8.1 Einleitung.- 8.2 Bit-level Decision Diagrams.- 8.3 Word-level Decision Diagrams.- 8.4 Aufgaben.- 9 Ausblick und weitere Anwendungen.- 9.1 Einleitung.- 9.2 Logiksynthese.- 9.3 Testen.- 9.4 Verifikation.- 9.5 Ausblicke.- 10 Weitere Ansätze mit Decision Diagrams.- 10.1 Einleitung.- 10.2 Zero-Suppressed-BDDs.- 10.3 Freie Decision Diagrams.- 10.4 Mehrfachlesen von Variablen.- 10.5 Mehrwertige Decision Diagrams.- 10.6 Decision Diagrams mit Operationsknoten.- 10.7 Aufgaben.- 11 Schlußbemerkung.