Introduction to logic design

ÌN

TC

SẢCHKẺMTIIEO Đ U C D Đ Ặ T T Ặ I

PHỔNG NGHE NHỈN

rí—^ I _,'cv— ''<—'

\ “rd

Ỉl-Hỉi cmàis

^iKMĩmom .r

W f O R B E M t f

V

WfflEWMTIOH

Ihy vten l)l1K fC N -I >

l i l i i i i l l l l

KNV 14000812

^ I \ B. 1VĨAKCĨ5

■Coupms

'OHLY

Introduction to Logic Design

Introduction to Logic Design

Second Edition

A l a n B . M a r c o v i t z

Florida Atlantic U niversin

P V ' i ' t N V -

ĐẠI HỌC THAI NOUYẼN

TRUNGTẢMHỌCLIỆU

Higher Education

Boston Burr Ridge. IL Dubuque, lA Madison, Wl New York San Francisco St. Louis

Bangkok Bogotá Caracas Kuala Lum pur Lisbon London M adrid Mexico City

Milan Montreal New Delhi Santiago Seoul Singapore Sydney Taipei Toronto

INTRODUCTION TO LOGIC DESIGN. SECOND EDITION

Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue o f the Americas. New York.

NY 10020. Copyright © 2005.2002 by The McGraw-Hill Companies, Inc. All rights reserved. No part of this publication may

be reproduced or disưibuted in any form or by any means, or stored in a database or retrieval system, without the prior wrinen

consent of The McGraw-Hill Companies, Inc., including, but not limited to, in any network or other electronic storage or

transmission, or broadcast for distance learning.

Some ancillaries. including electronic and print components, may not be available to customers outside the United States.

This book is printed on acid-free paper.

Domestic 2 3 4 5 6 7 8 9 0 DOC/DOC0 9 8 7 6 5

ISBN 0-07-286516-^

Publisher: Elizabeth A. Jones

Senior sponsoring editor: Carlise Paulson

Developmental editor: Melinda D. Bilecki

Marketing manager: Dawn R. Bercier

Senior project manager: Jane Mohr

Lead production supervisor: Sandy Ludovissx

Lead media project manager: Audrey A. Reiter

Senior media technology producer: Eric A. Weber

Designer: Rick D. Noel

Cover designer; Rokusek Design

Cover illustration: Rokusek Design

Compositor: Interactive Composition Corporaiion

Typeface: Ì0/I2 Times Roman

Printer: R. R. Donnelley Crawfordsville, IN

L ibrary of Congress Cata]oging>in-Publication Data

Marcovitz, Alan B.

Introduction to logic design / Alan B. Marcovitz. — 2nd ed.

p. cm.

Includes index.

ISBN 0-07-286516-4

1. Logic circuits. 2. Logic design. 1. Title.

TK7868.L6M355 2005

621,39’5-dc22 2003044277

CIP

www.mhhe.com

BRIEF CONTENTS

C hapter 1 Inưoductíon I

C hapter 2 Switching Algebra and Logic Circuits 45

C h a p te r s The Karnaugh Map 129

C hapter 4 Function Minimization Algorithms 211

C hapter 5 Larger Combinational Systems 261

C hapter 6 Analysis o f Sequential Systems 363

C hapter 7 The Design o f Sequential Systems 409

C hapter 8 Solving Larger Sequential Problems 485

C hapter 9 Simplification o f Sequential Circuits 533

Appendix A Laboratory Experiments 583

Appendix B Answers to Selected Exercises 612

Appendix c Chapter Test Answers 635

Index 647

CONTENTS

Preface ix

Chapter 1

Introduction 1

1.1 A B rief R eview o f Num ber System s 3

1.1.1 Octal and Hexadecinml 6

1.1.2 B inary A ddition 8

1.1.3 Sig n ed N um bers 10

1.1.4 B inary Subtraction 13

1.1.5 B inary C oded D ecim a l (B C D ) 15

1.1.6 Other Codes 16

1.2 The D esign Process for Com binational

System s 19

1.3 D on't Care C onditions 22

1.4 The D evelopm ent o f Truth Tables 23

1.5 The Laboratory 27

1.6 S olved Problem s 28

1.7 E xercises 37

1.8 Chapter 1 Test 42

C ^ a o te ’ 2

Switching Algebra and Logic

Circuits

2.1 Definition o f Sw itchina Algebra 46

2.2 Basic Properties o f Sw itching

Algebra 49

2.3 M anipulation o f A lgebraic Functions 51

2.4 Implem entation o f Functions wiứi A N D . OR.

and N O T Gates 56

2.5 From the Truth Table to Algebraic

Expressions 61

2.6 Inưoduction to ứie Karnaugh Map 65

2.7 The Com plem ent and Product o f Sum s 73

2.8 N A N D , N OR. and E xclusive-O R

Gates 75

2 .9 Sim plification o f A lgebraic Expressions 82

2.10 M anipulation o f Algebraic Functions and

N A N D Gate Im plem entations 90

2.11 A More General B oolean A lgebra 98

2 .1 2 S olved Problem s 100

2.13 Exercises 119

2 .1 4 Chapter 2 Test 126

Chapter 3

The Karnaugh Map 129

3.1 M inim um Sum o f Product E xpressions U sing

ứie Karnaugh M ap 133

3.2 D on't Cares 146

3.3 Product o f Sum s 150

3.4 M inim um C ost Gate Im plem entations 154

3.5 F ive- and Six-V ariable M aps 156

3.6 M ultiple Output Problem s 163

3.7 S olved Problem s 174

3.8 E xercises 202

3.9 Chapter 3 Test 207

Chapter 4

Function Minimization

Algorithms 211

4.1 Q uine-M cC luskey M ethod for

One Output 211

4.2 Iterated C onsensus for c ,

4.3 Prime Implicant Tables fo. , g

4.4 Q uine-M cC luskey for Multip.

Problem s 226

4.5 Iterated C onsensus for M ultiple I :

Problem s 229

4.6 Prime Implicant Tables for M ultiple c lut

Problem s 232

4 .7 Solved Problems 236

4 .8 Exercises 257

4 .9 Chapter 4 Test 258

C h a p te r 5

Uirger Combinational

Systems 261

5.1 Delay in Combinanoaal Lofflc Circuits 262

S ã Adders and Other Ariứunetic Circuits 264

5.2.1 Adders 2 M

5J.J1 SubtnK ĩors and Á d íừ r SubmỉCtors 26S

5.2.3 Comparators 269

5 J Decoders 270

5.4 Encoders and Priorit> Encoders 276

5.5 Multiplexers 278

5.6 Three-State Gates 281

5.7 Gate Arravs— ROMs. PLAs. and P.\Ls :S2

5.7.1 Desiiinin^ Hiĩh Retsd-On[y

Memorit;s 2S7

5 .1 ^ Desiiĩniniỉ M'iih P w ĩn im m ư b u t i ’iiV

Amnj￾5.7.3 D esigning with ProĩnmưruứiU A rnjy

U>ị Í 291

5.8 Laraer Examples 294

5-8-1 S w en -S ti^m im D isplays I F im M ajor

E uunplm 2 9 Ĩ

5.5.2 A n E n v r Coding Syỉtfíĩt Ỉ0 2

5.9 Solved Problems 306

5.10 Exercises 346

5.11 Chapter 5 Tsst 358

C hapter 6

Analysis of Sequential

Systems 363

6.1 State Tables and Diagrams 365

Latches and Flip Flops 36"'

6-3 --\nalvsi> o f Sequendal Sv>tem5 3“b

6.4 Solved Problsữis ,’ S6

6 ^ Exercises 3'W

6.6 Chapcer 6 Teit 40’

C h a p te r 7

Th« Design of Sequential

Systems 409

7.1 F% H op Itesign Techniques 414

The D esira o f S>-ncbroooui Counters 430

7 3 D esisn ot'As>TK:hronous Counters 440

7.4 Derivation o f Siaie Tables and Stale

Diaarams 443

7 j Solved Problems 45S

7.6 Exercises 475

7.7 Chapter 7 Test 4S3

C M acter 8

Solving Larger Sequential

Problems 48Õ

8.1 Shift R eãsters 4S5

8 ^ Counters 491

8-J Proaranmable L o á c D evices I PLDsi 49S

8.4 Design Using ASM Diagrams 503

8 ^ One-Shoi Encodini 50 “

8.6 Hardware D esisn L anỉuases 50S

8.7 More Complex Examples 511

o Solved Problems 5 1 '

8 ^ Exercises 52"

8.10 Chapters Test 531

C -ac :e - 9

Simplification of Sequential

Circuits 533

9.1 A Tibulir Method for Siaie Reducncn 5.'5

Pam ũotiỉ 5-tI

'Ỉ.I.l P 'L r^ riii r: .-J.'

FinJirj ÍP Ps.’r.-c’-j .--i?

9-3 Stita ReducúOE U sĩiiỉ Pirúứ oci 5-ù

9.4 Cttooiiag a Scdtí A íiiỉn iiien : Í5-1

9 J Solved Problems 5e<Ị

9 .6 E x ercises í " s

9.7 Cáipter Test ?S0

v iii Contents

A ppendix A

Laboratory Experiments 583

A .l Hardware L ogic Lab 583

A .2 WinBreadboard''''^ and

M acBreadboard™ 587

A .3 Introduction to LogicW orks 4 589

A .4 Introduction to Altera M ax+plusII 594

A .5 A Set o f L ogic D esign Experim ents 598

A.5.1 Experiments Based on Chapter 2

Material 598

A.5.2 Experiments Based on Chapter 5

Material 600

A .5.3 Experim ents B a sed on C hapter 6

Material 603

A.5.4 Experiments Based on Chapter 7

Material 605

A.5.5 E xperim ents B a sed on Chapter 8

Material 606

A .6 Layout o f C hips R eferenced in the Text

and Experim ents 607

A ppendix B

Answers to Selected

Exercises 612

A ppendix c

Chapter Test Answers 635

Index 647

PREFACE

T

his book is intended as an inưoducton losic design book for

students in computer science, computer ensineering. and elecDri￾cal engineering. It has no prerequisites, alứiough the maturit)-

attained through an inưoduction 10 endneering course or a first pro￾gramming course would be helpful.

The book sơesses fundamentals. It leaches through a large number

o f examples. The philosophy o f the author is ửiat the only way to leam

logic design is to do a large number of design problems. Thus, in addi￾tion to the numerous examples in the body of ứìe ĩexỉ. each chapter has a

set o f Solved Problems, that is. problems and their solutions, a larse set

o f Exercises (with answers to selected exercises in Appendix B). and a

Chapter Test (with answers in Appendix C). In addition, there are a set of

laboratory experiments that tie the ứieorv' to the real world. Appendix A

provides the background to do these experiments with a standard hard￾ware laboratory (chips, switches, lights, and wires), a breadboard simu￾lator (for the PC or Macintosh), and two schematic capture tools. The

course can be taught widiout the laboraior>-. but the student w ill beneftt

sisnificantly from ửie addition o f 8 to 10 selected experiments.

Although computer-aided tools are widely used for the desiffn o f

large systems, the student must first understand the basics. The basics

provide more than enough material for a ftrst course. The schemaiic cap￾ture laboratory exercises and a section on Hardware D esisn Lanauaees

in Chapter 8 provide som e material for a ưansition to a second course

based on one o f the computer-aided tool sets.

Chapter 1 gives a brief overv iew o f number systems as it applies to

the material o f this book. (Those students who have studied this in an

earlier course can skip to Section 1.2.) It Chen discusses the steps in ứie

design process for combinational systems and the development of cruth

tables.

Chapter 2 inơoduces switching alsebra and the implementaiion of

switching functions using common sates— ANT). OR. NOT. N .W D .

NOR. E\clusive-O R . and Exclusive-NOR. We are only concerned with

die Ì02ÌC b e h a v io r of the gates, n o t ứìe e le c ơ o n ic im p lem en taiio n .

Chapter 3 deals with simplification usins the Kamaueh map. It p ro ­

v id es m eth o d s fo r s o lv in g pro b lem s (Up to six v ariab les) iứì b oth single

and multiple outputs.

Chapter 4 inưoduces two algorithmic methods for soh ine com bi￾national problems— the Quine-McCluskev method and Iterated Con￾sensus. Both provide all o f the prime impUcants o f a function or set of

functions, and then use the sam e tabular m ethod to find m inim um sum o f

products solutions.

Chapter 5 is concerned with the design o f larger com binational

system s. It introduces a num ber o f com m ercially available larger d e￾vices, including adders, comparators, decoders, encoders and priority

encoders, and m ultiplexers. That is follow ed by a discussion o f ứie use

o f logic arrays— RO M s, PLA s, and PALs for the im plem entation o f

m edium scale com binational system s. Finally, tw o larger system s are

designed.

Chapter 6 introduces sequential system s. It starts by exam ining the

behavior o f latches and flip flops. It then d iscu sses techniques to analyze

ứie behavior o f sequential system s.

Chapter 7 inừoduces the design process for sequential system s. The

special case o f counters is studied next. Finally, the solution o f word

problem s, developing the state table or state diagram from a verbal

description o f the problem is presented in detail.

Chapter 8 look s at larger sequential system s. It starts by exam ining

ứie design o f shift registers and counters. Then, PL D s are presented.

Three techniques that are useful in the design o f m ore com plex

system s— A SM diagram s, one-shot encoding, and H D L s— are discussed

next. Finally, tw o exam ples o f larger system s are presented.

Chapter 9 deals with state reduction and state assignm ent issues.

First, a tabular approach for state reduction is presented. Then partitions

are utilized both for state reduction and for achieving a state assignm ent

that w ill utilize less com binational logic.

A feature o f this text is the S olved Problem s. Each chapter has a

large num ber o f problem s, illustrating the techniques d eveloped in the

body o f the text, follow ed by a detailed solution o f each problem . Stu￾dents are urged to solve each problem (w ithout looking at the solution)

and then com pare their solution with the one show n.

Each chapter contains a large set o f exercises. A nsw ers to a selection

o f these are contained in A ppendix B. Solutions w ill be m ade available

to instructors through the W eb. In addition, each chapter con clud es with

a Chapter Test; answers are given in A ppendix c.

Another unique feature o f the book is the laboratory exercises, in￾cluded in Appendix A. Four platform s are presented— a hardware based

Logic Lab (using chips, w ires, etc.); a hardware lab sim ulator that allow s

the student to “connect" w ires on the com puter screen; and tw o circuit

capture programs, LogicW orks 4 and Altera M ax+plus n. Enough

information is provided about each to allow the student to perform a

variety o f experim ents, A set o f 26 laboratory exercises are presented.

Several o f these have options, to allow the instructor to chanae the

details from one term to ứie next.

We teach this material as a four-credit course that includes an

averase o f 3 1/2 hours per w eek o f lecture, plus, typically, eight labo￾ratory exercises. (The lab is unscheduled; it is manned by Graduate

Preface

Assistants 40 hours per week; thev srade ứie labs.) In that course we

cover

Chapter 1: all o f it

Chapter 2: all but 2.11

Chapter 3: all o f it

Chapter 4: if time permits at the end o f the semester

Chapter 5: all but 5.8. However, there is a siaded design problem

based on that material (10 percent o f the grade; students usually

working in groups o f 2 or 3).

Chapter 6: all o f it

Chapter 7: all o f it

Chapter 8: 8.1. 8.2. 8.3. We sometimes have a second project based

on 8.7.

Chapter 9 and Chapter 4: We often have some dme to look at one

of these. We have never been able to cover both.

With less time, the coverage o f Section 2.10 could be minimized.

Section 3.5 is not needed for continuin*; Section 3.6 is used somewhat in

the discussion o f PLAs in Section 5.7.2. Chapter 5 is not needed for any￾thing else in the text, although many o f the topics are useful to students

e lsew h ere. The insưuctor can pick and choose among the topics. The SỈỈ

and r flip flops could be omitted in Chapters 6 and 7. Sections 7.2 and 7.3

could be omined without loss o f condnuit>-. As is the case for Chapter 5.

the instructor can pick and choose amona the topics o f Chapter 8. With a

limited amount o f time. Section 9.1 could be covered. With more rime, it

could be skipped and state reduction taueht usina partitions ^9.2 and 9.3).

ACKNOWLEDGMENTS

I want to lhank my w ife. A lh n . for her encouragemenỉ and for enduring

endless hours when I w as closeted in my office working on Uie manu￾script. Several o f my colleagues at Florida Atlantic Universit>- have read

pans o f the manuscript and have taught from earlier drafts. I wish to ac￾knowledge especially Mohammad Ilvas. Iraad Mahsoub. Oae Marques.

Imad Jawhar, Abhi Pandya. and Shi Zhong for theữ help. In addition. I

wish to express my appreciation to my chairs. Mohanunad Ilyas. Rov

Le\ . and Borko Fuhrt who made assisnmenis ứiat allowed me to work

on the book. Even more importantly. I want to thank my students who

provided me with the impetus to write a more suitable text, w ho suffered

through earlier drafts of ứie book, and who made manv suggestions and

coưections. I want to thank Visram Raihnam for his contributions to ứie

section on Altera tools. The reviewers—

Michael McCool. ưniversiụ- o f Waterloo:

Pinaki Mazumder, Universir\' o f Michisan:

x ii Preface

N ick Phillips, Southern Illinois U niversity;

Gary J. M inden, U niversity o f Kansas;

D aniel J. Tylavsky, A rizona State University;

Nadar I. Rafla, B o ise State University;

Dan Stanzione, C lem son U niversity;

Frank M . Candocia, Florida International University;

Lynn Stauffer, Sonom a State U niversity;

R ajeev Barua, U niversity o f M aryland—

provided m any useful com m ents and suggestions. The book is m uch

better because o f their efforts. Finally, the staff at M cG raw -H ill, par￾ticularly C arlise Paulson, M elinda Dougharty, Jane Mohr, B etsy Jones.

Barbara Som ogyi, R ick N oel, Sandy Ludovissy, Audrey Reiter, and Daw n

Bercier have been indispensable in producing the final product, as has

M ichael Bohrer-Clancy at Interactive C om position Corporation.

A la n M a rco v itz