Engineering Digital Design : Revised Second Edition

Engineering Digital Design, Second Edition provides the most extensive coverage of any available textbook in digital logic and design. The new REVISED Second Edition published in September of 2002 provides 5 productivity tools free on the accompanying CD ROM. This software is also included on the Instructor's Manual CD ROM and complete instructions accompany each software program. In the REVISED Second Edition modern notation combines with state-of-the-art treatment of the most important subjects in digital design to provide the student with the background needed to enter industry or graduate study at a competitive level. Combinatorial logic design and synchronous and asynchronous sequential machine design methods are given equal weight, and new ideas and design approaches are explored. The productivity tools provided on the accompanying CD are outlined below: [1] EXL-Sim2002 logic simulator: EXL-Sim2002 is a full-featured, interactive, schematic-capture and simulation program that is ideally suited for use with the text at either the entry or advanced-level of logic design. Its many features include drag-and-drop capability, rubber banding, mixed logic and positive logic simulations, macro generation, individual and global (or randomized) delay assignments, connection features that eliminate the need for wire connections, schematic page sizing and zooming, waveform zooming and scrolling, a variety of printout capabilities, and a host of other useful features. [2] BOOZER logic minimizer: BOOZER is a software minimization tool that is recommended for use with the text. It accepts entered variable (EV) or canonical (1's and 0's) data from K-maps or truth tables, with or without don't cares, and returns an optimal or near optimal single or multi-output solution. It can handle up to 12 functions Boolean functions and as many inputs when used on modern computers. [3] ESPRESSO II logic minimizer: ESPRESSO II is another software minimization tool widely used in schools and industry. It supports advanced heuristic algorithms for minimization of two-level, multi-output Boolean functions but does not accept entered variables. It is also readily available from the University of California, Berkeley, 1986 VLSI Tools Distribution. [4] ADAM design software: ADAM (for Automated Design of Asynchronous Machines) is a very powerful productivity tool that permits the automated design of very complex asynchronous state machines, all free of timing defects. The input files are state tables for the desired state machines. The output files are given in the Berkeley format appropriate for directly programming PLAs. ADAM also allows the designer to design synchronous state machines, timing-defect-free. The options include the lumped path delay (LPD) model or NESTED CELL model for asynchronous FSM designs, and the use of D FLIP-FLOPs for synchronous FSM designs. The background for the use of ADAM is covered in Chapters 11, 14 and 16 of the REVISED 2nd Edition. [5] A-OPS design software: A-OPS (for Asynchronous One-hot Programmable Sequencers) is another very powerful productivity tool that permits the design of asynchronous and synchronous state machines by using a programmable sequencer kernel. This software generates a PLA or PAL output file (in Berkeley format) or the VHDL code for the automated timing-defect-free designs of the following: (a) Any 1-Hot programmable sequencer up to 10 states. (b) The 1-Hot design of multiple asynchronous or synchronous state machines driven by either PLDs or RAM. The input file is that of a state table for the desired state machine. This software can be used to design systems with the capability of instantly switching between several radically different controllers on a time-shared basis. The background for the use of A-OPS is covered in Chapters 13, 14 and 16 of the REVISED 2nd Edition. The above software, as bundled with the REVISED 2nd Edition, will be unique and highly useful to students and faculty alike for both instructional and research purposes. All of the above software, except the EXL-Sim2002 simulator, require the use of a text editor. A "Slideshow" and a "Software Overview" are also included on the CD ROM to provide additional information regarding these productivity tools and the many other new and unique features found in Engineering Digital Design REVISED Second Edition). Other new features found in the REVISED Second Edition include numerous new end-of-chapter problems that have been added to enrich the student's learning experience by making use of the software tools listed above. After inspecting the REVISED Second Edition and using the software bundled with it readers will find a fresh new approach to logic design and analysis has been introduced. The text is designed to be used at the entry, intermediate or advanced levels thereby making it unnecessary for students to change texts between successive courses in the subject area. * CD-ROM bundled with text includes 5 powerful productivity tools free * The most complete coverage of any text in digital logic and design * Appropriate for introductory and intermediate courses in digital logic and design * Over 670 figures and tables help to replace lengthy explanations * More than 1000 worked and unworked exercises and problems aid the learning process * Unique coverage of ALUs * Extensive coverage of number systems, binary arithmetic and codes * Exceptionally strong in synchronous and asynchronous machine design * Extensive glossary presented at the beginning of the text Contents 10 Preface 20 1. Introductory Remarks and Glossary 30 1.1 What Is So Special about Digital Systems? 30 1.2 The Year 2000 and Beyond? 32 1.3 A Word of Warning 34 1.4 Glossary of Terms, Expressions, and Abbreviations 34 2. Number Systems, Binary Arithmetic, and Codes 60 2.1 Introduction 60 2.2 Positional and Polynomial Representations 61 2.3 Unsigned Binary Number System 62 2.4 Unsigned Binary Coded Decimal, Hexadecimal, and Octal 63 2.4.1 The BCD Representation 63 2.4.2 The Hexadecimal and Octal Systems 65 2.5 Conversion between Number Systems 66 2.5.1 Conversion of Integers 67 2.5.2 Conversion of Fractions 69 2.6 Signed Binary Numbers 72 2.6.1 Signed-Magnitude Representation 73 2.6.2 Radix Complement Representation 74 2.6.3 Diminished Radix Complement Representation 77 2.7 Excess (Offset) Representations 78 2.8 Floating-Point Number Systems 78 2.9 Binary Arithmetic 81 2.9.1 Direct Addition and Subtraction of Binary Numbers 81 2.9.2 Two's Complement Subtraction 82 2.9.3 One's Complement Subtraction 83 2.9.4 Binary Multiplication 84 2.9.5 Binary Division 87 2.9.6 BCD Addition and Subtraction 91 2.9.7 Floating-Point Arithmetic 93 2.9.8 Perspective on Arithmetic Codes 96 2.10 Other Codes 97 2.10.1 The Decimal Codes 97 2.10.2 Error Detection Codes 98 2.10.3 Unit Distance Codes 99 2.10.4 Character Codes 99 3. Background for Digital Design 108 3.1 Introduction 108 3.2 Binary State Terminology and Mixed Logic Notation 108 3.2.1 Binary State Terminology 108 3.3 Introduction to CMOS Terminology and Symbology 111 3.4 Logic Level Conversion: The Inverter 112 3.5 Transmission Gates and Tri-State Drivers 113 3.6 AND and OR Operators and Their Mixed-Logic Circuit Symbology 116 3.6.1 Logic Circuit Symbology for AND and OR 116 3.6.2 NAND Gate Realization of Logic AND and OR 117 3.6.3 NOR Gate Realization of Logic AND and OR 118 3.6.4 NAND and NOR Gate Realization of Logic Level Conversion 119 3.6.5 The AND and OR Gates and Their Realization of Logic AND and OR 121 3.6.6 Summary of Logic Circuit Symbols for the AND and OR Functions and Logic Level Conversion 123 3.7 Logic Level Incompatibility: Complementation 124 3.8 Reading and Construction of Mixed-Logic Circuits 126 3.9 XOR and EQV Operators and Their Mixed-Logic Circuit Symbology 127 3.9.1 The XOR and EQV Functions of the XOR Gate 129 3.9.2 The XOR and EQV Functions of the EQV Gate 129 3.9.3 Multiple Gate Realizations of the XOR and EQV Functions 130 3.9.4 The Effect of Active Low Inputs to the XOR and EQV Circuit Symbols 131 3.9.5 Summary of Conjugate Logic Circuit Symbols for XOR and EQV Gates 132 3.9.6 Controlled Logic Level Conversion 132 3.9.7 Construction and Waveform Analysis of Logic Circuits Containing XOR-Type Functions 133 3.10 Laws of Boolean Algebra 134 3.10.1 NOT, AND, and OR Laws 135 3.10.2 The Concept of Duality 136 3.10.3 Associative, Commutative, Distributive, Absorptive, and Consensus Laws 137 3.10.4 DeMorgan's Laws 139 3.11 Laws of XOR Algebra 140 3.11.1 Two Useful Corollaries 143 3.11.2 Summary of Useful Identities 144 3.12 Worked Examples 145 4. Logic Function Representation and Minimization 160 4.1 Introduction 160 4.2 SOP and POS Forms 160 4.2.1 The SOP Representation 160 4.2.2 The POS Representation 163 4.3 Introduction to Logic Function Graphics 166 4.3.1 First-Order K-maps 167 4.3.2 Second-Order K-maps 167 4.3.3 Third-Order K-maps 169 4.3.4 Fourth-Order K-maps 172 4.4 Karnaugh Map Function Minimization 173 4.4.1 Examples of Function Minimization 175 4.4.2 Prime Implicants 177 4.4.3 Incompletely Specified Functions: Don't Cares 179 4.5 Multiple Output Optimization 181 4.6 Entered Variable K-map Minimization 187 4.6.1 Incompletely Specified Functions 191 4.7 Function Reduction of Five or More Variables 194 4.8 Minimization Algorithms and Application 198 4.8.1 The Quine–McCluskey Algorithm 0 4.8.2 Cube Representation and Function Reduction 202 4.8.3 Qualitative Description of the Espresso Algorithm 202 4.9 Factorization, Resubstitution, and Decomposition Methods 203 4.9.1 Factorization 204 4.9.2 Resubstitution Method 205 4.9.3 Decomposition by Using Shannon's Expansion Theorem 206 4.10 Design Area vs Performance 209 4.11 Perspective on Logic Minimization and Optimization 210 4.12 Worked EV K-map Examples 210 5. Function Minimization by Using K-map XOR Patterns and Reed–Muller Transformation Forms 0 5.1 Introduction 226 5.2 XOR-Type Patterns and Extraction of Gate-Minimum Cover from EV K-maps 227 5.2.1 Extraction Procedure and Examples 229 5.3 Algebraic Verification of Optimal XOR Function Extraction from K-maps 233 5.4 K-map Plotting and Entered Variable XOR Patterns 234 5.5 The SOP-to-EXSOP Reed–Muller Transformation 0 5.6 The POS-to-EQPOS Reed–Muller Transformation 0 5.7 Examples of Minimum Function Extraction 238 5.8 Heuristics for CRMT Minimization 246 5.9 Incompletely Specified Functions 247 5.10 Multiple Output Functions with Don't Cares 251 5.11 K-map Subfunction Partitioning for Combined CRMT and Two-Level Minimization 254 5.12 Perspective on the CRMT and CRMT/Two-Level Minimization Methods 258 6. Nonarithmetic Combinational Logic Devices 266 6.1 Introduction and Background 266 6.1.1 The Building Blocks 266 6.1.2 Classification of Chips 267 6.1.3 Performance Characteristics and Other Practical Matters 267 6.1.4 Part Numbering Systems 270 6.1.5 Design Procedure 270 6.2 Multiplexers 271 6.2.1 Multiplexer Design 271 6.2.2 Combinational Logic Design with MUXs 274 6.3 Decoders/Demultiplexers 277 6.3.1 Decoder Design 277 6.3.2 Combinational Logic Design with Decoders 280 6.4 Encoders 283 6.5 Code Converters 286 6.5.1 Procedure for Code Converter Design 286 6.5.2 Examples of Code Converter Design 286 6.6 Magnitude Comparators 294 6.7 Parity Generators and Error Checking Systems 302 6.8 Combinational Shifters 304 6.9 Steering Logic and Tri-State Gate Applications 307 6.10 Introduction to VHDL Description of Combinational Primitives 308 7. Programmable Logic Devices 324 7.1 Introduction 324 7.2 Read-Only Memories 324 7.2.1 PROM Applications 328 7.3 Programmable Logic Arrays 330 7.3.1 PLA Applications 331 7.4 Programmable Array Logic Devices 336 7.5 Mixed-Logic Inputs to and Outputs from ROMs, PLAs, and PAL Devices 339 7.6 Multiple PLD Schemes for Augmenting Input and Output Capability 341 7.7 Introduction to FPGAs and Other General-Purpose Devices 346 7.7.1 AND–OR–Invert and OR–AND–Invert Building Blocks 0 7.7.2 Actel Field Programmable Gate Arrays 348 7.7.3 Xilinx FPGAs 350 7.7.4 Other Classes of General-Purpose PLDs 357 7.8 CAD Help in Programming PLD Devices 357 8. Arithmetic Devices and Arithmetic Logic Units (ALUs) 364 8.1 Introduction 364 8.2 Binary Adders 364 8.2.1 The Half Adder 365 8.2.2 The Full Adder 366 8.2.3 Ripple-Carry Adders 367 8.3 Binary Subtracters 369 8.3.1 Adder/Subtractors 371 8.3.2 Sign-Bit Error Detection 372 8.4 The Carry Look-Ahead Adder 374 8.5 Multiple-Number Addition and the Carry-Save Adder 378 8.6 Multipliers 379 8.7 Parallel Dividers 382 8.8 Arithmetic and Logic Units 386 8.8.1 Dedicated ALU Design Featuring R-C and CLA Capability 387 8.8.2 The MUX Approach to ALU Design 392 8.9 Dual-Rail Systems and ALUs with Completion Signals 398 8.9.1 Carry Look-Ahead Configuration 407 8.10 VHDL Description of Arithmetic Devices 409 9. Propagation Delay and Timing Defects in Combinational Logic 420 9.1 Introduction 420 9.2 Static Hazards in Two-Level Combinational Logic Circuits 421 9.3 Detection and Elimination Hazards in Multilevel XOR-Type Functions 428 9.3.1 XOP and EOS Functions 429 9.3.2 Methods for the Detection and Elimination of Static Hazards in Complex Multilevel XOR-type Functions 432 9.3.3 General Procedure for the Detection and Elimination of Static Hazards in Complex Multilevel XOR-Type Functions 437 9.3.4 Detection of Dynamic Hazards in Complex Multilevel XOR-Type Functions 438 9.4 Function Hazards 441 9.5 Stuck-at Faults and the Effect of Hazard Cover on Fault Testability 441 10. Introduction to Synchronous State Machine Design and Analysis 448 10.1 Introduction 448 10.1.1 A Sequence of Logic States 449 10.2 Models for Sequential Machines 450 10.3 The Fully Documented State Diagram: The Sum Rule 453 10.4 The Basic Memory Cells 457 10.4.1 The Set-Dominant Basic Cell 457 10.4.2 The Reset-Dominant Basic Cell 460 10.4.3 Combined Form of the Excitation Table 462 10.4.4 Mixed-Rail Outputs of the Basic Cells 463 10.4.5 Mixed-Rail Output Response of the Basic Cells 464 10.5 Introduction to Flip-Flops 465 10.5.1 Triggering Mechanisms 466 10.5.2 Types of Flip-Flops 467 10.5.3 Hierarchical Flow Chart and Model for Flip-Flop Design 467 10.6 Procedure for FSM (Flip-Flop) Design and the Mapping Algorithm 469 10.7 The D Flip-Flops: General 469 10.7.1 TheD-Latch 470 10.7.2 The RET D Flip-Flop 473 10.7.3 The Master–Slave D Flip-Flop 0 10.8 Flip-Flop Conversion: The T, JK Flip-Flops and Miscellaneous Flip-Flops 479 10.8.1 The T Flip-Flops and Their Design from D Flip-Flops 480 10.8.2 The JK Flip-Flops and Their Design from D Flip-Flops 482 10.8.3 Design of T and D Flip-Flops from JK Flip-Flops 484 10.8.4 Review of Excitation Tables 486 10.8.5 Design of Special-Purpose Flip-Flops and Latches 488 10.9 Latches and Flip-Flops with Serious Timing Problems: A Warning 490 10.10 Asynchronous Preset and Clear Overrides 492 10.11 Setup and Hold-Time Requirements of Flip-Flops 494 10.12 Design of Simple Synchronous State Machines with Edge-Triggered Flip-Flops: Map Conversion 495 10.12.1 Design of a Three-Bit Binary Up/Down Counter: D-to-T K-map Conversion 495 10.12.2 Design of a Sequence Recognizer: D-to-JK K-map Conversion 500 10.13 Analysis of Simple State Machines 505 10.14 VHDL Description of Simple State Machines 509 10.14.1 The VHDL Behavorial Description of the RET D Flip-flop 509 10.14.2 The VHDL Behavioral Description of a Simple FSM 510 11. Synchronous FSM Design Considerations and Applications 520 11.1 Introduction 520 11.2 Detection and Elimination of Output Race Glitches 520 11.2.1 ORG Analysis Procedure Involving Two Race Paths 525 11.2.2 Elimination of ORGs 525 11.3 Detection and Elimination of Static Hazards in the Output Logic 528 11.3.1 Externally Initiated Static Hazards in the Output Logic 529 11.3.2 Internally Initiated Static Hazards in the Output of Mealy and Moore FSMs 531 11.3.3 Perspective on Static Hazards in the Output Logic of FSMs 538 11.4 Asynchronous Inputs: Rules and Caveats 539 11.4.1 Rules Associated with Asynchronous Inputs 539 11.4.2 Synchronizing the Input 540 11.4.3 Stretching and Synchronizing the Input 541 11.4.4 Metastability and the Synchronizer 543 11.5 Clock Skew 546 11.6 Clock Sources and Clock Signal Specifications 549 11.6.1 Clock-Generating Circuitry 549 11.6.2 Clock Signal Specifications 550 11.6.3 Buffering and Gating the Clock 551 11.7 Initialization and Reset of the FSM: Sanity Circuits 551 11.7.1 Sanity Circuits 552 11.8 Switch Debouncing Circuits 555 11.8.1 The Single-Pole/Single-Throw Switch 555 11.8.2 The Single-Pole/Double-Throw Switch 557 11.8.3 The Rotary Selector Switch 558 11.9 Applications to the Design of More Complex State Machines 559 11.9.1 Design Procedure 559 11.9.2 Design Example: The One- to Three-Pulse Generator 561 11.10 Algorithmic State Machine Charts and State Tables 565 11.10.1 ASM Charts 566 11.10.2 State Tables and State Assignment Rules 568 11.11 Array Algebraic Approach to Logic Design 571 11.12 State Minimization 576 12. Module and Bit-Slice Devices 590 12.1 Introduction 590 12.2 Registers 590 12.2.1 The Storage (Holding) Register 591 12.2.2 The Right Shift Register with Synchronous Parallel Load 591 12.2.3 Universal Shift Registers with Synchronous Parallel Load 594 12.2.4 Universal Shift Registers with Asynchronous Parallel Load 597 12.2.5 Branching Action of a 4-Bit USR 599 12.3 Synchronous Binary Counters 601 12.3.1 Simple Divide-by-N Binary Counters 602 12.3.2 Cascadable BCD Up-Counters 604 12.3.3 Cascadable Up/Down Binary Counters with Asynchronous Parallel Load 608 12.3.4 Binary Up/Down Counters with Synchronous Parallel Load and True Hold Capability 610 12.3.5 One-Bit Modular Design of Parallel Loadable Up/Down Counters with True Hold 613 12.3.6 Perspective on Parallel Loading of Counters and Registers: Asynchronous vs Synchronous 617 12.3.7 Branching Action of a 4-Bit Parallel Loadable Up/Down Counter 618 12.4 Shift-Register Counters 619 12.4.1 Ring Counters 619 12.4.2 Twisted Ring Counters 622 12.4.3 Linear Feedback Shift Register Counters 623 12.5 Asynchronous (Ripple) Counters 629 13. Alternative Synchronous FSM Architectures and Systems-Level Design 642 13.1 Introduction 642 13.1.1 Choice of Components to be Considered 642 13.2 Architecture Centered around Nonregistered PLDs 643 13.2.1 Design of the One- to Three-Pulse Generator by Using a PLA 644 13.2.2 Design of the One- to Three-Pulse Generator by Using a PAL 646 13.2.3 Design of the One- to Three-Pulse Generator by Using a ROM 647 13.2.4 Design of a More Complex FSM by Using a ROM as the PLD 651 13.3 State Machine Designs Centered around a Shift Register 655 13.4 State Machine Designs Centered around a Parallel Loadable Up/Down Counter 661 13.5 The One-Hot Design Method 665 13.5.1 Use of ASMs in One-Hot Designs 669 13.5.2 Application of the One-Hot Method to a Serial 2's Complementer 672 13.5.3 One-Hot Design of a Parallel-to-Serial Adder/Subtractor Controller 674 13.5.4 Perspective on the Use of the One-Hot Method: Logic Noise and Use of Registered PLDs 676 13.6 System-Level Design: Controller, Data Path, and Functional Partition 678 13.6.1 Design of a Parallel-to-Serial Adder/Subtractor Control System 680 13.6.2 Design of a Stepping Motor Control System 684 13.6.3 Perspective on System-Level Design in This Text 695 13.7 Dealing with Unusually Large Controller and System-Level Designs 695 14. Asynchronous State Machine Design and Analysis: Basic Concepts 712 14.1 Introduction 712 14.1.1 Features of Asynchronous FSMs 713 14.1.2 Need for Asynchronous FSMs 714 14.2 The Lumped Path Delay Models for Asynchronous FSMs 714 14.3 Functional Relationships and the Stability Criteria 716 14.4 The Excitation Table for the LPD Model 717 14.5 State Diagrams, K-maps, and State Tables for Asynchronous FSMs 718 14.5.1 The Fully Documented State Diagram 718 14.5.2 Next-State and Output K-maps 719 14.5.3 State Tables 720 14.6 Design of the Basic Cells by Using the LPD Model 721 14.6.1 The Set-Dominant Basic Cell 721 14.6.2 The Reset-Dominant Basic Cell 723 14.7 Design of the Rendezvous Modules by Using the Nested Cell Model 724 14.8 Design of the RET D Flip-Flop by Using the LPD Model 727 14.9 Design of the RET JK Flip-Flop by Flip-Flop Conversion 729 14.10 Detection and Elimination of Timing Defects in Asynchronous FSMs 730 14.10.1 Endless Cycles 731 14.10.2 Races and Critical Races 732 14.10.3 Static Hazards in the NS and Output Functions 734 14.10.4 Essential Hazards in Asynchronous FSMs 740 14.10.5 Perspective on Static Hazards and E-hazards in Asynchronous FSMs 747 14.11 Initialization and Reset of Asynchronous FSMs 748 14.12 Single-Transition-Time Machines and the Array Algebraic Approach 749 14.13 Hazard-Free Design of Fundamental Mode State Machines by Using the Nested Cell Approach 759 14.14 One-Hot Design of Asynchronous State Machines 763 14.15 Perspective on State Code Assignments of Fundamental Mode FSMs 767 14.16 Design of Fundamental Mode FSMs by Using PLDs 769 14.17 Analysis of Fundamental Mode State Machines 770 15. The Pulse Mode Approach to Asynchronous FSM Design 802 15.1 Introduction 802 15.2 Pulse Mode Models and System Requirements 802 15.2.1 Choice of Memory Elements 803 15.3 Other Characteristics of Pulse Mode FSMs 806 15.4 Design Examples 808 15.5 Analysis of Pulse Mode FSMs 817 15.6 Perspective on the Pulse Mode Approach to FSM Design 824 16. Externally Asynchronous/Internally Clocked (Pausable) Systems and Programmable Asynchronous Sequencers 834 16.1 Introduction 834 16.2 Externally Asynchronous/Internally Clocked Systems and Applications 835 16.2.1 Static Logic DFLOP Design 836 16.2.2 Domino Logic DFLOP Design 841 16.2.3 Introduction to CMOS Dynamic Domino Logic 843 16.2.4 EAIC System Design 845 16.2.5 System Simulations and Real-Time Tests 846 16.2.6 Variations on the Theme 849 16.2.7 How EAIC FSMs Differ from Conventional Synchronous FSMs 850 16.2.8 Perspective on EAIC Systems as an Alternative Approach to FSM Design 851 16.3 Asynchronous Programmable Sequencers 852 16.3.1 Microprogrammable Asynchronous Controller Modules and System Architecture 852 16.3.2 Architecture and Operation of the MAC Module 853 16.3.3 Design of the MAC Module 856 16.3.4 MAC Module Design of a Simple FSM 859 16.3.5 Cascading the MAC Module 861 16.3.6 Programming the MAC Module 862 16.3.7 Metastability and the MAC Module: The Final Issue 863 16.3.8 Perspective on MAC Module FSM Design 863 16.4 One-Hot Programmable Asynchronous Sequencers 864 16.4.1 Architecture for One-Hot Asynchronous Programmable Sequencers 864 16.4.2 Design of a Four-State Asynchronous One-Hot Sequencer 866 16.4.3 Design and Operation of a Simple FSM by Using a Four-State One-Hot Sequencer 867 16.4.4 Perspective on Programmable Sequencer Design and Application 868 16.5 Epilogue to Chapter 16 871 A: Other Transistor Logic Families 878 A.1 Introduction to the Standard NMOS Logic Family 878 A.2 Introduction to the TTL Logic Family 879 A.3 Performance Characteristics of Important 1C Logic Families 881 B: Computer-Aided Engineering Tools 884 B.1 Productivity Tools Bundled with this Text 884 B.2 Other Productivity Tools 885 C: IEEE Standard Symbols 888 C.1 Gates 888 C.2 Combinational Logic Devices 888 C.3 Flip-Flops, Registers, and Counters 889 Index 892 A 892 B 894 C 895 D 897 E 898 F 900 G 901 H 901 I 902 J 902 K 902 L 902 M 903 N 905 O 905 P 906 Q 908 R 908 S 909 T 911 U 912 V 912 W 913 X 913 Y 913 Z 913 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 Engineering Digital Design, Second Edition provides the most extensive coverage of any available textbook in digital logic and design. The new REVISED Second Edition published in September of 2002 provides 5 productivity tools free on the accompanying CD ROM. This software is also included on the Instructor's Manual CD ROM and complete instructions accompany each software program.

In the REVISED Second Edition modern notation combines with state-of-the-art treatment of the most important subjects in digital design to provide the student with the background needed to enter industry or graduate study at a competitive level. Combinatorial logic design and synchronous and asynchronous sequential machine design methods are given equal weight, and new ideas and design approaches are explored.

The productivity tools provided on the accompanying CD are outlined below:
[1] EXL-Sim2002 logic simulator: EXL-Sim2002 is a full-featured, interactive, schematic-capture and simulation program that is ideally suited for use with the text at either the entry or advanced-level of logic design. Its many features include drag-and-drop capability, rubber banding, mixed logic and positive logic simulations, macro generation, individual and global (or randomized) delay assignments, connection features that eliminate the need for wire connections, schematic page sizing and zooming, waveform zooming and scrolling, a variety of printout capabilities, and a host of other useful features.

[2] BOOZER logic minimizer: BOOZER is a software minimization tool that is recommended for use with the text. It accepts entered variable (EV) or canonical (1's and 0's) data from K-maps or truth tables, with or without don't cares, and returns an optimal or near optimal single or multi-output solution. It can handle up to 12 functions Boolean functions and as many inputs when used on modern computers.

[3] ESPRESSO II logic minimizer: ESPRESSO II is another software minimization tool widely used in schools and industry. It supports advanced heuristic algorithms for minimization of two-level, multi-output Boolean functions but does not accept entered variables. It is also readily available from the University of California, Berkeley, 1986 VLSI Tools Distribution.

[4] ADAM design software: ADAM (for Automated Design of Asynchronous Machines) is a very powerful productivity tool that permits the automated design of very complex asynchronous state machines, all free of timing defects. The input files are state tables for the desired state machines. The output files are given in the Berkeley format appropriate for directly programming PLAs. ADAM also allows the designer to design synchronous state machines, timing-defect-free. The options include the lumped path delay (LPD) model or NESTED CELL model for asynchronous FSM designs, and the use of D FLIP-FLOPs for synchronous FSM designs. The background for the use of ADAM is covered in Chapters 11, 14 and 16 of the REVISED 2nd Edition.

[5] A-OPS design software: A-OPS (for Asynchronous One-hot Programmable Sequencers) is another very powerful productivity tool that permits the design of asynchronous and synchronous state machines by using a programmable sequencer kernel. This software generates a PLA or PAL output file (in Berkeley format) or the VHDL code for the automated timing-defect-free designs of the following: (a) Any 1-Hot programmable sequencer up to 10 states. (b) The 1-Hot design of multiple asynchronous or synchronous state machines driven by either PLDs or RAM. The input file is that of a state table for the desired state machine. This software can be used to design systems with the capability of instantly switching between several radically different controllers on a
time-shared basis. The background for the use of A-OPS is covered in Chapters 13, 14 and 16 of the REVISED 2nd Edition.