Division One Fundamental Concepts
1 Outline and Basics ........................................... 3
1.1 Specifying a Circuit in Plain Prose ...................... 3
1.2 Diagram of Successive Events ............................. 4
1.3 Table of Asserted Events * ............................... 5
1.4 Logic Variables and Logic Formulas* ...................... 7
1.5 Drawing the Circuits ..................................... 9
1.6 Sequential Circuits* .................................... 10
1.7 Verifying a Circuit* .................................... 12
2 Switching Devices ........................................... 14
2.1 Pneumatic Valves ........................................ 14
2.2 Electric Relays ......................................... 18
2.3 CMOS Transistor Circuits ................................ 23
3 Functions ................................................... 27
3.1 Ordered Pairs ........................................... 27
3.2 Speaking of Functions ................................... 31
3.3 Switching Functions ..................................... 33
4 Logic Functions and Gates ................................... 36
4.1 Elementary Switching Functions .......................... 36
4.2 Positive versus Negative Logic* ......................... 37
4.3 Elementary Logic Functions* ............................. 38
4.4 The Basic Gates* ........................................ 40
4.5 Derived Gates* .......................................... 43
5 Synthesis and Duality ....................................... 46
5.1 Minterm Functions & Minterms* ........................... 46
5.2 Maxterm Functions & Maxterms* ........................... 49
5.3 Synthesis via Partial Outputs* .......................... 50
5.4 Duality* ................................................ 53
6 Karnaugh Maps ............................................... 57
6.1 Speaking of Sets ........................................ 57
6.2 Introducing the Karnaugh Map* ........................... 59
6.3 Karnaugh Maps for multiple Inputs ....................... 62
6.4 Karnaugh Sets* .......................................... 64
7 Utilising Karnaugh Maps ..................................... 66
7.1 Specifying Switching Circuits in K-maps* ................ 66
7.2 Obtaining Disjunctive Formulas .......................... 67
7.3 Obtaining Conjunctive Formulas* ......................... 68
7.4 Logically Equivalent Expressions* ....................... 70
7.5 Logical Implications* ................................... 72
7.6 K-maps of Dual Functions* ............................... 74
Division Two Logic
8 Tautologies ................................................. 79
8.1 Logic Expressions ....................................... 79
8.2 Truth Tables ............................................ 81
8.3 Speaking of Tautologies ................................. 82
8.4 Replacement versus Substitution ......................... 85
8.5 Logic Reasoning ......................................... 86
9 Propositional Logic ......................................... 89
9.1 Axiomatic Approach to Propositional Logic ............... 89
9.2 Complementation ......................................... 91
9.3 IMPLICATION and NEGATION ................................ 93
9.4 DeMorgan's Theorems ..................................... 94
9.5 Commutativity of AND and OR ............................. 96
9.6 Logic Implications of IMPLICATIONS ...................... 97
9.7 Formulas with a single Variable ......................... 99
10 Summary of Theorems ........................................ 101
10.1 Commutative and Associative Laws* ..................... 101
10.2 Single-Variable Formulas .............................. 103
10.3 Distributive Laws* .................................... 104
10.4 Generalised DeMorgan Theorems ......................... 106
10.5 Basic Theorems on AND, OR and NOT ..................... 109
11 Algebraic Proofs ........................................... 110
11.1 Min- and Maxterms are Complementary* .................. 110
11.2 Disjunction of all Minterms* .......................... 111
11.3 Conjunction of two Mintermms* ......................... 113
11.4 Maxterm as the Disjunction of Minterms* ............... 114
11.5 Minterm AND/OR Maxterm* ............................... 115
11.6 Solving a System of Logic Equations* .................. 117
11.7 DeMorgan on DeMorgan .................................. 118
12 On Predicate Logic ......................................... 121
12.1 Inside a Proposition .................................. 121
12.2 Symbolic Notation of Propositions ..................... 122
12.3 The Switching Algebra Connection* ..................... 124
12.4 Quantifiers ........................................... 124
12.5 Quantification and Replication* ....................... 126
12.6 Free and Bound Variables .............................. 126
13 Predicate Logic ............................................ 129
13.1 Axioms and Rules of Switching Algebra* ................ 129
13.2 Theorems on Identity .................................. 132
13.3 Theorems on Quantification ............................ 135
Division Three Combinational Circuits
14 Canonical Normal Forms ..................................... 141
14.1 An Overview ........................................... 141
14.2 Direct Derivation of Normal Forms* .................... 144
14.3 Shannon's Expansion Theorems* ......................... 147
14.4 Shannon's Expansion to Normal Forms ................... 149
15 Shegalkin Normal Form ...................................... 151
15.1 An Overview ........................................... 151
15.2 Developing the Shegalkin Polynomial* .................. 153
15.3 Shegalkin Coefficients ................................ 155
15.4 On Combinations of Input Variables .................... 156
15.5 Dual Shegalkin Polynomial ............................. 157
15.6 Necessary and Sufficient Connectives .................. 160
16 Synthesis Examples ......................................... 162
16.1 Multiplexers and Demultiplexers ....................... 162
16.2 Binary Coded Decimal Digits ........................... 163
16.3 Priority Decoders ..................................... 165
16.4 Comparators ........................................... 166
17 Concepts Old and New ....................................... 171
17.1 Multiple Events* ...................................... 171
17.2 Karnaugh Sets Revisited* .............................. 172
17.3 Generalised Minterms* ................................. 173
17.4 Generalised Maxterms* ................................. 175
17.5 Partitions and Equivalents ............................ 176
17.6 Prime Sets ............................................ 177
17.7 Covers ................................................ 177
17.8 Inclusions and Exclusions* ............................ 179
17.9 Evaluation Formulas* .................................. 180
18 Minimisation Preliminaries ................................. 182
18.1 Aspects of Minimisation ............................... 182
18.2 Incomplete Specification .............................. 183
18.1 Prime Sets that cover Don't Cares ..................... 185
18.4 Evaluation Formulas for Don't Cares* .................. 188
18.5 Minimisation by K-maps ................................ 189
18.6 Algebraic Minimisation ................................ 190
19 Minimisation—an Excerp ..................................... 193
19.1 On Adjacent K-Sets and their Consensus* ............... 193
19.2 Formalising Adjacency and Consensus ................... 195
19.3 Finding the Full Cover * .............................. 198
19.4 Finding Minimal Covers* ............................... 201
19.5 Minimisation considering Don't Cares* ................. 204
20 Reduced Karnaugh Maps ...................................... 207
20.1 Reducing the Dimension of a K-map ..................... 207
20.2 K-maps within K-maps* ................................. 209
20.3 Evaluating Reduced K-maps* ............................ 211
20.4 Specification by Map-Entered Variables* ............... 215
21 NOT-AND and NOT-OR ......................................... 219
21.1 Miscellaneous Theorems ................................ 219
21.2 Two-Level Circuits .................................... 221
21.3 Multilevel NOT-AND Circuits ........................... 222
21.4 Multilevel NOT-OR Circuits ............................ 228
22 Composition of Circuits* ................................... 231
22.1 The Basic Concept ..................................... 231
22.2 Catenation ............................................ 233
22.3 Choosing a Generic Function ........................... 234
22.4 Hinge Sets ............................................ 236
22.5 Composing a Circuit: Example 1 ........................ 236
22.6 Composing a Circuit: Example 2 ........................ 239
22.7 Composing a Circuit: Example 3 ........................ 239
23 Hazards .................................................... 242
23.1 Hazards on Stationary Signals ......................... 242
23.2 Single-Input Hazards .................................. 243
23.3 Gates and Delays ...................................... 245
23.4 Detecting Single-Input Hazards ........................ 246
23.5 Hazard-Detecting Formulas ............................. 248
23.6 Hazards in a NOT-AND Circuit .......................... 249
23.7 Hazards in a Composed Circuit ......................... 251
Division Four Latches
24 Memorising by Feedback ..................................... 255
24.1 What is Memorisation? ................................. 255
24.2 The Feedback Model of Memory ......................... 258
24.3 Transient versus Stationary Behaviour ................. 261
24.4 Latches without Feedback .............................. 263
24.5 Is a Delay in the Feedback necessary?* ................ 264
25 Basic Theory of Latches .................................... 267
25.1 What is a Latch?* ..................................... 267
25.2 Specifying Latches in Reduced K-maps* ................. 269
25.3 Evaluation Formulas and Generic Latches* .............. 270
25.4 An Evaluation Example ................................. 272
25.5 Identical and Isomorphic Latches* ..................... 273
25.6 Inverting a Sample Memory-Circuit ..................... 275
25.7 General Negation of Latches* .......................... 277
26 Optimised Latches .......................................... 279
26.1 Designing Minimised Latches* .......................... 279
26.2 A Minimised Latch - an Example ........................ 280
26.3 Designing Hazard-Free Latches* ........................ 282
26.4 A Hazard-Free Latch - an Example ...................... 285
27 Elementary Latches ......................................... 288
27.1 Classification of Elementary Latches .................. 288
27.2 Two Systems of Symbolic Latches* ...................... 291
27.3 Symbols with Complementary Outputs* ................... 293
27.4 Symbolic Latches with a Common Event* ................. 294
27.5 Standard Symbols for Elementary Latches ............... 297
28 Composition of Latches* .................................... 300
28.1 Catenation Diagram for Latches ........................ 300
28.2 Composing the D-Latch using a SR-Latch ................ 302
28.3 Checking for a Hazard-Free Solution ................... 303
28.4 Avoiding Undesirable Input-Events ..................... 305
Division Five Sequential Circuits with
Continuously Read Inputs
29 Automata and Programs* ..................................... 311
29.1 Continuously reading Automata ......................... 311
29.2 Developing an Example Flow Table ...................... 313
29.3 The Word-Recognition Tree ............................. 318
29.4 Evaluating a Sequential Circuit ....................... 320
30 Word-Recognition Tables* ................................... 325
30.1 Developing Word-Recognition Tables .................... 325
30.2 Primitive Determinateness ............................. 327
30.3 General Determinateness ............................... 330
30.4 Evaluation and Partial Mappings ....................... 332
30.5 Testing for General Determinateness ................... 333
31 Catenation Model* .......................................... 335
31.1 The Moore and Mealy Models ............................ 335
31.2 Catenation Model - Feedback and Delays ................ 337
31.3 Moore and Mealy Flow Tables ........................... 340
31.4 Merging Moore and Mealy Flow Tables ................... 341
31.5 From Mealy to Moore Flow Tables ....................... 344
31.6 The Composite Word-Recognition Table .................. 345
32 Toggle Circuits ............................................ 349
32.1 T-Flipflop - its Feedback Design ...................... 349
32.2 T-Flipfiop - its Composition .......................... 352
32.3 JK-Flipflop - its Feedback Design ..................... 355
32.4 JK-Flipflop - its Composition ......................... 357
33 Triggering and Synchronising ............................... 360
33.1 Triggering ............................................ 360
33.2 Sampling .............................................. 363
33.3 Synchronising ......................................... 366
34 Verifying a Logic Design* .................................. 370
34.1 A Verification-DSE for the D-Latch .................... 370
34.2 A Verification-DSE for a given Example ................ 376
34.3 Grafting a Verification Tree .......................... 379
35 Discussing Huffman's Theory ................................ 385
35.1 Basics of Huffman's Synthesis Procedure* .............. 386
35.2 Delay and Feedback .................................... 387
35.3 State Encoding and Circuit Realisation ................ 389
35.4 Problems with Arbitrary Binary Encodings .............. 392
35.5 Race Analysis in the Catenation Model* ................ 394
36 State Encoding Techniques .................................. 398
36.1 Introducing Multiple State-Transitions ................ 399
36.2 Adding Unstable States Intuitively .................... 401
36.3 On the Number of Adjacent Encodings ................... 402
36.4 One-Hot Code .......................................... 403
36.5 Safe but Slow standardised Encodings .................. 404
36.6 Safe and Fast standardised Encodings .................. 408
36.7 Number of Required State Variables .................... 410
Bibliography .................................................. 411
Index ......................................................... 415
Those Sections or Chapters marked by an asterisk (*) contain
new concepts, proofs, or methods.
|
