Switching Theory for Logic Synthesis - Tsutomu Sasao

Résumé :
Switching Theory for Logic Synthesis covers the basic topics of switching theory and logic synthesis in fourteen chapters. Chapters 1 through 5 provide the mathematical foundation. Chapters 6 through 8 include an introduction to sequential circuits, optimization of sequential machines and asynchronous sequential circuits. Chapters 9 through 14 are the main feature of the book. These chapters introduce and explain various topics that make up the subject of logic synthesis: multi-valued input two-valued output function, logic design for PLDs/FPGAs, EXOR-based design, and complexity theories of logic networks. An appendix providing a history of switching theory is included. The reference list consists of over four hundred entries. Switching Theory for Logic Synthesis is based on the author's lectures at Kyushu Institute of Technology as well as seminars for CAD engineers from various Japanese technology companies. Switching Theory for Logic Synthesis will be of interest to CAD professionals and students at the advanced level. It is also useful as a textbook, as each chapter contains examples, illustrations, and exercises.

Sommaire:
1 Mathematical Foundation.- 1.1 Set.- 1.2 Relation.- 1.3 Equivalence Class.- 1.4 Function.- 1.5 Ordered Set.- 2 Lattice and Boolean Algebra.- 2.1 Algebra.- 2.2 Lattice.- 2.3 Distributive Lattice and Complemented Lattice.- 2.4 Boolean Algebra.- 2.5 Logic Function.- 2.6 Group, Ring, and Field.- 3 Logic Functions and Their Representations.- 3.1 Logic Elements and Logic Networks.- 3.2 Logic Functions and Combinational Networks.- 3.3 SOP and POS.- 3.4 Shannon Expansion.- 3.5 Reed-Muller Expression.- 3.6 Logical Expressions and Multi-Level Logic Networks.- 3.7 Binary Decision Diagram.- 3.8 Comparison of Representation Methods.- 3.9 Logical Equations and Propositional Calculus.- 4 Optimization of and-or Two-Level Logic Networks.- 4.1 SOPs and Two-Level Logic Networks.- 4.2 n-Dimensional Cube.- 4.3 Karnaugh Map.- 4.4 Prime Implicant.- 4.5 Minimum SOP.- 4.6 Simplification of SOPs with Karnaugh Map.- 4.7 Quine-McCluskey Method.- 4.8 MSOPs and their Applications.- 4.9 Simplification of Multi-Output Networks.- 5 Logic Functions with Various Properties.- 5.1 Self-Dual Function.- 5.2 Monotone Function and Unate function.- 5.3 Linear Function.- 5.4 Symmetric Function.- 5.5 Threshold Function.- 5.6 Universal Set of Logic Functions.- 5.7 Equivalence Classes of Logic Functions.- 6 Sequential Networks.- 6.1 Introduction to Sequential Networks.- 6.2 Flip-Flops.- 6.3 Representation of Sequential Networks.- 6.4 State Assignment and State Table.- 6.5 Realization of Sequential Networks.- 7 Optimization of Sequential Networks.- 7.1 Optimization of Completely Specified Sequential Machines.- 7.2 Optimization of Incompletely Specified Sequential Machines.- 7.3 State Assignment.- 8 Delay and Asynchronous Behavior.- 8.1 Transient Response of Combinational Networks.- 8.2 Asynchronous Sequential Networks.- 8.3 Malfunctions of Asynchronous Sequential Networks.- 9 Multi-Valued Input Two-Valued Output Function.- 9.1 Multi-Valued Input Two-Valued Output Function.- 9.2 Bit Representation.- 9.3 Restriction.- 9.4 Tautology.- 9.5 Inclusion Relation.- 9.6 Equivalence.- 9.7 Divide and Conquer Method.- 9.8 Complementation of SOPs.- 9.9 Tautology Decision.- 9.10 Generation of Prime Implicants.- 9.11 Sharp Operation.- 10 Heuristic Optimization of Two-Level Networks.- 10.1 Simplification of SOPs with Many Inputs.- 10.2 Merge, Expansion, and Delete.- 10.3 Reduce and Reshape.- 10.4 Detection of Essential Prime Implicants.- 10.5 Multi-Output Function.- 10.6 PRESTO.- 10.7 MINI and ESPRESSO.- 10.8 Encoding Method for Combinational Networks.- 10.9 State Assignment for Sequential Networks.- 11 Multi-Level Logic Synthesis.- 11.1 Logic Synthesis System.- 11.2 Factoring using Product Terms.- 11.3 Two-Variable Function Generator.- 11.4 Algebraic Division of Logical Expressions.- 11.5 Functional Decomposition.- 11.6 Transformation of Networks.- 11.7 Simplification using Don't Care.- 11.8 Boolean Relation.- 11.9 Timing Optimization.- 12 Logic Design Using Modules.- 12.1 Logic Design using PLAs.- 12.2 Design using Multiplexers.- 12.3 Logic Design using ROMs.- 13 Logic Design Using Exors.- 13.1 Classification of AND-EXOR Expressions.- 13.2 Simplification of ESOPs.- 13.3 Fault Detection and Boolean Difference.- 14 Complexity of Logic Networks.- 14.1 Complexity of Two-Level Logic Networks.- 14.2 Complexity of Multi-Level Logic Networks.- A History of Switching Theory.- References.