Ebook: Graphenbasierte Funktionsdarstellung: Boolesche und Pseudo-Boolesche Funktionen

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

---

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

---

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
Content:
Front Matter....Pages 1-12
Einleitung....Pages 13-17
Decision Diagrams....Pages 19-35
Bit-level Decision Diagrams....Pages 37-50
Word-level Decision Diagrams....Pages 51-58
Darstellungsgr??e von Decision Diagrams....Pages 59-97
Algorithmen f?r Decision Diagrams....Pages 99-129
Implementierung....Pages 131-145
Experimentelle Ergebnisse....Pages 147-159
Ausblick und weitere Anwendungen....Pages 161-171
Weitere Ans?tze mit Decision Diagrams....Pages 173-180
Schlu?bemerkung....Pages 181-181
Back Matter....Pages 183-200

---

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
Content:
Front Matter....Pages 1-12
Einleitung....Pages 13-17
Decision Diagrams....Pages 19-35
Bit-level Decision Diagrams....Pages 37-50
Word-level Decision Diagrams....Pages 51-58
Darstellungsgr??e von Decision Diagrams....Pages 59-97
Algorithmen f?r Decision Diagrams....Pages 99-129
Implementierung....Pages 131-145
Experimentelle Ergebnisse....Pages 147-159
Ausblick und weitere Anwendungen....Pages 161-171
Weitere Ans?tze mit Decision Diagrams....Pages 173-180
Schlu?bemerkung....Pages 181-181
Back Matter....Pages 183-200
....