Computer System Architecture Textbook PDF

M. Morris Mano ·.1l  Preface This book deals with computer architecture as well as computer organization and design. Computer architecture is concerned with the structure and behav­ ior of the various functional modules of the computer and how they interact to...

M. Morris Mano ·.1l  Preface This book deals with computer architecture as well as computer organization and design. Computer architecture is concerned with the structure and behav­ ior of the various functional modules of the computer and how they interact to provide the processing needs of the user. Computer organization is con­ cerned with the way the hardware components are connected together to form a computer system. Computer design is concerned with the development of the hardware for the computer taking into consideration a given set of specifJCa­ tions. The book provides the basic knowledge necessary to understand the hardware operation of digital computers and covers the three subjects associ­ ated with computer hardware. Chapters 1 through 4 present the va.rious digital components used in the organization and design of digital computers. Chap­ ters 5 through 7 show the detailed steps that a designer must go through in order to design an elementary basic computer. Chapters 8 through 10 deal with the organization and architecture of the cential processing unit. Chapters 11 and 12 present the organization and architecture of input-output and memory. Chapter 13 introduces the concept of multiprocessing. The plan of the book is to present the simpler material first and introduce the more advanced subjects later. Thus, the first seven chapters cover material needed for the basic under­ standing of computer organization, design, and programming of a simple digital computer. The last six chapters present the organization and architec­ ture of the separate functional units of the digital computer with an emphasis on more advanced topics. The material in the third edition is organized in the same manner as in the second edition and many of the features remain the same. The third edition, however, offers several improvements over the second edition. All chapters except two (6 and 10) have been completely revised to bring the material up to date and to clarify the presentation. Two new chapters were added: chapter 9 on pipeline and vector processing, and chapter 13 on multiprocessors. Two sections deal with the reduced instruction set computer (RISC). Chapter 5 has been revised completely to simplify and clarify the design of the basic com­ puter. New problems have been formulated for eleven of the thirteen chapters. The physical organization of a particular computer including its registers, XV xvi Preface the data flow, the microoperations, and control functions can be described symbolically by means of a hardware description language. In this book we develop a simple register transfer language and use it to specify various com­ puter operations in a concise and precise manner. The relation of the register transfer language to the hardware organization and design of digital computers is fully explained. The book does not assume prior knowledge of computer hardware and the material can be understood without the need of prerequisites. However, some experience in assembly language programming with a microcomputer will make the material easier to understand. Chapters 1 through 3 can be skipped if the reader is familiar with digital logic design. The following is a brief description of the subjects that are covered in each chapter with an emphasis on the revisions that were made in the third edition. Chapter 1 introduces the fundamental knowledge needed for the design of digital systems constructed with individual gates and flip-flops. It covers Boolean algebra, combinational circuits, and sequential circuits. This provides the necessary background for understanding the digital circuits to be presented. Chapter 2 explains in detail the logical operation of the most common standard digital components. It includes decoders, multiplexers, registers, counters, and memories. These digital components are used as building blocks for the design of larger units in the chapters that follow. Chapter 3 shows how the various data types found in digital computers are represented in binary form in computer registers. Emphasis is on the representation of numbers employed in arithmetic operations, and on the binary coding of symbols used in data processing. Chapter 4 introduces a register transfer language and shows how it is used to express microoperations in symbolic form. Symbols are defined for arithmetic, logic, and shift microoperations. A composite arithmetic logic shift unit is developed to show the hardware design of the most common micro­ operations. Chapter 5 presents the organization and design of a basic digital com­ puter. Although the computer is simple compared to commercial computers, it nevertheless encompasses enough functional capabilities to demonstrate the power of a stored program general purpose device. Register transfer language is used to describe the internal operation of the computer and to specify the requirements for its design. The basic computer uses the same set of instruc­ tions as in the second edition but its hardware organization and design has been completely revised. By going through the detailed steps of the design presented in this chapter, the student will be able to understand the inner workings of digital computers. Chapter 6 utilizes the twenty five instructions of the basic computer to illustrate techniques used in assembly language programming. Programming examples are presented for a number of data processing tasks. The relationship  Preface xvii between binary programs and symbolic code is explained by examples. The basic operations of an assembler are presented to show the translation from symbolic code to an equivalent binary program. Chapter 7 introduces the concept of microprogramming. A specific micro­ programmed control unit is developed to show by example how to write microcode for a typical set of instructions. The design of the control unit is carried-out in detail including the hardware for the microprogram sequencer. Chapter 8 deals with the central processing unit (CPU). An execution unit with common buses and an arithmetic logic unit is developed to show the general register organization of a typical CPU. The operation of a memory stack is explained and some of its applications are demonstrated. Various instruction formats are illustrated together with a variety of addressing modes. The most common instructions found in computers are enumerated with an explanation of their function. The last section introduces the reduced instruction set com­ puter (RISC) concept and discusses its characteristics and advantages. Chapter 9 on pipeline and vector processing is a new chapter in the third edition. (The material on arithmetic operations from the second edition has been moved to Chapter 10. ) The concept of pipelining is explained and the way it can speed-up processing is illustrated with several examples. Both arithmetic and instruction pipeline is considered. It is shown how RISC processors can achieve single-cycle instruction execution by using an efficient instruction pipeline together with the delayed load and delayed branch techniques. Vector processing is introduced and examples are shown of floating-point operations using pipeline procedures. Chapter 10 presents arithmetic algorithms for addition, subtraction, mul­ tiplication, and division and shows the procedures for implementing them with digital hardware. Procedures are developed for signed-magnitude and signed-2's complement fixed-point numbers, for floating-point binary numbers, and for binary coded decimal (BCD) numbers. The algorithms are presented by means of flowcharts that use the register transfer language to specify the sequence of microoperations and control decisions required for their implementation. Chapter 11 discusses the techniques that computers use to communicate with input and output devices. Interface units are presented to show the way that the processor interacts with external peripherals. The procedure for asynchronous transfer of either parallel or serial data is explained. Four modes of transfer are discussed: programmed 110, interrupt initiated transfer, direct memory access, and the use of input-output processors. Specific examples illustrate procedures for serial data transmission. Chapter 12 introduces the concept of memory hierarchy, composed of cache memory, main memory, and auxiliary memory such as magnetic disks.. The organization and operation of associative memories is explained in detail. The concept of memory management is introduced through the presentation of the hardware requirements for a cache memory and a virtual memory system. xviii Preface Chapter 13 presents the basic characteristics of mutiprocessors. Various interconnection structures are presented. The need for interprocessor arbitra­ tion, communication, and synchronization is discussed. The cache coherence problem is explained together with some possible solutions. Every chapter includes a set of problems and a list of references. Some of the problems serve as exercises for the material covered in the chapter. Others are of a more advanced nature and are intended to provide practice in solving problems associated with computer hardware architecture and design. A solu­ tions manual is available for the instructor from the publisher. The book is suitable for a course in computer hardware systems in an electrical engineering, computer engineering, or computer science depart­ ment. Parts of the book can be used in a variety of ways: as a first course in computer hardware by covering Chapters 1 through 7; as a course in computer organization and design with previous knowledge of digital logic design by reviewing Chapter 4 and then covering chapters 5 through 13; as a course in computer organization and architecture that covers the five functional units of digital computers including control (Chapter 7), processing unit (Chapters 8 and 9), arithmetic operations (Chapter 10), input-output (Chapter 11), and memory (Chapter 12). The book is also suitable for self-study by engineers and scientists who need to acquire the basic knowledge of computer hardware architecture. Acknowledgments My thanks goes to those who reviewed the text: particularly Professor Thomas L. Casavant of the University of Iowa; Professor Murray R. Berkowitz of George Mason University; Professor Cern Ersoy of Brooklyn Polytechnic University; Professor Upkar Varshney of the University of Missouri, Kansas City; Professor Karan Watson of Texas A&M University, and Professor Scott F. Midkiff of the Virginia Polytechnic Institute. M. Morris Mano  Contents Preface XV CHAPTER ONE Digital Logic Circuits 1·1 Digital Computers 1 1·2 Logic Gates 4 1-3 Boolean Algebra 7 Complemmr of a Function I0 1-4 Map Simplification II Prodvct-af·Swru Sfm Jlifico.tion /of Don't-Care Condirioru 16 1-S Combinational Circuits 18 Hai{-Mkr 19 MJI.Mkf 20 ,1-6 Flip-Flop 22 SR FU,.Fiop 22 0 FU,.Fiop 23 JK Flip-Flop 24 T Flip-Flop 24 E.dgc-Tfiumd Flip.Fiops 25 Exti!ation Talks 27 1-7 Sequential Circuits Flip-Flop Input Equ4tioru 28 SIOU Table 30 SIOU Oiogr11m 31 Example 32 Proced.at 36 Problems References iii iv Contents CHAPTER TWO Digital Components 41 2-1 Integrated Circuits 41 2-2 Decoders 43 NAND Gate Decoder 45 Decoder Expansion 46 Encoders 47 2·3 Multiplexers 48 2-4 Registers 50 Register with Parallel Load 51 2-5 Shift Registers 53 Bidirectional Shift Register with Parallel Load 53 2-6 Binary Counters 56 Binary Counter with Parallel Load 58 2-7 Memory Unit 58 Random-Access Memory 60 Read-Only Memory 61 Types of ROMs 62 Problems 63 References 65 CHAPTER THREE Data Representation 67 3-1 Data Types 67 Number Systems 68 Octal and Hexadecimal Numbers 69 Decimal Representation 72 Alphanumeric Representation 73 3-2 Complements 74 (r-l)'s Complement 75 (r's) Complement 75 Subtraction of Unsigned Numbers 76 3-3 Fixed-Point Representation 77 Integer Representation 78 Arithmetic Addition 79 Arithmetic Subtraction 80 Overflow 80 Decimal Fixed-Point Representation 81  Contents V 3-4 Floating-Point Representation 83 3-5 Other Binary Codes 84 Gray Code 84 Other Decimal Codes 85 Ocher Alphanumeric Codes 86 3-6 Error Detection Codes 87 Problems 89 References 91 CHAPTER FO UR Register Transfer and Microoperations 93 4·1 Register Transfer language 93 4·2 Register Transfer 95 4-3 Bus and Memory Transfers 97 Three-Stare Bus Buffers I00 Memory Transfer 10 I 4-4 Arithmetic Microoperations 102 Binary Adder 1 03 Binary Adder-Subtractor I04 Binary lncremenrer 1 05 Arithmetic Circuit I06 4-5 Logic Microoperations 108 List of Logic Microoperations 1 09 Hardware Implementation III Some Applications III 4-6 Shift Microoperations 114 Hardware Implementation II5 4-7 Arithmetic Logic Shift Unit 116 Problems 119 References 122 CHAPTER FIVE Basic Computer Organization and Design 123 5-1 Instruction Codes 123 Stored Prowam Organization I25 Indirect Address I26 vi Contents 5-2 Computer Registers 127 Common Bus System 1 29 5-3 Computer Instructions 132 Instruction Set Completeness 1 34 5-4 Timing and Control 135 5-5 Instruction Cycle 139 Fetch and Decode 1 39 Determine the Type of Instruction 1 41 Register-Reference Instructions 1 43 5-6 Memory-Reference Instructions 145 AND to AC 1 45 ADD wAC 1 46 LOA: Load to AC 1 46 STA: Store AC 1 47 BUN: Branch UnconditionaUy 1 47 BSA: Branch and Save Return Address 14 7 ISZ: Increment and Skip If Zero 149 Control Flowchart 1 49 5-7 Input-Output and Interrupt 150 Input-Output Configuration 1 51 Input-Output Instructions 1 52 Program Interrupt 15 3 Interrupt Cycle 1 56 5-8 Complete Computer Description 157 5-9 Design of Basic Computer 157 Control Logic Gates 1 60 Control of Registers and Memory 1 60 Control of Single Flip-Flops 1 62 Control of Common Bus 1 62 5-10 Design of Accumulator Logic 164 Control of AC Register 1 65 Adder and Logic Circuit 1 66 Problems 167 References 171 CHAPTER SIX Programming the Basic Computer 173 6-1 Introduction 173 6-2 Machine Language 174  Contents vii 6-3 Assembly Language 179 Rules of the Language 1 79 An Example 1 81 Translation to Binary 1 82 6-4 The Assembler 183 Representation of Symbolic Program in Memory 1 84 First Pass 1 85 Secorui Pass 1 87 6-5 Program Loops 190 6-6 Programming Arithmetic and Logic Operations 192 Multiplication Program 1 93 Double-Precision Addition 1 96 Logic Operations 1 97 Shift Operations 1 97 6-7 Subroutines 198 Subroutines Parameters and Dara Linkage 200 6-8 Input-Output Programming 203 Character Manipulation 204 Program Interrupt 205 Problems 208 References 211 CHAPTER SEVEN Microprogrammed Control 213 7-1 Control Memory 213 7-2 Address Sequencing 216 Coruiitional Branching 21 7 Mapping of Instruction 21 9 Subroutines 220 7-3 Microprogram Example 220 Computer Configuration 220 Microinstruction Format 222 Symbolic Microinstructions 225 The Fetch Routine 226 Symbolic Microprogram 227 Binary Microprogram 229 viii Contents 7-4 Design of Control Unit 231 Microprogram Sequencer 232 Problems 235 References 238 CHAPTER EIGHT Central Processing Unit 241 8-1 Introduction 241 8-2 General Register Organization 242 Control Word 244 Examples of Microoperations 246 8-3 Stack Organization 247 Register Stack 247 Memory Stack 249 Reverse Polish Notation 251 Evaluation of Arithmetic Expressions 253 8-4 Instruction Formats 255 Three-Address Instructions 258 Tw:J-Address Instructions 258 One-Address Instructions 259 Zero-Address Instructions 259 RISC Instructions 259 8-5 Addressing Modes 260 Numerical Example 264 8-6 Data Transfer and Manipulation 266 Data Transfer Instructions 267 Data Manipulation Instructions 268 Arithmetic Instructions 269 Logical and Bit Manipulation Instructions 270 Shift Instructions 271 8-7 Program Control 273 Status Bit Conditions 274 Conditional Branch Instructions 275 Subroutine Call and Return 278 Program Interrupt 279 Types of Interrupts 281 8-8 Reduced Instruction Set Computer (RISC) 282 CISC Characteristics 283 RISC Characteristics 284  Contents ix Overlapped Register Windows 285 B.,-keley ruse 1 288 Problems 291 References 297 CHAPTER N IN E Pipeline and Vector Processing 299 9-1 Parallel Processing 299 9-2 Pipelining 302 General Considerations 304 9-3 Arithmetic Pipeline 307 9-4 Instruction Pipeline 310 Example: Four-Segment Instruction Pipeline 31 1 Data Dependency 31 3 Handling of Branch Instructions 314 9-5 R ISC Pipeline 315 Example: Three-Segment Instruction Pipeline 31 6 Delayed Load 31 7 Delayed Branch 31 8 9-6 Vector Processing 319 Vector Op.,-ations 321 Matrix Multiplication 322 Memory Interleaving 324 Sup...comput£rs 325 9-7 Array Processors 326 Attached Array Processor 326 SIMD Array Processor 327 Problems 329 References 330 CHAPTER TEN Computer Arithmetic 333 10-1 Introduction 333 10.2 Addition and Subtraction 334 Addition and Subtraction with Signed-Magnitude Data 335 X Contents Hardware Implementation 336 Hardware Algorithm 337 Addition and Subtraction with Signed-2's Complement Data 338 10-3 Multiplication Algorithms 340 Hardware Implementation for Signed-Magnitude Data 341 Hardware Algorithm 342 Booth Multiplication Algorithm 343 Array Multiplier 346 10-4 Division Algorithms 348 Hardware Implementation for Signed-Magnitude Data 349 Divide Overflow 351 Hardware Algorithm 352 Other Algorithms 353 10-5 Floating-Point Arithmetic Operations 354 Basic Considerations 354 Register Configuration 357 Addition and Subtraction 358 Multiplication 360 Division 362 10-6 Decimal Arithmetic Unit 363 BCD Adder 365 BCD Subtraction 368 10-7 Decimal Arithmetic Operations 369 Addition and Subtraction 371 Multiplication 371 Division 374 Floating-Point Operations 376 Problems 376 References 380 CHAPTER ELEVEN Input-Output Organization 381 11-1 Peripheral Devices 381 ASCII Alphanumeric Characters 383 11-2 Input-Output Interface 385 110 Bus and Interface Modules 386 110 versus Memory Bus 387  Contents xi Isolated versus Memory-Mapped 110 388 Example of 110 Interface 389 11-3 Asynchronous Data Transfer 391 Strobe Control 391 Handshaking 393 Asynchronous Serial Transfer 396 Asynchronous Communication Interface 398 First-In, First-Out Buffer 400 11-4 Modes of Transfer 402 Example of Programmed 110 403 Interrupt-Initiated 110 406 Software Considerations 406 11-5 Priority Interrupt 407 Daisy-Chaining Priority 408 Parallel Priority Interrupt 409 Priority Encoder 41 1 Interrupt Cycle 41 2 Software Routines 413 Initial and Final Operations 414 11-6 Direct Memory Access (DMA) 415 DMA Controller 41 6 DMA Transfer 41 8 11-7 Input-Output Processor (lOP) 420 CPU-lOP Communication 422 IBM 370 110 Channel 423 Intel 8089 lOP 427 11-8 Serial Communication 429 Character-Oriented Protocol 432 Transmission Example 433 Data Transparency 436 Bit-Oriented Protocol 437 Problems 439 References 442 CHAPTER TWELVE Memory Organization 445 12-1 Memory Hierarchy 445 12-2 Main Memory 448 RAM and ROM Chips 449 xii Contents Memory Address Map 450 Memory Connection to CPU 452 12-3 Auxiliary Memory 452 Magnetic Disks 454 Magnetic Tape 455 12·4 Associative Memory 456 Hardware Organization 457 March Logic 459 Read Operation 460 Write Operation 461 12·5 Cache Memory 462 Associative Mapping 464 Direct Mapping 465 Set-Associative Mapping 467 Writing into Cache 468 Cache Initialization 469 12-6 Virrual Memory 469 Address Space and Memory Space 470 Address Mapping Using Pages 472 Associative Memory Page Table 474 Page Replacement 475 12·7 Memory Management Hardware 476 Segmented-Page Mapping 477 Numerical Example 479 Memory Protection 482 Problems 483 References 486 CHAPTER THIRTEEN Multiprocessors 489 13-1 Characteristics of Multiprocessors 489 13-2 Interconnection Structures 491 Time-Shared Common Bus 491 Multipart Memory 493 Crossbar Switch 494 Multistage Switching Network 496 Hypercube Interconnection 498 13·3 lnterprocessor Arbitration 500 System Bus 500  Contents xiii Serial Arbitration Procedure 502 Parallel Arbitration Logic 503 Dynamic Arbitration Algorithms 505 13·4 lnterprocessor Communication and Synchronization 506 lnterprocessor Synchronization 507 Mutual Exclusion with a Semaphore 508 13-5 Cache Coherence 509 Conditions for Incoherence 509 Solutions to the Cache Coherence Problem 51 0 Problems 5 12 References 5 14 Index 5 15  CHAPTER ONE Digital Logic Circuits lN THIS CHAPTER 1-1 Digital Computers 1-2 logic Gates 1-3 Boolean Algebra 1-4 Map Simplification 1-5 Combinational Circuits 1-6 Rip-Flops 1-7 Sequential Circuit> 1-1 Digital Computers digital The dgita i l computer is a dig it al system that performs various computational tasks. The word digital implies t.hat the information in the computer is repre­ sented by variables that take a limited number of discrete values. These values are processed intemally by components that can maintain a limited number of disaete states. The decimal digits 0, 1, 2,..., 9, for example, provide 10 discrete values. The first electronic digital computers, developed in the late 1940s, were used primarily for numerical computations. ln this case the dis­ crete el ements are the digits.From this application the termdigitAlc:omputuha.s emerged. In practice, digital computers function more reliably if only two states are used.Because of the physical restriction of components, and because.. human logic tends to be binary (i.e., true-r-false, yes-r-no statements), digital components that are constrained to take discrete values are further constrained to take only two values and are said to be bituzry. Digital computers use the binary number system, which has two digits: lrit 0 and 1. A binary digit is called a mi. Information is represented in digital computers in groups ofbits. By using various codingtechniques, groups ofbits can be made to represent not only binary numbers but also other discrete 2 CHAPTER ONE Digital Logic Circuits symbols, such as decimal digits or letters of the alphabet. By judicious use of binary arrangements and by using various coding techniques, the groups of bits are used to develop complete sets of instructions for performing various types of computations. In contrast to the common decimal numbers that employ the base 10 system, binary numbers use a base 2 system with two digits: 0 and I. The decimal equivalent of a binary number can be found by expanding it into a power series with a base of 2. For example, the binary number 1001011 repre­ sents a quantity that can be converted to a decimal number by multiplying each bit by the base 2 raised to an integer power as follows: The seven bits 10010ll represent a binary number whose decimal equivalent is 75. However, this same group of seven bits represents the letter K when used in conjunction with a binary code for the letters of the alphabet. It may also represent a control code for specifying some decision logic in a particular digital computer. In other words, groups of bits in a digital computer are used to represent many different things. This is similar to the concept that the same letters of an alphabet are used to construct different languages, such as English and French. A computer system is sometimes subdivided into two functional entities: hardware and software. The hardware of the computer consists of all the electronic components and electromechanical devices that comprise the phys­ ical entity of the device. Computer software consists of the instructions and data that the computer manipulates to perform various data-processing tasks. program A sequence of instructions for the computer is called a program. The data that are manipulated by the program constitute the data base. A computer system is composed of its hardware and the system software available for its use. The system software of a computer consists of a collection of programs whose purpose is to make more effective use of the computer. The programs included in a systems software package are referred to as the oper­ ating system. They are distinguished from application programs written by the user for the purpose of solving particular problems. For example, a high-level language program written by a user to solve particular data-processing needs is an application program, but the compiler that translates the high-level language program to machine language is a system program. The customer who buys a computer system would need, in addition to the hardware, any available software needed for effective operation of the computer. The system software is an indispensable part of a total computer system. Its function is to compensate for the differences that exist between user needs and the capability of the hardware. computer hardware The hardware of the computer is usually divided into three major parts, as shown in Fig. 1-1. The central processing unit (CPU) contains an arithmetic  SOCTION 1·1 0\gllal Compuru> 3 Figure 1·1 Block diaeram of a digital computer. and logic unit for manipulating dala, a number of registers for storing dala, and control circuits for fetching and executing inslnlctions. The memory of a computer contains storage for n i slnlctions and data. It is called a random· access memory (RAM) because the CPU can access any location in memory at random and retrieve the binaryinformation within a fixed interval of time. The input and output processor (lOP) contains electronic circuits for communicat­ ing and controlling the transfer of information between the computer and the outside world. The input and output devices connected to the computer include keyboards, printers, terminals, magnetic disk drives, and other com· munication devices. This book provides the basic knowledge necessary to understand the hardware operations of a computer syst m. The subject is sometimes consid­ ered from three different points of view, depending on the interest of the investigator. When dealing with computer hardware it is customary to distin· guish between what is referred to as com puter organi.ution, computer design, and computer architecture. CO"'P"t" Compul r organiZRiion is concerned with the way the hardwa re compo­ 0'8111d%11tiOrt nents operate and the way they are connected together to form the computer system. The various components are assumed to be in place and the task is to investigate the organhational slnlcture to verify that the computer parts oper­ ate as intended. computer dalgn Compute cksign is concerned with the hardware design of the computer. Once the computer specifications are formulated, it is the task of the designer to develop hardware for the system. Computer design is concerned with the determination of what hardware should be used and how the parts should be connected. This aspect of computer hardware is sometimes referred to as computer implrolhltation. computer Computer architecture is conc erned with the slnlcture and behavior of the m:hiteclurt computer as seen by the user. It includes the information formats, the inslnlc- 4 CHAPTER ONE Digital Logic Circuits tion set, and techniques for addressing memory. The architectural design of a computer system is concerned with the specifications of the various func­ tional modules, such as processors and memories, and structuring them to­ gether into a computer system. The book deals with all three subjects associated with computer hard­ ware. In Chapters 1 through 4 we present the various digital components used in the organization and design of computer systems. Chapters 5 through 7 cover ·the steps that a designer must go through to design and program an elementary digital computer. Chapters 8 and 9 deal with the architecture of the central processing unit. In Chapters 11 and 12 we present the organization and architecture of the input-output processor and the memory unit. 1 -2 Logic Gates Binary information is represented in digital computers by physical quantities called signals. Electrical signals such as voltages exist throughout the computer in either one of two recognizable states. The two states represent a binary variable that can be equal to 1 or 0. For example, a particular digital computer may employ a signal of 3 volts to represent binary 1 and 0.5 volt to represent binary 0. The input terminals of digital circuits accept binary signals of 3 and 0.5 volts and the circuits respond at the output terminals with signals of 3 and 0.5 volts to represent binary input and output corresponding to 1 and 0, respectively. Binary logic deals with binary variables and with operations that assume a logical meaning. It is used to describe, in algebraic or tabular form, the manipulation and processing of binary information. The manipulation of bi­ gates nary information is done by logic circuits called gates. Gates are blocks of hardware that produce signals of binary 1 or 0 when input logic requirements are satisfied. A variety of logic gates are commonly used in digital computer systems. Each gate has a distinct graphic symbol and its operation can be described by means of an algebraic expression. The input-output relationship of the binary variables for each gate can be represented in tabular form by a truth table. The names, graphic symbols, algebraic functions, and truth tables of eight logic gates are listed in Fig. 1-2. Each gate has one or two binary input variables designated by A and Band one binary output variable designated by AND x. The AND gate produces the AND logic function: that is, the output is 1 if input A and input B are both equal to 1; otherwise, the output is 0. These conditions are also specified in the truth table for the AND gate. The table shows that output x is 1 only when both input A and input Bare 1. The algebraic operation symbol of the AND function is the same as the multiplication symbol of ordinary arithmetic. We can either use a dot between the variables or  Graphic AIKehral( Tmtll Name symh(J/ func/I(Jn tah/e A B 0 0 x=A B AND ;=C)---, 0' x=AB I I 0 0 I I A 8 x OR ;=:[)--- x x=A+B 0 0 I I Inverter A ---{>o--- x x =A' Buffer A -----t:>--.r x =A A 8 x NAND ; x x=(AB)' 0 0 0 I I I A 8 x NOR ; x x=(A+B)' 0 0 0 I I 0 0 I I A 8 x Exclusive-OR x=AfBB 0 0 0 (XOR) 0' 0 I I 0 x=A'B+AB' I I A B x Exclusive-NOR 0 0 A x=(AfBB)' or equivalence B x or 0 I I 0 0.\=A'B'+AB I I Figure.. 12 Digital logic gates. 5 6 CHAPTER ONE Digital Logic Circuits concatenate the variables without an operation symbol between them. AND gates may have more than two inputs, and by definition, the output is 1 if and only if all inputs are I. OR The OR gate produces the inclusive-OR function; that is, the output is 1 if input A or input B or both inputs are I; otherwise, the output is 0. The algebraic symbol of the OR function is +, similar to arithmetic addition. OR gates may have more than two inputs, and by definition, the output is 1 if any input is I. inverter The inverter circuit inverts the logic sense of a binary signal. It produces the NOT, or complement, function. The algebraic symbol used for the logic complement is either a prime or a bar over the variable symbol. In this book we use a prime for the logic complement of a binary variable, while a bar over the letter is reserved for designating a complement microoperation as defined in Chap. 4. The small circle in the output of the graphic symbol of an inverter desig­ nates a logic complement. A triangle symbol by itself designates a buffer circuit. A buffer does not produce any particular logic function since the binary value of the output is the same as the binary value of the input. This circuit is used merely for power amplification. For example, a buffer that uses 3 volts for binart 1 will produce an output of 3 volts when its input is 3 volts. However, the amount of electrical power needed at the input of the buffer is much less than the power produced at the output of the buffer. The main purpose of the buffer is to drive other gates that require a large amount of power. The NAND function is the complement of the AND function, as indicated by the graphic symbol, which consists of an AND graphic symbol followed by a small circle. The designation NAND is derived from the abbreviation of NOR NOT-AND. The NOR gate is the complement of the OR gate and uses an OR graphic symbol followed by a small circle. Both NAND and NOR gates may have more than two inputs, and the output is always the complement of the AND or OR function, respectively. exclusive-OR The exclusive-OR gate has a graphic symbol similar to the OR gate except for the additional curved line on the input side. The output of this gate is I if any input is 1 but excludes the combination when both inputs are I. The exclusive-OR function has its own algebraic symbol or can be expressed in terms of AND, OR, and complement operations as shown in Fig. 1-2. The exclusive-NOR is the complement of the exclusive-OR, as indicated by the small circle in the graphic symbol. The output of this gate is 1 only if both inputs are equal to 1 or both inputs are equal to 0. A more fitting name for the exclusive-OR operation would be an odd function; that is, its output is I if an odd number of inputs are I. Thus in a three-input exclusive-OR (odd) function, the output is 1 if only one input is 1 or if all three inputs are 1. The exclusive-OR and exclusive-NOR gates are commonly available with two inputs, and only seldom are they found with three or more inputs.  SECTION 1-J Boolean Algebra 7 1 -3 Boolean Algebra Boolean algebra is an algebra that deals with binary variables and logic oper­ ations. The variables are designated by letters such as A, B, x, andy. The three Boolean function basic logic operations are AND, OR, and complement. A Boolean function can be expressed algebraically with binary variables, the logic operation symbols, parentheses, and equal sign. For a given value of the variables, the Boolean function can be either 1 or 0. Consider, for example, the Boolean function F = x + y'z The function F is equal to 1 if x is 1 or if bothy' and z are equal to I; F is equal to 0 otherwise. But saying that y' = 1 is equivalent to saying that y = 0 since y' is the complement of y. Therefore, we may say that F is equal to 1 if x = 1 or if yz = 01. The relationship between a function and its binary variables can :ruth table be represented in a truth table. To represent a function in a truth table we need a list of the 2' combinations of then binary variables. As shown in Fig. l-3(a), there are eight possible distinct combinations for assigning bits to the three variables x, y, and z. The function F is equal to 1 for those combinations where x = 1 or yz = 01; it is equal to 0 for all other combinations. A Boolean function can be transformed from an algebraic expression into :.,gic diagram a logic diagram composed of AND, OR, and inverter gates. The logic diagram for F is shown in Fig. l-3(b). There is an inverter for input y to generate its complementy'. There is an AND gate for the termy'z, and an OR gate is used to combine the two terms. In a logic diagram, the variables of the function are taken to be the inputs of the circuit, and the variable symbol of the function is taken as the output of the circuit. The purpose of Boolean algebra is to facilitate the analysis and design of digital circuits. It provides a convenient tool to: 1. Express in algebraic form a truth table relationship between binary variables. F Figure 1.. 3 Truth table and logic diagram for F = x + y1z.. : F y 0 0 0 0 0 0 I I 0 I 0 0 0 I I 0 I 0 0 I z I 0 I I I I 0 I I I I I (a) Truth table (b) Logic diagram 8 CHAPTER ONE Digital Logic Circuits 2. Express in algebraic form the input- 39 · Draw the logic diagram oE the c:ircWt. b. Tabulate the state table. 1·20. Design a 2-bit count-down countet. This s i a sequential c:ircW t with two llip flops and one input x. When x 0, the state of the Dip-flops does nnt change. When x I, the state sequence is U, \0, 01, 00, 11, and repeat. 1·21. Design a sequential circuit with two TK flip-Oops A and B and two inputs E and x. U E = 0, the circuit remains in the same state regardless of thevalue of x. When E = 1 and x = 1, the circuit goes through the state transitions from 00 to 01 to 10 to II back to 00, and repeat. When E a I and x = 0, the c:ircWt goes through the state transitions &om 00 to 11 to10 to 01 bad< to 00, and repeat. REFERENCES 1. Hill, F. J., and G. R. Person. lntrodU£tion to Switching Tlltwyond Logioll Design, 3rd et ed. New York: john W ey. 1981. 2. Mano, M. M, Digitd Design, 2nd ed. Englewood Cliffs, N): Prenlitt HAIL 1991. 3. Roth, C. H.. Fund.ttmcJtols of Logic Design, 3rd ed. St. Paul, MN: West Publishing, 1985. 4. Sandige, R. S., Moden Digitol Design. New Yodc McGraw-Hill. 1990. S. Shlva, S. G., /ntrodudion to LDgic Design. Glenview, 11.; Smtt, Foresman, 1988. 6. Wakerly, J. F., Digitol Design Prindpl., 1md Practi«s. Englewood Oiffs, N): Prentice HaU, 1990. 7. Ward, S. A., and R. H. Halstead, Jr., U>mputation Strudum. Cambridge, MA: MIT Press, 1990.  CHAPTER T W O Digital Components IN THIS CHAPTER 2·1 Integrated Circuits 2-2 Decoders 2·3 Multiplexers 2-4 Registen 2·5 Shift Regineno U Binary Counters 2-7 Memory Unit 2·1 Integrated Circuits Digital circuits are constructed with integrated circuits. Azl ni tegrated cin:uit IC (abbreviated IC) is a small silicon semiconductor crystal. called a dlip, contain· ing the electronic components for the digital gates. The various gates are i te.rconnected inside the chip to form the required circuit. Thechip ismounted n I a ceramic or plastic container, and connections are welded by thin gold wines n to external pins to form the n i tegrated circuit. The number of pins may range from 14 in a small IC package to 100 or more in a larger package. Each IC has a numeric designation printed on the surface of the package for identification. Each vendor publishes a data book or catalog that contains the exact descrip­ tion and all the necessa.ry information about the ICs that it manufactures. As the technology of ICs has improved the number of gates that can be , put in a single chip has increased considerably. The differentiation between those chips that have a few internal gates and those having hundreds or thousands of gates s i made by a customary reference to a packa$1! as being either a small·, medium·, or large-scale integration device. SSI SmaU-5Cille nttgralion i (SSI) devices contain several independent gates in a single package. The inputs and outputs of the gates are connected directly 42 CHAPTER 1WO Digital Components to the pins in the package. The number of gates is usually less than 10 and is limited by the number of pins available in the !C. MSI Medium-scale integration (MSI) devices have a complexity of approximately 10 to 200 gates in a single package. They usually perform specific elementary digital functions such as decoders, adders, and registers. LSI Large-scale integration (LSI) devices contain between 200 and a few thou- sand gates in a single package. They include digital systems, such as proces­ sors, memory chips, and programmable modules. VLSI Very-large-scale integration (VLSI) devices contain thousands of gates within a single package. Examples are large memory arrays and complex microcomputer chips. Because of their small size and low cost, VLSI devices have revolutionized the computer system design technology, giving designers the capability to create structures that previously were not economical. Digital integrated circuits are classified not only by their logic operation but also by the specific circuit technology to which they belong. The circuit technology is referred to as a digital logic family. Each logic family has its own basic electronic circuit upon which more complex digital circuits and functions are developed. The basic circuit in each technology is either a NAND, a NOR, or an inverter gate. The electronic components that are employed in the construction of the basic circuit are usually used for the name of the technol­ ogy. Many different logic families of integrated circuits have been introduced commercially. The following are the most popular. TTL Transistor-transistor logic ECL Emitter-coupled logic MOS Metal-oxide semiconductor CMOS Complementary metal-oxide semiconductor TTL is a widespread logic family that has been in operation for many years and is considered as standard. ECL has an advantage in systems requir­ ing high-speed operation. MOS is suitable for circuits that need high compo­ nent density, and CMOS is preferable in systems requiring low power consumption. TTL The transistor-transistor logic family was an evolution of a previous technology that used diodes and transistors for the basic NAND gate. This technology was called DTL, for "diode-transistor logic." Later the diodes were replaced by transistors to improve the circuit operation and the name of the logic family was changed to "transistor-transistor logic." This is the reason for mentioning the word "transistor" twice. There are several variations of the TTL family besides the standard TTL, such as high-speed TTL, low-power TTL, Schottky TTL, low-power Schottky TTL, and advanced Schottky TTL. The  SECTION 2-2 Decoders 43 power supply voltage for TIL circuits is 5 volts, and the two logic levels are approximately 0 and 3.5 volts. ECL The emitter-coupled logic (ECL) family provides the highest-speed digital circuits in integrated form. ECL is used in systems such as supercomputers and signal processors where high speed is essentiaL The transistors in ECL gates operate in a nonsaturated state, a condition that allows the achievement of propagation delays of 1 to 2 nanoseconds. The metal-oxide semiconductor (MOS) is a unipolar transistor that depends on the flow of only one type of carrier, which may be electrons (n-channel) or holes (p-channel). This is in contrast to the bipolar transistor used in TIL and ECL gates, where both carriers exist during normal operation. A p-channel MOS is referred to as PMOS and an n-channel as NMOS. NMOS is the one that is commonly used in circuits with only one type of MOS CMOS transistor. The complementary MOS (CMOS) technology uses PMOS and NMOS transistors connected in a complementary fashion in all circuits. The most important advantages of CMOS over bipolar are the high packing density of circuits, a simpler processing technique during fabrication, and a more economical operation because of low power consumption. Because of their many advantages, integrated circuits are used exclu­ sively to provide various digital components needed in the design of computer systems. To understand the organization and design of digital computers it is very important to be familiar with the various components encountered in integrated circuits. For this reason, the most basic components are introduced in this chapter with an explanation of their logical properties. These compo­ nents provide a catalog of elementary digital functional units commonly used as basic building blocks in the design of digital computers. 2-2 Decoders Discrete quantities of information are represented in digital computers with binary codes. A binary code of n bits is capable of representing up to 2" distinct elements of the coded information. A decoder is a combinational circuit that converts binary information from the n coded inputs to a maximum of 2" unique outputs. If the n-bit coded information has unused bit combinations, the decoder may have less than 2" outputs. decoder The decoders presented in this section are called n-to-m-line decoders, where m :5 2". Their purpose is to generate the 2" (or fewer) binary combina­ tions of the n input variables. A decoder has n inputs and m outputs and is also referred to as an n x m decoder. The logic diagram of a 3-to-8-line decoder is shown in Fig. 2-L The three data inputs, Ao, A1, and A,, are decoded into eight outputs, each output 44 CHAPTER TWO Digital Components ()()() A, Do -----1 ,...---.. v 00 1 -{)o- - -----j 010 v, ,...---.. 01 1 D, 100 101 Ds -----1.....----.. 1 10 Ill D, Enable (E) Figure 2.-1 J..to.-8.-line decoder. representing one of the combinations of the three binary input variables. The three inverters provide the complement of the inputs, and each of the eight AND gates generates one of the binary combination. A particular application of this decoder is a binary-to-octal conversion. The input variables represent a binary number and the outputs represent the eight digits of the octal number system. However, a 3-to-8-line decoder can be used for decoding any 3-bit code to provide eight outputs, one for each combination of the binary code. Enable input Commercial decoders include one or more enable inputs to control the operation of the circuit. The decoder of Fig. 2-1 has one enable input, E. The decoder is enabled when E is equal to 1 and disabled when E is equal to 0. The operation of the decoder can be clarified using the truth table listed in Table 2-1. When the enable input E is equal to 0, all the outputs are equal to 0 regardless of the values of the other three data inputs. The three x ' s in the table designate don't-care conditions. When the enable input is equal to I, the decoder operates in a normal fashion. For each possible input combina­ tion, there are seven outputs that are equal to 0 and only one that is equal to I. The output variable whose value is equal to 1 represents the octal number equivalent of the binary number that is available in the input data lines.  SECTION 2-2 Decoders 45 TABLE 2- 1 Truth Table for 3-to-8-Line Decoder Enable Inputs Outputs E A, A, Ao D, D, D, D, D, D, D, Do 0 X X X 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 I 0 0 I 0 0 0 0 0 0 I 0 0 I 0 0 0 0 0 0 I 0 0 0 I I 0 0 0 0 I 0 0 0 0 0 0 0 0 I 0 0 0 0 0 I 0 0 I 0 0 0 0 0 0 0 I 0 0 0 0 0 0 0 0 0 0 0 0 0 NAND Gate Decoder Some decoders are constructed with NAND instead of AND gates. Since a NAND gate produces the AND operation with an inverted output, it becomes more economical to generate the decoder outputs in their complement form. A 2-to-4-line decoder with an enable input constructed with NAND gates is shown in Fig. 2-2. The circuit operates with complemented outputs and a complemented enable input E. The decoder is enabled when E is equal to 0. As indicated by the truth table, only one output is equal to 0 at any given time; the other three outputs are equal to 1. The output whose value is equal to 0 represents the equivalent binary number in inputs A1 and A,. The circuit is disabled when E is equal to 1, regardless of the values of the other two inputs. Figure 2-2 2-to-4-line decoder with NAND gates. Do E A, Ao Do D, D, D, 0 0 0 0 D, 0 0 D, 0 0 0 D, X X (a) Logic diagram (b) Truth >able 46 CHAPTER TWO Digital Components When the circuit is disabled, none of the outputs are selected and all outputs are equal to 1. In general, a decoder may operate with complemented or uncomplemented outputs. The enable input may be activated with a 0 or with a 1 signal level. Some decoders have two or more enable inputs that must satisfy a given logic condition in order to enable the circuit. Decoder Expansion There are occasions when a certain-size decoder is needed but only smaller sizes are available. When this occurs it is possible to combine two or more decoders with enable inputs to form a larger decoder. Thus if a 6-to-64-line decoder is needed, it is possible to construct it with four 4-to-16-line decoders. Figure 2-3 shows how decoders with enable inputs can be connected to form a larger decoder. Two 2-to-4-line decoders are combined to achieve a 3-to-8-line decoder. The two least significant bits of the input are connected to both decoders. The most significant bit is connected to the enable input of one decoder and through an inverter to the enable input of the other decoder. It is assumed that each decoder is enabled when its E input is equal to 1. When E is equal to 0, the decoder is disabled and all its outputs are in the O level. When A, = 0, the upper decoder is enabled and the lower is disabled. The lower decoder outputs become inactive with all outputs at 0. The outputs of the upper decoder generate outputs Do through D3, depending on the values of A1 and A0 (while A, = 0). When A, = 1, the lower decoder is enabled and the upper is disabled. The lower decoder output generates the binary equivalent D4 through D, since these binary numbers have a 1 in the A, position. Figure z,J A 3 X 8 decoder constructed with two 2 X 4 decoders. 2x4 decoder Ao 2' A, 2' A, E 2x4 decoder D, 2' Ds 2' Do E D,  SECTION 2-2 Decoders 47 The example demonstrates the usefulness of the enable input in decoders or any other combinational logic component. Enable inputs are a convenient feature for interconnecting two or more circuits for the purpose of expand­ ing the digital component into a similar function but with more inputs and outputs. Encoders An encoder is a digital circuit that performs the inverse operation of a decoder. An encoder has 2" (or less) input lines and n output lines. The output lines generate the binary code corresponding to the input value. An example of an encoder is the octal-to-binary encoder, whose truth table is given in Table 2-2. It has eight inputs, one for each of the octal digits, and three outputs that generate the corresponding binary number. It is assumed that only one input has a value of 1 at any given time; otherwise, the circuit has no meaning. TABLE 2-2 Truth Table for Octal-to-Binary Encoder Inputs Outputs D, D, D, D, D, D, D, Do A, A, A, 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 The encoder can be implemented with OR gates whose inputs are deter­ mined directly from the truth table. Output Ao = 1 if the input octal digit is 1 or 3 or 5 or 7. Similar conditions apply for the other two outputs. These conditions can be expressed by the following Boolean functions: Ao = D1 + D, + Ds + D7 A, = D2 + D3 + D, + D7 A, = D4 + D5 + D, + D, The encoder can be implemented with three OR gates. 48 CHAPTER TWO Digital Components 2-3 Multiplexers multiplexer A multiplexer is a combinational circuit that receives binary information from one of 2" input data lines and directs it to a single output line. The selec­ tion of a particular input data line for the output is determined by a set of selection inputs. A 2"-to-1 multiplexer has 2" input data lines and n input selection lines whose bit combinations determine which input data are selected for the output. A 4-to-1-line multiplexer is shown in Fig. 2-4. Each of the four data inputs I0 through I, is applied to one input of an AND gate. The two selection inputs 51 and 50 are decoded to select a particular AND gate. The outputs of the AND gates are applied to a single OR gate to provide the single output. To demon­ strate the circuit operation, consider the case when 5150 = 10. The AND gate associated with input I, has two of its inputs equal to 1. The third input of the gate is connected to I2 The other three AND gates have at least one input equal to 0, which makes their outputs equal to 0. The OR gate output is now equal to the value of I,, thus providing a path from the selected input to the output. The 4-to-1 line multiplexer of Fig. 2-4 has six inputs and one output. A truth table describing the circuit needs 64 rows since six input variables can have 26 binary combinations. This is an excessively long table and will not be shown here. A more convenient way to describe the operation of multiplexers is by means of a function table. The function table for the multiplexer is shown in Table 2-3. The table demonstrates the relationship between the four data inputs and the single output as a function of the selection inputs 51 and 50. Figure 2,4 4 to- l-line multiplexer. y So -----' --- s, --  SECTION 2-3 Multiplexers 49 When the selection inputs are equal to 00, output Y is equal to input /0 When the selection inputs are equal to 01, input 11 has a path to output Y, and similarly ta selector for the other two combinations. The multiplexer is also called a data selector, since it selects one of many data inputs and steers the binary information to the output. TABLE 2.-3 Function Table for 4;to; l;Line Multiplexer Select Output 5, s, y 0 0 I, 0 1 I, 0 I, I, The AND gates and inverters in the multiplexer resemble a decoder circuit, and indeed they decode the input selection lines. In general, a 2"-to-1- line multiplexer is constructed from an n-to-2" decoder by adding to it 2" input lines, one from each data input. The size of the multiplexer is specified by the number 2" of its data inputs and the single output. It is then implied that it also contains n input selection lines. The multiplexer is often abbreviated as MUX. As in decoders, multiplexers may have an enable input to control the operation of the unit. When the enable input is in the inactive state, the outputs are disabled, and when it is in the active state, the circuit functions as a normal multiplexer. The enable input is useful for expanding two or more multiplexers to a multiplexer with a larger number of inputs. In some cases two or more multiplexers are enclosed within a single integrated circuit package. The selection and the enable inputs in multiple-unit construction are usually common to all multiplexers. As an illustration, the block diagram of a quadruple 2-to-1-line multiplexer is shown in Fig. 2-5. The circuit has four multiplexers, each capable of selecting one of two input lines. Output Y0 can be selected to come from either input Ao or Bo. Similarly, output Y; may have the value of A 1 or B 1 , and so on. One input selection line S selects one of the lines in each of the four multiplexers. The enable input E must be active for normal operation. Although the circuit contains four multiplexers, we can also think of it as a circuit that selects one of two 4-bit data lines. As shown in the function table, the unit is enabled when E = 1. Then, if S = 0, the four A inputs have a path to the four outputs. On the other hand, if S = 1, the four B inputs are applied to the outputs. The outputs have all O's when E = 0, regardless of the values of S. 50 CHAPTER lWO Digital Components Enable E Select s Yo E y Quadruple r, X All O's 2x l multiplexers Y, 0 A r, 8 (b) Function lable (a) Block diagram Figure 2.. 5 Quadruple 2-to- 1 line multiplexers. 2-4 Registers A register is a group of flip-flops with each flip-flop capable of storing one bit of information. An n-bit register has a group of n flip-flops and is capable of storing any binary information of n bits. In addition to the flip-flops, a register may have combinational gates that perform certain data-processing tasks. In its broadest definition, a register consists of a group of flip-flops and gates that effect their transition. The flip-flops hold the binary information and the gates control when and how new information is transferred into the register. Various types of registers are available commercially. The simplest regis­ ter is one that consists only of flip-flops, with no external gates. Figure 2-6 shows such a register constructed with four D flip-flops. The common clock input triggers all flip-flops on the rising edge of each pulse, and the binary data available at the four inputs are transferred into the 4-bit register. The four outputs can be sampled at any time to obtain the binary information stored in the register. The clear input goes to a special terminal in each flip-flop. When this input goes to 0, all flip-flops are reset asynchronously. The clear input is useful for clearing the register to all O's prior to its clocked operation. The clear input must be maintained at logic 1 during normal clocked operation. Note that the clock signal enables the D input but that the clear. input is independent of the clock. register load The transfer of new information into a register is referred to as loading the register. If all the bits of the register are loaded simultaneously with a common  SECTION 2·"1 Registers 51 lo D Q - Ao Clock c y /I D Q - c y 12 D Q r--- c y h D Q r--- c Clear y Figure 2-6 4-bit register. clock pulse transition, we say that the loading is done in parallel. A clock transition applied to the C inputs of the register of Fig. 2-6 will load all four inputs 10 through 13 in parallel. In this configuration, the clock must be inhibited from the circuit if the content of the register must be left unchanged. Register with Parallel Load Most digital systems have a master clock generator tha t supplies a continuous train of clock pulses. The clock pulses are applied to all flip-flops and registers in the syste m. The master clock acts like a pump that supplies a constant beat to all parts of the system. A separate control signal must be used to decide which specific clock pulse will have an effect on a particular register. A 4-bit register with a load control input that is directed through gates and into the D inputs is shown in Fig. 2-7. The C inputs receive clock pulses at all times. The buffer gate in the dock input reduces the power requirement  SECTION 2-5 Shift Registers 53 With each clock pulse, the D input determines the next state of the output. To leave the output unchanged, it is necessary to make the D input equal to the present value of the output. Note that the clock pulses are applied to the C inputs at all times. The load input determines whether the next pulse will accept new information or leave the information in the register intact. The transfer of information from the inputs into the register is done simultaneously with all four bits during a single pulse transition. 2-5 Shift Registers A register capable of shifting its binary information in one or both directions is called a shift register. The logical configuration of a shift register consists of a chain of flip-flops in cascade, with the output of one flip-flop connected to the input of the next flip-flop. All flip-flops receive common clock pulses that initiate the shift from one stage to the next. The simplest possible shift register is one that uses only flip-flops, as shown in Fig. 2-8. The output of a given flip-flop is connected to the D input serial input of the flip-flop at its right. The clock is common to all flip-flops. The serial input determines what goes into the leftmost position during the shift. The serial output is taken from the output of the rightmost flip-flop. Sometimes it is necessary to control the shift so that it occurs with certain clock pulses but not with others. This can be done by inhibiting the clock from the input of the register if we do not want it to shift. When the shift register of Fig 2-8 is used, the shift can be controlled by connecting the clock to the input of an AND gate, and a second input of the AND gate can then control the shift by inhibiting the clock. However, it is also possible to provide extra circuits to control the shift operation through the D inputs of the flip-flops rather than the clock input. Bidirectional Shift Register with Parallel Load A register capable of shifting in one direction only is called a unldirectional shift register. A register that can shift in both directions is called a bidirectional shift register. Some shift registers provide the necessary input and output terminals Figure 2-8 4 bit shift register. Serial output 54 CHAPTER TWO Digital Components for parallel transfer. The most general shift register has all the capabilities listed below. Others may have some of these capabilities, with at least one shift operation. 1. An input for clock pulses to synchronize all operations. 2. A shift-right operation and a serial input line associated with the shift­ right. 3. A shift-left operation and a serial input line associated with the shift-left. 4. A parallel load operation and n input lines associated with the parallel transfer. 5. n parallel output lines. 6. A control state that leaves the information in the register unchanged even though clock pulses are applied continuously. A 4-bit bidirectional shift register with parallel load is shown in Fig. 2-9. Each stage consists of a D flip-flop and a 4 x 1 multiplexer. The two selection inputs 51 and 50 select one of the multiplexer data inputs for the D flip-flop. The selection lines control the mode of operation of the register according to the function table shown in Table 2-4. When the mode control 5150 = 00, data input 0 of each multiplexer is selected. This condition forms a path from the output of each flip-flop into the input of the same flip-flop. The next clock transition transfers into each flip-flop the binary value it held previously, and no change of state occurs. When 5150 = 01, the terminal marked 1 in each multiplexer has a path to the D input of the corresponding flip-flop. This causes a shift-right operation, with the serial input data transferred into flip-flop A0 and the content of each flip-flop A, _ 1 transferred into flip-flop A; for i = 1, 2, 3. When 5150 = 10 a shift-left operation results, with the other serial input data going into flip-flop A, and the content of flip-flop A, + 1 transferred into flip-flop A; for i = 0, I, 2. When 5150 = 1 1 , the binary information from each input 10 through I, is transferred into the corresponding flip-flop, resulting in a parallel load operation. Note that the way the diagram is drawn, the shift-right operation shifts the contents of the register in the down direction while the shift left operation causes the contents of the register to shift in the upward direction. TABLE 2·4 Function Table for Register of Fig. 2-9 Mode control s, s, Register operation 0 0 No change 0 I Shift right (down) I 0 Shift left (up) I Parallel load  2-S Shift R< 1 c 0 MUX r- input I 2 ' 3 So s, f-I- D Q Ao 4xl 0 MlJl( I- c I l lo l. s, 1--r-- D Q 0 MUX4xl I- c I 2 J s So f-1-- D Q 4 >< 1 0 M\..'X I->c i - I Serial 2 ' l Shiftregistersare oftenused tointerlace digital systems situaledremotely from each other. For example, suppose that it is nece5Sal)' to transmit an n-bi t quantity between two points. U the distance between the source and the destination is too far, it will be expensive to use " Jines to transmit the " bits In parallel. It may be more economical to use a single line and transmit the information serially one bit at a time. The transmitter loads the n-bit data in 56 CHAPTIR TWO Digital Components parallel into a shift register and then transmits the data from the serial output line. The receiver accepts the data serially into a shift register through its serial input line. When the entire n bits are accumulated they can be taken from the outputs of the register in parallel. Thus the transmitter performs a parallel-to­ serial conversion of data and the receiver converts the incoming serial data back to parallel data transfer. 2-6 Binary Counters A register that goes through a predetermined sequence of states upon the application of input pulses is called a counter. The input pulses may be clock pulses or may originate from an external source. They may occur at uniform intervals of time or at random. Counters are found in almost all equipment containing digital logic. They are used for counting the number of occurrences of an event and are useful for generating timing signals to control the sequence of operations in digital computers. Of the various sequences a counter may follow, the straight binary se­ quence is the simplest and most straightforward. A counter that follows the binary number sequence is called a binary counter. An n-bit binary counter is a register of n flip-flops and associated gates that follows a sequence of states according to the bi