دانلود کتاب Applications of Zero-Suppressed Decision Diagrams (Synthesis Lectures on Digital Circuits and Systems)

فهرست مطالب :

Contents
Preface
Acknowledgments
1 Introduction to Zero-Suppressed Decision Diagrams Alan Mishchenko
Chapter Summary
1.1 Introduction
1.2 Definitions
1.2.1 BDD and ZDD Reduction Rules
1.3 Comparing BDDs and ZDDs
1.3.1 Boolean Functions
1.3.2 Sets of Subsets
1.3.3 Cube Covers
1.4 Basic ZDD Procedures
1.4.1 Procedures Working with Functions
1.4.2 Procedures Working with Covers
1.4.3 Generic Structure of a Recursive ZDD Procedure
1.5 Manipulation of Sets
1.5.1 A Case Study of the CUDD Source Code
1.6 Manipulation of Cube Covers
1.7 Mixed ZDD/BDD Applications
1.7.1 Computation of the Set of All Primes
1.7.2 Computation of an Irredundant SOP
1.8 A List of Published ZDD Applications
1.9 Conclusions
1.10 Acknowledgements
1.11 Appendix A
1.12 Appendix B
1.13 Exercises
References
2 Efficient Generation of Prime Implicants and Irredundant Sum-of-Products Expressions Tsutomu Sasao
Chapter Summary
2.1 Logical Expressions
2.2 Monotone and Unate Functions
2.3 Prime Implicants
2.4 Generation of All the Prime Implicants
2.5 Generation of Irredundant Sum-of-Products Expressions
2.6 Morreale’s Algorithm
2.7 Conclusion and Comments
2.8 Exercises
References
3 .e Power of Enumeration–BDD/ZDD-Based Algorithms for Tackling Combinatorial Explosion Shin-ichi Minato
Chapter Summary
3.1 Introduction
3.2 BDDs/ZDDs and Graph Enumeration
3.3 Frontier-Based Method
3.3.1 Knuth’s SimPath Algorithm
3.3.2 Frontier-Based Method for Various Problems
3.3.3 Recent Topics on the Path Enumeration Problem
3.4 Conclusion
3.5 Exercises
References
4 Regular Expression Matching Using Zero-Suppressed Decision Diagrams Shinobu Nagayama
Chapter Summary
4.1 Introduction
4.2 Preliminaries
4.2.1 Regular Expressions and Finite Automaton
4.2.2 Binary Decision Diagrams
4.3 BDDs and ZDDs for NFAs
4.3.1 Representations of NFAs Using BDDs
4.3.2 Representations of NFAs Using ZDDs
4.4 Matching Method Using BDDs and ZDDs
4.4.1 Regular Expression Matching Method Using BDDs [39
4.4.2 Regular Expression Matching Method Using ZDDs
4.5 Experimental Results
4.5.1 Comparison of the Number of Nodes
4.5.2 Comparison of Computation Time
4.6 Conclusion and Comments
Acknowledgments
4.7 Exercises
References
A Solutions
A.1 Chapter 1
A.2 Chapter 2
A.3 Chapter 3
A.4 Chapter 4
Authors’ and Editors’ Biographies
Index