Switching Theory for Logic Synthesis

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.