Sasao / Fujita Representations of Discrete Functions

Erscheinungsjahr 2012
ISBN: 978-1-4613-1385-4
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 332 Seiten, eBook

Representations of Discrete Functions is an edited volume containing 13 chapter contributions from leading researchers with a focus on the latest research results. The first three chapters are introductions and contain many illustrations to clarify concepts presented in the text. It is recommended that these chapters are read first. The book then deals with the following topics: binary decision diagrams (BDDs), multi-terminal binary decision diagrams (MTBDDs), edge-valued binary decision diagrams (EVBDDs), functional decision diagrams (FDDs), Kronecker decision diagrams (KDDs), binary moment diagrams (BMDs), spectral transform decision diagrams (STDDs), ternary decision diagrams (TDDs), spectral transformation of logic functions, other transformations oflogic functions, EXOR-based two-level expressions, FPRM minimization with TDDs and MTBDDs, complexity theories on FDDs, multi-level logic synthesis, and complexity of three-level logic networks. Representations of Discrete Functions is designed for CAD researchers and engineers and will also be of interest to computer scientists who are interested in combinatorial problems. Exercises prepared by the editors help make this book useful as a graduate level textbook.

Zielgruppe

Research

Autoren/Hrsg.

Sasao, Tsutomu

Fujita, Masahira

Inhaltsverzeichnis

1 Graph-Based Representations of Discrete Functions.- 1.1 Introduction.- 1.2 BDDs.- 1.3 Representation of Multi-Valued Functions.- 1.4 Representation of Cube Sets.- 1.5 Summary.- References.- 2 Representations of Logic Functions Using EXOR Operators.- 2.1 Introduction.- 2.2 Trees using EXOR Operators.- 2.3 Various AND-EXOR Expressions.- 2.4 Decision Diagrams using EXORs.- 2.5 EXOR Ternary Decision Diagrams.- 2.6 Conclusion and Comments.- References.- 3 Spectral Transform Decision Diagrams.- 3.1 Introduction.- 3.2 Matrix Theory.- 3.3 BDDs and FDDs.- 3.4 Generalization.- 3.5 Arithmetic Transform.- 3.6 Walsh Transform.- 3.7 Reduced STDDs.- 3.8 Relation Between STDDs and other DDs.- 3.9 STDDs for Arithmetic Functions.- 3.10 Conclusions and Comments.- References.- 4 Multi-Terminal Binary Decision Diagrams and Hybrid Decision Diagrams.- 4.1 Introduction.- 4.2 Multi-terminal Binary Decision Diagrams.- 4.3 Matrix Operations.- 4.4 Spectral Transformations of Binary Valued Functions.- 4.5 Kronecker Transformations.- 4.6 Hybrid Decision Diagrams.- 4.7 Summary and Directions for Future Research.- References.- 5 Edge Valued Binary Decision Diagrams.- 5.1 Introduction.- 5.2 Pseudo Boolean Functions.- 5.3 Edge Valued Binary Decision Diagrams.- 5.4 The Probability Transform and its Spectrum.- 5.5 Reed-Muller Coefficients.- 5.6 Factored Edge Valued Binary Decision Diagrams.- 5.7 Summary.- References.- 6 Arithmetic Transform of Boolean Functions.- 6.1 Arithmetic Transforms: Why they Need be Studied.- 6.2 An Integer-Valued Arithmetic Transform.- 6.3 More on A-Transforms: Introducing Numeric Values.- 6.4 Field Expressions and BDDs: Semi-Numeric Decision Diagrams.- 6.5 Application in Probabilistic Equivalence Verification.- 6.6 Conclusion.- References.- 7 OKFDDs — Algorithms, Applicationsand Extensions.- 7.1 Introduction.- 7.2 Ordered Kronecker Functional Decision Diagrams.- 7.3 Basic Algorithms on OKFDDs.- 7.4 Implementation of an OKFDD Package.- 7.5 Applications and Extensions.- 7.6 Conclusions.- References.- 8 Exact Minimization of FPRMS Using Multi-Terminal EXOR TDDs.- 8.1 Introduction.- 8.2 Definition and Basic Properties.- 8.3 Optimization of FPRMs.- 8.4 Data Structure and Implementation.- 8.5 Optimization of Kronecker Expressions.- 8.6 Experimental Results.- 8.7 Conclusion and Comments.- References.- 9 Multiple Domain Logic Synthesis.- 9.1 Introduction.- 9.2 Basics.- 9.3 The Multiple Domain Minimization Approach.- 9.4 Results.- 9.5 Conclusion.- References.- 10 Satisfiability Problems for OFDDs.- 10.1 Introduction.- 10.2 Fundamental Concepts and Definitions.- 10.3 Computing Satisfying Assignments.- 10.4 Counting Satisfying Assignments.- 10.5 Conclusions.- 10.6 Proof of Theorem 2.- References.- 11 Complexity Theoretical Aspects of OFDDs.- 11.1 Introduction.- 11.2 Improving the Variable Ordering of OFDDs is NP-complete.- 11.3 Minimal OFDD Covers.- 11.4 An Exponential Blow-Up by the Replacement of Variables by Constants.- 11.5 The Effect of Local Changes of the Variable Ordering.- 11.6 Conclusion.- References.- 12 Ternary Decision Diagrams and their Applications.- 12.1 Introduction.- 12.2 Definitions and Basic Properties.- 12.3 AND TDDs.- 12.4 Reduced Ordered TDD and SOP.- 12.5 Prime TDD and Generation of Prime Implicants.- 12.6 BDDs and TDDs for Symmetric Functions.- 12.7 Experimental Results.- 12.8 Conclusion and Comments.- References.- 13 Or-and-Or Three-Level Networks.- 13.1 Introduction.- 13.2 Upper Bound on the Number of Gates.- 13.3 Lower Bound on the Number of Gates.- 13.4 Experimental Results.- 13.5 Conclusion and Comments.- References.- Exercise.- Appendix A.- Appendix B.