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