Representations of Discrete Functions

Inbunden, Engelska, 1996

AvTsutomu Sasao,Howard Kunreuther,Tsutomu Sasao,Masahira Fujita

2 019 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt för medlemmar vid köp för minst 249 kr.

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.

Produktinformation

Utgivningsdatum1996-04-30
Mått155 x 235 x 24 mm
Vikt699 g
FormatInbunden
SpråkEngelska
Antal sidor332
Upplaga1996
FörlagKluwer Academic Publishers
ISBN9780792397205

Tillhör följande kategorier

Diskret matematik inom Naturvetenskap och teknik
Energiteknik inom Naturvetenskap och teknik
CAD-program inom Data och it
Systemvetenskap och AI inom Data och it
Elektronik och kommunikationer inom Naturvetenskap och teknik

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.