Fundamentals of Switching Theory and Logic Design

Preface xi

1. 1

1 Sets 1

2 RelaTIons 2

3 FuncTIons 4

4 RepresentaTIons of Logic FuncTIons 9

4.1 SOP and POS expressions 13

4.2 Positional Cube Notation 16

5 Factored Expressions 17

6 Exercises and Problems 19

2. 21

1 Algebraic Structure 21

2 Finite Groups 21

3 Finite Rings 24

4 Finite Fields 25

5 Homomorphisms 27

6 Matrices 30

7 Vector spaces 33

8 Algebra 37

9 Boolean Algebra 38

9.1 Boolean expressions 40

10 Graphs 42

11 Exercises and Problems 44

SETS, RELATIONS, FUNCTIONS

Acronyms xiii

LOGIC

ALGEBRAIC STRUCTURES FOR LOGIC DESIGN

vi FUNDAMENTALS OF SWITCHING THEORY AND LOGIC DESIGN

3. FUNCTIONAL EXPRESSIONS 47

1 Shannon Expansion Rule 50

2 Reed-Muller Expansion Rules 51

3 Fast Algorithms for Calculation of RM-expressions 56

4 Negative Davio Expression 57

5 Fixed Polarity Reed-Muller Expressions 59

6 Algebraic Structures for Reed-Muller Expressions 62

7 Interpretation of Reed-Muller Expressions 63

8 Kronecker Expressions 64

8.1 Generalized bit-level expressions 67

9 Word-Level Expressions 68

9.1 Arithmetic expressions 70

9.2 Calculation of Arithmetic Spectrum 73

9.3 Applications of ARs 74

10 Walsh Expressions 77

11 Walsh Functions and Switching Variables 80

12 Walsh Series 80

13 Relationships Among Expressions 82

14 Generalizations to Multiple-Valued Functions 85

15 Exercises and Problems 87

4. DECISION DIAGRAMS 89

1 Decision Diagrams 89

2 Decision Diagrams over Groups 97

3 Construction of Decision Diagrams 99

4 Shared Decision Diagrams 102

5 Multi-terminal binary decision diagrams 103

6 Functional Decision Diagrams 103

7 Kronecker decision diagrams 108

8 Pseudo-Kronecker decision diagrams 110

9 Spectral Interpretation of Decision Diagrams 112

9.1 Spectral transform decision diagrams 112

9.2 Arithmetic spectral transform decision diagrams 114

9.3 Walsh decision diagrams 115

10 Reduction of Decision Diagrams 119

11 Exercises and Problems 122

FOR SWITCHING

FUNCTIONS

FOR REPRESENTATION OF

SWITCHING FUNCTIONS

Contents vii

5. CLASSIFICATION OF SWITCHING FUNCTIONS 125

1 NPN-classification 126

2 SD-Classification 129

3 LP-classification 133

4 Universal Logic Modules 137

5 Exercises and Problems 145

6. SYNTHESIS WITH MULTIPLEXERS 147

1 Synthesis with Multiplexers 149

1.1 Optimization of Multiplexer Networks 151

1.2 Networks with Different Assignments of Inputs 153

1.3 Multiplexer Networks from BDD 154

2 Applications of Multiplexers 157

3 Demultiplexers 162

4 Synthesis with Demultiplexers 162

5 Applications of Demultiplexers 166

6 Exercises and Problems 168

7. REALIZATIONS WITH ROM 171

1 Realizations with ROM 171

2 Two-level Addressing in ROM Realizations 176

3 Characteristics of Realizations with ROM 180

4 Exercises and Problems 181

8. REALIZATIONS WITH 183

1 Realizations with PLA 184

2 The optimization of PLA 186

3 Two-level Addressing of PLA 189

4 Folding of PLA 191

5 Minimization of PLA by Characteristic Functions 194

6 Exercises and Problems 196

9. UNIVERSAL CELLULAR ARRAYS 199

1 Features of Universal Cellular Arrays 199

2 Realizations with Universal Cellular Arrays 201

3 Synthesis with Macro Cells 205

4 Exercises and Problems 208

PROGRAMMABLE

 LOGIC ARRAYS

viii FUNDAMENTALS OF SWITCHING THEORY AND LOGIC DESIGN

10. 211

1 Synthesis with FPGAs 221

2 Synthesis with Antifuse-Based FPGAs 222

3 Synthesis with LUT-FPGAs 224

3.1 Design procedure 225

4 Exercises and Problems 233

11. BOOLEAN DIFFERENCE AND APPLICATIONS 235

1 Boolean difference 236

2 Properties of the Boolean Difference 237

3 Calculation of the Boolean Difference 238

4 Boolean Difference in Testing Logic Networks 242

4.1 Errors in combinatorial logic networks 242

4.2 Boolean difference in generation of test sequences 246

5 Easily Testable Logic Networks 250

5.1 Features of Easily Testable Networks 251

6 Easily Testable Realizations from PPRM-expressions 251

7 Easily Testable Realizations from GRM-expressions 257

7.1 Related Work, Extensions, and Generalizations 263

8 Exercises and Problems 265

12. SEQUENTIAL NETWORKS 269

1 Basic Sequential Machines 271

2 State Tables 274

3 Conversion of Sequential Machines 277

4 Minimization of States 278

5 Incompletely Specified Machines 281

6 State Assignment 283

7 Decomposition of Sequential Machines 287

7.1 Serial Decomposition of Sequential Machines 287

7.2 Parallel Decomposition of Sequential Machines 290

8 Exercises and Problems 294

13. REALIZATION OF SEQUENTIAL NETWORKS 297

1 Memory Elements 298

2 Synthesis of Sequential Networks 302

3 Realization of Binary Sequential Machines 304

FIELD PROGRAMMABLE LOGIC ARRAYS

IN

TESTING LOGIC NETWORKS

Contents ix

4 Realization of Synchronous Sequential Machines 306

5 Pulse Mode Sequential Networks 309

6 Asynchronous Sequential Networks 313

7 Races and Hazards 318

7.1 Race 319

7.2 Hazards 320

8 Exercises and Problems 322

References 325

Index 339