Logic Synthesis and Optimization

Logic Synthesis and Optimization presents up-to-date research information in a pedagogical form. The authors are recognized as the leading experts on the subject. The focus of the book is on logic minimization and includes such topics as two-level minimization, multi-level minimization, application of binary decision diagrams, delay optimization, asynchronous circuits, spectral method for logic design, field programmable gate array (FPGA) design, EXOR logic synthesis and technology mapping. Examples and illustrations are included so that each contribution can be read independently. Logic Synthesis and Optimization is an indispensable reference for academic researchers as well as professional CAD engineers.

1 A New Exact Minimizer For Two-Level Logic Synthesis.- 1.1 Introduction.- 1.2 Notation.- 1.3 The Minimum Canonical Cover.- 1.4 Obtaining the Minimum Canonical Cover.- 1.5 Generating the Minimum Cover From the Minimum Canonical Cover.- 1.6 Heuristic Minimization Procedures.- 1.7 Experimental Results.- 1.8 Related Work.- 2 A New Graph Based Prime Computation Technique.- 2.1 Introduction.- 2.2 Definitions and Notations.- 2.3 The IPS Representation.- 2.4 Prime Computation of Boolean Functions.- 2.5 Prime Computation of Boolean Vectorial Functions.- 2.6 Experimental Results.- 2.7 Conclusion.- 3 Logic Synthesizers, The Transduction Method And Its Extension, Sylon.- 3.1 Introduction.- 3.2 Transduction Method.- 3.3 Logic Design of MOS Networks.- 3.4 New Logic Synthesis System, SYLON.- 3.5 Conclusions.- 4 Network Optimization Using Don't-Cares And Boolean Relations.- 4.1 Introduction.- 4.2 Multi-Level Combinational Networks.- 4.3 Permissible Functions, Don't-Cares, and Boolean Relations.- 4.4 Minimization Using Don't-Cares.- 4.5 Minimization Using Boolean Relations.- 4.6 Conclusion.- 5 Multi-Level Logic Minimization Of Large Combinational Circuits By Partitioning.- 5.1 Introduction.- 5.2 Boolean minimization.- 5.3 Partitioning for Boolean minimizers.- 5.4 Top-down application of two-way partitioning.- 5.5 Experimental results.- 5.6 Conclusions.- 6 A Partitioning Method For Area Optimization By Tree Analysis.- 6.1 Introduction.- 6.2 Logic Partition and Partial Collapsing.- 6.3 Partial Collapsing Based on Tree Structure Analysis.- 6.4 Logic Optimization.- 6.5 Algorithms.- 6.6 Experimental Results.- 6.7 Conclusions.- 7 A New Algorithm For 0-1 Programming Based On Binary Decision Diagrams.- 7.1 Introduction.- 7.2 Preliminaries.- 7.3 The Algorithm.- 7.4 Experimental Results.-7.5 Conclusions and Future Work.- 8 Delay Models And Exact Timing Analysis.- 8.1 Introduction.- 8.2 Ternary Delay Simulation and a Waveform Calculus.- 8.3 Delay Models.- 8.4 Combinational Timing Verification Under the XBDO Model.- 8.5 Combinational Timing Verification Under the XBD Model.- 8.6 Conclusions.- 9 Challenges To Dependable Asynchronous Processor Design.- 9.1 Introduction.- 9.2 System Timing Failures.- 9.3 Delay Models.- 9.4 Asynchronous Architecture.- 9.5 Asynchronous Control and Data Transfer.- 9.6 Logic Synthesis.- 9.7 Testing and Concurrent Checking.- 9.8 Metastability.- 9.9 Conclusions.- 10 Efficient Spectral Techniques for Logic Synthesis.- 10.1 Introduction.- 10.2 Transformation and Complexity of Boolean Functions.- 10.3 Efficient Spectral Methods for Logic Synthesis.- 10.4 Conclusion.- 11 Fpga Design by Generalized Functional Decomposition.- 11.1 Introduction.- 11.2 Generalized Functional Decomposition.- 11.3 Generalized Functional Decomposition using BDD.- 11.4 Design Method for LUT Networks.- 11.5 Experimental Results.- 11.6 Conclusions and Comments.- 12 Logic Synthesis With Exor Gates.- 12.1 Introduction.- 12.2 Design Method of AND-EXOR circuits.- 12.3 Simplification of AND-EXOR expressions.- 12.4 Design Method for AND-OR-EXOR circuits.- 12.5 Experimental Results.- 12.6 Conclusions and Comments.- 13 And-Exor Expressions and their Optimization.- 13.1 Introduction.- 13.2 Several Classes of AND-EXOR Expressions.- 13.3 Comparison of Complexity.- 13.4 Minimization of PSDKROs.- 13.5 Experimental Results.- 13.6 Conclusion.- 14 A Generation Method for Exor-Sum-of-Products Expressions Using Shared Binary Decision Diagrams.- 14.1 Introduction.- 14.2 Preliminaries.- 14.3 Algorithm.- 14.4 Experimental Results.- 14.5 Conclusion.- 15 A New Technology Mapping Method Based on Concurrent Factorization And Mapping.- 15.1 Introduction.- 15.2 Concurrent Factorization and Mapping.- 15.3 Process of Technology Mapping.- 15.4 Experimental Results.- 15.5 Conclusions and Future work.- 16 Gate Sizing For Cell-Based Designs.- 16.1 Introduction.- 16.2 Previous Works.- 16.3 The Theda.CBS System.- 16.4 Experimental Results.- 16.5 Summary and Future Works.- A About the Authors.