Digital Principles and Design

Donald D. Givone
University at Buffalo
The State University of New York

Grauu

Boston Burr Ridge, IL Dubuque, IA Madison, Wl New York San Francisco St. Louis
Bangkok Bogota Caracas Kuala Lumpur Lisbon London Madrid Mexico City
Milan Montreal New Delhi Santiago Seoul Singapore Sydney Taipei Toronto
 CONTENTS

Preface xiii 2.5.4 Verification of the Iterative Method

for Fractions 23
[Link] 1 2.5.5. A Final Example 23
2.6 Special Conversion Procedures 24
Introduction 1
2.7. Signed Numbers and Complements 26
1.1 The Digital Age 1
2.8 Addition and Subtraction with r's-
1.2 Analog and Digital Representations Complements 31
of Information 2
2.8.1 Signed Addition and Subtraction 33
1.3 The Digital Computer 2
2.9 Addition and Subtraction with (r - l ) ' s -
1.3.1 The Organization of a Digital Complements 36
Computer 3
2.9.1 Signed Addition and Subtraction 39
1.3.2 The Operation of a Digital Computer 5
2.10 Codes 41
1.4 An Overview 5
2.10.1 Decimal Codes 41
2.10.2 Unit-Distance Codes 44
2.10.3 Alphanumeric Codes 46
Number Systems, Arithmetic, 2.11 Error Detection 48
and Codes 7 2.12 Error Correction 50
2.12.1 Hamming Code 51
2.1 Positional Number Systems 7
2.12.2 Single-Error Correction plus Double-Error
2.2 Counting in a Positional Number Detection 54
System 9
2.12.3 Check Sum Digits for Error
2.3 Basic Arithmetic Operations 11 Correction 54
2.3.1 Addition 11 Problems 55
2.3.2 Subtraction 11
2.3.3 Multiplication 14
2.3.4 Division 16
2.4 Polynomial Method of Number Boolean Algebra and
Conversion 16 Combinational Networks 61
2.5 Iterative Method of Number Conversion- 19 3.1 Definition of a Boolean Algebra 62
2.5.1 Iterative Method for Converting 3.1.1 Principle of Duality 63
Integers 20
3.2 Boolean Algebra Theorems 63
2.5.2 Verification of the Iterative Method
for Integers 21 3.3 A Two-Valued Boolean Algebra 70
2.5.3 Iterative Method for Converting 3.4 Boolean Formulas and Functions 73
Fractions 22 3.4.1 Normal Formulas 75

vii
viii DIGITAL PRINCIPLES AND DESIGN

3.5 Canonical Formulas 76 Chapter A

3.5.1 Minterm Canonical Formulas 76 Simplification of Boolean
3.5.2 m-Notation 78 Expressions 127
3.5.3 Maxterm Canonical Formulas 80
4.1 Formulation of the Simplification
3.5.4 M-Notation 81
Problem 127
3.6 Manipulations of Boolean Formulas 83 4.1.1 Criteria of Minimality 128
3.6.1 Equation Complementation 83 4.1.2 The Simplification Problem 129
3.6.2 Expansion about a Variable 84
4.2 Prime Implicants and Irredundant Disjunctive
3.6.3 Equation Simplification 84
Expressions 129
3.6.4 The Reduction Theorems 86
4.2.1 Implies 129
3.6.5 Minterm Canonical Formulas 87
4.2.2 Subsumes 130
3.6.6 Maxterm Canonical Formulas 88
4.2.3 Implicants and Prime Implicants 131
3.6.7 Complements of Canonical
4.2.4 Irredundant Disjunctive Normal
Formulas 89
Formulas 133
3.7 Gates and Combinational Networks 91
4.3 Prime Implicates and Irredundant Conjunctive
3.7.1 Gates 92 Expressions 133
3.7.2 Combinational Networks 92
4.4 Karnaugh Maps 135
3.7.3 Analysis Procedure 93
4.4.1 One-Variable and Two-Variable
3.7.4 Synthesis Procedure 94
Maps 135
3.7.5 A Logic Design Example 95
4.4.2 Three-Variable and Four-Variable
3.8 Incomplete Boolean Functions and Don't- Maps 136
Care Conditions 97 4.4.3 Karnaugh Maps and Canonical
3.8.1 Describing Incomplete Boolean Formulas 138
Functions 99 4.4.4 Product and Sum Term Representations
3.8.2 Don't-Care Conditions in Logic on Karnaugh Maps 141
Design 99 4.5 Using Karnaugh Maps to Obtain Minimal
3.9 Additional Boolean Operations and Expressions for Complete Boolean
Gates 101 Functions 145
3.9.1 The Nand-Function 102 4.5.1 Prime Implicants and Karnaugh
3.9.2 The Nor-Function 103 Maps 145
3.9.3 Universal Gates 103 4.5.2 Essential Prime Implicants 150
3.9.4 Nand-Gate Realizations 105 4.5.3 "Minimal Sums 151
3.9.5 Nor-Gate Realizations 108 4.5.4 Minimal Products 155
3.9.6 The Exclusive-Or-Function 111 4.6 Minimal Expressions of Incomplete Boolean
3.9.7 The Exclusive-Nor-Function 113 Functions 157
3.10 Gate Properties 113 4.6.1 Minimal Sums 158
3.10.1 Noise Margins 115 4.6.2 Minimal Products 159
3.10.2 Fan-Out 116 4.7 Five-Variable and Six-Variable Karnaugh
3.10.3 Propagation Delays 117 Maps 160
3.10.4 Power Dissipation 118 4.7.1 Five-Variable Maps 160
Problems 118 4.7.2 Six-Variable Maps 163
 CONTENTS

4.8 The Quine-McCluskey Method of Generating 4.14.4 Incompletely Specified Functions 213
Prime Implicants and Prime Implicates 166 4.14.5 Maps Whose Entries Are Not Single-
4.8.1 Prime Implicants and the Quine-McCluskey Variable Functions 218
Method 167
4.8.2 Algorithm for Generating Prime Problems 222
Implicants 170
4.8.3 Prime Implicates and the Quine-McCluskey Chapter 5
Method 173 Logic Design with MSI
4.9 Prime-Implicant/Prime-Impricate Tables and Components and Programmable
Irredundant Expressions 174 Logic Devices 230
4.9.1 Petrick' s Method of Determining 5.1 Binary Adders and Subtracters 231
Irredundant Expressions 175 5.1.1 Binary Subtracters 233
4.9.2 Prime-Implicate Tables and Irredundant 5.1.2 Carry Lookahead Adder 236
Conjunctive Normal Formulas 178 5.1.3 Large High-Speed Adders Using the Carry
Lookahead Principle 238
4.10 Prime-Implicant/Prime-Implicate Table
Reductions 178 5.2 Decimal Adders 242
4.10.1 Essential Prime Implicants 179 5.3 Comparators 246
4.10.2 Column and Row Reductions 180 5.4 Decoders 248
4.10.3 A Prime-Implicant Selection 5.4.1 Logic Design Using Decoders 249
Procedure 184 5.4.2 Decoders with an Enable Input 256
4.11 Decimal Method for Obtaining Prime 5.5 Encoders 260
Implicants 184 5.6 Multiplexers 262
4.12 The Multiple-Output Simplification 5.6.1 Logic Design with Multiplexers 266
Problem 187 5.7 Programmable Logic Devices (PLDs) 276
4.12.1 Multiple-Output Prime Implicants 191 5.7.1 PLD Notation 279
4.13 Obtaining Multiple-Output Minimal Sums and 5.8 Programmable Read-Only Memories
Products 191 (PROMs) 279
4.13.1 Tagged Product Terms 192 5.9 Programmable Logic Arrays (PLAs) 283
4.13.2 Generating the Multiple-Output Prime 5.10 Programmable Array Logic (PAL)
Implicants 193 Devices 292
4.13.3 Multiple-Output Prime-Implicant
Problems 294
Tables 195
4.13.4 Minimal Sums Using Petrick's
Method 196 ChaptPir 6
4.13.5 Minimal Sums Using Table Reduction Flip-Flops and Simple Flip-Flop
Techniques 198 Applications 301
4.13.6 Multiple-Output Minimal Products 201 6.1 The Basic Bistable Element 302
4.14 Variable-Entered Karnaugh Maps 202 6.2 Latches 303
4.14.1 Constructing Variable-Entered Maps 203 6.2.1 The SR Latch 304
4.14.2 Reading Variable-Entered Maps 6.2.2 An Application of the SR Latch: A Switch
for Minimal Sums 207 Debouncer 305
4.14.3 Minimal Products 212 6.2.3 The SR Latch 307
 DIGITAL PRINCIPLES AND DESIGN

6.2.4 The Gated SR Latch 308 7.2 Analysis of Clocked Synchronous Sequential
6.2.5 The Gated D Latch 309 Networks 371
6.3 Timing Considerations 310 7.2.1 Excitation and Output Expressions 373
6.3.1 Propagation Delays 310 7.2.2 Transition Equations 374
6.3.2 Minimum Pulse Width 312 7.2.3 Transition Tables 375
6.3.3 Setup and Hold Times 312 7.2.4 Excitation Tables 377
6.4 Master-Slave Flip-Flops (Pulse-Triggered 7.2.5 State Tables 379
Hip-Flops) 313 7.2.6 State Diagrams 380
6.4.1 The Master-Slave SR Flip-Flop 314 7.2.7 Network Terminal Behavior 382
6.4.2 The Master-Slave JK Flip-Flop 317 7.3 Modeling Clocked Synchronous Sequential
6.4.3 0' s and 1' s Catching 319 Network Behavior 385
6.4.4 Additional Types of Master-Slave 7.3.1 The Serial Binary Adder as a Mealy
Flip-Flops 320 Network 385
6.5 Edge-Triggered Flip-Flops 321 7.3.2 The Serial Binary Adder as a Moore
Network 388
6.5.1 The Positive-Edge-Triggered D
Flip-Flop 321 7.3.3 A Sequence Recognizer 390
6.5.2 Negative-Edge-Triggered D 7.3.4 A 0110/1001 Sequence Recognizer 393
Flip-Flops 324 7.3.5 A Final Example 396
6.5.3 Asynchronous Inputs 324 7.4 State Table Reduction 398
6.5.4 Additional Types of Edge-Triggered 7.4.1 Determining Equivalent Pairs
Flip-Flops 326 of States 399
6.5.5 Master-Slave Flip-Flops with Data 7.4.2 Obtaining the Equivalence Classes
Lockout 328 of States 405
6.6 Characteristic Equations 329 7.4.3 Constructing the Minimal State Table 406
6.7 Registers 332 7.4.4 The 0110/1001 Sequence Recognizer 410
6.8 Counters 337 7.5 The State Assignment 415
6.8.1 Binary Ripple Counters 337 7.5.1 Some Simple Guidelines for Obtaining State
6.8.2 Synchronous Binary Counters 340 Assignments 418
6.8.3 Counters Based on Shift Registers 345 7.5.2 Unused States 422
6.9 Design of Synchronous Counters 347 7.6 Completing the Design of Clocked
Synchronous Sequential Networks 424
6.9.1 Design of a Synchronous Mod-6 Counter
Using Clocked JK Flip-Flops 348 7.6.1 Realizations Using Programmable Logic
6.9.2 Design of a Synchronous Mod-6 Counter Devices 432
Using Clocked D, T, or SR Flip-Flops 352
6.9.3 Self-Correcting Counters 356 Problems 436
Problems 358
Chaptfir 8
Chapter 7 Algorithmic State Machines 444
Synchronous Sequential 8.1 The Algorithmic State Machine 444
Networks 367 8.2 ASM Charts 447
7.1 Structure and Operation of Clocked 8.2.1 The State Box 448
Synchronous Sequential Networks 368 8.2.2 The Decision Box 449
8.2.3 The Conditional Output Box 450
 CONTENTS Xi

8.2.4 ASM Blocks 450 9.4.2 The Primitive Flow Table for Example
8.2.5 ASM Charts 456 9.4 526
8.2.6 Relationship between State Diagrams and 9.5 Reduction of Input-Restricted Flow
ASM Charts 459 Tables 529
8.3 Two Examples of Synchronous Sequential 9.5.1 Determination of Compatible Pairs
Network Design Using ASM Charts 461 of States 530
8.3.1 A Sequence Recognizer 461 9.5.2 Determination of Maximal
8.3.2 A Parallel (Unsigned) Binary Compatibles 533
Multiplier 463 9.5.3 Determination of Minimal Collections
of Maximal Compatible Sets 535
8.4 State Assignments 468
9.5.4 Constructing the Minimal-Row Flow
8.5 ASM Tables 470 Table 536
8.5.1 ASM Transition Tables 470 9.6 A General Procedure to Flow Table
8.5.2 Assigned ASM Transition Tables 472 Reduction 538
8.5.3 Algebraic Representation of Assigned 9.6.1 Reducing the Number of Stable
Transition Tables 475 States 538
8.5.4 ASM Excitation Tables 477 9.6.2 Merging the Rows of a Primitive Flow
8.6 ASM Realizations 479 Table 540
8.6.1 Realizations Using Discrete Gates 479 9.6.3 The General Procedure Applied to Input-
8.6.2 Realizations Using Multiplexers 484 Restricted Primitive Flow Tables 543
8.6.3 Realizations Using PLAs 487 9.7 The State-Assignment Problem and the
8.6.4 Realizations Using PROMs 490 Transition Table 545
9.7.1 The Transition Table for Example 9.3 546
8.7 Asynchronous Inputs 491
9.7.2 The Transition Table for Example 9.4 550
Problems 493
9.7.3 The Need for Additional State
Variables 551
Chapter 9 9.7.4 A Systematic State-Assignment
Procedure 555
Asynchronous Sequential
Networks 505 9.8 Completing the Asynchronous Sequential
Network Design 557
9.1 Structure and Operation of Asynchronous 9.9 Static and Dynamic Hazards in Combinational
Sequential Networks 506 Networks 561
9.2 Analysis of Asynchronous Sequential 9.9.1 Static Hazards 562
Networks 510 9.9.2 Detecting Static Hazards 565
9.2.1 The Excitation Table 512 9.9.3 Eliminating Static Hazards 568
9.2.2 The Transition Table 514 9.9.4 Dynamic Hazards 570
9.2.3 The State Table 516 9.9.5 Hazard-Free Combinational Logic
9.2.4 The Flow Table 517 Networks 571
9.2.5 The Flow Diagram 519 9.9.6 Hazards in Asynchronous Networks
9.3 Races in Asynchronous Sequential Involving Latches 571
Networks 520 9.10 Essential Hazards 573
9.4 The Primitive Flow Table 522 9.10.1 Example of an Essential Hazard 574
9.4.1 The Primitive Flow Table for Example 9.10.2 Detection of Essential Hazards 575
9.3 523 Problems 578
xii DIGITAL PRINCIPLES AND DESIGN

Appendix A A.9 The MOS Field-Effect Transistor 641

Digital Circuits 589 A.9.1 Operation of the n-Channel, Enhancement-
Type MOSFET 641
A.I The pn Junction Semiconductor A.9.2 The w-Channel, Depletion-Type
Diode 590 MOSFET 645
A.I.I Semiconductor Diode Behavior 590 A.9.3 Thep-ChannelMOSFETs 646
A.1.2 Semiconductor Diode Models 592 A.9.4 Circuit Symbols 646
A.2 Diode Logic 593 A.9.5 The MOSFET as a Resistor 647
A.2.1 The Diode And-Gate 594 A.9.6 Concluding Remarks 648
A.2.2 The Diode Or-Gate 595 A.10 NMOS and PMOS Logic 649
A.2.3 Negative Logic 596 A.10.1 The NMOS Inverter (Not-Gate) 649
A.3 The Bipolar Junction Transistor 597 A.10.2 NMOS Nor-Gate 650
A.3.1 Simplified dc Transistor Operation 598 A.10.3 NMOS Nand-Gate 651
A.3.2 Normal Active Mode 600 A.10.4 PMOS Logic 652
A.3.3 Inverted Active Mode 602 A.10.5 Performance 652
A.3.4 Cutoff Mode 603 A . l l CMOS Logic 654
A.3.5 Saturation Mode 605 A.11.1 The CMOS Inverter (Not-Gate) 654
A.3.6 Silicon npn Transistor Characteristics 606 A.11.2 CMOS Nor-Gate 655
A.3.7 Summary 608 A.11.3 CMOS Nand-Gate 656
A.4 The Transistor Inverter 608 A.11.4 Performance 657
A.4.1 Loading Effects 611 Problems 657
A.5 Gate Performance Considerations 614
A.5.1 Noise Margins 614
A.5.2 Fan-Out 616 Appendix B
A.5.3 Speed of Operation and Propagation Delay Tutorials 665
Times 616
B.I A Gentle Introduction to Altera
A.5.4 Power Dissipation 618 MAX+plus II10.1 Student Edition 665
A.6 Diode-Transistor Logic (DTL) 618 B.2 A Gentle Introduction to
A.6.1 Loading Effects 620 LogicWorks™4 678
A.6.2 Modified DTL 621
A.7 Transistor-Transistor Logic (TTL) 622
Bibliography 684
A.7.1 Wired Logic 625
A.7.2 TTL with Totem-Pole Output 626
A.7.3 Three-State Output TTL 630 Index 687
A.7.4 SchottkyTTL 632
A.7.5 Concluding Remarks 634 Additional Resources
A.8 Emitter-Coupled Logic (ECL) 634 1. CD-ROM with Altera MAX+plus II and
A.8.1 The Current Switch 635 Multisim 2001 (included with book)
A.8.2 The Emitter-Follower Level Restorers 638 2. Website at [Link] that
A.8.3 The Reference Supply 639 includes labs for both Altera MAX+plus II
A.8.4 Wired Logic 639 and LogicWorks™4