Engineering Digital Design

Contents......Page 10
Preface......Page 20
1.1 What Is So Special about Digital Systems?......Page 30
1.2 The Year 2000 and Beyond?......Page 32
1.4 Glossary of Terms, Expressions, and Abbreviations......Page 34
2.1 Introduction......Page 60
2.2 Positional and Polynomial Representations......Page 61
2.3 Unsigned Binary Number System......Page 62
2.4.1 The BCD Representation......Page 63
2.4.2 The Hexadecimal and Octal Systems......Page 65
2.5 Conversion between Number Systems......Page 66
2.5.1 Conversion of Integers......Page 67
2.5.2 Conversion of Fractions......Page 69
2.6 Signed Binary Numbers......Page 72
2.6.1 Signed-Magnitude Representation......Page 73
2.6.2 Radix Complement Representation......Page 74
2.6.3 Diminished Radix Complement Representation......Page 77
2.8 Floating-Point Number Systems......Page 78
2.9.1 Direct Addition and Subtraction of Binary Numbers......Page 81
2.9.2 Two\'s Complement Subtraction......Page 82
2.9.3 One\'s Complement Subtraction......Page 83
2.9.4 Binary Multiplication......Page 84
2.9.5 Binary Division......Page 87
2.9.6 BCD Addition and Subtraction......Page 91
2.9.7 Floating-Point Arithmetic......Page 93
2.9.8 Perspective on Arithmetic Codes......Page 96
2.10.1 The Decimal Codes......Page 97
2.10.2 Error Detection Codes......Page 98
2.10.4 Character Codes......Page 99
3.2.1 Binary State Terminology......Page 108
3.3 Introduction to CMOS Terminology and Symbology......Page 111
3.4 Logic Level Conversion: The Inverter......Page 112
3.5 Transmission Gates and Tri-State Drivers......Page 113
3.6.1 Logic Circuit Symbology for AND and OR......Page 116
3.6.2 NAND Gate Realization of Logic AND and OR......Page 117
3.6.3 NOR Gate Realization of Logic AND and OR......Page 118
3.6.4 NAND and NOR Gate Realization of Logic Level Conversion......Page 119
3.6.5 The AND and OR Gates and Their Realization of Logic AND and OR......Page 121
3.6.6 Summary of Logic Circuit Symbols for the AND and OR Functions and Logic Level Conversion......Page 123
3.7 Logic Level Incompatibility: Complementation......Page 124
3.8 Reading and Construction of Mixed-Logic Circuits......Page 126
3.9 XOR and EQV Operators and Their Mixed-Logic Circuit Symbology......Page 127
3.9.2 The XOR and EQV Functions of the EQV Gate......Page 129
3.9.3 Multiple Gate Realizations of the XOR and EQV Functions......Page 130
3.9.4 The Effect of Active Low Inputs to the XOR and EQV Circuit Symbols......Page 131
3.9.6 Controlled Logic Level Conversion......Page 132
3.9.7 Construction and Waveform Analysis of Logic Circuits Containing XOR-Type Functions......Page 133
3.10 Laws of Boolean Algebra......Page 134
3.10.1 NOT, AND, and OR Laws......Page 135
3.10.2 The Concept of Duality......Page 136
3.10.3 Associative, Commutative, Distributive, Absorptive, and Consensus Laws......Page 137
3.10.4 DeMorgan\'s Laws......Page 139
3.11 Laws of XOR Algebra......Page 140
3.11.1 Two Useful Corollaries......Page 143
3.11.2 Summary of Useful Identities......Page 144
3.12 Worked Examples......Page 145
4.2.1 The SOP Representation......Page 160
4.2.2 The POS Representation......Page 163
4.3 Introduction to Logic Function Graphics......Page 166
4.3.2 Second-Order K-maps......Page 167
4.3.3 Third-Order K-maps......Page 169
4.3.4 Fourth-Order K-maps......Page 172
4.4 Karnaugh Map Function Minimization......Page 173
4.4.1 Examples of Function Minimization......Page 175
4.4.2 Prime Implicants......Page 177
4.4.3 Incompletely Specified Functions: Don\'t Cares......Page 179
4.5 Multiple Output Optimization......Page 181
4.6 Entered Variable K-map Minimization......Page 187
4.6.1 Incompletely Specified Functions......Page 191
4.7 Function Reduction of Five or More Variables......Page 194
4.8 Minimization Algorithms and Application......Page 198
10.7.3 The Master–Slave D Flip-Flop......Page 0
4.8.3 Qualitative Description of the Espresso Algorithm......Page 202
4.9 Factorization, Resubstitution, and Decomposition Methods......Page 203
4.9.1 Factorization......Page 204
4.9.2 Resubstitution Method......Page 205
4.9.3 Decomposition by Using Shannon\'s Expansion Theorem......Page 206
4.10 Design Area vs Performance......Page 209
4.12 Worked EV K-map Examples......Page 210
5.1 Introduction......Page 226
5.2 XOR-Type Patterns and Extraction of Gate-Minimum Cover from EV K-maps......Page 227
5.2.1 Extraction Procedure and Examples......Page 229
5.3 Algebraic Verification of Optimal XOR Function Extraction from K-maps......Page 233
5.4 K-map Plotting and Entered Variable XOR Patterns......Page 234
5.7 Examples of Minimum Function Extraction......Page 238
5.8 Heuristics for CRMT Minimization......Page 246
5.9 Incompletely Specified Functions......Page 247
5.10 Multiple Output Functions with Don\'t Cares......Page 251
5.11 K-map Subfunction Partitioning for Combined CRMT and Two-Level Minimization......Page 254
5.12 Perspective on the CRMT and CRMT/Two-Level Minimization Methods......Page 258
6.1.1 The Building Blocks......Page 266
6.1.3 Performance Characteristics and Other Practical Matters......Page 267
6.1.5 Design Procedure......Page 270
6.2.1 Multiplexer Design......Page 271
6.2.2 Combinational Logic Design with MUXs......Page 274
6.3.1 Decoder Design......Page 277
6.3.2 Combinational Logic Design with Decoders......Page 280
6.4 Encoders......Page 283
6.5.2 Examples of Code Converter Design......Page 286
6.6 Magnitude Comparators......Page 294
6.7 Parity Generators and Error Checking Systems......Page 302
6.8 Combinational Shifters......Page 304
6.9 Steering Logic and Tri-State Gate Applications......Page 307
6.10 Introduction to VHDL Description of Combinational Primitives......Page 308
7.2 Read-Only Memories......Page 324
7.2.1 PROM Applications......Page 328
7.3 Programmable Logic Arrays......Page 330
7.3.1 PLA Applications......Page 331
7.4 Programmable Array Logic Devices......Page 336
7.5 Mixed-Logic Inputs to and Outputs from ROMs, PLAs, and PAL Devices......Page 339
7.6 Multiple PLD Schemes for Augmenting Input and Output Capability......Page 341
7.7 Introduction to FPGAs and Other General-Purpose Devices......Page 346
7.7.2 Actel Field Programmable Gate Arrays......Page 348
7.7.3 Xilinx FPGAs......Page 350
7.8 CAD Help in Programming PLD Devices......Page 357
8.2 Binary Adders......Page 364
8.2.1 The Half Adder......Page 365
8.2.2 The Full Adder......Page 366
8.2.3 Ripple-Carry Adders......Page 367
8.3 Binary Subtracters......Page 369
8.3.1 Adder/Subtractors......Page 371
8.3.2 Sign-Bit Error Detection......Page 372
8.4 The Carry Look-Ahead Adder......Page 374
8.5 Multiple-Number Addition and the Carry-Save Adder......Page 378
8.6 Multipliers......Page 379
8.7 Parallel Dividers......Page 382
8.8 Arithmetic and Logic Units......Page 386
8.8.1 Dedicated ALU Design Featuring R-C and CLA Capability......Page 387
8.8.2 The MUX Approach to ALU Design......Page 392
8.9 Dual-Rail Systems and ALUs with Completion Signals......Page 398
8.9.1 Carry Look-Ahead Configuration......Page 407
8.10 VHDL Description of Arithmetic Devices......Page 409
9.1 Introduction......Page 420
9.2 Static Hazards in Two-Level Combinational Logic Circuits......Page 421
9.3 Detection and Elimination Hazards in Multilevel XOR-Type Functions......Page 428
9.3.1 XOP and EOS Functions......Page 429
9.3.2 Methods for the Detection and Elimination of Static Hazards in Complex Multilevel XOR-type Functions......Page 432
9.3.3 General Procedure for the Detection and Elimination of Static Hazards in Complex Multilevel XOR-Type Functions......Page 437
9.3.4 Detection of Dynamic Hazards in Complex Multilevel XOR-Type Functions......Page 438
9.5 Stuck-at Faults and the Effect of Hazard Cover on Fault Testability......Page 441
10.1 Introduction......Page 448
10.1.1 A Sequence of Logic States......Page 449
10.2 Models for Sequential Machines......Page 450
10.3 The Fully Documented State Diagram: The Sum Rule......Page 453
10.4.1 The Set-Dominant Basic Cell......Page 457
10.4.2 The Reset-Dominant Basic Cell......Page 460
10.4.3 Combined Form of the Excitation Table......Page 462
10.4.4 Mixed-Rail Outputs of the Basic Cells......Page 463
10.4.5 Mixed-Rail Output Response of the Basic Cells......Page 464
10.5 Introduction to Flip-Flops......Page 465
10.5.1 Triggering Mechanisms......Page 466
10.5.3 Hierarchical Flow Chart and Model for Flip-Flop Design......Page 467
10.7 The D Flip-Flops: General......Page 469
10.7.1 TheD-Latch......Page 470
10.7.2 The RET D Flip-Flop......Page 473
10.8 Flip-Flop Conversion: The T, JK Flip-Flops and Miscellaneous Flip-Flops......Page 479
10.8.1 The T Flip-Flops and Their Design from D Flip-Flops......Page 480
10.8.2 The JK Flip-Flops and Their Design from D Flip-Flops......Page 482
10.8.3 Design of T and D Flip-Flops from JK Flip-Flops......Page 484
10.8.4 Review of Excitation Tables......Page 486
10.8.5 Design of Special-Purpose Flip-Flops and Latches......Page 488
10.9 Latches and Flip-Flops with Serious Timing Problems: A Warning......Page 490
10.10 Asynchronous Preset and Clear Overrides......Page 492
10.11 Setup and Hold-Time Requirements of Flip-Flops......Page 494
10.12.1 Design of a Three-Bit Binary Up/Down Counter: D-to-T K-map Conversion......Page 495
10.12.2 Design of a Sequence Recognizer: D-to-JK K-map Conversion......Page 500
10.13 Analysis of Simple State Machines......Page 505
10.14.1 The VHDL Behavorial Description of the RET D Flip-flop......Page 509
10.14.2 The VHDL Behavioral Description of a Simple FSM......Page 510
11.2 Detection and Elimination of Output Race Glitches......Page 520
11.2.2 Elimination of ORGs......Page 525
11.3 Detection and Elimination of Static Hazards in the Output Logic......Page 528
11.3.1 Externally Initiated Static Hazards in the Output Logic......Page 529
11.3.2 Internally Initiated Static Hazards in the Output of Mealy and Moore FSMs......Page 531
11.3.3 Perspective on Static Hazards in the Output Logic of FSMs......Page 538
11.4.1 Rules Associated with Asynchronous Inputs......Page 539
11.4.2 Synchronizing the Input......Page 540
11.4.3 Stretching and Synchronizing the Input......Page 541
11.4.4 Metastability and the Synchronizer......Page 543
11.5 Clock Skew......Page 546
11.6.1 Clock-Generating Circuitry......Page 549
11.6.2 Clock Signal Specifications......Page 550
11.7 Initialization and Reset of the FSM: Sanity Circuits......Page 551
11.7.1 Sanity Circuits......Page 552
11.8.1 The Single-Pole/Single-Throw Switch......Page 555
11.8.2 The Single-Pole/Double-Throw Switch......Page 557
11.8.3 The Rotary Selector Switch......Page 558
11.9.1 Design Procedure......Page 559
11.9.2 Design Example: The One- to Three-Pulse Generator......Page 561
11.10 Algorithmic State Machine Charts and State Tables......Page 565
11.10.1 ASM Charts......Page 566
11.10.2 State Tables and State Assignment Rules......Page 568
11.11 Array Algebraic Approach to Logic Design......Page 571
11.12 State Minimization......Page 576
12.2 Registers......Page 590
12.2.2 The Right Shift Register with Synchronous Parallel Load......Page 591
12.2.3 Universal Shift Registers with Synchronous Parallel Load......Page 594
12.2.4 Universal Shift Registers with Asynchronous Parallel Load......Page 597
12.2.5 Branching Action of a 4-Bit USR......Page 599
12.3 Synchronous Binary Counters......Page 601
12.3.1 Simple Divide-by-N Binary Counters......Page 602
12.3.2 Cascadable BCD Up-Counters......Page 604
12.3.3 Cascadable Up/Down Binary Counters with Asynchronous Parallel Load......Page 608
12.3.4 Binary Up/Down Counters with Synchronous Parallel Load and True Hold Capability......Page 610
12.3.5 One-Bit Modular Design of Parallel Loadable Up/Down Counters with True Hold......Page 613
12.3.6 Perspective on Parallel Loading of Counters and Registers: Asynchronous vs Synchronous......Page 617
12.3.7 Branching Action of a 4-Bit Parallel Loadable Up/Down Counter......Page 618
12.4.1 Ring Counters......Page 619
12.4.2 Twisted Ring Counters......Page 622
12.4.3 Linear Feedback Shift Register Counters......Page 623
12.5 Asynchronous (Ripple) Counters......Page 629
13.1.1 Choice of Components to be Considered......Page 642
13.2 Architecture Centered around Nonregistered PLDs......Page 643
13.2.1 Design of the One- to Three-Pulse Generator by Using a PLA......Page 644
13.2.2 Design of the One- to Three-Pulse Generator by Using a PAL......Page 646
13.2.3 Design of the One- to Three-Pulse Generator by Using a ROM......Page 647
13.2.4 Design of a More Complex FSM by Using a ROM as the PLD......Page 651
13.3 State Machine Designs Centered around a Shift Register......Page 655
13.4 State Machine Designs Centered around a Parallel Loadable Up/Down Counter......Page 661
13.5 The One-Hot Design Method......Page 665
13.5.1 Use of ASMs in One-Hot Designs......Page 669
13.5.2 Application of the One-Hot Method to a Serial 2\'s Complementer......Page 672
13.5.3 One-Hot Design of a Parallel-to-Serial Adder/Subtractor Controller......Page 674
13.5.4 Perspective on the Use of the One-Hot Method: Logic Noise and Use of Registered PLDs......Page 676
13.6 System-Level Design: Controller, Data Path, and Functional Partition......Page 678
13.6.1 Design of a Parallel-to-Serial Adder/Subtractor Control System......Page 680
13.6.2 Design of a Stepping Motor Control System......Page 684
13.7 Dealing with Unusually Large Controller and System-Level Designs......Page 695
14.1 Introduction......Page 712
14.1.1 Features of Asynchronous FSMs......Page 713
14.2 The Lumped Path Delay Models for Asynchronous FSMs......Page 714
14.3 Functional Relationships and the Stability Criteria......Page 716
14.4 The Excitation Table for the LPD Model......Page 717
14.5.1 The Fully Documented State Diagram......Page 718
14.5.2 Next-State and Output K-maps......Page 719
14.5.3 State Tables......Page 720
14.6.1 The Set-Dominant Basic Cell......Page 721
14.6.2 The Reset-Dominant Basic Cell......Page 723
14.7 Design of the Rendezvous Modules by Using the Nested Cell Model......Page 724
14.8 Design of the RET D Flip-Flop by Using the LPD Model......Page 727
14.9 Design of the RET JK Flip-Flop by Flip-Flop Conversion......Page 729
14.10 Detection and Elimination of Timing Defects in Asynchronous FSMs......Page 730
14.10.1 Endless Cycles......Page 731
14.10.2 Races and Critical Races......Page 732
14.10.3 Static Hazards in the NS and Output Functions......Page 734
14.10.4 Essential Hazards in Asynchronous FSMs......Page 740
14.10.5 Perspective on Static Hazards and E-hazards in Asynchronous FSMs......Page 747
14.11 Initialization and Reset of Asynchronous FSMs......Page 748
14.12 Single-Transition-Time Machines and the Array Algebraic Approach......Page 749
14.13 Hazard-Free Design of Fundamental Mode State Machines by Using the Nested Cell Approach......Page 759
14.14 One-Hot Design of Asynchronous State Machines......Page 763
14.15 Perspective on State Code Assignments of Fundamental Mode FSMs......Page 767
14.16 Design of Fundamental Mode FSMs by Using PLDs......Page 769
14.17 Analysis of Fundamental Mode State Machines......Page 770
15.2 Pulse Mode Models and System Requirements......Page 802
15.2.1 Choice of Memory Elements......Page 803
15.3 Other Characteristics of Pulse Mode FSMs......Page 806
15.4 Design Examples......Page 808
15.5 Analysis of Pulse Mode FSMs......Page 817
15.6 Perspective on the Pulse Mode Approach to FSM Design......Page 824
16.1 Introduction......Page 834
16.2 Externally Asynchronous/Internally Clocked Systems and Applications......Page 835
16.2.1 Static Logic DFLOP Design......Page 836
16.2.2 Domino Logic DFLOP Design......Page 841
16.2.3 Introduction to CMOS Dynamic Domino Logic......Page 843
16.2.4 EAIC System Design......Page 845
16.2.5 System Simulations and Real-Time Tests......Page 846
16.2.6 Variations on the Theme......Page 849
16.2.7 How EAIC FSMs Differ from Conventional Synchronous FSMs......Page 850
16.2.8 Perspective on EAIC Systems as an Alternative Approach to FSM Design......Page 851
16.3.1 Microprogrammable Asynchronous Controller Modules and System Architecture......Page 852
16.3.2 Architecture and Operation of the MAC Module......Page 853
16.3.3 Design of the MAC Module......Page 856
16.3.4 MAC Module Design of a Simple FSM......Page 859
16.3.5 Cascading the MAC Module......Page 861
16.3.6 Programming the MAC Module......Page 862
16.3.8 Perspective on MAC Module FSM Design......Page 863
16.4.1 Architecture for One-Hot Asynchronous Programmable Sequencers......Page 864
16.4.2 Design of a Four-State Asynchronous One-Hot Sequencer......Page 866
16.4.3 Design and Operation of a Simple FSM by Using a Four-State One-Hot Sequencer......Page 867
16.4.4 Perspective on Programmable Sequencer Design and Application......Page 868
16.5 Epilogue to Chapter 16......Page 871
A.1 Introduction to the Standard NMOS Logic Family......Page 878
A.2 Introduction to the TTL Logic Family......Page 879
A.3 Performance Characteristics of Important 1C Logic Families......Page 881
B.1 Productivity Tools Bundled with this Text......Page 884
B.2 Other Productivity Tools......Page 885
C.2 Combinational Logic Devices......Page 888
C.3 Flip-Flops, Registers, and Counters......Page 889
A......Page 892
B......Page 894
C......Page 895
D......Page 897
E......Page 898
F......Page 900
H......Page 901
L......Page 902
M......Page 903
O......Page 905
P......Page 906
R......Page 908
S......Page 909
T......Page 911
V......Page 912
Z......Page 913