• Author / Uploaded
• M10

Citation preview

DIGITAL LOGIC and

Microprocessors

Fredrick J. Hill & Gerald R. Peterson

This comprehensive, integrated introduction to digital hardware design features an up-todate treatment of the fundamentals of logic design, microprocessors, interface design, and assembly language programming. Digital Logic and Microprocessors also includes an introduction to hardware description languages which provides a means of describing more complex sequential circuits and serves as a transition to the discussion of microprocessors. To come to grips with realworld details, the book uses an actual microprocessor (the 6502) as a tool for programming instruction, giving readers experience in those areas vital to system design, including input-output interfacing. The choice of the 6502 makes it possible to illustrate important programming topics with complete routines. Digital Logic and Microprocessors is accessible enough to be understood without prerequisites. This rigorously tested guide presents engineering design topics that can be grasped without a prior background in calculus. As a further aid, numerous completely developed examples appear throughout the book. It therefore can be used by working electrical and computer engineers, students specializing in computer technology or electrical engineering, nonmajors with some knowledge of a high-level language, or by any reader with sufficient interest and desire to learn about computer hardware.

DIGITAL LOGIC AND MICROPROCESSORS

FREDERICK J. HILL

GERALD R. PETERSON

Digital Logic and Microprocessors

Digital Logic and Microprocessors

Fredrick J. Hill and Gerald R. Peterson

John Wiley & Sons

New York Chichester Brisbane Toronto Singapore

Copyright © 1984, by John Wiley & Sons, Inc. All rights reserved. Published simultaneously in Canada.

Reproduction or translation of any part of this work beyond that permitted by Sections 107 and 108 of the 1976 United States Copyright Act without the permission of the copyright owner is unlawful. Requests for permission or further information should be addressed to the Permissions Department, John Wiley & Sons.

Library of Congress Cataloging in Publication Data: Hill, Fredrick J. Digital logic and microprocessors. Includes index. 1. Logic design. 2. Microprocessors—Design and construction. I. Peterson, Gerald R. II. Title. TK7888.4.H55 1984 ISBN 0-471-08539-1

621.3819'58

Printed in the United States of America 109 8 76543 2 1

84-7377

Preface

This volume has been designed to serve as a textbook for the first course in computer hardware. The topics have been chosen to introduce digital hardware to the student who will go on to study nothing more about computers than using a high-level language as well as to the student who plans to specialize in computer science or computer engineering. It begins with the time-honored topics in logic design, moves smoothly into microprocessors, and finishes with an in-depth treatment of interface design and assembly-language programming. The material should be suitable for a class of students including a broad range of majors or for a class of electrical engineering and computer science students. The authors use the book for a two-semester course given in the sophomore year to students in electrical and computer engineering. Very little in the way of prior background has been assumed. Only the interest and desire to learn about computer hardware is required. Many students will have had prior experience with some high-level language, but even this is not essential. For a few pages in Chapter 5 the reader is presumed to have been previously introduced to electricity at the level of ohms law. In classes where this background is not uniformly present, the instructor need only take a more descriptive approach to the material on loading and delay. Our intention has been to satisfy the need for a so-called “modern approach” to the topics of digital hardware. This need is easily justified by the observation that the two current action areas of digital design were unknown 15 or even 10 years before this writing. These two related, but separate, subjects are VLSI design and microprocessor-based system design. Chapters 1 through 10 of this book provide the

v

vi

Preface

fundamentals of digital logic common to both these areas. The potential VLSI designer will then go on to study MOS electronics, interactive graphics, exploitation of the pass transistor, and silicon compilers in other courses. A much larger portion of the readers will be involved at some level with microprocessor-based design. Chapters 11 through 16 continue with this topic. Mastery of these chapters should make it possible for students to apply this subject in the work place whether or not they subsequently take more advanced courses. Chapters 2, 3, and 4 present the traditional subjects of Boolean algebra, number systems, and Karnaugh maps to develop students’ background and catch their interest. Chapters 5 and 7 introduce the common off-the-shelf SSI and MSI parts and notation to facilitate their use. Chapter 6 treats arithmetic and coding, including such microprocessor-related topics as BCD addition and subtraction and overflow. The treatment of circuits with memory, or sequential circuits, in Chapters 8, 9, and 10 has been somewhat abbreviated from that of the authors’ previous book. Introduction to Switching Theory and Logical Design. Understanding the fundamental timing assumptions of sequential circuits is as important as ever, so this subject has not been neglected. State table minimization and state assignment have been deemphasized. The algorithmic state machine or ASM chart is introduced as an alternative notation to the state table. Only clock-mode sequential circuits are considered in these chapters. For the reader who wishes to explore the problems that appear when the clock-mode assumption cannot be satisfied, a comprehensive treatment is included at the end of the book as Chapter 17. A simplified RTL notation is introduced in Chapter 10 and is found helpful (in moderation) in Chapters 11, 13, 14, and 15. Chapters 11 through 16 treat microprocessors at the hardware and assembly^ language level. To come to grips with “real world” details and to include programming, it was necessary to select a particular microprocessor. We chose the 6502 as the simplest architecture still in (and likely to remain in) the marketplace. The instruction set of the TB6502, used in the book, is a proper subset of and includes nearly all the features of the 6502 instruction set. By not requiring the TB6502 to be cycle-by-cycle compatible with the 6502, we were able to provide a partial RTL description of the former at a level appropriate to this book. Simplified versions of the common parallel and serial interface chips were devised to familiarize the students most efficiently with the typical control features of these units. Whether the students are freshmen, sophomores, juniors, or seniors, this book can serve as a first introduction to digital hardware. It may be used for either one or two semesters. The first 10 chapters can fit nicely into a one-semester course supplemented by a logic design laboratory. Chapters 11 through 16 can constitute a second semester, if supported by a comprehensive laboratory experience in assembly-language programming. With less emphasis on laboratory, Chapters 11 and 12 might be added to the first semester, thereby providing a brief introduction to microprocessors. Chapter 17 could be included at the end of either the first or the second semester. For the second semester a laboratory using a 6502-based microcomputer, such as the AIM or SYM, is ideal but not essential. At the assembly-language level, there

Preface

vii

is considerable similarity between the various 8-bit microprocessors. It should be quite satisfactory to use this book for the lecture portion of a course in conjunction with a laboratory supported by a non-6502-based microcomputer and programming manuals for that computer. Fredrick J. Hill Gerald R. Peterson

Contents

1

Between the Transistor and the High-Level Language

1

1.1 1.2 1.3 1.4 1.5

1 3 6 8 9

Prior Perceptions A Spectrum of Digital Languages Control Flow Terms and Roles Some Digital History

2 Boolean Algebra and Digital Logic 2.1 2.2 2.3 2.4 2.5 2.6 2.7

11

Computer Logic Circuits Application of Logic Circuits Evaluation of Boolean Functions Boolean Algebra Simplification of Boolean Functions Boolean Algebra as an Algebra of Subsets On the History of the Algebra of Logic Problems References

11 15 19 21 26 28 31 31 33

3 0,1: Binary Numbers or Logical Values?

35

3.1 3.2

The Binary Number System Conversion between Bases

35 37

ix

X

Contents

3.3 3.4

Binary Coding of Decimal Digits Historical Note Problems References

4 Simplification of Boolean Functions 4.1 4.2 4.3 4.4 4.5

Standard Forms of Boolean Functions Karnaugh Map Representation of Boolean Functions Simplification of Functions on the Karnaugh Map Map Minimization of Product-of-Sums Expressions Incompletely Specified Functions Problems References

5 Standard Digital Integrated Circuits 5.1 5.2 5.3 5.4 5.5 5.6 5.7

Introduction Small-Scale Integrated Circuits Fan-out, Fan-in, and Noise Immunity Switching Delay in Logic Circuits Circuit Implementation with NAND and NOR Gates Multilevel All-NAND Realizations Reducing Package Counts in Multilevel Realizations Problems References

6 Computer Arithmetic and Codes

40 43 44 44

45 45 52 60 66 68 71 73

75 75 79 80 85 87 89 94 98 101

101

Introduction Conversion between Number Bases Coding of Information Parity Binary Arithmetic Implementation of Binary and BCD Addition Carry and Overflow Problems References

103 103 106 111 113 117 121 123 126

7 Combinational MSI Parts, ROMs, and PLAs

127

6.1 6.2 6.3 6.4 6.5 6.6 6.7

7.1 7.2 7.3 7.4

Perspective Combinational MSI Parts Read-Only Memory Chip-Select, Buses, and Three-State Switches

127 128 137 144

xi

Contents

7.5 Programmed Logic Arrays 7.6 Describing Multiplexers with a Graphic Vector Notation 7.7 Special Purpose MSI Parts Problems References

8 Sequential Circuits 8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8

Storage of Information Clocking Registers Memory Element Input Logic A First Design Example The J-K Flip-Flop Design of Counters MSI Registers and Counters Problems References

9 Synthesis of State Machines 9.1 9.2 9.3 9.4 9.5 9.6 9.7

A Language is Needed Standard Symbols for the ASM Chart Vending Machine Control From ASM Charts to Transition Tables Circuit Realization The State Diagram, an Alternative Notation Compatible States Problems References

10 Register Transfer Design 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9 10.10

Generalized ASM Output ASM Chart Representation of a Control Unit Register Transfer Language (RTL) Notation Construction of a Data Unit from an RTL Description Timing of Connections and Transfers Sequencing of Control Combinational Logic and Conditional Transfers Graphical and RTL Bus Notation Timing Refinements in RTL Systems An RTL Design Example Problems References

147 153 154 158 161

163 163 166 171 173 174 177 181 187 195 197

199 199 200 204 208 212 216 221 223 227

229 229 231 233 239 242 245 248 254 256 257 262 266

xii

Contents

11 Small Computer Organization and Programming 11.1 11.2 11.3 11.4

11.5 11.6 11.7 11.8

Introduction Central Processor and Memory Organization CPU Organization and Instruction Formats Fundamental Internal Sequence of a Single-Address Computer Transfer-of-Control and Register-Only Instructions Addition and Subtraction with Carry Commands That Affect Only the Flags Programming Procedures Problems

12 Addressing and Assembly Language 12.1 12.2 12.3 12.4 12.5

Microprocessor Addressing Addressing Modes Assembly Language Programming More Programming Data Conversion, Decimal Arithmetic, and Subroutines Problems

13 Memory and Input/Output 13.1 13.2 13.3 13.4 13.5 13.6 13.7 13.8

Memory Mapping Timing of Memory Operation Parallel Input/Output Interfacing Interactive Input/Output Programming Time Delays Device Drivers Substituting Input Scanning for Combinational Logic Time-Sharing of Interface Ports Problems References

14 Serial Input/Output 14.1 14.2 14.3 14.4 14.5

Serial to Parallel Conversion A Serial Communications Interface Adapter TBSIA A Subroutine for Serial I/O through a TBSIA Interconnecting RS-232 Equipments Computer Networks Problems References

267 267 268 270 272 279 286 290 292 296

301 301 302 311 316 320 330

333 333 338 340 346 355 359 366 370 375 378

379 379 388 393 396 400 403 406

xiii

Contents

15

Additional ProgrammingTopics 15.1 15.2 15.3 15.4 15.5

Pointer Addressing and Stacks Subroutines Interrupts Start-up and Reset Tables and Other Data Structures Problems References

16 Microprocessor-Based SystemsDesign 16.1 16.2 16.3 16.4 16.5 16.6 16.7

Introduction Vending Machine Operation System Specifications Control Unit Design Planning the Program Memory Map Layout Coding the Program Problems

17 The Clock-Mode Assumption Reexamined 17.1 17.2 17.3 17.4 17.5 17.6 17.7 17.8 17.9

Attention to Output Waveforms Elimination of Hazards Synchronizing Inputs to Clock-Mode Circuits Clock Skew on Edge-Triggered Flip-Flops Is That Clock Really Necessary? Synthesis of Level-Mode Sequential Circuits from a Flow Table Races in State Variable Transitions Critical Race-Free State Assignments More Constraints on Level-Mode Realizations Problems References

Appendix A Powers off Two Appendix B Summary off TB65O2 Instruction Set

407 407 411 426 437 439 450 455

457 457 457 459 462 465 471 475 479

481 481 484 486 491 493

498 504 511 516 518 522

523 524

Appendix C TB6502 Instruction Set: Opcodes, Bytes, Cycles Appendix D Mapping the TB6502 into the 6502

527 530

Index

533

Digital Logic and Microprocessors

1

Between the Transistor and the High-Level Language

1.1 Prior Perceptions As the title suggests, this book is organized to serve the reader without previous background in digital hardware. It would be surprising, however, to discover a reader who had no previous experience with the digital world. One encounters the digital computer in the office, in the home, in the elementary and high school classroom, in the game arcade, and on film. Bits and pieces of information about the computer are necessarily accumulated in the process of these encounters. Some readers may have sampled some of the material in the early chapters of this book in their work experience or in precollege course work. The typical reader’s perception of the inside of the computer is quite likely as characterized by Fig. 1.1. The reader may have learned that the active elements inside the box, labeled “computer,” are transistors, as symbolized in the figure by the schematic diagram symbol for the transistor. Sometimes, a very large number of these transistors are found together in a tiny package called an integrated circuit (IC). Mysterious networks of these transistors “think and compute.” Wires connect the computer box to other equipment such as the CRT (cathode ray tube) terminal and printer shown in Fig. 1.1. Through these peripheral devices, with outer covers that also conceal transistors and integrated circuits, the computer communicates with the outside world. Many readers will have had some experience programming a computer in some high-level language such as BASIC, FORTRAN, or PASCAL. These programming tools are called “languages” simply because they are media for communicating orga-

1

2

1

Between the Transistor and the High-Level Language Listing

High-level language program

Computer

Figure 1.1

The computer: inside and out

nized information between intelligent systems, in this case between the user and the computer. These languages are termed “high level” because they permit the user to express concepts in familiar formats. In general, the higher the level of a language the more convenient it is for the user. The notion of typing programs in a high-level language on a CRT terminal and receiving results from a printer as depicted in Fig. 1.1 is probably shared even by those readers without personal programming experience. The scope of this book includes neither the design of transistor circuits for computers nor programming in a high-level language. Most readers will have the opportunity to learn more about transistor circuits in electronics courses. If any readers have not yet studied programming in a high-level language, they are almost certain to do so before they complete their formal education. This book will approach the spectrum of computer topics between these two extremes. Transistors and other electronic components are connected to form the basic building blocks from which computers and other digital systems are constructed. The large majority of these building blocks fall into two classes, those that perform logic and those that store information. A schematic diagram showing how one such logic building block is constructed from transistors, resistors, and diodes is shown in Fig. 1.2. The rules for constructing such schematic diagrams can be thought of as a language. Text written in this language is two-dimensional graphics rather than a one-

1.2 A Spectrum of Digital Languages

Figure 1.2

3

TTL (transistor-transistor-logic) AND gate.

dimensional sequence of symbols, but in the broadest sense it is a language nonetheless. A digital computer might consist of tens of thousands of logic elements, only one of which is shown in Fig. 1.2. It is easily seen that a representation of a computer as a composite diagram consisting of thousands of copies of Fig. 1.2 would be bewildering indeed. Electronic schematic diagrams are an inefficient language for designing and communicating the structures of digital computers.

1.2 A Spectrum of Digital Languages A spectrum of languages, in addition to high-level languages and the lowest-level electronic diagrams, is both available and necessary for describing and using digital systems. Providing you with an understanding of these intermediate languages is the object of this book. In this chapter our goal is to provide a map showing the relationship between the various representations of digital systems and an indication of where these topics might be treated in later chapters. As was the case with Fig. 1.2, details will be displayed with which you may not be completely comfortable until you have considered subsequent chapters. The spectrum of languages available for describing digital systems and exploiting computers is summarized in Fig. 1.3. The lowest level, electronic schematic diagrams, is shown at the bottom of the chart; high-level languages are at the top. A variety of features distinguish the languages entered at various vertical levels in the chart. The single measure that applies to all the entries in the chart and increases from language to language moving upward through the chart may be characterized as efficiency of description. A higher-level language will be provided with more powerful and more complex building blocks or primitives and, therefore, will usually require fewer symbols, fewer lines, or less space on a page to describe a given system