STRUCTURED
`
`COMPUTER ORGANIZATION
`
`SECOND EDITIGN
`
`ANDREW S. TANENBAUM
`
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`PRENnCE-HALL, INC.
`
`ENGLEWOOD CLIFFS, NEW JERSEY 07632
`
`Intel Exhibit 1043
`Intel v. Iida
`
`

`

`Library ofCongress Cataloging in Publication Data
`Tanenbaum, Andrew, S. (date)
`Structured Computer Organization
`Includes index.
`1. Electronic digital computers—Programming.
`L. Title
`A76.6.T38
`1984
`001.642
`83-2916
`ISBN 0-13-854489-1
`
`To Suzanne, Barbara, Marvin and the memory of Sweetie =
`
`Productionteditorial supervision: Nancy Milnamow
`Manufacturing buyer: Gordon Osbourne
`
`© 1984 by Prentice-Hall, Inc., Englewood Cliffs, N. J. 07632
`
`All rights reserved. No part of this book
`may be reproduced in any form or by any means
`without permission in writing from the publisher.
`
`098765 4 3
`
`Printed in the United States of America
`
`ISBN O-13-6544a89-1
`
`PRENTICE-HALL INTERNATIONAL, INC., London
`PRENTICE-HALL OF AUSTRALIA PTY. LTD., Sydney
`EDITORA PRENTICE-HALL DO BRASIL, LTDA., Rio de Janeiro
`PRENTICE-HALL OF CANADA,LTD., Toronto
`PRENTICE-HALL OF INDIA PRIVATE LTD., New Delhi
`PRENTICE-HALL OF JAPAN,INC., Tokyo
`PRENTICE-HALL OF SOUTHEAST ASIA PTE. LTD., Singapore
`WHITEHALL BOOKS LTD., Wellington, New Zealand
`
`

`

`CONTENTS
`
`X
`
`1
`
`19
`
`PREFACE
`
`1 INTRODUCTION
`
`1.1.
`
`1.2,
`
`1.3.
`
`1.4.
`
`LANGUAGES, LEVELS, AND VIRTUAL MACHINES 3
`
`CONTEMPORARY MULTILEVEL MACHINES 4
`
`HISTORICAL EVOLUTION OF MULTILEVEL MACHINES 8&8
`
`HARDWARE, SOFTWARE, AND MULTILEVEL MACHINES
`
`10
`
`1.5.
`
`PROCESSES
`
`13
`
`1.6.
`
`OUTLINE OF THIS BOOK 15
`
`2 COMPUTER SYSTEMS ORGANIZATION
`
`2.1.
`
`2.2.
`
`19
`PROCESSORS
`20
`2.1.1
`Instruction Execution
`2.1.2 Parallel Instruction Execution
`2.1.3. Processor Classification 25
`
`23
`
`MEMORY 26
`2.2.1 Bits
`26
`2.2.2 Memory Addresses
`2.2.3. Metabits
`29
`2.2.4 Secondary Memory
`
`27
`
`30
`
`iti
`
`

`

`CONTENTS
`
`INPUT/OUTPUT 34
`2.3.1 VO Devices
`35
`35
`2.3.2 VO Processors
`36
`2.3.3 Character Codes
`36
`2.3.4 Erzror-Correcting Codes
`2.3.5 Frequency-Dependent Codes 40
`
`COMPUTER NETWORKSAND DISTRIBUTED SYSTEMS 43
`2.4.1 Long-Haul Networks
`43
`2.4.2 Telecommunication 46
`2.4.3 Local Networks
`51
`2.4.4 Distributed Systems 52
`SUMMARY 53
`
`2.3.
`
`2.4,
`
`2.5.
`
`3 THE DIGITAL LOGIC LEVEL
`
`58
`
`3.1.
`
`3.2.
`
`3.3.
`
`GATES AND BOOLEAN ALGEBRA 58
`3.1.1 Gates
`59
`61
`3.1.2 Boolean Algebra
`3.1.3
`Implementation of Boolean Functions
`3.1.4 Circuit Equivalence 64
`
`62
`
`BASIC DIGITAL LOGIC CIRCUITS 68
`3.2.1
`Integrated Circuits 69
`3.2.2 Combinational Circuits
`3.2.3 Arithmetic Circuits 76
`3.2.4 Clocks
`80
`
`70
`
`MEMORY 83
`83
`3.3.1 Latches
`3.3.2 Flip-Flops and Registers
`3.3.3. Memory Organization
`3.3.4 Memory Properties
`91
`
`86
`
`87
`
`MICROPROCESSORS AND MICROCOMPUTERS 94
`3.4.1 Microprocessor Chips
`94
`3.4.2. Microcomputer Buses
`95
`3.4.3. The Z80 Microprocessor
`3.4.4 The 68000 Microprocessor
`3.5.
`INTERFACING—105
`3.5.1 YOChips
`105
`107
`3.5.2 Address Decoding
`3.5.3 An Example Microcomputer
`SUMMARY 112
`
`3.4.
`
`3.6.
`
`97
`
`110
`
`

`

`4 THE MICROPROGRAMMING LEVEL
`
`CONTENTS
`
`Vv
`
`117
`
`4.1. REVIEW OF THE DIGITAL LOGIC LEVEL 118
`4.1.1 Registers
`118
`4.1.2 Buses
`119
`4.1.3 Multiplexers and Decoders
`4.1.4 ALUs and Shifters
`122
`4.1.5 Clocks
`123
`124
`4.1.6 Main Memory
`4.1.7 Component Packaging
`
`124
`
`121
`
`4.2. AN EXAMPLE MICROARCHITECTURE 126
`4.2.1 The Data Path
`126
`4.2.2 Microinstructions
`128
`129
`4.2.3. Microinstruction Timing
`4.2.4 Microinstruction Sequencing
`
`133
`
`4.3. AN EXAMPLE MACROARCHITECTURE 134
`4.3.1
`Stacks
`135
`4.3.2 The Macroinstructicn Set
`
`140
`
`4.4. AN EXAMPLE MICROPROGRAM 142
`4.4.1 The Micro Assembly Language
`142
`4.4.2 The Example Microprogram 143
`4.4.3 Remarks about the Microprogram 148
`4.4.4 Perspective
`148
`
`4.5. DESIGN OF THE MICROPROGRAMMING LEVEL 149
`4.5.1 Horizontal versus Vertical Microprogramming 149
`4.5.2 Nanoprogramming 156
`158
`4.5.3.
`Improving Performance
`4.6. THE IBM 370/125 MICROPROGRAMMING LEVEL 162
`4.6.1 The IBM 370/125 Microarchitecture
`163
`4.6.2 IBM 3125 Microinstructions
`166
`
`4.7, THE PDP-11/60 MICROPROGRAMMING LEVEL 169
`4.7.1 The PDP-11/60 Microarchitecture
`169
`4.7.2 The PDP-11/60 Microinstructions
`172
`
`4.8. SUMMARY 177
`
`5 THE CONVENTIONAL MACHINE LEVEL
`
`181
`
`5.1. EXAMPLES OF THECONVENTIONAL MACHINE LEVEL 181
`5.1.1
`IBM Systenv/370
`182
`5.1.2 DEC PDP-11
`185
`5.1.3. Motorola MC68000
`5.1.4 Zilog Z80
`196
`
`190
`
`

`

`vi
`
`CONTENTS
`
`5.2.
`
`INSTRUCTION FORMATS 200
`5.2.1 Design Criteria for Instruction Formats
`5.2.2 Expanding Opcodes
`203
`5.2.3. Examplesof Instruction Formats
`
`204
`
`202
`
`213
`
`218
`
`233
`
`5.3. ADDRESSING 213
`5.3.1
`Immediate Addressing
`3.3.2 Direct Addressing 214
`5.3.3 Register Addressing
`214
`5.3.4 Indirect Addressing 215
`5.3.5
`Indexing
`217
`5.3.6 Base-Register Addressing
`3.3.7 Stack Addressing
`220
`5.3.8 Addressing on the PDP-11 and the 68000
`5.3.9 Discussion of Addressing Modes
`231
`INSTRUCTION TYPES 232
`5.4.1 Data MovementInstructions
`5.4.2 Dyadic Operations
`235
`5.4.3. Monadic Operations
`236
`5.4.4 Comparisons and Conditional Jumps
`5.4.5. Procedure Call Instructions
`240
`5.4.6 Loop Control
`241
`5.4.7 Input/Output
`243
`
`5.4.
`
`227
`
`238
`
`5.5. FLOW OF CONTROL 246
`5.5.1
`Sequential Flow of Control and Jumps
`5.5.2 Procedures
`248
`5.5.3 Coroutines
`255
`5.5.4 Traps
`263
`5.5.5
`Interrupts
`5.7. SUMMARY 269
`6 THE OPERATING SYSTEM MACHINE LEVEL
`
`263
`
`247
`
`274
`
`6.1.
`
`IMPLEMENTATION OF THE OPERATING SYSTEM MACHINE LEVEL 274
`
`6.2. VIRTUAL I/O INSTRUCTIONS 277
`6.2.1
`Sequential Files
`277
`.
`6.2.2 Random Access Files
`279
`6.2.3
`Implementation of Virtual /O Instructions
`6.2.4 Directory ManagementInstructions
`285
`6.2.5
`IBM 370 Virtual VO 286
`6.2.6 UNIX Virtual YO 290
`6.2.7 CP/M Virtual YO 295
`
`280
`
`6.3. VIRTUAL INSTRUCTIONS USED IN PARALLEL PROCESSING 298
`6.3.1
`Process Creation
`299
`6.3.2 Race Conditions
`301
`6.3.3. Process Synchronization Using Semaphores
`
`304
`
`

`

`CONTENTS
`
`vii
`
`315
`
`6.4,
`
`VIRTUAL MEMORY 308
`6.4.1
`Paging 308
`6.4.2 Implementation of Paging 311
`6.4.3 Demand Paging and the Working Set Model
`6.4.4 Page Replacement Policy
`318
`6.4.5 Page Size and Fragmentation 320
`6.4.6 Cache Memory
`321
`6.4.7 Segmentation 322
`327
`6.4.8 The MULTICS Virtual Memory
`6.4.9 Virtual Memory on the IBM 370 331
`6.4.10 Virtual Memory on the PDP-11
`333
`6.4.11 Virtual Memory on the 68000
`338
`
`6.5.
`
`JOB CONTROL LANGUAGES 341
`
`6.6.
`
`SUMMARY 344
`
`7 THE ASSEMBLY LANGUAGE LEVEL
`
`350
`
`7.1.
`
`7.2.
`
`7.3.
`
`7A,
`
`INTRODUCTION TO ASSEMBLY LANGUAGE 351
`7.1.1 What Is an Assembly Language?
`351
`352
`7.1.2 Format of an Assembly Language Statement
`7.1.3. Comparison of Assembly Language and Problem-Oriented “anguages
`7.1.4 Program Tuning 355
`
`354
`
`THE ASSEMBLY PROCESS 357
`7.2.1 Two-Pass Assemblers
`358
`7.2.2 Pass One
`359
`7.2.3 Pass Two 363
`7.2.4 Symbol Table
`
`365
`
`MACROS 367
`7.3.1 Macro Definition, Call, and Expansion
`7.3.2 Macros with Parameters
`369
`7.3.3.
`Implementation of a Macro Facility in an Assembler 370
`
`367
`
`LINKING AND LOADING 371
`372
`7.4.1 Tasks Performed by the Linker
`375
`7.4.2 Structure of an Object Module
`7.4.3, Binding Time and Dynamic Relocation 377
`7.4.4 Dynamic Linking
`380
`
`7.5.
`
`SUMMARY 382
`
`

`

`viii
`
`CONTENTS
`
`8 MULTILEVEL MACHINES
`
`385
`
`8.1.
`
`8.2.
`
`8.3.
`
`METHODS OF IMPLEMENTING NEW LEVELS 385
`8.1.1
`Interpretation
`385
`8.1.2 Translation
`386
`8.1.3 Procedural Extension
`
`390
`
`DESIGN STRATEGIES FOR MULTILEVEL MACHINES 391
`8.2.1 Top-Down Design 391
`8.2.2 Bottom-Up Design
`393
`8.2.3 Middle-Out Design 395
`PROGRAM PORTABILITY 396
`8.3.1 A Universal Programming Language
`8.3.2 The Brute Force Approach
`398
`8.3.3 UNCOL 399
`8.3.4 Abstract Machine Language 402
`8.3.5 Portable Compilers 404
`8.3.6 Emulation
`405
`
`397
`
`8.4.
`
`8.5.
`
`8.6.
`
`SELF-VIRTUALIZING MACHINES 406
`8.4.1
`IBM VM/370 System 408
`8.4.2 Goals of Self-Virtualizing Machines 408
`8.4.3 Implementation of a Self-Virtwalizing Machine
`THE COMPILER-INTERPRETER INTERFACE 418
`8.5.1 High-Level Interfaces 419
`8.5.2 Discussion of High-Level Interfaces 420
`SUMMARY 423
`
`411
`
`9 READING LIST AND BIBLIOGRAPHY
`
`426
`
`9.1.
`
`9.2.
`
`SUGGESTIONS FOR FURTHER READING 426
`9.1.1
`Introduction and General Works 426
`9.1.2 Computer Systems Organization
`427
`9.1.3 The Digital Logic Level
`428
`429
`9.1.4 The Microprogramming Level
`9.1.5 The Conventional Machine Level 429
`9.1.6 The Operating System Machine Level 430
`9.1.7 The Assembly Language Level
`431
`9.1.8 Multilevel Machines 432
`433
`9.1.9 Binary Numbers and Arithmetic
`ALPHABETICAL BIBLIOGRAPHY 433
`
`

`

`APPENDIXES
`
`A BINARY NUMBERS
`
`A.1, FINITE PRECISION NUMBERS 439
`
`A.2. RADIX NUMBER SYSTEMS 441
`
`A.3. CONVERSION FROM ONE RADIX TO ANOTHER 442
`
`A.4. NEGATIVE BINARY NUMBERS 445
`
`A.5. BINARY ARITHMETIC
`
`448
`
`B FLoaTING-POINT NUMBERS
`
`INDEX
`
`439
`
`451
`
`457
`
`

`

`3
`
`THE DIGITAL LOGIC LEVEL
`
`the
`At the bottom of the hierarchy of Fig. 1-2 we find the digital logic level,
`computer’s real hardware.
`In this chapter, we will examine many aspects of digital
`logic, as a building block for the study of higher levels in subsequent chapters. Our
`study will emphasize microcomputers over larger machines not only because they are
`simpler (and thus easier to study) but also because they are becoming increasingly
`important compared to larger machines.
`The basic elements from which all digital computers are constructed are amaz-
`ingly simple. We will begin our study by looking at these basic elements and also at
`the special two-valued algebra (Boolean algebra) used to analyze them. Next we will
`examine some fundamental circuits that can be built using gates in simple combina-
`tions, including circuits for doing arithmetic. The following topic is how gates can be
`combined to store information, that is, how memories are organized. After that, we
`come to the subject of CPUs and especially how single chip CPUs interface with
`memory and peripheral devices.
`
`3.1. GATES AND BOOLEAN ALGEBRA
`
`Digital circuits can be constructed from a small number of primitive elements by
`combining them in innumerable ways.
`In the following sections we will describe
`these primitive elements, show how they can be combined, and introduce a powerful
`tool for analyzing their behavior.
`
`58
`
`

`

`SEC. 3.1
`
`GATES AND BOOLEAN ALGEBRA
`
`59
`
`3.1.1. Gates
`
`A digital circuit is one in which only two logical values are present. Typically, a
`signal between 0 and 1 volt represents one value(e.g., binary 0) and a signal between
`2 and 5 volts represents the other value (e.g., binary 1). Voltages outside these two
`ranges are not permitted. Tiny electronic devices, called gates, can compute various
`functions of these two-valued signals. These gates form the hardware basis on which
`all digital computers are built.
`Although the details of how gates work inside is really beyond the scope of this
`book, belonging to a level below our level 0, the device level, we will now digress
`ever so briefly to take a quick look at the basic idea, which is really quite simple. All
`modern digital
`logic ultimately rests on the fact that a transistor can be made to
`
`operate as a very fast binary switch. In Fig. 3-1(a) we have shownasingle bipolar
`transistor (the circle) embedded in a simple circuit. This transistor has three connec-
`tions to the outside world: the collector, the base, and the emitter. When the input
`voltage, Vj,
`is below a certain critical value, the transistor turns off and acts like an
`infinite resistance, causing the output of the circuit, V,,,,
`to take on a value close to
`Vie. When V;, exceeds the critical value, the transistor switches on and acts like a
`perfect conductor, causing V,,, to be pulled down to ground (by convention, 0 volts).
`
`Nec
`
`+Vcc
`
`+V cc
`
`out
`
`Collector
`
`Vout
`
`Base
`
`Emitter
`
`Vout
`
`(a)
`
`(b)
`
`(c)
`
`Fig. 3-1. (a) A transistor inverter.
`
`(b) A NAND gate.
`
`(c) A NORgate.
`
`is high, and vice
`is low, V,,,
`The important thing to notice is that when V;,
`versa. This circuit is thus an inverter, converting a logical 0 to a logical 1, and a log-
`ical
`1 to a logical 0. The resistor is needed to limit the amount of current drawn by
`the transistor. The time required to switch from one state to the other is typically a
`few nanoseconds.
`
`

`

`60
`
`THE DIGITAL LOGIC LEVEL
`
`CHAP. 3
`
`If both V, and V2 are high,
`In Fig. 3-1(b) two transistors are cascaded in series.
`If either input is low, the
`both transistors will conduct and V,,, will be pulled low.
`corresponding transistor will tum off, and the output will be high.
`In other words,
`Vou Will be low if and only if both V, and V2are high.
`In this
`In Fig. 3-1(c) the two transistors are wired in parallel instead of in series.
`configuration, if either input is high, the corresponding transistor will turn on and pull
`the output down to ground.
`If both inputs are low, the output will remain high.
`These three circuits, or their equivalents, form the three simplest gates. They are
`called NOT, NAND, and NOR gates, respectively. NOT gates are often called inverters,
`we will use the two terms interchangeably.
`If we now adopt the convention that
`“high” (V,, volts) is a logical 1, and that “low” (ground) is a logical 0, we can
`express the output value as a function of the input values. The conventional symbols
`used to depict these three gates are shown in Fig. 3-2(a)-(c), along with the functional
`behavior for each circuit.
`
`NOT
`
`NAND
`
`NOR
`
`AND
`
`OR (a)
`
`Fig. 3-2. The symbols and functional behavior for the five basic gates.
`
`If the output signal of Fig. 3-1(b) is fed into an inverter circuit, we get another
`circuit with precisely the inverse of the NAND gate—namely, a circuit whose outputis
`1 if and only if both inputs are 1. Such a circuit is called an AND gate; its symbol
`and functional description are given in Fig. 3-2(d). Similarly, the NOR gate can be
`connected to an inverter to yield a circuit whose output is 1 if either or both inputs is
`a 1 but 0 if both inputs are 0. The symbol and functional description of this circuit,
`called an OR gate, are given in Fig. 3-2(e). The small circles used as part of the sym-
`bols for the inverter, NAND gate, and NOR gate are called inversion bubbles. They
`are often used in other contexts as well to indicate an inverted signal.
`The five gates of Fig. 3-2 are the principal building blocks of the digital logic
`level. From the foregoing discussion, it should be clear that the NAND and NOR gates
`require two transistors each, whereas the AND and OR gates require three each. For
`this reason, many computers are based on NAND and NORgates rather than the more
`familiar AND and OR gates.
`(In practice, all
`the gates are implemented somewhat
`
`

`

`SEC. 3.1
`
`GATES AND BOOLEAN ALGEBRA
`
`61
`
`differently, but NAND and NORare still simpler than AND and oR.) In passing it is
`worth noting that gates may have more than two inputs.
`In principle, a NAND gate,
`for example, may have arbitrarily many inputs, but in practice more than eight inputs
`is unusual.
`Although the subject of how gates are constructed belongs to the device level, we
`would like to mention the major families of manufacturing technology because they
`are referred to frequently. The two major technologies are bipolar and MOS (Metal
`Oxide Semiconductor). The major bipolar
`types are TTL (Transistor-Transistor
`Logic), which has been the workhorse of digital electronics for years, and ECL
`(Emitter-Coupled Logic), which is used when very high-speed operation is required.
`MOS gates are 10 times slower than TTL and 100 times slower than ECL but
`require almost no power and almost no space, so large numbers of them can be
`packed together tightly. MOS comes in many varieties,
`including PMOS, NMOS,
`and CMOS, with new varieties continually appearing.
`
`3.1.2. Boolean Algebra
`
`To describe the circuits that can be built by combining gates, a new type of alge-
`bra is needed, one in which variables and functions can take on only the values 0 and
`1. Such an algebra is called a Boolean algebra, after its discoverer,
`the English
`mathematician George Boole (1815-1864). Strictly speaking, we are really referring
`to a specific type of Boolean algebra, a switching algebra, but the term “Boolean
`algebra” is so widely used to mean “switching algebra” that we will not make the
`distinction.
`Just as there are functions in “ordinary” (i.e, secondary-school) algebra, so are
`there functions in Boolean algebra. A Boolean function has one or more input vari-
`ables and yields a result that depends only on the values of these variables. A simple
`function, f, can be defined by saying that f(A) is 1 if A is O and f(A) is 0 if A is 1.
`This function is the NOT function of Fig. 3-2(a).
`Because a Boolean function of » variables has only 2” possible sets of input
`values, the function can be completely described by giving a table with 2” rows, each
`row telling the value of the function for a different combination of input values. Such
`a table is called a truth table. The tables of Fig. 3-2 are examples of truth tables.
`If
`we agree to alwayslist the rows of a truth table in numerical order (base 2), thatis,
`for two variables in the order 00, 01, 10, and 11,
`the function can be completely
`described by the 2"—bit binary number obtained by reading the result column of the
`truth table vertically. Thus NAND is 1110, NOR is 1000, AND is 0001, and oR is 0111.
`Obviously, only 16 Boolean functions of two variables exist, corresponding to the 16
`possible 4-bit result strings.
`In contrast, ordinary (i.e., high school) algebra has an
`infinite number of functions of two variables, none of which can be described by giv-
`ing a table of outputs for all possible inputs because each variable can take on any one
`of an infinite number of possible values. Clearly, finiteness has its virtues.
`Figure 3-3(a) shows the truth table for a Boolean function of three variables:
`M = f(A, B, C). This function is the majority logic function, that is, it is 0 if a
`
`

`

`62
`
`THE DIGITAL LOGIC LEVEL
`
`CHAP. 3
`
`majority of its inputs are 0, and 1 if a majority of its inputs are 1. Although any
`Boolean function can be fully specified by giving its truth table, as the number of
`variables increases, this notation becomes increasingly cumbersome.
`Instead, another
`notation is frequently used.
`To see how this other notation comes about, note that any Boolean function can
`be specified by telling which combinations of input variables give an output value of
`1, For the function of Fig. 3-3(a) there are four combinations of input variables that
`make M 1. By convention, we will place a bar over an input variable to indicate that
`its value is 0. The absence of a bar means that it is 1. Furthermore, we will use
`implied multiplication or a dot to mean AND and + to mean OR. Thus, for example,
`ABC means A = 1 and B = 0 and C = 1. Also, AB + BC means (A = 1 and
`B = Q)or(@® = 1 andC = 0). Thefour rowsof Fig. 3-3(a) producing1bits in the
`output are: ABC, ABC, ABC, and ABC. The function, M,is true if any one of these
`four conditions is true; hence we can write
`
`M = ABC + ABC + ABC + ABC
`
`as a compact way of giving the truth table. A function of n variables can thus be
`described by giving a “sum” of at most 2” n-variable “product” terms. This formula-
`tion is especially important, as we will see shortly, because it leads directly to an
`implementation of the function using standard gates.
`
`3.1.3. Implementation of Boolean Functions
`
`As mentioned above, the formulation of a Boolean function as a sum of up to 2”
`product terms leads directly to a possible implementation. Using Fig. 3-3 as an exam-
`ple, we can see how this implementation is accomplished.
`In Fig. 3-3(b), the inputs,
`A, B, and C, are shown at the left edge and the output function, M, is shown at the
`right edge. Because complements of the input variables are needed,
`they are gen-
`erated by tapping the inputs and passing them through the inverters labeled 1, 2, and
`3. To keep the figure from becoming cluttered, we have drawn in six vertical lines,
`three of which are connected to the input variables, and three of which are connected
`to their complements. These lines provide a convenient source for the inputs to subse-
`quent gates. For example, gates 5, 6, and 7 all use A as an input.
`In an actual circuit
`these gates would probably be wired directly to A without using any intermediate
`“vertical” wires.
`Thecircuit contains four AND gates, one for each term in the equation for M (i.e.,
`one for each row in the truth table having a 1 bit in the result column). Each AND
`gate computes one row of the truth table, as indicated. Finally, all the product terms
`are ORed together to get the final result.
`The circuit of Fig. 3-3(b) uses a convention that we will need repeatedly
`throughout this book: when two lines cross, no connection is implied unless a heavy
`dot is present at the intersection. For example, the output of gate 3 crosses all six
`vertical lines but it is connected only to C. Be warned that some authors use other
`conventions.
`
`

`

`SEC. 3.1
`
`GATES AND BOOLEAN ALGEBRA
`
`63
`
`Fig. 3-3. (a) The truth table for the majority function of three variables.
`(b) A circuit for (a).
`
`

`

`64
`
`THE DIGITAL LOGIC LEVEL
`
`CHAP. 3
`
`From the example of Fig. 3-3 it should be clear how to implementa circuit for
`any Boolean function:
`
`Write down the truth table for the function.
`
`vAFkWH. Feed the output of all the AND gatesinto an ORgate.
`
`. Provide inverters to generate the complementof each input.
`
`. Draw an AND gate for each term with a | in the result column.
`
`. Wire the AND gates to the appropriate inputs.
`
`Although we have shown how any Boolean function can be implemented using
`NOT, AND, and OR gates, it is often convenient to implementcircuits using only a sin-
`gle type of gate. Fortunately,it is straightforward to convert circuits generated by the
`preceding algorithm to pure NAND or pure NOR form. To make such a conversion, all
`we need is a way to implement NOT, AND, and OR using a single gate type. The top
`row of Fig. 3-4 shows how all three of these can be implemented using only NAND
`gates; the bottom row shows how it can be done using only NOR gates.
`In both cases
`a value can be inverted using a single gate, whereas both AND and OR require three
`gates each. Thus to implement a Boolean function using only NAND or only NOR
`gates, first follow the procedure given above for constructing it with NOT, AND, and
`OR. Then replace the multi-input gates with equivalent circuits using two-input gates.
`For example, A + B + C + D can be computed as (A + B) + (C + D), using
`three two-input OR gates. Finally,
`the NOT, AND, and OR gates are replaced by the
`circuits of Fig. 3-4.
`Although this procedure does not lead to the optimal circuits, in the sense of the
`minimum number of gates,
`it does show that a solution is always feasible. Both
`NAND and NORgates are said to be complete, because any Boolean function can be
`computed using either of them. No other gate has this property, which is another rea-
`son they are often preferred for the building blocksofcircuits.
`
`3.1.4. Circuit Equivalence
`
`Circuit designers naturally try to reduce the number of gates in their products to
`reduce component cost, printed circuit board space, power consumption, and so on.
`To reduce the complexity of a circuit, the designer must find another circuit that com-
`putes the same function as the original but does so with fewer gates (or perhaps with
`simpler gates, for example, two-input gates instead of four-input gates).
`In the search
`for equivalent circuits, Boolean algebra can be a valuabletool.
`As an example of how Boolean algebra can be used, consider the circuit and truth
`table for AB + AC shown in Fig. 3-5(a). Although we have not discussed them yet,
`many of the rules of ordinary algebra also hold for Boolean algebra.
`In particular,
`AB + ACcan be factored into A(B + C) using the distributive law. Figure 3-5(b)
`shows the circuit and truth table for A(B + C). Because two functions are
`
`

`

`SEC. 3.1
`
`GATES AND BOOLEAN ALGEBRA
`
`65
`
`—y+A
`
`A ) > A
`
`(a)
`
`A
`
`B
`
`A
`
`B
`
`AB
`
`AB
`
`B
`
`A
`
`B
`
`A+B
`
`A+8B
`
`(b)
`
`(c)
`
`Fig. 3-4. Construction of (a) NOT,
`NAND gates or only NOR gates.
`
`(b) AND, and (c) OR gates using only
`
`equivalent ifand only if they have the same output for all possible inputs, it is easy to
`see from the truth tables of Fig. 3-5 that A(B + C) is equivalent to AB + AC.
`Despite this equivalence,
`the circuit of Fig. 3-5(b)
`is clearly better than that of
`Fig. 3-5(a) because it contains fewergates.
`In general, a circuit designer can represent a circuit as a Boolean function and
`then apply the laws of Boolean algebra to this representation in an attempt to find a
`simpler but equivalent one. From the final representation, a new circuit can be con-
`structed.
`To use this approach, we need someidentities from Boolean algebra. Figure 3-6
`shows some of the major ones.
`It is interesting to note that each law has two forms
`that are duals of each other. By interchanging AND and OR andalso 0 and 1, either
`form can be produced from the other one. All the laws can be easily proven by
`
`

`

`A
`
`C
`
`B+C
`
`A(B + C)
`
`66
`
`THE DIGITAL LOGIC LEVEL
`
`CHAP. 3
`
`
`palsicialo+c|a+c)|
`
`Fig. 3-5. Two equivalent functions.
`
`(a) AB + AC. (b)A(B + C).
`
`constructing their truth tables. Except for de Morgan’s law, the absorption law, and
`the AND form of the distributive law,
`the results are reasonably intuitive. De
`Morgan’s law can be extended to more variables, for example, ABC = A +B +C.
`
`law
`
`Name
`AND form
`OR form
` Identity law
`
`O+A=A
`
`T+A=1
`Nul] Taw
`
`Idempotent
`AtAZz=A
`
`Inverse law
`A+R =]
`
`Commutative law
`A+B=BH+A
`
`Associative law
`(AB)C = A(BC)
`(A+B) +C =A + (B+C)
`
`
`Distributive law
`A+ BC = (A + B)(A +C)
`A(B + C) = AB + AC
`A+AB=A
`Absorption law
`
`
`A(A +B) =A
`De Morgan's law
`AB=A+8
`
`
`A+B = BB
`
`Fig. 3-6. Someidentities of Boolean algebra.
`
`In Fig. 3-7(a) the AND form is
`De Morgan’s law suggests an alternative notation.
`shown with negation indicated by inversion bubbles, both for input and output. Thus
`
`

`

`SEC, 3.1
`
`GATES AND BOGLEAN ALGEBRA
`
`67
`
`an OR gate with inverted inputs is equivalent to a NAND gate. From Fig. 3-7(b), the
`dual form of de Morgan’s law,
`it is clear that a NOR gate can be drawn as an AND
`gate with negated inputs. By negating both forms of de Morgan’s law, we arrive at
`Fig. 3-7(c) and (d), which shown equivalent representations of the AND and OR gates.
`Analogous symbols exist for the multiple variable forms of de Morgan’s law (e.g., an
`n input NAND gate becomes an OR gate with n inverted inputs).
`
`AB
`
`=
`
`A+B
`
`A+B
`
`=
`
`AB
`
`(a)
`
`(b)
`
`AB
`
`2
`
`
`
`A+B
`
`A+B
`
`=
`
`ao
`
`A
`
`(c)
`
`(d)
`
`Fig. 3-7. Alternative symbols for some gates: (a) NAND. (b) NOR. (c) AND.
`(d) OR.
`
`it
`Using the identities of Fig. 3-7 and the analogous ones for multi-input gates,
`becomes mucheasier to convert the sum-of-products representation of a truth table to
`pure NAND or pure NOR form. As an example, consider the XOR (exclusive or) func-
`tion of Fig. 3-8(a). The standard sum-of-products circuit is shown in Fig. 3-8(b). To
`convert to NAND form, the lines connecting the output of the AND gates to the input of
`the OR gate should be redrawn with two inversion bubbles, as shown in Fig. 3-8(c).
`Finally, using Fig. 3-7(a), we arrive at Fig. 3-8(d). The variables A and B can be
`generated from A and B using NAND or NOR gates with their inputs tied together.
`Note that inversion bubbles can be moved along a line at will, for example, from the
`outputs of the input gates in Fig. 3-8(d) to the inputs of the output gate.
`As a final note on circuit equivalence, we will now demonstrate the surprising
`result that the same physical gate can compute different functions, depending on the
`conventions used.
`In Fig. 3-9(a) we show the output of a certain gate, F, for different
`input combinations. Both inputs and outputs are shown in volts. Lf we adopt the con-
`vention that 0 volts is logical 0 and 5 volts is logical 1, called positive logic, we get
`the truth table of Fig. 3-9(b),
`the AND function.
`If, however, we adopt negative
`logic, which has 0 volts as logical 1 and 5 volts as logical 0, we get the truth table of
`Fig. 3-9(c), the OR function.
`Thus the convention chosen to map voltages onto logical values is of great impor-
`tance. Except where otherwise specified, we will henceforth use positive logic, so the
`terms logical 1, true, and high are synonyms, as are logical 0, false, and low.
`
`

`

`68
`
`THE DIGITAL LOGIC LEVEL
`
`CHAP. 3
`
`(b)
`
`(4)
`
`A B
`
`A B
`
`A
`B
`
`A
`B
`
`
`
`(c)
`
`ry
`B
`
`A
`B
`
`Fig. 3-8. (a) Truth table for EXCLUSIVE OR.
`computingit.
`
`(b)-(d) Three circuits for
`
`
`
`(a) Electrical characteristics of a device. (b)
`Fig. 3-9.
`Positive logic. (c) Negative logic.
`—
`
`3.2. BASIC DIGITAL LOGIC CIRCUITS
`
`In the previous sections we saw how to implementtruth tables and other simple
`circuits using individual gates.
`In practice, few circuits are actually constructed gate-
`by-gate anymore, although this once was common. Nowadays,
`the usual building
`blocks are modules containing a number of gates.
`In the following sections we will
`examine these building blocks more closely and see how they are used and how they
`can be constructed from individual gates.
`
`

`

`SEC. 3.2
`
`BASIC DIGITAL LOGIC CIRCUITS
`
`69
`
`3.2.1. Integrated Circuits
`
`in units called
`Gates are not manufactured or sold individually but rather
`integrated circuits, often called ICs or chips. An IC is a square piece of silicon
`about 5 X 5 mm on which some gates have been deposited.
`ICs are usually mounted
`in rectangular plastic or ceramic packages measuring 5 to 15 mm wide and 20 to 50
`mm long. Along the long edges are two parallel rows of pins about 5 mm long that
`can be inserted in sockets or soldered to printed circuit boards. Each pin connects to
`the input or output of some gate on the chip or to power or to ground. The packages
`with two rows of pins outside and ICs inside are technically known as dual inline
`packages or DIPs, but everyone calls them chips,
`thus blurring the distinction
`between the piece of silicon and its package. The most common packages have 14,
`16, 18, 20, 22, 24, 28, 40, 64, or 68 pins. For some special applications square
`packages with pins on all four sides are sometimes used.
`Chips can be divided into rough classes based on the number of gates they con-
`
`tain:
`
`| to 10 gates
`SSI (Smail Scale Integrated) circuit:
`MSI (Medium Scale Integrated) circuit: 10 to 100 gates
`LSI (Large Scale Integrated) circuit: 100 to 100,000 gates
`VLSI (Very Large Scale Integrated) circuit: > 100,000 gates
`
`These classes have different properties and are used in different ways.
`An SSI chip typically contains two to six independent gates, each of which can be
`used individually,
`in the style of the previous sections. Figure 3-10 illustrates a
`schematic drawing of a common SSI chip containing four NAND gates. Each of these
`
`gates has two inputs and one output, requiringatotal of 12 pins for the four gates. In
`addition, the chip needs power(typically about 5 volts, denoted by V,,), and ground
`(GND), which are shared by all gates. The package generally has a notch near pin |
`to identify the orientation. To avoid clutter in circuit diagrams, neither power, nor
`ground, nor unused gates are conventionally shown.
`Figure 3-11 shows some other common SSI chips. These chips belong to the
`7400 TTL series developed by Texas Instruments and now produced by many semi-
`conductor manufacturers. They are most appropriate for simple circuits that cannot be
`realized any other way. The circuit of Fig. 3-3(b) could be constructed from one
`7404,
`two 7411s, and one 7432. No four-input OR gate is available in the 7400
`series, but the same function can be computed by ORing pairs of inputs and then ORing
`the results together. Symbolically, this can be represented as A +B +C +D=
`(A + B)+(C + D), that is, A and B are ORed together as are C and D, with these
`two sums then being ORed.
`If the circuit of Fig. 3-3(b) were actually constructed this
`way, the printed circuit board on which they were mounted would contain conducting
`wire-like tracks to connect the appropriate pins. Some of the gates would not be
`used. The 7486 chip contains a gate we have not shown before, the EXCLUSIVE OR
`gate, which is a one-gate equivalent to the circuit of Fig. 3-8.
`
`|
`
`

`

`70
`
`THE DIGITAL LOGIC LEVEL
`
`CHAP. 3
`
`Notch
`
`Fig. 3-10. An SSI chip containing four gates.
`
`For our purposes, all gates are ideal in the sense that the output appears as soon
`as the input is applied.
`In reality, chips have a finite gate delay, which is the timeit
`takes for the signal to propagate from the input to the output. Typical delays are 1 to
`20 nsec.
`In schematics one often sees numbers like 74800, 74L00, 74HOO, and
`74LS00.
`These
`represent
`functionally
`equivalent
`chips with
`different
`delay/power/price trade-offs. The 74C00 series consists of CMOS chips that are func-
`tionally identical to the corresponding 7400 TTL ones.
`It is within the current state of the art to put nearly a million gates on a single
`chip. Because any circuit can be built up from NAND gates, you might think that a
`manufacturer could make a very general chip containing the equivalent of 250,000
`chips like the 7400. Unfortunately, such a chip would n