Digital design : from Gates to intelligent machines

D igital D esig n :

From Cates to

Intelligent Machines

LIMITED W ARRANTY AN D DISCLAIM ER OF LIABILITY

THE CD-ROM THAT ACCOMPANIES THE BOOK M AY BE U SE D ON A SINGLE PC

ONLY. THE LICENSE DOES NOT PERMIT THE USE ON A NETW ORK (OF ANY

i ^ D ) . YOU FURTHER AGREE THAT THIS LICENSE GRANTS PERMISSION TO

USE THE PRODUCTS CONTAINED HEREIN, BUT DOES NOT GIVE YO U RIGHT

OF O W E R S H IP TO A NY OF THE CONTENT OR PRODUCT CONTAINED ON THIS

CD-ROM. USE OF THIRD-PARTY SOFTWARE CONTAINED ON THIS CD-ROM IS

LIMITED TO AN D SUBJECT TO LICENSING TERMS FOR THE RESPECTIVE

PRODUCTS,

CHARLES RIVER M EDIA, INC. (“CRM”) A N D /O R A N Y O N E WHO HAS BEEN

INVOLVED EN THE WRITING, CREATION, OR PRODUCTION OF THE ACCOM￾PANYING CODE (“THE SOFTW ARE”) OR THE THIRD-PARTY PRODUCTS CON￾TAINED ON THE CD ROM OR TEXTUAL MATERIAL IN THE BOOK, CANNOT

AND DO NOT W ARRANT THE PERFORMANCE OR RESULTS THAT M AY BE OB￾TAINED BY USING THE SOFTW ARE OR CONTENTS OF THE BOOK. THE A U￾THOR A N D PUBLISHER HAVE USED THEIR BEST EFFORTS TO ENSURE THE

ACCURACY A ND FUNCTIONALITY OF THE TEXTUAL M ATERIAL A N D PRO￾GRAMS CONTAINED HEREIN. WE HOW EVER, M AKE N O W AR RANTY OF ANY

KIND, EXPRESS OR IMPLIED, REGARDING THE PERFORM ANCE OF THESE

PROGRAMS OR CONTENTS. THE SOFTW ARE IS SOLD “A S IS” WITHOUT W AR￾RANTY (EXCEPT FOR DEFECTIVE MATERIALS U SE D IN M ANUFACTURING

THE DISK OR DUE TO FAULTY W ORKMANSHIP).

THE AUTHOR, THE PUBLISHER, DEVELOPERS OF THIRD-PARTY SOFTWARE,

A ND ANYONE INVOLVED IN THE PRODUCTION A N D M ANUFACTURING OF

THIS WORK SHALL NOT BE LIABLE FOR DA M AGES OF A N Y KIND ARISING

OUT OF THE USE OF (OR THE INABILITY TO USE) THE PROGRAM S, SOURCE

CODE, OR TEXTUAL MATERIAL CONTAINED IN THIS PUBLICATION. THIS IN￾CLUDES. BUT IS NOT LIMITED TO, LOSS OF REVENUE OR PROFIT, OR OTHER

INCIDENTAL OR CONSEQUENTIAL DAM AGES ARISING OUT OF THE USE OF

THE PRODUCT.

THE s o p REMEDY IN THE EVENT OF A CLAIM OF A N Y KIND IS EXPRESSLY

LIMITED TO REPLACEMENT OF THE BOOK AN D/O R CD-ROM , A N D ONLY AT

THE DISCRETION OF CRM.

THE USE OF ‘^MPLIED W ARRANTY” A N D CERTAIN “EXC LUSIO NS” VARIES

FROM STATE TO STATE. AND M AY NOT APPLY TO THE PURCHASER OF THIS

PRODUCT.

D igita l D esig n :

From Cates to

intelligent Machines

,n ' :;ir

T H - ’ V iỆ ?J

t'H O ? :13 '

B ruce K atz

/..H O CTH /(M /?iiVỀrf

.. _J

D

DA VINCI ENGINEERING PRESS

Hingham, Massachusetts

Copyright 2006 by THOMSON DELMAR LEARNING. Published by DA VINCI ENGDJEERING PRESS.

All rights reserved.

Software contained on the CD-ROM was developed by Bruce Katz and is used with his permission.

No part of this publication may be reproduced in any way, stored in a retrieval system of any type, or

transmitted by any means or media, electronic or mechanical, including, but not limited to, photocopy,

recording, or scanning, without prior permission in writing from the publisher.

Cover Design: The Printed Image

DA VINCI ENGINEERING PRESS

CHARLES RIVER MEDIA, INC.

10 Downer Avenue

Hingham, Massachusetts 02043

781-740-0400

781-7^40-8816 (FAX)

[email protected]

www.charlesriver.com

This book is printed on acid-free paper.

Library of Congress Cataloging-in-Publication Data

Katz, Bruce F., 1959-

Digiro/ design from Gates to intelligent machines / Bruce F. Katz.— 1st ed.

p. cm.

Includes index.

ISBN 1-58450-374-2 (alk. paper)

1. Logic circuits. 2. Logic design. 3. Computer architecture. I. Title.

TK7868.L6K384 2006

621.39'5—dc22

2005022086

All brand names and product names mentioned in this book are trademarks or service marks of their

respective companies. Any omission or misuse (of any kind) of service marks or trademarks should

not be regarded as intent to infringe on the property of others. The publisher recognizes and respects

all marks used by companies, manufacturers, and developers as a means to distinguish their products.

Printed in the United States of America

05 7 6 5 4 3 2 First Edition

CHARLES RIVER MEDIA titles are available for site license or bulk purchase by instimtions, user

groups, corporations, etc. For additional information, please contact the Special Sales Department at

781-740-0400.

Requests for replacement of a defective CD-ROM must be accompanied by the original disc, your

mailing address, telephone number, date of purchase and purchase price. Please state the nature of

the problem, and send the information to CHARLES RIVER MEDIA, INC., 10 Downer Avenue.

Hingham, Massachusetts 02043. CRM’s sole obligation to the purchaser is to replace the disc, based

on defective materials or faulty workmanship, but not on the operation or functionality of the product.

Contents

Preface xvii

1 Numbers and Number Systems 1

Inưoduction 1

Numbers 4

Positional Number S\ stems and Bases 5

Conversions Benveen Bases s

Conversions to and from Other Bases to Base 10 9

Binar> Number Svstems 11

Binar>-Addition and Submcrion 12

Binan-Multiplication 15

Ne23ti\ e Numbers in Bmar\': Signed Maanitude and T«o's Complement 15

Codes 18

BCD IS

GrayCodina 19

Parir>‘ 20

ASCII and Unicode 20

Summan.' 22

Exercises : :

LATTICE Exercises 23

2 Boolean Algebra 25

Inơoduction 25

Loỉical Functions in Boolean Algebra 26

Truth Tables 29

vi Contents

Tautology, Equivalence, and Logical Laws 31

Other Useftil Logical Operators 33

Simplification 34

Simplification with Logical Laws 35

Minterms and Maxterms 37

Karnaugh Maps and M inimization 42

Summary 50

Exercises 51

LATTICE Exercises 53

Elementary Combinational Circuits 55

Introduction 55

Logic, Gates, and Circuits 56

Elementary Gates 56

Circuits to Functions and Truth Tables 59

Realizing a Function Directly 61

Realizing a Circuit Through Minterms and Maxterms 63

Alternative Representations o f SOP and POS Functions 64

Realizing a M inimized Form o f a Function 6 6

Gates and Integrated Circuits in Practice 67

Logic Technologies and Logic Families 6 8

Values and Voltages 69

Fan-In and Fan-Out 70

Gate Delays and Circuit Delays 72

Implementation o f Gates 74

Summary 78

Exercises 78

LATTICE Exercises 80

Complex Combinational Circuits 81

Introduction 81

Binary Adders 82

Full Adder 82

Ripple-Cam- Adder 85

Cam-Look-Ahead Adder 8 6

Two's Complement Addition and Subưaction 8 8

Decoders and Encoders 90

Binan Decoders 91

Decoder Applications 95

Encoders 97

Multiplexers and Demultiplexers 100

Programmable Logic Devices (PLDs) 107

Proaranunable Read Only Memor>' (PROM) 107

Prosrammable .Ajrav Losic (P.-VLt) 108

Programmable Logic .\rray (PLA) 109

SummaiẠ' 112

Exercises 114

LATTICE Exercises 116

Elements of Sequential Design 117

Inơoduction 117

Latches 119

SR Latch 119

D Latch 123

Flip-Flops 125

Edge-Triggered D Flip-Flop 125

Edae-Triaaered J-K Flip-Flop 12'

Registers 130

Parallel-Load Registers 130

Shift Registers 132

Suntman- 134

Exercises 134

LATTICE Exercises 137

Contents vii

viii Contents

Sequential Machines 139

Introduction 139

Finite State Machines 140

M ealy and Moore Machines 144

Sequential Machine Analysis 145

Sequential Machine Synthesis 150

General Method 150

The Parity Example 153

A Sequence Recognition Example 157

A Maze Example 162

Designing with J-K Flip-Flops 170

Summary 174

Exercises 175

LATTICE Exercises 177

Elements of Computer Design 179

Introduction 179

Computer Organization 182

Memory 183

The CPU 189

I/O 191

Summary 193

Exercises 194

LATTICE Exercises 195

The Design of a Simple CPU and Computer 197

Introduction 197

The Register Set 198

The Instruction Set 201

The Control Unit 204

The Fetch-Decode-Execute Cycle 205

The Control Unit Finite State Machine 207

Contents IX

Data Paths 210

The ALU 214

Putting It All Togeứier 218

Further Issues in Computer Design 223

Microsequencing 224

Interrupts 224

ÍUSC and Pipelining 225

High-Level Languages 226

Summary 226

Exercises 227

LATTICE Exercises 228

plorations in Digital Intellligence 229

Introduction 229

Pattern Recognition 232

Pattern Completion 235

Interference and Expert Systems 236

Neural Networks 240

Learning 249

Search 254

Emergent Behavior 256

Summary 259

LATTICE Exercises 260

The LATTICE System 263

Introduction 263

Installation 264

System Requirements 264

Installation Procedure 264

General Operation 265

Program Layout 265

File Menu Options 265

Animation Options 266

M ouse Buttons 266

Truth Systems 267

Variable Drop-Down Box 267

Operator Drop-Down Box 268

Truth Table Options (Bottom o f Screen) 269

Variable Settings Dialog B ox 269

State Systems 270

Column 1 (State Color) 271

Column 2 (State Action) 271

Column 3 (State Name) 273

Columns 4 Through the End o f the Table (State Transitions) 273

State Variable Settings 273

State Table Options (Bottom o f Screen) 275

Tricks o f the Trade 275

System Submission 277

Index 279

X Contents

Preface

F

1 or a \ ariety o f reasons, but most sisnificantly. die rise of the computer as a

cenffal, if not dominating, force in our lives, digital cừcuits have taken on a

new importance in ửie past nventy years. There are abundant and various re￾sources on the softw are that drives these machines, and whole sections o f book￾stores are de\ oted to the topic. But for die student who w ishes to understand what

really makes computers and ứieir sừnpler digital counterparts work, the choices are

limited to a set of well-meanina, but dr\'. textbooks on digital design.

This book aims to remedy tìiis problem in uvo ways. Fừst, it explicitl) ac￾knowledges that digital desian is an intrinsically \ isual and dNTiamic process. It is

visual in the sense that the end products (digital circuits), are physical objects best

represented in diaarammatic form. Abo\ e all. it is visual in the sense that for ứie

tvvo intellectual underpinninas of die design process (truth tables and finite state

diagrams), the most direct and instinctual representations are tw o-dimensional

drawinas.

Therefore, most books written on the topic are liberalh' populated with figiires.

This captures the v isual aspect of ứie diaital design, but does linle to address the

d\Tiamic aspect. To take just one example, a ơuth table is both a %‘isual and d\ -

namic object. It is ưivially \ isual m the sense ứiat it is a table, but it is also d\Tiamie

in the sense that it ouaht to be possible to quickly ehanae the cormecti\ es or the

\ ariables or the expressions themselves to see the effect on the truứi \ alues. This,

of course, is not possible on the written paae. but is eminenth- suited to a prosram

running on a digital machine. It is ironic, but not without precedent, that ửie teach￾ing meửiods for a ai\ en topic lag behind the technoloa\ that the teaching is sup￾posed to be about.

This book closes the gap beween pedaaoav and technoloa\ w ith the inclusion

of the LATTICE softi\ are s> stem. LATTICE contains ffuth tables and state tables

for simulatina combinational and sequential circuits, respectively. These tables

x i

xii Preface

drive cellular automata to provide a direct visual counterpart to the dynamics that

they represent. This differs significantly from other simulation techniques in that

( 1 ) it is easier to use— the student can be up and running with minimal effort, and

(2 ) it abstracts the notion o f the underlying logic and dynamics from the particular

implementation o f such. This is not to say that circuit realization is not important,

and in fact, this process is at the heart o f this book. Rather, it provides an entry to

what is a daunting topic for many by providing a direct animated counterpart to the

topic at hand. It is also hoped that the emergent visual and musical behavior o f cel￾lular automata offers a relatively painless environment whereby difficult material

can be absorbed unconsciously and with relatively little effort.

The other main difference between this book and competing texts is that the

cuưent effort aims to be comprehensive without presenting an overwhelm ing

amount o f material. An introductory textbook in the field o f digital design can aim

at two distinct and competing goals. The first is to provide the student with the

foundation for future progress in the field, and the second is to serve as a compre￾hensive reference for future use. It is not hard to imagine a professor putting the

finishing touches on his 900-page tome all the while dreaming o f a working engi￾neer some twenty years after graduation saying to him self, “Hmm, tricky problem.

I think I’ll consult my w ell-w om Cholmondesley from freshman design on this

one.” However gratifying this imaginative diversion may be, m y experience has

been the beginning engineer w ill suffer by this approach, even if he is later com ­

pensated. The reason is that there is simply too much material to grasp in a single

course. It would be as if a Physics 101 book provided a detailed account o f N ew ­

tonian mechanics and quantxim mechanics. Normally, the former is provided in de￾tail and the latter, if at all, in outline only.

The mind o f the budding engineer is not different from the rising physicist in

the sense that it needs to understand the nature o f the problem before it can grasp

the intricacies o f the solution. What is (are) the problem(s) o f digital design? They

are twofold. The first is to understand how a device that implements a logical func￾tion can be built, and the second is the design and implementation o f a sequential

machine. Neither o f these is difficult for the student with the proper background

but it would be a mistake to assume that this background is firmly in place for all

students. Logic is the foundation for the former and it is poorly taught, if at all. in

the secondary school system, and is not always given a formal introduction in un￾dergraduate education. Discrete mathematics in general, and finite state machines

in particular, are the foundation for the latter, and this also too often falls victim to

Preface xiii

spotty treatment. In both cases, the LATTICE system provides a means of making

these abstract endeavors direct and concrete.

Finally, and less obvious, tìie problem of digital design can no longer be held

separate from the design o f intelligent machines. As argued in ứie final chapter, so￾called smart devices are increasingly common. It is not possible however, to begin

to design such devices vviửiout a grasp o f the foundations of intelligent machines.

This topic is invariably skipped in an introductory text because it’s construed as

either too advanced or too esoteric. Yet as the final chapter shows, many o f the

concepts are extensions of what has already been developed in earlier chapters.

One cannot ignore the motivational properties o f such topics. It is one ứiing to build

a mod 5 counter, and quite anotìier to build a machine that uses the principles of ge￾netic algorithms to design a better musical composition. The excitement that the

student feels cannot be held separate from the educational process, and it is hoped

that this excitement will facilitate the grasping of the primary material, and ulti￾mately provide the desire to create the next generation of digital machines.

ACKNOWLEDGMENTS______________________________________________________

I would like to thank the many people 1 have taught digital design with over the

years including s. “Basu” Basavaiah, Tim Kurzweg, Alex Meystel, A1 Tonik. Oleh

Tretiak, and Lazar Trachtenburg. Other colleagues, especially Allon Guez. also

contributed valuable suggestions with respect to the accompanying software. They

provided valuable insights into the subject and often influenced this book wiửiout

realizing it, I would also like to thank the many hundreds o f students who ha\ e

contributed by suffering through my pedagogical experiments until I arrived at an

adequate way o f presenting this material, and especially Dan Lofaro for his help

with the music files. Finally. I would like to thank my wife. Ayẹa who suffered, by

putting up with me as I struggled to complete this work and by listenine to the

unusual maqams generated by the LATTICE prosram.