Overview

This 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 of logic 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. The book is designed for CAD researchers and engineers and should 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.

Full Product Details

Author:   Tsutomu Sasao ,  Masahira Fujita
Publisher:   Springer
Imprint:   Springer
Edition:   1996 ed.
Dimensions:   Width: 15.50cm , Height: 2.00cm , Length: 23.50cm
Weight:   1.490kg
ISBN:  

9780792397205

ISBN 10:   0792397207
Pages:   332
Publication Date:   30 April 1996
Audience:   College/higher education ,  Professional and scholarly ,  Postgraduate, Research & Scholarly ,  Professional & Vocational
Format:   Hardback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

Table of Contents

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.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions