Digital Logic
`and
`Computer Design
`
`
`
`
`M. MORRIS MANO
`
`INTEL 1014
`
`INTEL 1014
`
`

`

`
`

`

`
`
`Digital Logic
`and —
`Computer Design
`
`
`
`M. MORRIS MANO
`Professor of Engineering
`California State University, Los Angeles
`
`s
`
`sonesnpcuns-aneveii@nenranmmyeennnssiiMe
`
`
`socencpneyemenanoutanstrtneiliininasersachetHr
`
`Prentice-Hall, Inc., EnglewoodCliffs, N.J. 07632
`
`Sannin
`
`

`

`Library of Congress Cataloging in Publication Data
`
`(date)
`Mano, M. Morris
`Digital logic and computer design.
`Bibliography: p.
`Includes index.
`1.-Electronic digital computers.
`2.~Logic
`4,-Logic design.
`1.-Title.
`circuits. 3.-Digital integrated circuits.
`TK7888.3.M345
`621.3815'3
`
`ISBN 0-13-214510-3
`
`78-21462
`
`snmeesi SRita
`
`.
`
`:
`
`.4%ct
`A i \
`\ Sy
`
`»
`
`i vf
`
`by
`
`é
`\
`t cf
`
`TX
`
`298-870
`
`a mee
`
`©1979 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.
`
`Printed in the United States of America
`
`0987654321
`
`Editorial/ Production Supervision by Lynn S. Frankel
`Cover Design by Edsal Enterprise
`Manufacturing Buyer: Gordon Osbourne
`
`PRENTICE-HALL INTERNATIONAL, INC., London
`PRENTICE-HALL OF AUSTRALIA PTY. LIMITED, Sydney
`PRENTICE-HALL OF CANADA, LTD., Toronto
`PRENTICE-HALL OF INDIA PRIVATE LIMITED, New Delhi
`PRENTICE-HALL OF JAPAN,INC., Tokyo
`PRENTICE-HALL OF SOUTHEAST ASIA PTE. LTD., Singapore
`WHITEHALL BOOKS LIMITED, Wellington, New Zealand
`
`al
`
`
`
`

`

`
`
`
`
`Contents
`
`
`
`viii
`
`1
`
`/
`
`PREFACE
`
`1
`
`_ BINARY SYSTEMS
`
`1-1
`1-2
`1-3.
`1-4
`1-5
`1-6
`1-7
`1-8
`1-9
`
`Digital Computers and Digital Systems
`Binary Numbers
`4
`6
`Number Base Conversion
`Octal and Hexadecimal Numbers
`Complements 0
`|
`Binary Codes
`16
`Binary Storage and Registers
`Binary Logic
`25
`integrated Circuits
`References 3/
`Problems
`3/
`
`9
`
`22
`
`30
`
`2
`
`BOOLEAN ALGEBRA AND LOGIC GATES
`
`—
`
`(34
`
`2-1
`2-2
`2-3.
`
`2-4
`2-5
`2-6
`2-7
`2-8
`
`34
`Basic Definitions
`Axiomatic Definition of Boolean Algebra
`Basic Theorems and Properties
`of Boolean Algebra
`39
`Boolean Functions
`43
`Canonical and Standard Forms
`Other Logic Operations
`53
`Digital Logic Gates
`56
`IC Digital Logic Families
`References
`68
`Problems
`
`47
`
`60
`
`68
`
`36
`
`fii
`
`

`

`CONTENTS
`
`SIMPLIFICATION OF BOOLEAN FUNCTIONS
`
`72 -
`
`3-1
`3-2
`3-3
`3-4
`3-5
`3-6
`3-7
`3-8
`3-9
`3-10
`3-14
`3-12
`
`72
`
`72
`The Map Method
`Two- and Three-Variable Maps
`Four-Variable Map
`77
`80
`Five- and Six-Variable Maps
`83
`Product of Sums Simplification
`NAND and NOR Implementation 986
`Other Two-Level Implementations
`93
`Don’t-Care Conditions
`100
`The Tabulation Method
`1/02
`Determination of Prime-Implicants
`Selection of Prime-implicants
`108
`Concluding Remarks
`//0
`References
`//2
`Problems
`1/12
`
`102
`
`COMBINATIONAL LOGIC
`
`116
`
`4-1
`4-2
`4-3
`4-4
`4-5
`4-6
`4-7
`4-8
`4-9
`
`/17
`
`Introduction 16
`Design Procedure
`Adders
`119
`123
`Subtractors
`Code Conversion 125
`Analysis Procedure
`128
`132
`Multilevel NAND Circuits
`/4/
`Multilevel NOR Circuits
`Exclusive-or and Equivalence Functions
`References
`150
`Problems
`150
`
`145
`
`COMBINATIONAL LOGIC WITH MSI AND LSI
`
`154
`
`5-1
`5-2
`5-3
`5-4
`5-5
`5-6
`5-7
`5-8
`5-9
`
`155
`
`164
`
`Introduction 154
`Binary Parallel Adder
`- Decimal Adder
`/6/
`Magnitude Comparator
`Decoders
`167 .
`Multiplexers
`175
`1/82
`Read-Only Memory (ROM)
`Programmable Logic Array (PLA)
`Concluding Remarks
`195
`References
`196
`Problems
`196
`
`1/89
`
`
`
`
`
`

`

`
`
`CONTENTS
`
`v
`
`202
`
`6
`
`SEQUENTIAL LOGIC
`
`
`
`DRAMWMDAAAHDMD
`
`OONODOROD—
`
`202 .
`Introduction
`204
`Flip-Flops
`Triggering of Flip-Flops 2/0
`Analysis of Clocked Sequential Circuits 2/7
`State Reduction and Assignment
`224
`Flip-Flop Excitation Tables
`230
`Design Procedure
`233
`Design of Counters
`243
`Design with State Equations
`References 25/
`Problems
`252 .
`
`247 |
`
`7
`
`REGISTERS, COUNTERS, AND THE MEMORY UNIT
`
`256
`
`ONOAAWH
`NNNNNNNN
`
`CROMDDMDMOMMDMDOM—~=-+©ONoOOaRK@OND—pe—-Oo
`
`256
`Introduction
`Registers
`257
`263
`Shift Registers
`272
`Ripple Counters
`Synchronous Counters
`Timing Sequences
`284
`The Memory Unit
`289
`Examples of Random Access Memories
`References
`300
`Problems
`301
`
`276
`
`294
`
`Introduction 305
`308
`Interregister Transfer
`Arithmetic, Logic, and Shift Micro-Operations
`Conditional Control Statements
`32/
`Fixed-Point Binary Data
`322
`Overflow 327
`‘
`Arithmetic Shifts
`Decimal Data
`331
`332
`Floating-Point Data
`335
`Non-Numeric Data
`339
`Instruction Codes
`Design of Simple Computer
`References
`352
`Problems
`352
`
`344
`
`329
`
`8
`
`REGISTER TRANSFER LOGIC
`
`305
`
`316
`
`

`

`
`
`vi
`
`CONTENTS
`
`PROCESSOR LOGIC DESIGN
`
`358
`
`
`
`COODODNDHOODSO~(OOCO™SHOr®&&POA'
`
`iitt
`I'i
`
`©
`
`368
`
`.
`Introduction 358
`Processor Organization 359
`Arithmetic Logic Unit
`367
`Design of Arithmetic Circuit
`Design of Logic Circuit
`376
`Design of Arithmetic Logic Unit
`Status Register
`382
`Design of Shifter
`384
`Processor Unit
`386
`Design of Accumulator 39/
`References
`402
`Problems
`402
`
`378
`
`10
`
`CONTROL LOGIC DESIGN
`
`407
`
`10-1
`10-2
`10-3
`10-4
`10-5
`10-6
`10-7
`10-8
`
`introduction 407.
`409
`Control Organization
`Hard-Wired Control Example 1
`Microprogram Control
`424
`429
`Control of Processor Unit
`Hard-Wired Control Example 2
`PLA Control
`443
`Microprogram Sequencer
`References
`453
`Problems
`453
`
`446
`.
`
`41/5
`
`432
`
`11
`
`COMPUTER DESIGN
`
`459
`
`11-1
`11-2
`11-3
`11-4
`11-5
`11-6
`11-7
`11-8
`
`460
`464
`
`459
`Introduction
`System of Configuration
`ComputerInstructions
`Timing and Control
`477
`473
`Execution of Instructions
`Design of Computer Registers
`Design of Control
`484
`Computer Console
`493
`References
`494
`Problems
`495
`
`479
`
` ||i |
`
`}i|i
`
`

`

`MICROCOMPUTER SYSTEM DESIGN
`
`499
`
`12-1
`12-2
`12-3
`12-4
`12-5
`12-6
`12-7
`12-8
`
`Introduction 499
`Microcomputer Organization 502
`Microprocessor Organization 506
`Instructions and Addressing Modes 5/4
`Stack, Subroutines, and Interrupt
`523
`Memory Organization 532
`Input-Output Interface
`537
`Direct Memory Access
`547
`References
`55/
`Problems
`552
`
`DIGITAL INTEGRATED CIRCUITS
`
`556
`
`558
`
`556
`Introduction
`13-1
`Bipolar Transistor Characteristics
`13-2
`RTL and DTL Circuits
`562
`13-3
`Integrated-Injection Logic (I?L) 565
`13-4
`13-5 Transistor-Transistor Logic (TTL) © 568
`13-6
`Emitter-Coupled Logic (ECL)
`578
`13-7
`Metal-Oxide Semiconductor (MOS)
`- 13-8
`Complementary MOS (CMOS)
`584
`References
`586
`Problems
`586
`
`580
`
`.
`
`APPENDIX:—Answers to Selected Problems
`
`INDEX
`
`589
`
`606
`
`CONTENTS—vii
`
`13
`
` 12
`
`

`

`
`
`
`
`WeipaAER
`
`
`
`Binary
`systems
`
`
`
`
`
`
`1-1 DIGITAL COMPUTERS
`AND DIGITAL SYSTEMS
`
`Digital computers have made possible many scientific, industrial, and commercial
`advances that would have been unattainable otherwise. Our space program would
`have been impossible without real-time, continuous computer monitoring, and
`many business enterprises function efficiently only with the aid of automatic data
`processing. Computers are used in scientific calculations, commercial and business
`data processing, air traffic control, space guidance, the educational field, and many
`other areas. The most striking property of a digital computeris its generality. It
`can follow a sequence of instructions, called a program, that operates on given data.
`The user can specify and changeprograms and/or data according to the specific
`need. As a result of this flexibility, general-purpose digital computers can perform
`a wide variety of information-processing tasks.
`The general-purpose digital computer is the best-known example of a digital
`system. Other examples include telephone switching exchanges, digital voltmeters,
`frequency counters, calculating machines, and teletype machines. Characteristic of
`‘a digital system is its manipulation of discrete elements of information. Such
`discrete elements may be electric impulses, the decimal digits, the letters of an
`alphabet, arithmetic operations, punctuation marks, or any other set of meaningful
`symbols. The juxtaposition of discrete elements of information represents a quan-
`tity of information. For example, the letters d, 0, and g form the word dog. The
`digits 237 form a number. Thus, a sequence of discrete elements forms a language,
`that is, a discipline that conveys information. Early digital computers were used
`mostly for numerical computations. In this case the discrete elements used are the
`digits. From this application,
`the term digital computer has emerged. A more
`appropriate namefor a digital computer would be a “discrete information process-
`ing system.”
`Discrete elements of information are represented in a digital system by
`physical quantities called signals. Electrical signals such as voltages and currents
`
`INDUeERRSAEERaaeBe
` sreeabiraotehbans
`
`See
`
`1
`
`

`

`2
`
` BINARYSYSTEMS)
`
`
`
`are the most common. The signals in all present-day electronic digital systems
`have only two discrete values and are said to be binary. The digital-system designer
`is restricted to the use of binary signals. because of the lower reliability of
`many-valued electronic circuits. In other words, a.circuit withten states, using one
`discrete voltage value for each state, can be designed, but it would possess a very
`low reliability of operation. In contrast, a transistor circuit that is either on or off
`has two possible signal values and can be constructed to be extremely reliable.
`Because of this physical restriction of components, and because human logic tends
`to be binary, digital systems that are constrained to take discrete values are further
`constrained to take binary values.
`Discrete quantities of information emerge either from the nature of the
`process or may be purposely quantized from a continuous process. For example, a
`payroll schedule is an inherently discrete process that contains employee names,
`social
`security numbers, weekly salaries,
`income taxes, etc. An employee’s
`paycheck is processed using discrete data values such as letters of the alphabet
`(names), digits (salary), and special symbols such as $..On the other hand, a
`research scientist may observe a continous process but record only specific quanti-
`ties in tabular form. The scientist is thus quantizing his continuous data. Each
`numberin his table is a discrete element of information.
`Many physical systems can be described mathematically by differential
`equations whose solutions as a function of time give the complete mathematical
`behavior of the process. An analog computer performs a direct simulation of a
`physical system. Each section of the computer is the analog of some particular
`portion of the process under study. The variables in the analog computer are
`represented by continoussignals, usually electric voltages that vary with time. The
`signal variables are considered analogous to those of the process and behavein the
`same manner. Thus measurements of the analog voltage can be substituted for
`variables of the process. The term analog signal
`is sometimes substituted for
`continuous signal because “analog computer” has come to mean a computer that
`manipulates continuous variables.
`To simulate a physical process in a digital computer, the quantities must be
`quantized. Whenthe variables of the process are presented by real-time continuous
`signals,
`the latter are quantized by an analog-to-digital conversion device. A
`physical system whose behavior is described by mathematical equations is simu-
`lated in a digital computer by means of numerical methods. When the problem to
`be processed is inherently discrete, as in commercial applications, the digital
`computer manipulates the variables in their natural form.
`|
`A block diagram of the digital computer is shown in Fig. 1-1. The memory —
`unit stores programs as well as input, output, and intermediate data. The processor
`unit performs arithmetic and other data-processing tasks as specified by a program.
`The control unit supervises the flow of information between the various units. The
`control unit retrieves the instructions, one by one, from the program which is
`stored in memory. For each instruction, the control unit informs the processor to
`execute the operation specified by the instruction. Both program and data are
`
`CH. 1
`
` 2 oneaeRNRRSENSON
`
`

`

` sesaang
`
`eoiennoaleeuie
`
`
`
`
`
`Control
`Unit
`
`Processor
`or
`A TT
`
`
`
`Storage
`or
`
`Memory Unit
`
`
`
`
`
`
`
`Output
`Input
`Devices
`Devices
`
`and Control
`—
`and Control
`.
`
`
`Figure 1-1 Block diagram of a digital computer
`
`.
`
`stored in memory. The control unit supervises the program instructions, and the
`processor manipulates the data as specified by the program.
`The program and data prepared by the user are transferred into the memory
`unit by meansof an input device such as punch-card readeror a teletypewriter. An
`output device, such as a. printer, receives the result of the computations and the
`printed results are presented to the user. The input and output devices are special
`digital systems driven by electromechanical parts and controlled by.electronic
`digital circuits.
`An electronic calculator is a digital system similar to a digital computer, with
`the input device being a keyboard and the output device a numerical display.
`Instructions are entered in the calculator by means of the function keys, such as
`plus and minus. Data are entered through the numeric keys. Results are displayed
`directly in numeric form. Some calculators come close to resembling a digital
`computer by having printing capabilities and programmable facilities. A digital
`computer, however,
`is a more powerful device than a calculator. A digital com-
`puter can accommodate many other input and output devices; it can perform not
`only arithmetic computations but logical operations as well and can be pro-
`grammed to make decisions based on internal and external conditions.
`A digital computer is an interconnection of digital modules. To understand
`the operation of each digital module, it is necessary to have a basic knowledge of
`digital systems and their general behavior. The first half of this book deals with
`digital systems in general to provide the background necessary for their design.
`The secondhalf of the book discusses the various modules of the digital computer,
`their operation and design. The operational characteristics of the memory unit are
`explained in Chapter 7. The organization and design of the processor unit
`is
`
`3
`
`

`

` , :i
`
`osuSe
`
`ahem
`
`
` SIAaliahehtenahcuaaleecheideasisbnreasies
`
`4
`
`BINARY SYSTEMS
`
`CH. 1
`
`undertaken in Chapter 9. Various methods for designing the control unit are
`introduced in Chapter 10. The organization and design of a small, complete digital
`computer is presented in Chapter 11.
`A processor, when combined with the control unit, forms a component
`referred to as a central processor unit or CPU. A CPU enclosed in small
`integrated-circuit package is called a microprocessor. The memory unit, as well as
`the part that controls the interface between the microprocessor and the input and
`output devices, may be enclosed within the microprocessor package or may be
`available in other small integrated-circuit packages. A CPU combined with mem-
`ory and interface control to form a small-size computeris called a microcomputer.
`The availability of microcomputer components has revolutionized the digital sys-
`tem design technology, giving the designer the freedom to create structures that
`were previously uneconomical. The various components of a microcomputer sys-
`tem are presented in Chapter 12.
`It has already been mentioned that a digital computer manipulates discrete
`elements of information and that these elements are represented in the binary form.
`Operands used for calculations may be expressed in the binary number system.
`Other discrete elements, including the decimal digits, are represented in binary
`codes. Data processing is carried out by means of binary logic elements using
`binary signals. Quantities are stored in binary storage elements. The purpose of
`this chapter is to introduce the various binary concepts as a frame of reference for
`further detailed study in the suceeding chapters.
`
`1-2. BINARY NUMBERS
`
`digits and the coefficients are multiplied by powers of 10. The binary system is a
`
`A decimal numbersuch as 7392 represents a quantity equal to 7 thousands plus 3
`hundreds, plus 9 tens, plus 2 units. The thousands, hundreds, etc., are powers of 10
`implied by the position of the coefficients. To be more exact, 7392 should be
`written as:
`
`7x 10+3 x 10? +9 x 10'+2 x 10°
`
`However, the convention is to write only the coefficients and from their position
`deduce the necessary powers of 10. In general, a number with a decimal point.is
`represented by a series of coefficients as follows:
`
`A5A4A44,0 Ay. A_A_»A_4
`
`The a, coefficients are one of the ten digits (0, 1, 2,..., 9), and the subscript value
`J gives the place value and, hence, the power of 10 by which the coefficient must be
`multiplied.
`
`10°a; + 10a, + 10°a, + 10a, + 10'a, + 10%+ 107 'a_,
`+107%a_, + 10~%a_,
`
`The decimal number system is said to be of base, or radix, 10 because it uses ten
`
`
`
`

`

`LIBRARNEAT
`
`Q0009037561
`
`Digital Logic
`and
`Computer Design |
`
`M. Morris Mano
`
`“With the advent of integrated circuits, and especially the introduction
`of microcomputer LSI components, the classical method for describing
`the operations of digital circuits seems to be far removed from practical
`applications,” says Professor M. Morris Mano. Recognizing the need to
`restructure some aspects of digita! logic and computer hardware design
`while retaining thosestill considerec essential to the internal construc-
`tion of many digital functions, Dr. Mano employs the integrated circuit
`MS! functions to ensure a most effective transition from such classical
`approaches as Boolean algebra, combinational and sequential logic, to
`the newer register-transfer concept.
`
`The first six chapters present digital logic design techniques from the
`classical point of view, covering binary systems, Boolean algebra and
`logic gates, simplificatior of Boolean functions, combinational logic,
`combinational logic with MS! and LSI, and sequential fogic.
`
`Chapters 7 through 12 treat digital system design methods from the
`regisier-transfer viewpoint and are devoted to discussions of registers,
`counters, and the ‘memory unit, register transfer logic, processor logic
`design, controi logic design, computer design, and microcomputer sys-
`tem design.
`.
`
`The concluding chapter focuses on the electronics of digital circuits and
`presents the most common families of integrated circuit digital logic.
`Each chapter inc!udes references, illustrative problems, with answers to
`selected problems in the appendix.
`
`PRENTICE-HALL, INC., Englewood Cliffs,
`. New Jersey 07632
`
`* af
`
`
`
`0-13-214510-3
`
`
`
`