Tsutomu Sasao
Springer,
Feb. 1999/ ISBN: 0-7923-8456-3
PREFACE ix 1 Mathematical Foundation 1 1.1 Set 1 1.2 Relation 4 1.3 Equivalence Class 5 1.4 Function 8 1.5 Ordered Set 10 2 Lattice and Boolean Algebra 17 2.1 Algebra 17 2.2 Lattice 17 2.3 Distributive Lattice and Complemented Lattice 18 2.4 Boolean Algebra 19 2.5 Logic Function 25 2.6 Group, Ring, and Field 27 3 Logic Functions and Their Representations 35 3.1 Logic Elements and Logic Networks 35 3.2 Logic Functions and Combinational Networks 39 3.3 SOP and POS 41 3.4 Shannon Expansion 42 3.5 Reed-Muller Expression 44 3.6 Logical Expressions and Multi-level Logic Networks 46 3.7 Binary Decision Diagram 50 3.8 Comparison of Representation Methods 54 3.9 Logical Equations and Propositional Calculus 56 4 Optimization of AND-OR Two-Level Logic Networks 63 4.1 SOPs and Two-Level Logic Networks 63 4.2 n-Dimensional Cube 64 4.3 Karnaugh Map 65 4.4 Prime Implicant 71 4.5 Minimum SOP 72 4.6 Simplification of SOPs with Karnaugh Map 74 4.7 Quine-McCluskey Method 75 4.8 MSOPs and their Applications 85 4.9 Simplification of Multi-Output Networks 86 5 Logic Functions with Various Properties 93 5.1 Self-dual Function 93 5.2 Monotone Function and Unate function 95 5.3 Linear Function 97 5.4 Symmetric Function 99 5.5 Threshold Function 100 5.6 Universal Set of Logic Functions 103 5.7 Equivalence Classes of Logic Functions 106 6 Sequential Networks 117 6.1 Introduction to Sequential Networks 117 6.2 Flip-Flops 118 6.3 Representation of Sequential Networks 126 6.4 State Assignment and State Table 127 6.5 Realization of Sequential Networks 129 7 Optimization of Sequential Networks 139 7.1 Optimization of Completely Specified Sequential Machines 139 7.2 Optimization of Incompletely Specified Sequential Machines 143 7.3 State Assignment 147 8 Delay and Asynchronous Behavior 151 8.1 Transient Response of Combinational Networks 151 8.2 Asynchronous Sequential Networks 156 8.3 Malfunctions of Asynchronous Sequential Networks 166 9 Multiple-Valued Input Two-Valued Output Function 177 9.1 Multiple-Valued Input Two-Valued Output Function 177 9.2 Bit Representation 180 9.3 Restriction 181 9.4 Tautology 182 9.5 Inclusion Relation 183 9.6 Equivalence 183 9.7 Divide and Conquer Method 184 9.8 Complementation of SOPs 186 9.9 Tautology Decision 188 9.10 Generation of Prime Implicants 190 9.11 Sharp Operation 193 10 Heuristic Optimization of Two-Level Networks 201 10.1 Simplification of SOPs with Many Inputs 201 10.2 Merge, Expansion, and Delete 202 10.3 Reduce and Reshape 206 10.4 Detection of Essential Prime Implicants 208 10.5 Multiple-Output Function 210 10.6 PRESTO 214 10.7 MINI and ESPRESSO 217 10.8 Encoding Method for Combinational Networks 221 10.9 State Assignment for Sequential Networks 224 11 Multi-Level Logic Synthesis 229 11.1 Logic Synthesis System 229 11.2 Factoring using Product Terms 231 11.3 Two-Variable Function Generator 233 11.4 Algebraic Division of Logical Expressions 236 11.5 Functional Decomposition 242 11.6 Transformation of Networks 246 11.7 Simplification using Don't Care 248 11.8 Boolean Relation 252 11.9 Timing Optimization 253 12 Logic Design Using Modules 263 12.1 Logic Design using PLAs 263 12.2 Design using Multiplexers 282 12.3 Logic Design using ROMs 284 13 Logic Design Using EXORs 289 13.1 Classification of AND-EXOR Expressions 289 13.2 Simplification of ESOPs 300 13.3 Fault Detection and Boolean Difference 303 14 Complexity of Logic Networks 311 14.1 Complexity of Two-level Logic Networks 311 14.2 Complexity of Multi-level Logic Networks 313 A History of Switching Theory 321 A.1 Overview 321 A.2 Logic Elements 322 A.3 Two-level Logic Networks 322 A.4 Multi-level logic networks 325 A.5 Sequential Networks 326 A.6 Language and Design Systems 326 A.7 Switching Theory in Japan 327 REFERENCES 331 INDEX 355