Page 12 - Engineering Digital Design

CONTENTS xi

4.4 Karnaugh Map Function Minimization 144
4.4.1 Examples of Function Minimization 146
4.4.2 Prime Implicants 148
4.4.3 Incompletely Specified Functions: Don't Cares 150
4.5 Multiple Output Optimization 152
4.6 Entered Variable K-map Minimization 158
4.6.1 Incompletely Specified Functions 162
4.7 Function Reduction of Five or More Variables 165
4.8 Minimization Algorithms and Application 169
4.8.1 The Quine-McCluskey Algorithm 169
4.8.2 Cube Representation and Function Reduction 173
4.8.3 Qualitative Description of the Espresso Algorithm 173
4.9 Factorization, Resubstitution, and Decomposition Methods 174
4.9.1 Factorization 175
4.9.2 Resubstitution Method 176
4.9.3 Decomposition by Using Shannon's Expansion Theorem 177
4.10 Design Area vs Performance 180
4.11 Perspective on Logic Minimization and Optimization 181
4.12 Worked EV K-map Examples 181
Further Reading 188
Problems 189

5. Function Minimization by Using K-map XOR Patterns and Reed-Muller
Transformation Forms 197
5.1 Introduction 197
5.2 XOR-Type Patterns and Extraction of Gate-Minimum Cover from
EV K-maps 198
5.2.1 Extraction Procedure and Examples 200
5.3 Algebraic Verification of Optimal XOR Function Extraction from
K-maps 204
5.4 K-map Plotting and Entered Variable XOR Patterns 205
5.5 The SOP-to-EXSOP Reed-Muller Transformation 207
5.6 The POS-to-EQPOS Reed-Muller Transformation 208
5.7 Examples of Minimum Function Extraction 209
5.8 Heuristics for CRMT Minimization 217
5.9 Incompletely Specified Functions 218
5.10 Multiple Output Functions with Don't Cares 222
5.11 K-map Subfunction Partitioning for Combined CRMT and Two-Level
Minimization 225
5.12 Perspective on the CRMT and CRMT/Two-Level Minimization Methods 229
Further Reading 229
Problems 230
6. Nonarithmetic Combinational Logic Devices 237
6.1 Introduction and Background 237
6.1.1 The Building Blocks 237
6.1.2 Classification of Chips 238
6.1.3 Performance Characteristics and Other Practical Matters 238
6.1.4 Part Numbering Systems 241
6.1.5 Design Procedure 241