Digital Logic Design (eBook)

Front Cover 1
Digital Logic Design 4
Copyright Page 5
Contents 6
Preface to the fourth edition 13
Acknowledgments 14
Chapter 1. Number systems and codes 16
1.1 Introduction 16
1.2 Number systems 17
1.3 Conversion between number systems 18
1.4 Binary addition and subtraction 20
1.5 Signed arithmetic 21
1.6 Complement arithmetic 22
1.7 Complement representation for binary numbers 22
1.8 The vlidity of 1's and 2's complement arithmetic 24
1.9 Offset binary representation 25
1.10 Addition and subtraction of 2's complement numbrs 25
1.11 Graphical interpretation of 2's complemnt representation 27
1.12 Addition and subtraction of 1's complement numbers 28
1.13 Multiplication of unsigned binary numbers 28
1.14 Multiplication of signed binary numbers 29
1.15 Binary division 30
1.16 Floating point arithmetic 31
1.17 Binary codes for decimal digits 33
1.18 n-cubes and distance 34
1.19 Error detection and correction 35
1.20 The Hamming code 36
1.21 Gray code 38
1.22 The ASCII code 39
Chapter 2. Boolean algebra 43
2.1 Introduction 43
2.2 Boolean algebra 43
2.3 Derived Boolean operations 44
2.4 Boolean functions 44
2.5 Truth tables 45
2.6 The logic o a switch 45
2.7 The switch implementation of the AND function 46
2.8 The switch implementation of the OR function 47
2.9 The gating function of the AND and OR gates 48
2.10 The inversion function 48
2.11 Gate or switch imlementation of a Boolean function 49
2.12 The Boolean theorems 49
2.13 Complete sets 53
2.14 The exclusive-OR (XOR) function 53
2.15 The Reed–Muller equation 54
2.16 Set theory and the Venn diagram 55
Chapter 3. Karnaugh maps and function simplification 58
3.1 Introduction 58
3.2 Minterms and maxterms 58
3.3 Canonical forms 59
3.4 Boolean functions of two variables 60
3.5 The Karnaugh map 61
3.6 Poltting Boolean functions on a Karnaugh map 64
3.7 Maxterms on the Karnaugh map 65
3.8 Simplificaion of Boolean functions 66
3.9 The inverse function 69
3.10 'Don't care' terms 70
3.11 Simplification of products of maxterms 72
3.12 The Quine–McCluskey tablar simplification method 73
3.13 Properties of prime implicant tables 76
3.14 Cyclic prime implicant tables 76
3.15 Semi-cyclic prime implicant tables 78
3.16 Quine-McCluskey simplification of functions containing 'don't care' terms 79
3.17 Decimal approach to Quine–McCluskey simplification of Boolean functions 80
3.18 Multiple output circuits 82
3.19 Tabular methods for multiple output functions 85
3.20 Reduced dimension maps 88
3.21 Plotting RDMs from truth tables 90
3.22 Reading RDM functions 91
3.23 Looping rules for RDMs 91
3.24 Criteria for minimisation 92
Chapter 4. Combinational logic design principles 96
4.1 Introduction 96
4.2 The NAND function 96
4.3 NAND logic implementation of AND and OR functions 97
4.4 NAND logic implementation of sums-of-products 98
4.5 The NOR function 100
4.6 NOR logic implementation of AND and OR functions 101
4.7 NOR logic implementation of products-of-sums 101
4.8 NOR logic implementation of sums-of-products 102
4.9 Bookean algebraic analysis of NAND and NOR networks 103
4.10 Symbolic circuit analysis for NAND and NOR networks 104
4.11 Alternative function representations 105
4.12 Gate singnal conventions 106
4.13 Gate expanision 106
4.14 Miscellaneous gate networks 107
4.15 Exclusive-OR and Exclusive-NOR 109
4.16 Noise margins 113
4.17 Propagation time 114
4.18 Sped-power products 115
4.19 Fan-out 116
Chapter 5. Combinational logic design with MSI circuits 120
5.1 Introduction 120
5.2 Multiplexers and data selection 120
5.3 Available MSI multiplexers 121
5.4 Interconnecting multiplexers 121
5.5 The multiplexer as a Boolean function generator 122
5.6 Multip-level mulitiplexing 126
5.7 Demultiplexers 129
5.8 Multiplexer/demultiplexer data transmission system 130
5.9 Decoders 131
5.10 Decoder networks 134
5.11 The decoder as a minterm generator 136
5.12 Display decoding 137
5.13 Encoder circuit principles 138
5.14 Available MSI encoders 140
5.15 Encoding networks 142
5.16 Parity generatin and checking 144
5.17 Digital comparators 146
5.18 Iterative circuits 150
Chapter 6. Latches and flip-flops 157
6.1 Introduction 157
6.2 The bistable element 157
6.3 The SR latch 158
6.4 The controlled SR latch 161
6.5 The controlled D latch 162
6.6 Latch timing parameters 163
6.7 The JK flip-flop 164
6.8 The master/slave JK flip-flop 166
6.9 Asynchronous controls 167
6.10 1's and 0's catching 168
6.11 The master/slave SR flip-flop 168
6.12 The edge-triggered D flip-flop 169
6.13 The edge-triggered JK flip-flop 172
6.14 The T flip-flop 172
6.15 Mechanical switch debouncing 173
6.16 Registers 174
Chapter 7. Counters and registers 178
7.1 Introduction 178
7.2 The clock singnal 178
7.3 Basic counter desing 179
7.4 Series and parallel connection of counters 181
7.5 Scale-of-five up-counter 182
7.6 The design steps for a synchoronous counter 185
7.7 Gray code counters 185
7.8 Design of decade Gray code up-counter 187
7.9 Scale-of-16 up/down counter 187
7.10 Asynchronous binary counters 188
7.11 Decoding of asynchronous counters 191
7.12 Asynchronous resettable counters 192
7.13 Integrated circuit counters 193
7.14 Cascading of IC counter chips 197
7.15 Shift registers 198
7.16 The 4-bit 7494 shift register 200
7.17 The 4-bit 7495 universal shift register 201
7.18 The 74165 parallel loading 8-bit shift register 202
7.19 The use of shift registers as counters and sequence generators 202
7.20 The universal state diagram for shift registers 203
7.21 The design of a decade counter 204
7.22 The ring counter 206
7.23 The twisted ring or Johnson counter 207
7.24 Series and parallel interconnection of Johnson counters 210
7.25 Shift registers with XOR feedback 211
7.26 Multi-bit rate multiphiers 215
Chapter 8. Clock-driven sequential circuits 222
8.1 Introduction 222
8.2 The basic synchronous sequential circuit 222
8.3 Analysis of a clocked sequential circuit 222
8.4 Design steps for synchronous sequential circuits 225
8.5 The design of a sequence detector 230
8.6 The Moore and Mealy state machines 232
8.7 Analysis of a sequential circuit implemented with JK flip-flops 236
8.8 Sequential circuit design using JK flip-flops 238
8.9 State reduction 240
8.10 State assignment 244
8.11 Algorithmic state machine charts 247
8.12 Conversion of an ASM chart into hardware 250
8.13 The 'one-hot' state assignment 252
8.14 Clock skew 253
8.15 Clock timing constraints 254
8.16 Asynchronous inputs 255
8.17 The handshake 257
Chapter 9. Event driven circuits 263
9.1 Introduction 263
9.2 Design procedure for asynchronous sequential circuits 263
9.3 Stable and unstable states 264
9.4 Design of a lamp switching circuit 265
9.5 Races 267
9.6 Race free assignments 269
9.7 The pump problem 271
9.8 Design of a sequence detector 273
9.9 State reduction for incompletely specified machines 279
9.10 Compatibility 279
9.11 Determination of compatible pairs 280
9.12 The merger diagram 282
9.13 The state reduction procedure 282
9.14 Circuit hazards 283
9.15 Gate delays 283
9.16 The generation of spikes 283
9.17 The generation of static hazards in combinational networks 285
9.18 The elimination of static hazards 286
9.19 Design of hazard-free combinational networks 288
9.20 Detection of hazards in an existing network 290
9.21 Hazard-free asynchronous circuit design 292
9.22 Dynamic hazards 294
9.23 Function hazards 296
9.24 Essential hazards 297
Chapter 10. Instrumentation and interfacing 302
10.1 Introduction 302
10.2 Schmitt trigger circuits 302
10.3 Schmitt input gates 304
10.4 Digital-to-analogue conversion 307
10.5 Analogue-to-digital conversion 310
10.6 Flash converters 311
10.7 Integrating A/D converter types 313
10.8 A/D converter types using an embedded D/A converter 314
10.9 Shafft encoders and linear encoders 318
10.10 Sensing of motion 319
10.11 Absolute encoders 321
10.12 Conversion from Gray code to base 2 324
10.13 Petherick code 326
10.14 Incremental encoders 327
10.15 Open collector and tri-state gates 329
10.16 Use of open collector gates 331
10.17 Use of tri-state buffers and gates 335
10.18 Other interfacing components 337
Chapter 11. Programmable logic devices 341
11.1 Introduction 341
11.2 Read only memory 341
11.3 ROM timing 344
11.4 Internal ROM structure 345
11.5 Implementation of Boolean functions using ROMs 346
11.6 Internal addressing techniques in ROMs 349
11.7 Memory addressing 350
11.8 Design of sequential circuits using ROMs 352
11.9 Programable logic devices (PLDs) 352
11.10 Programmable gate arrays (PGAs) 354
11.11 Programmable logic arrays (PLAs) 356
11.12 Programmable array logic (PLA) 361
11.13 Programmable logic sequencers (PLSs) 364
11.14 Field programmable gate arrays (FPGAs) 370
11.15 Xilinx field programmable gate arrays 372
11.16 Actel programmable gate arrays 376
11.17 Altera erasable programmable logic devices 378
Chapter 12. Arithmetic circuits 382
12.1 Introduction 382
12.2 The half adder 382
12.3 The full adder 383
12.4 Banary subtraction 385
12.5 The 4-bit binary full adder 386
12.6 Carry look-ahead addtion 387
12.7 The 74283 4-bit carry look-ahead adder 388
12.8 Addition/subtraction circuits using complement arithmetic 391
12.9 Overflow 392
12.10 Serial additon and subtraction 393
12.11 Accumulating adder 395
12.12 Decimal arthmetic with MSI adders 396
12.13 Adder/subtractor for decimal arithmetic 398
12.14 The 7487 true/complement unit 400
12.15 Arithmetic/logic unit design 401
12.16 Available MSI arithmetic/logic units 405
12.17 Multiplication 407
12.18 Combinational multipliers 408
12.19 ROM implemented multiplier 409
12.20 The shift and add multiplier 411
12.21 Available multiplier packages 416
12.22 Signed arithmetic 416
12.23 Booth's algorithm 418
12.24 Implementation of Booth's algorithm 419
Chapter 13. Fault diagnosis and testing 423
13.1 Introduction 423
13.2 Fault detection and location 424
13.3 Gate sensitivity 427
13.4 A fault test for a 2-input AND gate 428
13.5 Path sensitisation 429
13.6 Path sensitisaition in networks with fan-out 431
13.7 Undetecble faults 434
13.8 Bridging falults 437
13.9 The fault detection table 438
13.10 Two-level circuit fault detection in AND/OR circuits 443
13.11 Two-level circuit fault detection in OR/AND ciruits 447
13.12 Boolean difference 450
13.13 Compact testing techniques 456
13.14 Signature analysis 457
13.15 The scan path testing technique 459
13.16 Designing for testability 462
Appendix. Functional logic symbols 466
A.1 Introduction 466
A.2 Basic principles of the functional symbol stystem 466
A.3 Dependency notation 469
A.4 Simple examples of G dependency in functional logic symbols 470
A.5 Control, Set, and Reset dependency 472
A.6 Bistable logic elements and C dependency 474
A.7 Counter, Z and M dependency 476
A.8 Shift registers 478
A.9 Programmable devices and A dependency 479
A.10 Arithmetic circuits and N dependency 480
Answers to problems 482
Bibliography 513
Index 515