مدار منطقی نلسون DIGITAL LOGIC CIRCUIT ANALYSIS & DESIGN

 

Contents

Preface DO Introduction

0.1

History of Computing 0.1.1 Beginnings: Mechanical Computers 0.1.2 Early Electronic Computers 0.1.3 The First Four Generations of Computers 0.1.4 The Fifth Generation and Beyond

0.2

0.3

Digital Systems 0.2.1 Digital vs Analog Systems 0.2.2 Digital System Design Hierarchy Organization of a Stored Program Digital Computer 0.3.1 Computer Instructions 0.3.2 Information Representation in Computers 0.3.3 Computer Hardware 0.3.4 Computer Software

0.4

Summary

สี

สี

1 Number Systems and Codes

1.1 Number Systems

1.1.1 Positional Notation 1.1.2 Commonly Used Number Systems

สี สี

=

iv

Contents

1.2

Arithmetic

1.2.1 1.2.2 1.2.3

Binary Arithmetic Octal Arithmetic Hexadecimal Arithmetic

1.3

Base Conversions 1.3.1 Conversion Methods 1.3.2 General Conversion Algorithms 1.3.3 Conversion Between Base A and Base B When B = Ak

1.4

1.5

Signed Number Representation 1.4.1 Sign-Magnitude Numbers 1.4.2 Complementary Number Systems Computer Codes 1.5.1 Numeric Codes 1.5.2 Character and Other Codes 1.5.3 Error Detection Codes and Correction Codes

1.6

Summary

78

2 Algebraic Methods for the Analysis and Synthesis of Logic Circuits

2.1 Fundamentals of Boolean Algebra

2.1.1 Basic Postulates 2.1.2 Venn Diagrams for Postulates [2] 2.1.3 Duality 2.1.4 Fundamental Theorems of Boolean Algebra

2.2

93

Switching Functions 2.2.1 Truth Tables 2.2.2 Algebraic Forms of Switching Functions 2.2.3 Derivation of Canonical Forms 2.2.4 Incompletely Specified Functions

94

101

3

103

Contents

V

2.3

104

Switching Circuits 2.3.1 Electronic Logic Gates 2.3.2 Basic Functional Components

104 108

2.4

120

120 123

128

Analysis of Combinational Circuits 2.4.1 Algebraic Method 2.4.2 Analysis of Timing Diagrams Synthesis of Combinational Logic Circuits 2.5.1 AND-OR and NAND Networks 2.5.2 OR-AND and NOR Networks 2.5.3 Two-Level Circuits 2.5.4 AND-OR-invert Circuits 2.5.5 Factoring

128 130 131 133 134

2.6

Applications

136

2.7

140

Computer-Aided Design of Logic Circuits 2.7.1 The Design Cycle 2.7.2 Digital Circuit Modeling 2.7.3 Design Synthesis and Capture Tools 2.7.4 Logic Simulation

140 140 148 152

2.8

Summary

165

3 Simplification of Switching Functions

3.1 Simplification Goals

172 173

3.2

Characteristics of Minimization Methods

174

3.3

175

Karnaugh Maps 3.3.1 Relationship to Venn Diagrams and Truth Tables 3.3.2 K-Maps of Four or More Variables

176 177

vi

Contents

3.4

Plotting Functions in Canonical Form on the K-Map

179

3.5

Simplification of Switching Functions Using K-Maps 185 3.5.1 Guidelines for Simplifying Functions Using K-Maps 187 3.5.2 General Terminology for Switching Function Minimization

187 3.5.3 Algorithms For Deriving Minimal SOP Forms From K-Maps

188

3.6

197

POS Form Using K-Maps 3.6.1 General Terminology for POS Forms 3.6.2 Algorithms For Deriving Minimal POS Forms From

K-Maps

197

197

3.7

Incompletely Specified Functions

203

3.8

Using K-Maps To Eliminate Timing Hazards

206

3.9

211

Quine-McCluskey Tabular Minimization Method 3.9.1 Covering Procedure 3.9.2 Incompletely Specified Functions 3.9.3 Systems With Multiple Outputs

215 218 219

3.10

Petricks Algorithm

222

224

227

3.11 Computer-aided Minimization of Switching

Functions 3.11.1 Cube Representation of Switching Functions 3.11.2 Algebraic Methods for Determining Prime

Implicants 3.11.3 Identifying Essential Prime Implicants 3.11.4 Completing a Minimal Cover 3.11.5 Other Minimization Algorithms

228 230 231 234

3.12 Summary

234

Contents

vii

242

4 Modular Combinational Logic

4.1 Top-Down Modular Design

243

4.2

245

246 247

Decoders 4.2.1 Decoder Circuit Structures 4.2.2 Implementing Logic Functions Using Decoders 4.2.3 Enable Control Inputs 4.2.4 Standard MSI Decoders 4.2.5 Decoder Applications

249

252 253

4.3

259

Encoders 4.3.1 Encoder Circuit Structures 4.3.2 Standard MSI Encoders

260 264

4.4

268

268

Multiplexers/Data Selectors 4.4.1 Multiplexer Circuit Structures 4.4.2 Standard MSI Multiplexers 4.4.3 Applications of Multiplexers

270

277

4.5

Demultiplexers/Data Distributors

280

4.6

283

Binary Arithmetic Elements 4.6.1 Basic Binary Adder Circuits 4.6.2 MSI Binary Adder Modules 4.6.3 High-speed Adder Units 4.6.4 Binary Subtraction Circuits 4.6.5 Arithmetic Overflow Detection

283 285 289 294 295

4.7

Comparators

298

4.8

Design Example: A Computer Arithmetic Logic Unit 302

4.9

312

Computer-aided Design of Modular Systems 4.9.1 Design Libraries 4.9.2 Drawing Hierarchical Schematics

312 314

viii

Contents

4.10 Simulation of Hierarchical Systems

317

4.11 Summary

319

5 Combinational Circuit Design with Programmable Logic Devices

5.1 Semicustom Logic Devices

327

329

5.2

330

Logic Array Circuits 5.2.1 Diode Operation in Digital Circuits 5.2.2 AND and OR Logic Arrays 5.2.3 Two-Level AND-OR Arrays 5.2.4 Field-Programmable AND and OR Arrays 5.2.5 Output Polarity Options 5.2.6 Bidirectional Pins and Feedback Lines 5.2.7 Commercial Devices

330 332 333 338 341 343

345

5.3

347

Field-programmable Logic Arrays 5.3.1 FPLA Circuit Structures 5.3.2 Realizing Logic Functions With FPLAS

347 347

5.4

Programmable Read-only Memory

350

5.4.1 PROM Circuit Structures 5.4.2 Realizing Logic Functions With PROMs 5.4.3 Lookup Tables 5.4.4 General Read-only Memory Applications 5.4.5 Read-only Memory Technologies

350 352 358 360 361

5.5

362

Programmable Array Logic 5.5.1 PAL Circuit Structures 5.5.2 Realizing Logic Functions With PALS 5.5.3 PAL Output and Feedback Options

362 363 366

Contents

ix

5.6

Computer-aided Design Tools for PLD Design

371

5.6.1 Design Representation with PDL 5.6.2 Processing a PDL Design File

373 379

5.7

Summary

380

382

D 6 Introduction to Sequential Devices

6.1 Models for Sequential Circuits

6.1.1 Block Diagram Representation

6.1.2 State Tables and Diagrams 6.2 Memory Devices

383 383 385

387

6.3

389

Latches 6.3.1 Set-Reset Latch 6.3.2 Gated SR Latch 6.3.3 Delay Latch

389 396 398

6.4

Flip-Flops 6.4.1 Master-Slave SR Flip-Flops 6.4.2 Master-Slave D Flip-Flops 6.4.3 Master-Slave JK Flip-Flops 6.4.4 Edge-triggered D Flip-Flops 6.4.5 Edge-triggered JK Flip-Flops 6.4.6 T Flip-flops 6.4.7 Latch and Flip-flop Summary

403 404 406 407 409 413 415

417

6.5

Other Memory Devices

418

6.6

418

Timing Circuits 6.6.1 One-shots 6.6.2 The 555 Timer Module

418 418

6.7

Rapidly Prototyping Sequential Circuits

421

6.8

Summary

425

X

Contents

432

433

7 Modular Sequential Logic

7.1 Shift Registers

7.1.1 A Generic Shift Register 7.1.2 Standard TTL Shift-Register Modules

434 436

7.2

446

Design Examples Using Registers 7.2.1 Serial Adder Unit 7.2.2 Serial Accumulators 7.2.3 Parallel Accumulators

446 448 450

7.3

450

Counters 7.3.1 Synchronous Binary Counters 7.3.2 Asynchronous Binary Counters 7.3.3 Down Counters 7.3.4 Up/Down Counters

451 455 458 460

7.4

Modulo-N Counters

464

7.4.1 Synchronous BCD Counters 7.4.2 Asynchronous BCD Counters 7.4.3 Modulo-6 and Modulo-12 Counters 7.4.4 Asynchronously Resetting Modulo-N Counters 7.4.5 Synchronously Resetting Modulo-N Counters

464 467 470 474 477

7.5

477

Shift Registers as Counters 7.5.1 Ring Counters 7.5.2 Twisted-ring Counters

478 482

on

7.6

Multiple-sequence Counters

489

7.7

489

Digital Fractional Rate Multipliers 7.7.1 TTL Modules 7.7.2 Cascading the Digital Fractional Rate Multipliers

491 495

7.8

Summary

496

Contents Xi

502

503

504 505

507

507 508 517

519

8 Analysis and Synthesis of Synchronous Sequential Circuits

8.1 Synchronous Sequential Circuit Models

8.1.1 Mealy Model

8.1.2 Moore Model 8.2 Sequential Circuit Analysis

8.2.1 Analysis of Sequential Circuit State Diagrams 8.2.2 Analysis of Sequential Circuit Logic Diagrams

8.2.3 Summary 8.3 Synchronous Sequential Circuit Synthesis

8.3.1 Synthesis Procedure 8.3.2 Flip-flop Input Tables 8.3.3 Application Equation Method for JK Flip-flops 8.3.4 Design Examples 8.3.5 Algorithmic State Machine Diagrams

8.3.6 One-hot Finite-State Machine Design Method 8.4 Incompletely Specified Circuits

8.4.1 State Assignment and Circuit Realization 8.5 Computer-aided Design of Sequential Circuits

8.5.1 Design Capture and Synthesis 8.5.2 Design Analysis and Verification

520 522 524 526 547 553

555

558

558

559

565

8.6

Summary

568

576

577

577

9 Simplification of Sequential Circuits

9.1 Redundant States

9.1.1 State Equivalence

9.1.2 Equivalence and Compatibility Relations 9.2 State Reduction in Completely Specified Circuits

9.2.1 Inspection

579

579

579

xii

Contents

9.3

9.2.2 Partitioning 9.2.3 Implication Table State Reduction In Incompletely Specified Circuits 9.3.1 State Compatibility 9.3.2 Minimization Procedure

581 584 588 589 594

9.4

Optimal State Assignment Methods

602

9.4.1 Unique State Assignments 9.4.2 State Assignment Guidelines 9.4.3 Partitioning 9.4.4 Optimal State Assignments

603 605 614

619

9.5

Summary

620

624

10 Asynchronous Sequential Circuits

10.1 Types of Asynchronous Circuits 10.2 Analysis of Pulse-mode Asynchronous Circuits

625

627

632

632

10.3 Synthesis of Pulse-mode Circuits

10.3.1 Design Procedure for Pulse-mode Circuits 10.4 Analysis of Fundamental-mode Circuits

10.4.1 Introduction 10.4.2 Tabular Representations 10.4.3 Analysis Procedure

641

645 648

648

10.5 Synthesis of Fundamental-mode Circuits

10.5.1 Synthesis Procedure

648

659

660

10.6 Introduction to Races, Cycles, and Hazards

10.6.1 Races and Cycles 10.6.2 Avoidance of Race Conditions 10.6.3 Race-free State Assignments 10.6.4 Hazards 10.6.5 Analysis

663 664

671

673

Contents

xiii

10.7 Summary

673

686

687

11 Sequential Circuits With Programmable Logic Devices

11.1 Registered Programmable Logic Devices

11.1.1 Field-Programmable Logic Sequencers 11.1.2 Registered PALS 11.1.3 PLDs with Programmable Logic Macrocells

691 696 700

702

705 713

11.2 Programmable Gate Arrays

11.2.1 Logic Cell Arrays

11.2.2 ACT FPGAs 11.3 Sequential Circuit Design and PLD Device Selection 11.4 PLD Design Examples

715

717

723

11.5 Computer-aided Design of Sequential PLDs

11.5.1 Sequential Circuit Design Representation with PDL 11.5.2 Processing a PDL Design File

729

11.6 Summary

733

738

12 Logic Circuit Testing and Testable Design

12.1 Digital Logic Circuit Testing

739

12.2 Fault Models

740

741

742

751

12.3 Combinational Logic Circuit Testing

12.3.1 Test Generation 12.3.2 Untestable Faults 12.3.3 Multiple Output Networks 12.3.4 Fault Detection Test Sets 12.3.5 Fault Location and Diagnosis 12.3.6 Random Testing

752 753 757

758

xiv

Contents

12.4 Sequential Logic Circuit Testing

760

12.5

763

Design For Testability 12.5.1 Scan Path Design

764

12.6

Built-in Self-test

768

769

12.6.1 12.6.2 12.6.3

Pseudorandom Test Vector Generation Signature Analysis Built-In Logic Block Observer

772 775

12.7 Board and System-level Boundary Scan

777

12.8 Summary

781

788

789

13 Design Examples

13.1 Electronic Slot Machine

13.1.1 Problem Definition 13.1.2 System Requirements and Solution Plan 13.1.3 Logic Design

789 790

792

801

13.2 Keyless Auto Entry System

13.2.1 Problem Definition 13.2.2 System Requirements 13.2.3 Logic Design

801 803

805

810

13.3 One-lane Traffic Controller

13.3.1 System Requirements 13.3.2 Logic Design

813 815

821

13.4 Grocery Store Cash Register

13.4.1 System Requirements 13.4.2 Logic Design

823 824

Index

833

Preface