Table of Contents

Foreword								 ix
Preface									 xi

Chapter1  Two-Level Logic Minimization					  1
	  Olivier Coudert and Tsutomu Sasao
	1.1 Introduction 						  1
	1.2 Exact Logic Minimization 					  2
	1.3 Heuristic Logic Minimization 				 12
	1.4 Conclusion 							 21

Chapter2  Multi-Level Logic Optimization 				 29
	  Masahiro Fujita, Yusuke Matsunaga and Maciej Ciesielski
	2.1 Introduction 						 29
	2.2 Algebraic Methods 						 31
	2.3 Boolean Methods 						 40
	2.4 Functional Decomposition 					 50
	2.5 Conclusions and Perspectives 				 60
	2.6 Acknowledgments 						 61

Chapter3  Flexibility in Logic 						 65
	  Ellen Sentovich and Daniel Brand
	3.1 Introduction 						 65
	3.2 Environment 						 67
	3.3 Types of Flexibility 					 71
	3.4 Historical Perspective 					 84

Chapter4  Multiple-Valued Logic Synthesis and Optimization 		 89
	  Elena Dubrova
	4.1 Introduction 						 89
	4.2 Multiple-Valued Functions 					 90
	4.3 Functional Completeness 					 91
	4.4 Chain-Based Post Algebra 					 96
	4.5 Representations of Multiple-Valued Functions 		 98
	4.6 Two-level Logic Optimization 				101
	4.7 Multi-Level Logic Optimization 				104
	4.8 Summary 							110
	4.9 Historical Perspectives 					111

Chapter5  Technology Mapping 						115
	  Leon Stok and Vivek Tiwari
	5.1 Introduction 						115
	5.2 Decomposition 						117
	5.3 Pattern Matching 						120
	5.4 Covering 							121
	5.5 Other Costs 						132
	5.6 Conclusions and Perspectives 				137

Chapter6  Technology-based Transformations 				141
	  Rajeev Murgai
	6.1 Introduction 						141
	6.2 Gate Delay Models 						143
	6.3 Logic Transformations 					144
	6.4 Trends 							160

Chapter7  Logical and Physical Design: A flow Perspective 		167
	  Olivier Coudert
	7.1 Introduction 						167
	7.2 Logical and Physical Design Challenges 			168
	7.3 Survey of Current Design Flows 				172
	7.4 Refinement-based Flow 					174
	7.5 Conclusion \& Perspective 					193

Chapter8  Logic Synthesis for Low Power 				197
	  Luca Benini and Giovanni De Micheli
	8.1 Introduction 						197
	8.2 Gate-Level Techniques 					200
	8.3 Register-Transfer Level Techniques 				209
	8.4 The Evolution of Low-Power Synthesis 			213
	8.5 Conclusions 						219

Chapter9  Optimization of Synchronous Circuits	 			225
	  Soha Hassoun and Tiziano Villa
	9.1 Introduction 						225
	9.2 State-Based Techniques 					226
	9.3 Structural Techniques 					239
	9.4 Future Challenges 						249

Chapter10 Asynchronous Control Circuits 				255
	  Luciano Lavagno and Steven M. Nowick
	10.1 Introduction 						255
	10.2 Burst-Mode Circuits 					259
	10.3 Speed-Independent Circuits 				271
	10.4 Conclusions 						280

Chapter11 Ordered Binary Decision Diagrams 				285
	  Randal E. Bryant and Christoph Meinel
	11.1 Introduction 						285
	11.2 Data Structures for Switching Functions 			286
	11.3 OBDDs -- Ordered Binary Decision Diagrams 			287
	11.4 Paradigmatic Applications of OBDDs 			293
	11.5 Optimization of Variable Ordering 				299
	11.6 Various Improvements of the BDD Data Structure 		301
	11.7 WWW-Portal for BDD Research 				304

Chapter12 SAT and ATPG: Algorithms for Boolean Decision Problems 	309
	  Wolfgang Kunz, Marques-Silva and Sharad Malik
	12.1 Introduction 						309
	12.2 SAT and ATPG Problem Formulations 				310
	12.3 Combinational Deterministic ATPG 				312
	12.4 SAT Algorithms: A Taxonomy 				318
	12.5 Search Acceleration Techniques 				323
	12.6 Implementation Issues 					334
	12.7 Historical Perspectives and Open Problems 			338

Chapter13 Combinational and Sequential Equivalence Checking 		343
	  Andreas Kuehlmann and Cornelis A.J. van Eijk
	13.1 Introduction 						343
	13.2 Problem Definition 					344
	13.3 General Approach to Formal Equivalence Checking 		346
	13.4 Deriving the Invariant $\varrho $ 				347
	13.5 Combinational Equivalence Checking 			353
	13.6 Sequential Equivalence Checking 				361
	13.7 Implementation and Application Issues 			367
	13.8 Summary and Future Problems 				368

Chapter14 Static Timing Analysis 					373
	  Yuji Kukimoto, Michel Berkelaar and Karem Sakallah
	14.1 Introduction 						373
	14.2 Basics 							374
	14.3 Path Exceptions 						380
	14.4 Transparent Latches 					387
	14.5 Incremental Timing Analysis 				392
	14.6 Statistical Timing Analysis 				393
	14.7 Summary and Future Challenges 				398
	14.8 Historical Perspective 					399

Chapter15 The Future of Logic Synthesis and Verification 		403
	  Robert K. Brayton
	15.1 Logic Synthesis - Introduction 				403
	15.2 Techniques On The Edge 					404
	15.3 Physical/Logical Design 					413
	15.4 DSM Issues 						416
	15.5 Design For Low Power 					420
	15.6 Use In Software Compilers 					420
	15.7 Sequential Issues 						424
	15.8 Implementation Issues 					425
	15.9 Additional Challenges 					426
	15.10 Verification: Introduction 				427
	15.11 Static Timing 						428
	15.12 ATPG and SAT 						429
	15.13 BDDs 							430
	15.14 Equivalence Checking 					431

Appendices								435
Appendix A: About the Authors						435
Appendix B: Author Contact Information					443
Index									447