Digital Computer Electronics Third Edition Albert Paul Malvino, Ph.D. Jerald A. Brown eel GLENCOE McGraw-Hill us, Ohio. Woodland New York, New York Columbu Hills, California Peoria, illinois“This textbook was prepared withthe assistance of Publishing Advisory Service. LSI ict photo: Manfred Kage’Peter Arnold lnc To my wife, Joanna, who encourages me to write ‘And to my daughters, Joanna, Antonia, Lucinds, Patricia, and Miriam, who keep me young APM to my wile Vickie dearest friend fellow adventurer love of my life LAB. Library of Congress Cataloging.n-Publiction Data Maino, Albert Paul Digital comauter electronics / Albert Paul Malvino, Jerald A. Brown. — 3d e6 poem Incudes index ISBN 0-02-800594-5 (nardcover) 1 Electronic egal computers. 2. Microcomputers. 3, Ito £8085 (Microprocessor) |. Brown, Jerald AI. Tile TK7856.3M337_ 1993 621.39'16—6c20 92-5895, cP Digital Computer Electronics, Third Eaton limpet 1900 Copyright© 1999, 1963 by Glencoe MeGraw-Hl Al ight osarved, Copjigh © 1989, 1977 by ‘MeGraw-til, nc, Al righ reserved, Prntd inthe Uniod Stats of Amora Except as ‘ermitlod undor tho Unite States Copyright Act, no part ofthis pubbeation may be reproduced ‘ralstrbuted in any form o by any moans, or sored in a Gatabasa or retrovl syst, witout prior rien pormssion othe pubtiser ISBN 0-02-800504-5, Printed in the United States of Ameria 486789101112 c0Wo43 03.0201 0009,es Contents PREFACE vi PART 1 Digital Principles 1 CHAPTER 1, NUMBER SYSTEMS AND CODES 1 J-1. Decimal Odometer 1-2. Binary Odometer 1-3. Number Codes 1-4. Why Binary Numbers Are Used 1-5. Binary-to-Decimal Conversion 1-6, Microprocessors 1-7. Decimal-to-Binary Conversion 1-8, Hexadecimal Numbers. 1-9. Hexadecimal-Binary Conversions 1-10. Hexadecimal-to-Decimal Conversion I-11, Decimal-to-Hexadecimal Conversion 1-12, BCD Numbers 1-13. The ASCII Code CHAPTER 2. GATES 19 2-1. Inverters 2-2, OR Gates 2-3, aNb Gates 24. Boolean Algebra CHAPTER 3. MORE LOGIC GATES 32 3-1. Nok Gates 3-2. De Morgan's First Theorem 3-3. Nanp Gates 3-4. De Morgan's Second Theorem 3.5. EXCLUSIVEOR Gates 3-6, The Controlled Inverter 3-7. EXCLUSIVENOR Gates CHAPTER 4. TTL CIRCUITS 48 4-1, Digital Integrated Circuits 4-2, 7400 Devices 4-3. TTL Characteristics 4-4. TTL Overview 45. AND ORINVERT Gates 4-6, Open-Collector Gates 4-7. Multiplexers CHAPTER 5. BOOLEAN ALGEBRA AND KARNAUGH MAPS 64 5-1. Boolean Relations ‘Sum-of-Products Method 5-3. Algebraic Simplification 5-4, Karnaugh Maps 5-5. Pairs. Quads. and Ovtels 5-6. Kamaugh Simplifications 5-7. Don’t-Care Conditions CHAPTER 6. ARITHMETIC-LOGIC UNITS 9 6-1. Binary Addition 6-2, Binary Subtraction 6-3, Half Adders 6-4, Full Adders 6-5, Binary Adders 6-6. Signed Binary Numbers 6-7, 2's Complement 6-8. 2°s-Complement Adler-Subtracter CHAPTER 7, FLIP-FLOPS 90 7-1. RS Latches 7-2. Level Clocking 7-3. D Latches 7-4. Edge-Triggered D Flip-Flops 7-5, Edge-Triggered JK Flip-Flops 7-6. JK Master-Slave Flip-Flop CHAPTER 8. REGISTERS AND COUNTERS 106 Buller Registers 8-2, Shift Registers Controlled Shift Registers 8-4. Ripple Counters Synchronous Counters 8-6, Ring Counters Other Counters 8-8, Three-State Registers Bus-Organized Computers CHAPTER 9. MEMORIES — 130 9-1. ROMs 9.2. PROMS and EPROMs 9-4. A Small TTL Memory Addresses 9.3. RAMs 9-5. Hexadecimal SAP (Simple-as Computers 140 CHAPTER 10. SAP-1 140 10-1, Architecture 10-2, Instruction Set 10-3. Programming SAP-1 10-4. Fetch Cycle 10-5. Execution Cycle 10:6. The SAP-1 Microprogram 10-7. ‘The SAP-1 Schematic Diagram 10-8. Microprogrammiing CHAPTER 11. SAP-2__ 173 1-1, Bidirectional Registers 11-2. 11-3, Memory-Reference Instructions Architecture 11-4, Register 11-5. Jump and Call Instructions 11-6. Logic Instructions 11-7 11-8. SAP-2 Summary Instructions Other InstructionsCHAPTER 12. SAP-3 195 12-1, Programming Model 12-2. MOV and MVL 12.3. Arithmetic Instructions 12-4. Increments, Decrements, and Rotates 12-5. Logic Instructions 12-6, Arithmetic and Logic Immediates 12-7. Jump Instructions 12-8. Extended-Register Instructions 12-9, Indirect Instructions 12-10. Stack Instructions Programming Popular Microprocessors 213 CHAPTER 13, INTRODUCTION TO MICROPROCESSORS | 213 13-1. Computer Hardware Definition of a Microprocessor Some Common Uses for Microprocessors Microprocessors Featured in This Text [Access to Microprocessors CHAPTER 14. PROGRAMMING AND LANGUAGES 216 14-1. Relationship between Electronics and Programming. 14-2. Programming 14-3, Fundamental Premise M4. Floweharts 14-5. Programming Languages 14.6, Assembly Language 14-7. Worksheets CHAPTER 15. SYSTEM OVERVIEW 224 New Concepts 15-1. Computer Architecture 15-2. Microprocessor Architecture Microprocessor Families S02 Family 15-4. 6800/6808 Family 15-5, 8080/8085/280 Family 15-6. 8086/8088 Family CHAPTER 16, DATA TRANSFER INSTRUCTIONS 240 New Concepts 16-1, CPU Control Instructions 16-2. Data Transfer Instructions Specific Microprocessor Families 16-3. 6502 Family 16-4. 6800/6808 Family 16-5. 8080/8085/280 Family 16-6. 8086/8088 Family CHAPTER 17. ADDRESSING MODES—I 263 New Concepts 17-1. What Is an Addressing Mode? 17-2. The Paging Concept 17-3. Basic Addressing Modes Specific Microprocessor Families 17-4. 6502 Family 17-5, 6800/6808 Family 17-6, 8080/8085/280 Family 8086:8088 Family iv Contents CHAPTER 18. ARITHMETIC AND FLAGS. 270 New Concepts 18-1. Microprocessors and Numbers 18.2. Arithmetic Instructions 18-3, Flag Instructions Specific Microprocessor Families 18.4 6502 Family 18-5. 6800/6808 Family 18-6. SO80:8085/Z80 Family 18-7. 8086/8088 Family CHAPTER 19. LO 305 New Concepts 19-1. The Anb Instruction 19.2. The ok Instruction 19.3. The EXCLUSIVE-OR (EOR, NOR) Instruction 19-4. ‘The Nor Instruction 19-5. The NEG (NEGate) Instruction Specific Microprocessor Families 19-6. 6502 Family 19-7. 6800/6808 Family 19-8. 8080:8085/Z80 Family 19.9, 8086/8088 Family ‘AL INSTRUCTIONS, CHAPTER 20. SHI INSTRUCTIONS 319 New Concepts 20-1. Rotating 20-3. An Example Specific Microprocessor Families 20-4. 6502 Family 20-5, 6800/6808 Family 20-6, 8080/8085/Z80 Family 20-7, 8086i8088 Family AND ROTATE 20-2. Shifting CHAPTER 21. ADDRESSING MODES—II 329 New Concepts 21-1, Advanced Addressing Modes Specific Microprocessor Far 6502 Family 3, 6800/6808 Family 21-4, 8080/8085/Z80 Family 1-5. 8086/8088 Family CHAPTER 22. BRANCHING AND LOOPS 342 New Concepts 22-1, Unconditional Jumps 22-2. Conditional Branching 22-3. Compare and Test Instructions 22-4, Increment and Decrement Instructions 22-5, Nested Loops Specific Microprocessor Families 22-6. 6502 Family 22-7. 68006808 Family 22-8, 8080/8085/Z80 Family 22-9, $086:8088 Family CHAPTER 23. SUBROUTINE AND STACK, INSTRUCTIONS | 363 New Concepts 23-1. Stack and Stack Pointer 23-2. Branching versus Subroutines 23.3, How Do Subroutines Return? 23-4. Pushing and Popping Registers Specific Microprocessor Families 23-. 6502 Family 23-6, 6800/6808 Family 23-7. 8080/8085/Z80 Family 24-8, 8086/8088 FamilyMicroprocessor Instruction Set Tables 379 A, Expanded Table of 8085/8080 and 780 (8080 Subset) Instructions Listed by Category 381 Mini Table of 8085/8080 and 280 (8080 Subset) Instructions Listed by Category 410 Condensed Table of 8085/8080 and Z80 (8080) Instructions Listed by Category 415 Condensed Table of 8085/8080 and Z80 (8080 Subset) Instructions Listed by Op Code 417 Condensed Table of 8085/8080 and 280 (8080 Subset) Instructions Listed Alphabetically by 8085/8080 Mnemonic 419 Condensed Table of 8085/8080 and Z80 (8080 Subset) Instructions Listed Alphabetically by Z80 Mnemonic 421 B. Expanded Table of 6800 Instructions Listed by Category 22 Short Table of 6800 Instructions Listed Alphabetically 434 Short Table of 6800 Instructions Listed by Category 437 Condensed Table of 6800 Instructions Listed by Category 441 Condensed Table of 6800 Instructions Listed Alphabetically 443 Condensed Table of 6800 Instructions Listed by Op Code 44a ic Expanded Table of 8086/8088 Instructions Listed by Category 445 Condensed Table of 8086/8088 Instructions Listed by Category 465 Condensed Table of 8086/8088 Instructions Listed Alphabetically 469 D. Expanded Table of 6502 Instructions Listed by Category 471 Short Table of 6502 Instructions Listed by Category 478. Condensed Table of 6502 Instructions Listed by Category 480 Condensed Table of 6502 Instructions Listed Alphabetically 481 Condensed Table of 6502 Instructions Listed by Op Code 482 APPENDIXES | 485, 1, The Analog Interface 2, Binary-Hexadecimal- Decimal Equivalents 3, 7400 Series TTL. 4. Pinouts and Function Tables 5. SAP-I Parts List 6. 8085 Instructions 7, Memory Locations: Powers of 2 8. Memory Locations: 16K and 8K Intervals 9. Memory Locations: 4K Intervals 10, Memory Locations: 2K Intervals 11, Memory Locations: 1K Intervals 12. Programming Models ANSWERS TO ODD-NUMBERED PROBLEMS. 513 INDEX 519 ContentsPreface Textbooks on microprocessors are sometimes hard £0 un= derstand. This text attempts to present the various aspects ‘of microprocessors in ways that are understandable and interesting. The only prerequisite 0 using this textbook is an understanding of diodes and transistors A unique aspect of this text is its wide range. Whether you are interested in the student-constructed SAP (simple: as:possible) microprocessor, the 6502, the 6800/6808, the '8080/8085/Z80, or the 8086/8088, this textbook can meet your needs ‘The text is divided into four parts. These parts can be used in different ways to meet the needs of a wide Variety of students, classrooms, and instructors. Part 1, Digital Principles, is composed of Chapters | to 9. Featured topics include number systems, gates, boolean algebra, flip-lops, registers, counters, and memory. This information prepares the student for the microprocessor sections which follow art 2, which consists of Chapters 10 to 12, presents the SAP (simple-as-possible) microprocessor. The student con- structs this processor using digital components. The SAP processor contains the most common microprocessor func: tions. It features an instruction set which is a subset of that ‘of the Intel 8085—leading naturally to a study of that microprocessor. Part 3, Programming Popular Microprocessors (Chapters 13 to 23), simultaneously treats the MOS/Rockwell 6502, the Motorola 6800/6808, the Intel 8080/8085 and Zilog £280, and the 16-bit Intel 8086/8088. Fach chapter is divided into two sections, The first section presents new concepts; second section applies the new concepts (0 each micropro- cessor family. Discussion, programming examples, and problems are provided. The potential for comparative study is excellent. This part ofthe text takes a strong programming approach to the study of microprocessors. Study is centered around the mieroprocessor's instruction set and programming mode! The 8-bit examples and homework problems can be per- formed by using either hand assembly or cross-assemblers. The 16-bit 8086/8088 examples and problems can be per- formed by using either an assembler or the DOS DEBUG. utility Part 4 is devoted to the presentation of the instruction sets of each microprocessor family in table form. Several tables are provided for each microprocessor family, per- rmitting instructions to be looked up alphabetically, by op code, or by functional category, with varying levels of detail. The same functional categories are correspondingly used in the chapters in Part 3. This coordination between parts makes the learning process easier and more enjoyable. Additional reference lables are provided in the appen- dlixes. Answers 10 odd-numbered problems for Chapters | 10 16 follow the appendixes. A correlated laboratory manual, Experiments for Digital Computer Electronics by Michael A. Miller, is available for use with this textbook. It contains experiments for every part of the text. It also includes programming problems for ich of the Featured microprocessors, ‘A teacher's manual is available which contains answers ‘0 all of the problems and programs for every micropro: cessor, In addition, a diskette (MS-DOS 360K 54-inch diskette) containing cross-assemblers is included in the teacher's manual Special thanks to Brian Mackin for being such a patient and supportive editor. To Olive Collen for her editorial work, To Michael Miller for his work on the laby manual And to Thomas Anderson of Speech ‘Technologies Inc. for the use of his cross-assemblers. Thanks also (© reviewers Lawrence Fryda, Illinois State University: Malachi Me- Ginnis, ITT Technical Institute, Garland Texas; and Ben- jamin Suntag. Albert Paul Malvino Jerald A, Brown A man of irue science uses but few hard words, ‘and those only when none other will answer his purpose; whereas the smatterer in science thinks that by mouthing hard words he understands hard things, Herman MelvillePea DIGITAL PRINCIPLES =D- 1 p> NUMBER SYSTEMS AND CODES Modern computers don’t work with decimal numbers Instead, they process binary numbers, groups of Os and Is. Why binary numbers? Because electronic de reliable when designed for two-state (binary) operation. This chapter discusses binary numbers and other concepts needed to understand computer operation ices are most 1-1 DECIMAL ODOMETER René Descartes (1596-1650) said that the way to learn a new subject is to go from the known to the unknown, from the simple to the complex. Let's ty it ‘The Known Everyone has seen an odometer (miles indicator) in action ‘When a car is new, its odometer stars with ‘00000 After 1 mile the reading becomes 0001 Successive miles produce 00002, ‘00009 (00003, and so on, up to AA familiar thing happens at the end of the tenth mile When the units wheel turns from 9 back fo 0, a tab on this wheel forces the tens wheel to advance by I. This is why the numbers change to 0010 Reset-and-Carry ‘The units wheel has reset to O and sent a carry to the tens wheel, Let's call this fumiliar action reset-and-carry The other wheels also reset and carry. After 999 miles the odometer shows 00999 What does the next mile do? The units wheel resets and carvies, the tens wheel resets and carries, the hundreds whee! resets and carries, and the thousands wheel advances by 1, to get 01000 Digits and Strings ‘The numbers on each odometer wheel are called digits The decimal number system uses ten digits, 0 through 9. In a decimal odometer, each time the units wheel runs out of digits, it resets to 0 and sends a carry to the tens wheel When the tens wheel runs out of digits, it resets to 0 and sends a carry to the hundreds wheel. And so on with the remaining wheels, One more point. A siring is a group of characters (either letters o digits) written one after another. For instan 74 is a string of 7, 3, and 4. Similarly, 2CBA is a string of 2, C, 8, and A 1-2 BINARY ODOMETER Binary means two. The binary number system uses only two digits, 0 and 1. All other digits (2 through 9) are thrown away, In other words, binary numbers are strings of Os and Is, ‘An Unusual Odometer Visualize an odometer whose wheels have only two digits, and I. When each whee! turns, it displays 0, then 1, then 1back to 0, and the cycle repeats. Because each wheel has only two digits, we call this device a binary odometer In a car a binary odometer starts with (0000. (zero) After 1 mile, it indicates 0001 (one) The next mile forces the units wheel to reset and carry; so the numbers change to 0010 (two) ‘The third mile results in oo1t (three) What happens after 4 miles? The units wheel resets and carries, the second wheel resets and carries, and the third wheel advances by 1. This gives 0100. four) Successive miles produce o1ol (five) O10 (six) OIL (seven) After 8 miles, the units wheel resets and caries, the second wheel resets and carries, the third wheel resets and carries, and the fourth wheel advances by 1, The result is 1000 (eight) The ninth mile gives 1001 (niney and the tenth mile produces 1010 (ten) (Try working out a few more readings on your own.) You should have the idea by now. Each mile advances the units wheel by 1, Whenever the units wheel runs out of digits, it resets and carries. Whenever the second wheel runs out of digits, i resets and carries. And so for the other wheels. Binary Numbers A binary odometer displays binary numbers, strings of Os and Is. The number 0001 stands for {, O00 for 2, 0011 2 Digital Computer Etectronics for 3, and so forth. Binary numbers are long when large amounts are involved. For instance, 101010 represents decimal 42, As another example, 111100001111 stands for decimal 3,855, ‘Computer circuits are like binary odometers: they count and work with binary numbers. Therefore, you have 0 learn to count with binary numbers, to convert them to decimal numbers, and to do binary arithmetic. Then you will be ready to understand how computers operate ‘A final point. When # decimal odometer shows 0036, we can drop the leading Os and read the number as 36. Similarly, when a binary odometer indicates OO11, we can drop the leading 0s and read the number as 11. With the leading Os omitted, the binary numbers are 0, 1, 10, 11, 100, 101, and so on, To avoid confusion with decimal numbers, read the binary numbers like this: zero, one, one- zero, one-one, one-Zer-7eF0, One-Z2F0-0Ne, ele 1-3 NUMBER CODES People used to count with pebbles. The numbers 1, 2, 3 looked like @, @@, @@@. Larger numbers were worse: seven appeared «5 @@@O@OO. Codes From the earliest times, people have been creating codes that allow us to think, calculate, and communicate. The decimal numbers are an example of a code (See Table IL-1. Ie's an old idea now, but at the time it revolutionary; 1 stands for @, 2 for @@, 3 for and so forth Table 1-1 also shows the binary code. | stands for @, 10 for @@, 11 for @@®, and soon. A binary number and a decimal number are equivalent if each represents the same amount of pebbles. Binary 10 and decimal 2 are equivalent because each represents @@. Binary 101 and decimal 5 are equivalent because each stands for TABLE 1-1, NUMBER CODES Decimal Pebbles Binary 0 None 0 1 1 2 10 3 u 4 100 5 lol 6 10 1 ML 8 1000 9 1001Equivalence is the common ground between us and computers; it tells us when we're talking about the same thing. If a computer comes up with a binary answer of 101, ‘equivalence means that the decimal answer is 5. As a start to understanding computers, memorize the binary-decimal equivalences of Table 1-1 EXAMPLE 1-1 Figure I-la shows four light-emitting diodes (LEDs). A. dark circle means that the LED is off; alight circle means it’s on. To read the display, use this code: @@00 @0e@o fo 1 Fig. 1 LED display of binary numbers, LED _ Binary om 0 On 1 What binary number does Fig. I-1a indicate? Fig. 1-16? SOLUTION Figure I-La shows off-off-on-on, This stands for binary O11, equivalent to decimal 3 Figure 1-1b is off-on-off-on, decoded as binary 0101 and. equivalent to decimal 5. EXAMPLE 1-2 A binary odometer has four wheels. What are the successive binary numbers? SOLUTION As previously discussed, the first cight binary numbers are (0000, 0001, 0010, 0011, 0100, 0101, 0110, and OLII. On the next count, the three wheels on the right reset and carry; the fourth wheel advances by one. So the next eight numbers are 1000, 1001, 1010, 1011, 1100, 1101, 1110, and 1111 ‘The final reading of 1111 is equivalent to decimal 15. The next mile resets all wheels to 0, and the cycle repeats Being able to count in binary from 0000 10 ILL is essential for understanding the operation of computers 2. BINARY-TO-DECIMAL EQUIVALENCES Decimal inary 8 1000 9 1001 10 lol un ton 2 1100 B Ho 4 1110 15 fry ‘Therefore, you should memorize the equivalences of Table 12 1.4 WHY BINARY NUMBERS ARE USED ‘The word “computer” is misleading because it suggests a machine that can solve only numerical problems. But a computer is more than an automatic adding machine. It can play games, translate languages, draw pictures, and so on. To suggest this broad range of application, a computer is often referred to as a data processor, Program and Data Data means names, numbers, facts, anything needed 10 work out a problem. Data goes into a computer, where it is processed or manipulated to get new information, Before it goes into a computer, however, the data must be coded in binary form. The reason was given earlier: a computer’s cireuits can respond only to binary numbers. Besides the data, someone has to work out a program, 4 list of instructions telling the computer what to do, These instructions spell out each and every step in the data processing. Like the data, the program must be coded in binary form before it goes into the computer. So the two things we must input to a computer are the program and the data. These are stored inside the computer before the processing begins. Once the computer run starts, each instruction is executed and the data is processed, Hardware and Software The electronic, magnetic, and mechanical devices of a computer are known as hardware. Programs are called software. Without software, a computer is a pile of dumb" metal Chapter 1 Number Systems and Codes 3‘An analogy may help. A phonograph is like hardware ‘and records ate like software. The phonograph is useless Without records. Furthermore, the music you get depends ‘on the record you play. A similar idea applies to computers. A computer is the hardware and programs ate the software. ‘The computer is useless without programs. The program stored in the computer determines what the computer will do; change the program and the computer processes the data in a different way. ‘Transistors Computers use integrated circuits (ICs) with thousands of transistors, either bipolar or MOS. The parameters (B,., Teo. 816.) an vary more than 50 percent with temperature change and from one transistor to the next. Yet these computer ICs work remarkably well despite the transistor variations. How is it possible? ‘The answer is nvo-state design, using only two points ‘on the load line of each transistor. For instance, the common two-state design is the cutoff-saturation approach; each transistor is forced to operate at either cutofT or saturation, When a transistors cut off or saturated, parameter variations have almost no effect. Because of this, it’s possible to design reliable two-state circuits that are almost independent of temperature change and transistor variations. ‘Transistor Register Here's an example of two-state design, Figure 1-2 shows a transistor register. (A register is a string of devices that store data.) The transistors on the left are cut off because the input base voltages are 0 V. The dark shading symbolizes the cutoff condition, The two transistors on the right have base drives of $ V. ‘The transistors operate at either saturation or cutoff. A base voltage of OV forces each transistor to cut off, while a base voltage of 5 V drives it into saturation, Because of this two-state action, each transistor stays in a given state until the base voltage switches it to the opposite stat. ov Fig. 1.2 Transistor register Digital Computer Electronics Another Code ‘Two-state operation is universal in digital electronics. By deliberate design, all input and output voltages are cither low or high. Here’s how binary numbers come in: low voltage represents binary 0, and high voltage stands for binary 1. In other words, we use this code: Voltage Low 0 High L For instance, the base voltages of Fig. 1-2 are low-low= high-high, or binary O11. The collector voltages are high- high-low-low, orbinary 1100. By changing the base voltages we can store any binary number from 0000 t0 1111 (decimal 010 15), Bit Bit is an abbreviation for binary digit, A binary number Tike 1100 has 4 bits; 110011 has 6 bits; and 11001100 has 8 bits. Figure 1-2 is @ 4-bit register, To store larger binary ‘numbers, itneeds more transistors. Add two transistors and you get a 6-bit register. With four more transistors, you'd hhave an 8-bit register. Nonsaturated Circuits Don’t get the idea that all two-state circuits switch between cutoff and saturation. When a bipolar transistor is heavily saturated, extra carriers are stored in the base region. If the base voltage suddenly switches from high to low, the transistor cannot come out of saturation until these extra carriers have a chance (0 leave the base region. The time it takes for these carriers to leave is called the saturation delay time 1,. Typically, 1, is in nanoseconds. In most applications the saturation delay time is too short {o matter. But some applications require the fastest possible av rKs tka ov ov Apr) (approx)‘switching time. To get this maximum speed, designers have come up with circuits that switch from cutoff (or near cutoff) to a higher point on the load line (but shor of saturation). These nonsaturated circuits rely on clamping diodes or heavy negative feedback (© overcome transistor variations, Remember this: whether saturated or nonsaturated circuits are used, the transistors switch between distinct points on the load line. This means that all input and output voltages are easily recognized as low or high, binary 0 or binary 1 THOS S959 Fig. 1-3 Core register Magnetic Cores Early digital computers used magnetic cores to store data. Figure 1-3a shows a 4-bit core register. With the right- hand rule, you can see that conventional current into a wire produces a clockwise flux; reversing the current gives a counterclockwise flux. (The same result is obtained if electron-flow is assumed and the left-hand rule is used.) ‘The cores have rectangular hysteresis loops: this means that flux remains ina core even though the magnetizing current is removed (see Fig. 1-36). This is why a core register can store binary data indefinitely. For instance, let's use the following code: Flux Binary Counterclockwise o Clockwise 1 Then, the core register of Fig. 1-36 stores binary 1001, equivalent to decimal 9. By changing the magnetizing currents in Fig. 1-3a we can change the stored data To store larger binary numbers, add more cores. Two cores added to Fig. 1-34 result in a 6-bit register; four more cores give an 8-bit register. The memory is one of the main parts of a computer. Some memories contain thousands of core registers, These registers store the program and data needed to run the computer Other Two-State Examples The simplest example of a two-state device is the on-off ‘switch. When this switch is closed, it represents binary 1: ‘when it's open, it stands for binary 0. Punched cards are another example of the two-state concept. A hole in a card stands for binary 1, the absence of a hole for binary 0. Using a prearranged code, a card- punch machine with a keyboard can produce a stack of cards containing the program and data needed to run a computer, Magnetic tape can also store binary numbers. Tape recorders magnetize some points on the tape (binary 1), while leaving other points unmagnetized (binary 0). By a prearranged code, a sow of points represents either a coded instruction or data. In this way, a reel of tape can store ‘thousands of binary instructions and data for later use in a computer, Even the lights on the control panel of a large computer are binary; a light that's on stands for binary 1, and one that’s off stands for binary 0. In a 16-bit computer, for instance, a row of 16 lights allows the operator to see the binary contents in different computer registers. The operator ‘can then monitor the overall operation and, when necessary, troubleshoot In summary, switches, transistors, cores, cards, tape, lights, and almost all other devices used with computers are based on two-state operation, This is why we are forced to use binary numbers when analyzing computer action, EXAMPLE 1-3 Figure 1-4 shows a strip of magnetic tape. The black circles are magnetized points and the white circles unmagnetized points. What binary number does each horizontal row represent? Fig. 1-4 Binary numbers on magnetic tape. SOLUTION ‘The tape stores these binary numbers: Row 1 00001111 Row 5 11100110 Row2 10000110 | Row 6 — o1001001 Row3 10110111 | Row 7 — 11001101 Row 4 00110001 Chapter 1 Number Systems and Codes 5(Note: these binary numbers may represent either coded instructions or data.) A string of 8 bits is called a byte. In this example, the magnetic tape stores 7 bytes. The first byte (row 1) is (00001111. The second byte (row 2) is 10000110. The third byte is 1110111. And so on, ‘A byte is the basic unit of data in computers. Mast process data in strings of 8 bits or some multiple 32, and so on). Likewise, the memory stores data in strings of 8 bits or some multiple of 8 bits 1-5 BINARY-TO-DECIMAL CONVERSION ‘You already know how to count to 15 using binary numbers, ‘The next thing to lear is how to convert larger binary ‘numbers to their decimal equivalents Fig. 1-5 (a) Decimal weights; (b) binary weights Decimal Weights ‘The decimal number system is an example of positional notation; each digit position has a weight or value. With decimal numbers the weights are units, tens, hundreds, thousands, and so on. The sum of all digits multiplied by their weights gives the total amount being. represented. For instance, Fig. 1-Sa illustrates a decimal odometer. Below each digit is its weight. The digit on the right has a ‘weight of 10° (units), the second digit has a weight of 10! Gens), the third digit a weight of 10° (hundreds), and so forth. The sum of all units multiplied by their weights is GS & 10) + 7 x 10) + © x 10) +B x 10) + (4 10%) = 50,000 + 7000 +0 + 30-44 57,034 Binary Weights, Positional notation i als used with binary numbers because each dist postion has a weight, Since only two digits are used, the weights are powers of? insead of 10. As shown in the binary odometer of Fig. 1-5b, these weights are 2° (nits), 2" (0s), 2° fours), 2 (eights), and 2" sinteens) IFlonger binary numbers ate involved, the weights continue in acending powers of 2 The decimal equivalent of «binary number equals the sum of all binary digits multiplied by their weights. For instance, the binary reading of Fig. 1-Sb has a decimal equivalent of 6 Digital Computer Electronics (X29 +x 2 + Ox 2) + OX 2) + (XM) = 1 +8 FOF 041 = 25 Binary 11001 is therefore equivalent o decimal 25 AS another example, the byte 11001100 converts to decimal as follows x2 + 0K H+ Ox 2+ Ox 2 +x DHX 24 Ox 2) 4.0% 2, = 1+ 64+ 0404844 404+0= 204 So, binary 11001100 is equivalent to decimal 204. Fast and Easy Conversion Here's a streamlined way to convert a binary number to its decimal equivalent 1. Write the binary number. Write the weights 1, 2, 4, 8, digits. 3. Cross out any weight under a 0. 4. Add the remaining weights «under the binary For instance, binary 1101 converts to decimal as follows: (Write binary number) I I 8421 (Write weights) 84 oO 1 (Cross out weights) 844404 1= 13 (Add weights) You can compress the steps even further: feat (step 1) 8 4 2 1513 Greps2to4) As another example, here's the conversion of binary 1110101 in compressed form: 11 1otod 64 32 16 #4 2 117 Base or Radix ‘The buse or radix of a number system equals the number of digits it has. Decimal numbers have a base of 10 because digits 0 through 9 are used. Binary numbers have a base of 2 because only the digits 0 and 1 are used. (In terms of an oxlometer, the base or radix is the number of digits on ceach wheel.) AA subscript attached t0 a number indicates the base of the number. 100; means binary 100, On the other hand, 1009 stands for decimal 100. Subscripts help clarify equa- tions where binary and decimal numbers are mixed. For instance, the last two examples of binary-to-decimal con- version can be written like this:L101; = 13 110101; = 1175 In this book we will use subscripts when necessary for clarity 1-6 MICROPROCESSORS What is inside « computer? What is a microprocessor? What is a microcomputer? Computer ‘The five main sections of a computer are input, memory, arithmetic and logic, control, and output. Here is a brief description of each, Input ‘This consists of all the circuits needed to get programs and data into the computer. In some computers the input seetion includes a typewriter keyboard that converts letters and numbers into strings of binary data Memory This stores the program and data before the computer run begins. It also can store partial solutions luting @ computer run, similar to the way we use a scratchpad while working out a problem, Control This is the computer's center of gravity, analo- Rous to the conscious part of the mind, The control section directs the operation ofall other sections. Like the conductor of an orchestra, it tells the other sections what to do and when to do it. Arithmetic and logic This is the number-erunching se tion of the machine. It can also make logical decisions With control telling it what to do and with memory feeding it data, the arithmetic-logic unit (ALU) grinds out answers to number and logic problems. Output This passes answers and other processed data to the outside world. The output section usually includes a Video display to allow the user to see the processed data Microprocessor The control section and the ALU are often combined physically into a single unit called the central processing unit (CPU). Furthermore, it’s convenient to combine the input and output sections into a single unit called the inpu- owiput (VO) unit. In earlier computers, the CPU, memory, and UO unit filled an entire room With the advent of integrated cireuits, the CPU, memory, and /O unit have shrunk dramatically. Nowadays the CPU can be fabricated on a single semiconductor chip called a ‘microprocessor. Inother words, a microprocessor is nothing ‘more than a CPU on a chip. Likewise, the VO circuits and memory can be fabricated ‘on chips. In this way, the computer circuits that once filled room now fit on a few chips Microcomputer As the name implies, a microcomputer is a small computer. More specifically, a microcomputer is a computer that uses 4 microprocessor for its CPU. The typical microcomputer has three kinds of chips: microprocessor (usually one chip), ‘memoty (several chips), and MO (one or more chips) If a small memory is acceptable, a manufacturer can fabricate all computer circuits on a single chip. For instance, the 8048 from Intel Corporation is aone-chip microcomputer with an 8-bit CPU, 1,088 bytes of memory, and 27 10 Fines, Powers of 2 Microprocessor design started with 4-bit devices, then evolved to 8 and 16-bit devices. In our later discussions ‘of microprocessors, powers of 2 keep coming up because of the binary nature of computers. For this reason, you should study Table 1-3. It lists the powers of 2 encountered in microcomputer analysis. As shown, the abbreviation K stands for 1,024 (approximately 1,000). Therefore, 1K means 1,024, 2K stands for 2,048, 4K for 4,096, and so. ‘Most personal microcomputers have 640K (or greater) memories that can store 655,360 bytes (or more), TABLE 1-3, POWERS OF 2 Powers of 2_Decimal equivalent Abbreviation 2 1 2 2 2 4 2 8 2 16 P 32 2 64 2 8 z 256 » 512 200 1,024 1k 2 2,048 2K 2" 4,096 4K 2» 8,192 8K 2 16,384 16K. 215 32,768 32K 216 65,536 64K The abbreviations 1K, 2K, and so on, became established before K- for filo- was in common use. Retaining the capital K serves as a useful reminder that K only approximates 1,000. Chapter 1 Number Systems and Codes 71-7 DECIMAL-TO-BINARY CONVERSION Next, you need to know how fo convert from decimal 10 binary. After you know how it’s done, you will be able 10 understand how circuits can be built to convert decimal numbers into binary numbers. Double-Dabble Double-dabble is a way of converting any decimal number to its binary equivalent. It requires successive division by 2, waiting down each quotient and its remainder. The remainders are the binary equivalent of the decimal number. ‘The only way to understand the method is to go through an example, step by step. Here is how to convert decimal 13 10 its binary equivalent. Step 1. Divide 13 by 2, writing your work like this 6 1 (first remainder) 208 ‘The quotient is 6 with a remainder of 1 Step 2. Divide 6 by 2 to get 3. 0 (second remainder) 276 1 2013 This division gives 3 with a remainder of 0. Step 3. Again you divide by 2 11> (third remainder) 273 0 276 1 2y3 Here you get a quotient of 1 and a remainder of 1 Step 4, One more division by 2 gives Read down ot oie PAE 261 208 8 Digital Computer Electronics In this final division, 2 does not divide into 1; therefore, the quotient is O with a remainder of 1 ‘Whenever you arrive at a quotient of O with a remainder of 1, the conversion is finished. The remainders when read downward give the binary equivalent. In this example, binary 1101 is equivalent to decimal 13, Double-dabble works with any decimal number. Pro- gressively divide by 2, writing each quotient and its remainder. When you reach a quotient of O and a remainder of 1, you are finished; the remainders read downward are the binary equivalent of the decimal number. Streamlined Double-Dabble There’s no need to keep writing down 2 before each division because you're always dividing by 2. From now on, here’s how to show the conversion of decimal 13 to its binary equivalent: 4 Wu 30 Joa 2y8 EXAMPLE 1-4 Convert decimal 23 10 binary. SOLUTION ‘The first step in the conversion looks like this: ie cores Afterall divisions, the finished work looks Tike this or vio a sa mt 278 This says that binary 10111 is equivalent to decimal 23.1-8 HEXADECIMAL NUMBERS Hexadecimal numbers are extensively used in micropro- cessor work. To bein with, they are much shorter than binary numbers. This makes them easy to write and remember. Furthermore, you can mentally convert them to binary form whenever necessary ‘An Unusual Odometer Hexadecimal means 16. The hexadecimal number system has a base or radix of 16. This means that it uses 16 digits to represent all numbers. The digits are 0 through 9, and A through F as follows: 0, 1, 2, 3, 4, 5, 6, 7, 8,9, A, B, C, DE, and F. Hexadecimal numbers are strings of these digits like 845, 4CF7, and ECS8. ‘An easy way to understand hexadecimal numbers is to visualize a hexadecimal odometer. Each wheel has 16 digits oon its circumference. As it turns, it displays 0 through 9 as before. But then, instead of resetting, it goes on to display A, B,C, D, E, and F. The idea of reset and carry applies to a hexadecimal cxlometer. When 2 wheel turns from F back to 0, it forces the next higher wheel to advance by I. In other words, when a wheel runs out of hexadecimal digits, it resets and If used in a car, a hexadecimal odometer would count as follows. When the car is new, the odometer shows all 0s: 0000 (zero) ‘The next 9 miles produce readings of 0001 (one) 0002 (two) 0003 (three) 0004 (four) 0005 (five) 0006 (six) 0007 (seven) 0008 (eight) 0009 (nine) ‘The next 6 miles give 0004 (ten) 000B (eleven) 000C (twelve) 000D (thirteen) 000 (Fourteen) 000F (fifteen) At this point the least significant wheel has run out of digits. Therefore, the next mile forces a reset-and-carry 10 set 0010 (sixteen) The next 15 miles produce these readings: 0011, 0012, 0013, 0014, 0015, 0016, 0017. 0018, 0019, 001A, 0018, OIC, OOID, OOIE, and OO1F. Once again, the least significant wheel has run out of digits. So, the next mile results in a reset-and-carry: 0020 (thirty-two) Subsequent readings are 0021, 0022, 0023, 0024, 0025, (0026, 0027, 0028, 0029, 002A, 0028, 002C, 002D, 0026, and 002F, You should have the idea by now. Each mile advances the least significant wheel by 1, When this wheel runs out of hexadecimal digits, it resets and carries. And so on for the other wheels. For instance, if the odometer reading is 35F the next reading is 8360. As another example, given SFFF the next hexadecimal number is 6000, Equivalences Table 1-4 shows the equivalences between hexadecimal, binary, and decimal digits. Memorize this table. I's essential that you be able to convert instantly from one system to another. TABLE 1-4. EQUIVALENCES Hexadecimal Binary Decimal 0 0000 0 1 001 1 2 010 2 3 oon 3 4 0100 4 5 o1or 5 6 o110 6 1 oun 7 8 1000 8 9 1001 9 A 1010 10 B 1011 " g 1100 2 D nol B E 1110 “4 F mt Is Chapter 1 Number Systems and Codes 91-9 HEXADECIMAL-BINARY CONVERSIONS After you know the equivalences of Table 1-4, you can mentally convert any hexadecimal string (0 its binary equivalent and vice versa Hexadecimal to Binary To convert a hexadecimal number to a binary number, convert each hexadecimal digit to its 4-bit equivalent, using Table 1-4. For instance, here's how 9AF converts to binary’ 9 AF too lor 1010 111 As another example, CSE2 converts like this: c os EE 2 4 4 + 1 1100 0101 1110 0010 Incidentally, for easy reading it's common practice to leave ‘space between the 4-bit strings. For example, instead of writing (CSE2,, = 1100010111100010; we can write C5E2 = 1100 0101 1110 0010; Binary to Hexadecimal To convert in the opposite direction, from binary 10 hexadecimal, you again use Table 1-4, Here are two examples. The byte 1000 1100 converis as follows: 1000 1100 tod 8 oC The 16-bit number 1110 1000 1101 0110 converts like this: 1110 1000 1101 oL10 t t + 1 E & D 6 In both these conversions, we start with a binary number ‘and wind up with the equivalent hexadecimal number, 10 digital Computer Electronics EXAMPLE 1-5 Solve the following equation for x: ay = MME LT 1111 SOLUTION This is the same as asking for the hexadecimal equivalent of binary 1111 1111 1111 L111. Since hexadecimal F is equivalent to 1111, x = FFF. Therefore, FFFF,, = WIL 111 111 1111; EXAMPLE 1-6 ‘As mentioned earlier, the memory contains thousands of registers (core or semiconductor) that store the program and. data needed for a computer run. These memory registers are known as memory locations. A typical microcomputer may have up to 65,536 memory locations, each storing 1 byte ‘Suppose the first 16 memory locations contain these bytes: 011 1100 1100 1101 101 O11 0010 1000 1111 0001 0010 1010 1101 0100 (0100 0000 our oi 1100 0011 1000 0100 0010 1000 0010 0001 011 1010 O11 1110 oor 1111 Convert these bytes to their hexadecimal equivalents. SOLUTION Here are the stored bytes and their hexadecimal equivalents: Memory Contents Hex Equivalents 011 1100 3c 1100 1101 cD 101 O11 37 010 1000 28 1111 0001 FI0010 1010 2a 1101 0100 Ds (0100 0000 40 omni on n 1100 0011 G. 1000 0100 84 0010 1000 8 0010 0001 21 oot! 1010 3A oon 1110, 3E 001 1111 IF ‘What's the point of this example? When talking about the contents of a computer memory, we can use either binary numbers or hexadecimal numbers. For instance, we ccan say that the first memory location contains O011 1100, ‘or we can say that it contains 3C. Either string gives the same information, But notice how much easier itis to say. write, and think 3C than it is to say, write, and think O11 1100. In other words, hexadecimal strings are much easier for people to work with, This is why everybody working ‘with microprocessors uses hexadecimal notation to represent panicular bytes. ‘What we have just done is known as chunking, replacing longer strings of data with shorter ones. AC the first memory location we chunk the digits 0011 1100 into 3C. At the second memory location we chunk the digits 1100 1101 into CD, and so on. EXAMPLE 1-7 ‘The typical microcomputer has a typewriter keyboard that allows you to enter programs and data; a video screen displays answers and other information Suppose the video screen of a microcomputer displays the hexadecimal contents of the first eight memory locations AT 2B 3 19 SA 4D 2c FS What are the binary contents of the memory locations? SOLUTION Convert from hexadecimal to binary to get 1o10 o111 0010 1000 1100 0011 (0001 1001 101 1010, 0100 1101 010 1100 1111 1000 ‘The first memory location stores the byte 1010 O111, the second memory location stores the byte 0010 1000, and so ‘This example emphasizes a widespread industrial prac- tice. Microcomputers are programmed to display chunked data, often hexadecimal, The user is expected to know hhexadecimal-binary conversions. In other words, acomputer ‘manufacturer assumes that you know that A7 represents 1010 OL11, 28 stands for 0010 1000, and so on, One more point. Notice that each memory location in this example stores I byte. This is typical of first-generation microcomputers because they use 8-bit microprocessors. 1-10 HEXADECIMAL-TO-DECIMAL CONVERSION You often need to convert a hexadecimal number to its decimal equivalent. This section discusses methods for doing it Hexadecimal to Binary to Decimal One way to convert from hexadecimal to decimal is the ‘two-step method of converting from hexadecimal to binary ‘and then from binary to decimal. For instance, here's how to convert hexadecimal 3C to its decimal equivalent. Step 1. Convert 3C to its binary equivalent 3 c 4 4 oon 1100 Step 2. Convert O11 1100 to its decimal equivalent: oo 1 11100 We of 22 16 8 4 2 160 ‘Therefore, decimal 60 is equivalent to hexadecimal 3C. As an equation, 3Cis = OOLT 1100; = 6040 Positional-Notation Method Positional notation is also used with hexadecimal numbers because each digit position has a weight. Since 16 digits are used, the weights are the powers of 16. As shown in Chapter 1 Number Systems and Codes 11Flele]s woe we we Fig. 1-6 Hexadecimal weights the hexadecimal odometer of Fig. 1-6, the weights are 16°, J6!, 16, and 16°. If longer hexadecimal numbers ane involved, the weights continue in ascending powers of 16. ‘The decimal equivalent of a hexadecimal string equals the sum of all hexadecimal digits multiplied by their weights, (dn processing hexadecimal digits A through F, use 10 through 15.) For instance, the hexadecimal reading of Fig, 1-6 has a decimal equivalent of (F x 16) + 8 x 16) + E x 16) + © x 16 15 x 169) + (8 x 16) + (14 x 161) + 6 x 16%) = 61,440 + 2,048 + 224 + 6 63,718, In other words, F8E6,, = 63,7180 000 [6 oo vot [eo coo [sr 003 [201 008 [Fr 005 [aa 0008 |“ oe 07 [so] 008 [77] toss 008 [es 00a [aa 008 [ae voc [~21 000 [aa coo [ae coor [TF FFF to oy ig. 1-7 (a) Fist 16 words in memory; (8) 64K memory Memory Locations and Addresses If a certain microcomputer has 64K memory, meaning {65,536 memory locations, each is able to store I byte. The \ifferent memory locations are identified by hexadecimal numbers called addresses. For instance, Fig. 1-4 shows the first 16 memory locations; their addresses are from 0000 to OO0F, The address of a memory location is different from its stored contents, just as a house address is different from 12 digital computer Etectronics the people living in the house. Figure 1-7a emphasizes the point. At address 0000 the stored contents are 3C (equivalent to 0011 1100). At address 0001 the stored contents are CD, at address 0002 the stored contents are 57, and so on, Figure 1-7 shows how to visualize a 64K memory. The first address is 0000, and the last is FFFF. Table of Binary-Hexadecimal-Decimal Equivalents A 64K memory has 65,536 hexadecimal addresses from (0000 to FFFF. The equivalent binary addresses are from (0000 0000 0000 0000 anata ua The first 8 bits are called the upper byte (UB); the second 8 bits are the ower byte (LB). If you have to do a lot of binary-hexadecimal-decimal conversions, use the table of equivalents in Appendix 2, which shows all the values for 64K memory, Appendix 2 has four headings: binary, hexadecimal, UB Gecimal, and LB decimal. Given a 16-bit address, you convert the upper byte to its decimal equivalent (UB decimal), the lower byte to its decimal equivalent (LB decimal), and then add the two decimal equivalents. For instance, suppose you want (0 convert 101 0111 1010 0010 to its decimal equivalent. The upper byte is 1101 O1N1, or hexadecimal D7; the lower byte is 1010 0010, or A2. Using Appendix 2, find D7 and its UB decimal equivalent DI 55,040 Next, find A2 and is LB decimal equivalent Ad 162 Add the UB and LB decimal equivalents to get 55,040 + 162 = 55,202 This is the decimal equivalent of hexadecimal D7A2 or binary 1101 0111 1010 0010. Once familiar with Appendix 2, you will find it enor ‘mously helpful. It is faster, more accurate, and less tring. than other methods, The only calculation required is adding the UB and LB decimal, easily done mentally, with pencil and paper, or if necessary, on a calculator. Furthermore, if You are interested in converting only the lower byte, no calculation is required, as shown in the next example,EXAMPLE 1-8 Convert hexadecimal 7E to its decimal equivalent. SOLUTION EXAMPLE 1-9 Convert decimal 141 to hexadecimal SOLUTION When converting only a single byte, all you are dealing with is the lower byte. With Appendix 2, look up 7E and its LB decimal equivalent to get TE 126 In other words, Appendix 2 can be used to convert single bytes to their decimal equivalents (LB decimal) or double bytes to their decimal equivalents (UB decimal + LB decimal), 1-11 DECIMAL-TO-HEXADECIMAL CONVERSION (One way to perform decimal-to-hexadecimal conversion is to go from decimal to binary then to hexadecimal. Another way is hex-dabble. The idea is to divide successively by 16, writing down the remainders. (Hex-dabble is like double~ dabble except that 16 is used for the divisor instead of 2.) Here's an example of how fo convert decimal 2,479 into hexadecimal form. The first division is 1841S F 16 2.475 ‘The next step is 9 1A yis@ 1s F 16 2,879 ‘The final step is Read down Ooo eee Vise 1s F 16 12,479 Notice how similar hex-dabble is to double-dabble. Also, remainders greater than 9 have to be changed to hexadecimal digits (10 becomes A, 15 becomes F, cte.). If you prefer, use Appendix 2 to look up the decimal- hexadecimal equivalents. The next two examples. show how. Whenever the decimal number is between 0 and 255, all you have to do is look up the decimal number and its inexadecimal equivalent. With Appendix 2, you can see at a glance that sD < 141 EXAMPLE 1-10 Convert decimal 36,020 to its hexadecimal equivalent SOLUTION If the decimal number is between 256 and 65,535, you need to proceed as follows. First, locate the largest UB decimal that is less than 36,020. In Appendix 2, the largest UB decimal is UB decimal 5,840 which has a hexadecimal equivalent of 8C = 35,840 This is the upper byte. Next, subtract the UB decimal from the original decimal number: 36,020 — 35,840 = 180 ‘The difference 180 has a hexadecimal equivalent B4 — 180 This is the lower byte By combining the upper and lower bytes, we get the ‘complete answer: 8CB4. This is the hexadecimal equivalent of 36,020, After a litte practice, you will find Appendix 2 to be Cone of the fastest methods of decimal-hexadecimal conver- 1-12 BCD NUMBERS Annibble is a string of 4 bits. Binary-coded-decimal (BCD) numbers express each decimal digit as anibble, For instance, decimal 2,945 converts to a BCD number as follows: Chapter 1 Number Systems and Codes 132 9 4 5 oyu 4 0010 1001 0100 101 [As you see, each decimal digit is coded as 2 nibble. Here's another example: 9,863,, convert like this: 9 8 6 3 4 4 ood + 1001 1000 0110 0011 Therefore, 1001 1000 0110 0011 is the BCD equivalent of 9.863 ‘The reverse conversion is similar. For instance, 0010 1000 0111 0100 converts as follows: 0010 1000 01110100 4 L 1 4‘ 2 8 7 4 Applications BCD numbers are useful wherever decimal information is transferred into or out of a digital system. The circuits inside pocket calculators, for example, can process BCD ‘numbers because you enter decimal numbers through the keyboard and see decimal answers on the LED of liquid- crystal display. Other examples of BCD systems are elec- tronic counters, digital voltmeters, and digital clocks; their circuits can work with BCD numbers. BCD Computers BCD numbers have limited value in computers. A few carly computers processed BCD numbers but were slower and more complicated than binary computers. As previously ‘mentioned. 2 computer is more than a number cruncher because it must handle names and other nonnumeric data. In other words, a modern computer must be able 10 process alphanumerics (alphabet letters, numbers, and other sym- bols). This why modern computers have CPUs that process binary numbers rather than BCD numbers. Comparison of Number Systems Table 1-5 shows the Four number systems we have discussed, Each number system uses strings of digits to represent quantity. Above 9, equivalent strings appear different. For instance, decimal string 128, hexadecimal string 80, binary string 1000 0000, and BCD string 0001 0010 1000 are equivalent because they represent the same number of pebbles. Machines have to use Tong strings of binary or BCD ‘numbers. but people prefer to chunk the data in either decimal or hexadecimal form. As long as we know how to 14 Digital computer Electronics TABLE 1-5. NUMBER SYSTEMS Decimal Hexadecimal Binary BCD 0 0 (0000 0000 9000 0000 0000 1 1 (0000 00019000 0000 0001 2 2 (0000 0010 0000 0000 0010 3 3 (0000 0011 0000 0000 0011 4 4 (0000 0100 0000 0000 0100 5 5 (0000 0101 0000 0000 0101 6 6 (0000 0110 0000 0000 0110 7 7 (0000 0111 0000 0000 0111 8 8 (0000 1000 9000 0000 1000 9 9 (0000 1001 000 0000 1001 10 A (0000 1010 9000 0001 0000 n B 0000 1011 0000 0001 0001 2 c (9000 1100 0000 0001 0010 B D 0000 1101 0000 0001 0011 ry E (0000 1110 0000 0001 0100 Is F 0000 1111 0000 0001 0101 16 10 (0001 0000 0000 0001 0110 32 20 (0010 0000 0000 0011 0010 o 40 (0100 0000 0000 0110 0100 128 80 1000 90000001 0010 1000, 255 FF 1111 L111 0010 0101 o101 convert from one number system to the next, we can always. get back to the ultimate meaning, which is the number of pebbles being represented. 1-13 THE ASCII CODE To get information into and out of a computer, we need t0 use numbers, leters, and other symbols. This implies some kind of alphanumeric code for the UO unit of a computer. At one time, every manufacturer had a different code, Which led to all kinds of confusion. Eventually, industry settled on an input-output code known as the American Standard Code for Information Imerchange (abbreviated ASCII). This code allows manufacturers to standardize VO hardware such as keyboards, printers, video displays, and so on. ‘The ASCII (pronounced ask'-ee) code is @ T-bit code whose format (arrangement) is XX XXKXsXy where each X is a 0 or a 1. For instance, the letter A is coded as 1000001 Sometimes, a space is inserted for easier reading: 100 0001‘TABLE 1-6, THE ASCII CODE 100 101110 Att N¥x2| 2 |} GATES For centuries mathematicians felt there was a connection between mathematics and logic, but no one before George Boole could find this missing link. In 1854 he invented symbolic logic, known today as boolean algebra. Each variable in boolean algebra has either of two values: true or false. The original purpose of this two-state algebra was to solve logic problems. Boolean algebra had no practical application until 1938, ‘when Claude Shannon used itto analyze telephone switching. circuits. He Tet the variables represent closed and open relays. In other words, Shannon came up with a new application for boolean algebra. Because of Shannon's work, engineers realized that boolean algebra could be applied to computer electronics. ‘This chapter introduces the gate, a circuit with one or ‘more input signals but only one output signal. Gates are digital (two-state) circuits because the input and output signals are cither low or high voltages. Gates are often called logic circuits because they can be analyzed with boolean algebra, 2-1 INVERTERS An inverter is a gate with only one input signal and one ‘output signal; the output state is always the opposite of the input state ‘Transistor Inverter Figure 2-1 shows a transistor inverter. This common-emitter amplifier switches between cutoff and saturation. When Vig is low (approximately 0 V), the transistor cuts off and Vou ishigh. On the other hand, a high Vi saturates the transistor, forcing Vox to go low. ‘Table 2-1 summarizes the operation, A low input produces a high output, and a high input results in a low output. Table 2-2 gives the same information in binary form; binary 0 stands for low voltage and binary 1 for high voltage, {An inverter is also called a NoT gate because the output is not the same as the input. The output is sometimes called the complement (opposite) of the input sv (ors) Fig. 2-1 Example of inverter design TABLE 2-1 TABLE 2-2 Vi Your 0 1 ww Mr fe ‘a1 Fig, 2-2 Logie symbols: (a) inverter; (b) another inverter symbol: () double inverter: (a) buer. Inverter Symbol Figure 2-2a is the symbol for an inverter of any design. Sometimes schematic diagram will use the altern symbol shown in Fig. 2-26; the bubble (small circle) is on 19the input side. Whenever you sce either of these symbols, remember thatthe output isthe complement of the input Noninverter Symbol If you cascade two inverters (Fig. 2-2), you get a nonin verting amplifier. Figure 2-2d is the symbol for « nonin- verting amplifier. Regardless ofthe circuit design, the action is always the same: a low input voltage produces a low output voltage, and a high input voltage results in a high output voltage. The main use of noninverting amplifier is buffering (isolating) two other circuits. More will be said about buffers in a later chapter. EXAMPLE 2-1 rege | ssn fi fn | | o -Lo 1 Fig. 2-3 Example 2-1 Figure 2-30 has an output, A to F, of 100101. Show how to complement cach bit SOLUTION Easy, Use an inverter on each signal line (Fig. 2-36). The final output is now 011010. A hex inverter is a commercially available IC containing six separate inverters. Given a 6-bit register like Fig. 2-34, wwe can connect a hex inverter fo complement each bit as shown in Fig. 2-36. ‘One more point, In Fig. 2-34 the bits may represent a coded instruction, number, letter, etc. To convey this variety of meaning, a string of bits is often called a binary word or simply a word. In Fig. 2-3b the word 100101 is complemented to get the word 011010. 2-2 oR GATES The OR gate has two or more input signals but only one ‘output signal. If any input signal is high, the output signal is high, 2O Digitat Computer Electronics Fig. 24 A 2:input diode on gate Diode on Gate Figure 2-4 shows one way to build an on gate. If both inputs are low, the output is low. If either input is high, the diode with the high input conducts and the output is high. Because of the two inputs, we call this circuit a 2- Input oR gate. ‘Table 2-3 summarizes the action; binary 0 stands for low voltage and binary 1 for high voltage. Notice that one or more high inputs produce a high output; this is why the circuit is called an OR gate 4o—Dt cope Fig. 2-8 A 3-input diode om gate More than Two Inputs Figure 2-5 shows a 3-input o8 gate. If all inputs are low all diodes are off and the output is low. If 1 or more inputs are high, the output is high. Table 2-4 summarizes the action. A table like this is called a truth table: it lists all the input possibilities and the corresponding outputs. When constructing a truth table, always list the input words in a binary progression as shown (000, 001, 010, 11D; this guarantees that all input possibilities will be accounted for. ‘An oR gate can have as many inputs as desired; add one diode for each additional input. Six diodes result in a 6- TABLE 2:3. TABLE 2-4. THREE- TWO INPUT INPUT on GATE or GATE, — AB cilyY A BIY _ ie a o 0 o|o O00) o o 1f4 eel Ot ot boot Of Ain eet 1 0 of 4 a 1 oo t]4 ror oO] 4 1 oi iiiinput OR gate, nine diodes in a 9-input oR gate, No matter how many inputs, the action of any OR gate is summarized like this: one or more high inputs produce a high output, Bipolar transistors and MOSFETs can also be used to build o gates. But no matter what devices are used, OR gates always produce a high output when one or more inputs are high. Figure 2-6 shows the logic symbols for 2, 3+, and 4-input OR gates. D- a> 3 Fig. 2-6 on-gate symbols. EXAMPLE 2-2 Show the truth fable of a 4-input oR gate SOLUTION Let ¥ stand for the output bit and A, B, C, D for input bits. Then the truth table has input words of 0000, 0001, 0010, ; I1IT, as shown in Table 2-5. As expected, output is 0 for input word 0000; ¥ is I for all other input words. ‘As a check, the number of input words in a truth table always equals 2", where n is the number of input bits, A 2-input oR gate has a truth table with 2? or 4 input words; ‘a 3-input on gate has 2° or 8 input words; and a 4-input on gate has 2 or 16 input words TABLE 2-5. FOUR-INPUT on GATE AB c piy 0 0 0 of o o 0 o tf a o 0 1 of 4 oO oO Foul a o 1 0 of} 4 Oo Si 1 on ert Oo i Oe et ot fo 0 ain er Oe ot Oe ee ot rotor aida EXAMPLE 2-3 How many inputs words are in the truth table of an 8-input ‘ox gate? Which input words produce a high output? SOLUTION ‘The input words are 0000 0000, 0000 0001, .... HILL ILLL. With the formula of the preceding example, the total number of input words is 2" = 2 = 256. In any oR gate, | or more high inputs produce a high ‘output. Therefore, the input word of 0000 0000 results in 4 low output; all other input words produce a high output. EXAMPLE 2-4 , | 7 te La hs ty | HS 4 + + ig, 27 Decimal to-binary encoder. ‘The switches of Fig. 2-7 are push-button switches like those of a pocket calculator. The bits out of the oR gates form a 4-bit word, designated Y,Y;¥,Yo. What does the circuit do? SOLUTION Figure 2-7 is a devimal-to-binary encoder, a circuit that converts decimal to binary. For instance, when push button 3 is pressed, the Y, and ¥) OR gates have high inputs; therefore, the output word is YaVY:Yp = 0011 Chapter 2 Gates 21If button 5 is keyed, the Y> and Yo oR gates have high inputs and the output word becomes YVAVYo = O10 When switch 9 is pressed, YaV.Y.Yp = 1001 Check the other input switches to convince yourself that the output word always equals the binary equivalent of the switch being pressed. 2-3 AND GATES ‘The AND gate has two or more input signals but only one ‘output signal. All inputs must be high fo get a high output ae ot 28 A 2.input aso gate (a cit () bot ints low: low input hgh bath np ih Diode anp Gate Figure 2-80 shows one way to build an AND gate. In this circuit the inputs can be either low (ground) or high (+5 V). When both inputs are low (Fig. 2-86), both diodes ‘conduct and pull the output down to a low voltage. If one of the inputs is low and the other high (Fig. 2-8¢), the diode with the fow input conducts and this pulls the output down 10 a low voltage. The diode with the high input, on the other hand, is reverse-biased or cut off, symbolized by the dark shading in Fig. 2-8 When both inputs are high (Fig. 2-84), both diodes are cut off. Since there is no current in the resistor, the supply. voltage pulls the output up to a high voltage (+5 V). 22 digital Computer Electronics TABLE 26, TWO- INPUT ayo GATE A 0 0 1 L oe » |-2e<|- Table 2-6 summarizes the action. As usual, binary zero stands for low voltage and binary | for high voltage. AS you sec, A and B must be high to get a high output; this is ‘why the circuit is called an AND gate. sv Fig. 29. A input avo gate More than Two Inputs Figure 2-9 is a 3-input AND gate. If all inputs are low, all, diodes conduct and pull the output down to a low voltage. Even one conducting diode will pull the output down to a low voltage; therefore, the only way to get a high output is to have all inputs high. When all inputs are high, all diodes are nonconducting and the supply voltage pulls the ‘output up to a high voltage Table 2-7 summarizes the 3-input AND gate. The output {0 for all input words except 111. That is, all inputs must be high to get « high output. [AND gates can have as many inputs as desired; add one diode for each additional input. Eight diodes, for instance, result in-an 8-input AND gate; sixteen diodes in a 16-input TABLE 2.7. THREE- INPUT Axo GATE 7 o 0 o|o o o 1lo o 1 oj] o o 1 1jo 1 0 of 0 1 0 1}o0 le Oo eee—-D- 210 an-zate symbols AND gate. No matter how many inputs an AND gate has, the action can be summarized like this: All inputs must be high to get a high output. Figure 2-10 shows the logic symbols for 2-, 3-, and 4- input AND gates. EXAMPLE 2-5 Describe the truth table of an 8-input AND gate SOLUTION ‘The input words are from 0000 000010 1111 1111, following the binary progression, The total number of input words is m The first 255 input words produce a 0 output. Only the last word, 1111 LILL, results in a 1 output, This is because all inputs must be high to get @ high output EXAMPLE 2-6 Fig. 2-11 Using avo gates to block of transmit data ‘The 6-bit register of Fig. 2-11 stores the word ABCDEF. ‘The ENABLE input can be low or high. What does the circuit do? SOLUTION One use of AND gates is to transmit data when certain conditions are satisfied. In Fig. 2-11 a low ENABLE blocks the register contents from the final output, but a high ENABLE transmits the register contents For instance, when ENABLE = 0 each AND gate has a low ENABLE input. No matter what the register contents, the output of each AND gate must be low. Therefore, the final word is YsY.YsY2¥ Yo = 000000 As you see, a low ENABLE blocks the register contents from the final output On the other hand, when ENABLE = 1 the output of each aNb gate depends on the data inputs (A. B,C, .. .j a low data input results in a low output, and ‘high data input ina high output. For example, if ABCDEF 100100, a high ENABLE gives Y.YAYY.¥1Y) = 100100 In general, # high ENABLE transmits the register contents to the final output to get YsYaYsY¥:¥o = ABCDEF 2-4 BOOLEAN ALGEBRA ‘As mentioned earlier, Boole invented two-state algebra to solve logic problems. This new algebra had no practical use until Shannon applied it to telephone switching circuits, Today boolean algebra is the backbone of computer circuit analysis and design, Inversion Sign In boolean algebra a variable can be either a 0 of a 1, For digital circuits, this means that a signal voltage can be either low or high. Figure 2-12 is an example of a digital circuit because the input and output voltages are either low or high. Furthermore, because of the inversion, Y is always the complement of A. A word equation for Fig. 2-12 is Fig, 2-12 Inverter Y= Nora en Chapter? Gates 23IA iso, Y=nor0=1 On the other hand, if A is 1 Y=norl=0 In boolean algebra, the overbar stands for the NOT operation, This means that Eq. 2-1 can be written y=a 22) Read this as “Y equals Nor” or “'Y equals the complement ‘of A."* Equation 2-2 is the standard way to write the output of an inverter. ‘Using the equation is easy. Given the value ofA, substitute and solve for ¥. For instance, if A is 0, YeA=d=1 because NOT 0 is 1. On the other hand, if A is 1 because NOT 1 is 0. Fig. 213 on gate on Sign ‘A word equation for Fig. 2-13 is Y= Aor 23) Given the inputs, you can solve for the output. For instance, ifA = OandB = 0, y ord = 0 because 0 comes out of an oR gate when both inputs are os. ‘As another example, if A = 0-and B = 1 Y=Oor1=1 because 1 comes out of an OR gate when either input is 1 Similarly, if A = 1 and B = 0, Y= 1or0=1 WA = landB = 1 Tor} =1 24 digital Computer Electronics In boolean algebra the + sign stands for the oR operation. In other words, Eq. 2-3 can be written Y=A+B Read this as “Y equals A ok B."° Equation 2-4 is the standard way to write the output of an oR gate. ‘Given the inputs, you can substitute and solve for the output, For instance, if 4 = 0 and 8 = 0, y=A+H=04020 WA = OmdB = 1, Y=A+B=041-1 because 0 oRed with I results in If = 1 and B= Y=A+B=1+0=1 If both inputs are high, Y=A+B=1+1=1 because 1 Red with 1 gives I Don’t let the new meaning of the + sign bother you. There's nothing unusual about symbols having more than fone meaning. For instance, “‘pot”” may mean a cooking ‘utensil, a flower container, the money wagered in a card game, a derivative of cannabis sativa and so forth; the intended meaning is clear from the sentence it’s used in. Similarly, the 4+ sign may stand for ordinary addition or (g addition; the intended meaning comes across in the way it’s used. If we're talking about decimal numbers, + means ordinary addition, but when the discussion is about logic circuits, + stands for ok addition —D>-- Fig, 214 ano gate AND Sign ‘A word equation for Fig. 2-14 is y AaNDB 2-5) In boolean algebra the multiplication sign stands for the AND operation. Therefore, Eq. 2-5 can be written Y=A-8 or simplyRead this as “Y equals A AND B."" Equation 2-6 is the standard way to write the output of an AND gate. Given the inputs, you can substitute and solve for the output, For instance, if both inputs are low, y AB=0-0=0 because 0 anped with 0 gives 0, If A is low and B is high, y because 0 comes out of an AND gate if any input is 0. IF A is Land B is 0, ¥y AB=1-0=0 When both inputs are high, Y=AB11=1 because 1 anped with I gives 1 Decision-Making Elements ‘The inverter, OR gate, and AND gate ate often called decision-making elements because they can recognize some input words while disregarding others. A gate recognizes a word when its output is high: it disregards a word when its output is low. For example, the AND gate disregards all words with one or more 0s; it recognizes only the word whose bits are all Is Notation In later equations we need to distinguish between bits that are ANDed and bits that are part of a binary word. To do this we will use italic (slanted) letters (A, B, ¥, ete.) for aNped bits and roman (upright) leters (A, B, Y, etc.) for bits that form a word. For example, ¥sV2¥i%y stands for the logical product (anping) of ¥s, Yo, ¥1, and Yy. IY = 1, Ys = 0, ¥; 0, and ¥o = 1, the product ¥,12¥;¥o will reduce as follows: YYWY) = 10-001 In this case, the italic leters represent bits that are being ANDed. On the other hand, Y,Y,Y,Yo is our notation for a 4-bit word. With the ¥ values just given, we can write YAVAY.Yo = 1001 In this equation, we are not dealing with bits that are aNbed; instead, we are dealing with bits that are part of a word, ‘The distinction between italic and roman notation will ‘become clearer when we get to computer analysis, Positive and Negative Logic A final point. Positive logic means that 1 stands for the more positive of the two voltage levels. Negative logic ‘means that I stands for the more negative of the two voltage levels. For instance, if the two voltage levels are 0 and —5 V, positive logic would have I stand for 0 V and 0 for ~5 V, whereas negative logic would have | stand for —5 V and 0 for 0 V. Ordinarily, people use positive logic with positive supply voltages and negative logic with negative supply voltages. ‘Throughout this book, we will be using positive logic: EXAMPLE 2-7 Fig. 215 Logie circuits What is the boolean equation for Fig. 2-154? The output if both inputs are high? SOLUTION Ais inverted before it reaches the ok gate; therefore, the "upper input to the oR gate is A, The final output is This is the boolean equation for Fig, 2-154. To find the output when both inputs are high, either of ‘two approaches can be used. Fitst, you can substitute directly into the foregoing equation and solve for ¥ YeAs+e=T+1=0+1 Alternatively, you can analyze the operation of Fig. 2-1Sa like this. If both inputs are high, the inputs to the ox gate are 0 and 1, Now, 0 oRed with 1 gives 1. Therefore, the Final output is high, EXAMPLE 2-8 ‘What isthe boolean equation for Fig. 2-156? If both inputs are high, what is the output? Chapter2 Gates 25SOLUTION The AND gate forms the logical product AB, which is inverted to get Read this as “Y ¢¢ complement of AB." I both inputs are high, direct substitution into the equation ives * or “Y equals the Note the order of operations: the ANDing is done first, then. the inversion. Instead of using the equation, you can analyze Fig. Sb as follows. If both inputs are high, the AND gate has ‘high output. Therefore, the final output is low. ts) pl o Fig, 2-16 Logie circuits ‘What is the boolean equation for Fig. 2-16a? The truth table? Which input words does the circuit recognize? SOLUTION The upper AND gate forms the logical product AB, and the lower AND gate gives CD. oRing these products results in Y=AB+ CD Read this as “Y equals AB ox CD."" Next, look at Fig. 2-16a. The final output is high if the OR gate has one or more high inputs. This happens when AB is 1, CD is 1, or both are Is. In tum, AB is 1 when Ast oad B=1 26 digital Computer Blectronics TABLE 2-8. TRUTH TABLE, FOR Y ee |+| CD is I when C=1 md p=1 Both products are Is when ee ae Cet de Dl ‘Therefore, the final output is high when A and B are Is, when C and D are 1s, or when all inputs are Is. Table 2-8 summarizes the foregoing analysis. From this it’s clear that the circuit recognizes these input words: 0011, OLLL, 1011, 1100, 1101, 1110, and 1111 EXAMPLE 2-10 Write the boolean equation for Fig. 2-160. If all inputs are hhigh, what is the output? SOLUTION The OR gate forms the logical sum B + C. This sum is aNped with A to get Y=AB+O (Parentheses indicate aNving.) (One way to find the output when all inputs are high is to substitute and solve as follows: Y=aB+Q=1d+)=1=1Alternatively, you can analyze Fig. 2-166 like this. If all inputs are high, the ox gate has a high output; therefore, both inputs to the AND gate are high. Since all high inputs to an AND gate result in a high output, the final output is high. EXAMPLE 2-11 a a c ° Fig. 2-17 A L0f-10 decoder What is the boolean equation for each ¥ output in Fig. 217? SOLUTION Each AND gate forms the logical product ofits input signals The inputs to the top AND gate are A, B, C and D; therefore, The inputs to the next AND gate are A, B, © and D; this ‘means that ¥, = ABCD Analyzing the remaining gates gives EXAMPLE 2-12 What does the circuit of Fig. 2-17 do? SOLUTION This is a binary-to-decimal decoder, a circuit that converts, from binary to decimal. For instance, when the register Contents are OI, the ¥; AND gate has all high inputs therefore, Ys is high. Furthermore, register contents of 0011 ‘mean that all other AND gates have at least one low input As aresult, all other AND gates have low outputs. (Analyze the circuit t0 convince yourself.) If the register contents change to 0100, only the ¥, AND ate has all high inputs; therefore, only ¥, is high, If the register contents change fo 0111, ¥> is the only high output. In general, the subscript of the high output equals the decimal equivalent of the binary number stored in the register. This is why the circuit is called a binary-to-decimal decoder. ‘The circuit of this example is also called a 4-Line-t0-10- line decoder because there are 4 input lines and 10 output lines. Another name for it is a I-of-10 decoder because only 1 of 10 output lines has @ high voltage GLOSSARY AND gate A logic circuit whose output is high only when all inputs are high, bootean algebra Originally known as symbolic logic, this modem algebra uses the set of numbers 0 and 1. The Chapter? Gates 27operations OR, AND, and NOr are sometimes called union, intersection, and inversion. Boolean algebra is ideally suited to digital circuit analysis. complement The output of an inverter, gate A logic circuit with one or more input signals but only one output signal, Inverter A gate with only 1 input and { output. The output is always the complement of the input. Also known as a Nor gate. logic circuit A cirovit whose input and output signals are two-state, either low or high voltages. The basic logic circuits are OR, AND, and NOT gates. (On gate A logic circuit with 2 or more inputs and only 1 ‘output; 1 of more high inputs produce a high output. truth table A table that shows all input and output possibilities for a logic circuit. The input words are listed in binary progression. word A string of bits that represent a coded instruction or data SELF-TESTING REVIEW Read each of the following and provide the missing words. Answers appear at the beginning of the next question |. A gate is @ logic circuit with one or more input signals but only — ‘output signal, These signals ate either _____ or high. 2. (one, low) An inverter is a gate with only input; the output is always in the opposite state from the input. An inverter is also called a gate. Sometimes the output is referred to as the complement of the input. 3. (I, Nor) The OR gate has two or more input signals, If any input is . the output is high. The number of input words in truth table always equals. _____, where 1 is the number of input bits 4. (high, 29) The — ‘gate has (wo or more input signals. All inputs must be high to get a high ‘output. 5. (AND) In boolean algebra, the overbar stands for the or operation, the plus sign stands for the — operation, and the times sign for the operation, 6. (OR, AND) The inverter, OR gate, and AND gate are called decision-making elements because they can recognize some input while disregarding others. A gate recognizes a word when its output is 7. (words, high) A binary-to-decimal decoder is also called a 4-line-1o-10-line decoder because it has 4 input lines and 10 output lines. Another name for it is the I-of-10 decoder because only 1 of its 10 output Tines is high at 2 time. PROBLEMS 241, How many inputs signals can a gate have? How ‘many output signals? 2:2, If you cascade seven inverters, does the overall circuit act like an inverter or noninverter? 2-3. Double inversion occurs when two inverters are cascaded. Does such a connection act like an inverter oF noninverter? 2-4, ‘The contents of the 6-bit register in Fig. 2-3b change to 101010, What is the decimal equivalent of the register contents? The decimal equivalent cout of the hex inverter? {An on gate has 6 inputs. How many input words are in its ruth table? What is the only input word that produces a 0 output? 2-6, Figure 2-18 shows a hexadecimal encoder, a cit= cuit that converts hexadecimal to binary. Press ing each push-button switch results in a differ- cent output word YY,Y,Yp. Starting with switch (0, what are the output words? (Note: The new symbol in Fig. 2-18 is another way to draw an oR gate, 28 digital Computer Electronics 2-7. In Fig. 2-18 what switches would you press to produce O11 1001 1100 1111 ‘Work from left to right.) 248, What is the 4-bit output in Fig. 2-18 when switch A is pressed? Switch 4? Switch E? Switch 6? 2.9, An AND gate has 7 inputs. How many input ‘words are in its truth table? What is the only input word that produces a 1 output? 210. Visualize the register contents of Fig. 2-19 as the word AjAg* + * Ao, and the final output as the word YY, ** + Yo. What is the output word for each of the following conditions: a. Ag+ ++ Ay = 1100 1010, ENABLE = 0. 1 Asay 101 1101, ENABLE cc. Ayes 1111 0000, ENABLE d.AJAgs ++ Ag = 1010 1010, ENABLE = 0.% % Fig, 2-18 Hexadecimal encoder. 7 % % % % % Fig. 2419 DAL. The 8-bit egister of Fig. 2-19 stores 59y9. What is the decimal equivalent of the final output word if ENABLE = 07 If ENABLE = 1? 2412. Answer these questions: 8, What input words does a 6-input on gate recognize? What word does it disregard? b. What input word does an 8-input AND gate recognize? What words does it disregard? ‘ % to mae Fig. 2-20 2-13. What is the boolean equation for Fig. 2-20a? The output if both inputs are high? 2-14. If all inputs are high in Fig. 2-205, what is the output? The boolean equation for the circuit? What is the only ABC input word the circuit recognizes? 2415. If you constructed the truth table for Fig, 2-20h, how many input words would it co Chapter 2 Gates 29oa 400 sus Fig. 221 108 Lox me vate az aie we Fig. 2-22 wus osz 12 wx ora Fig. 223, Fig. 225 A L-of-16 decoder. -.., Fig, 224 BO Digital Computer Electronics218, 219, 2:20, 221. 222, ‘What is the boolean equation for Fig. 2-214? The output if both inputs are high? If all inputs are high in Fig. 2-216, what is the ‘output? What is the boolean equation of the cir cuit? What ABC input words does the circuit recognize? What is the only word it disregards? ‘What is the boolean equation for Fig. 2-224? The ‘output if all inputs are 1s? If you were to con- struct the truth table, how many input words ‘would it have? Write the boolean equation for Fig, 2. inputs are Is, what is the output? If both inputs are bigh in Fig. 2-23, what is the ‘output? What is the boolean equation for the cir- cuit? Describe the truth table, ‘What is the boolean equation for Fig, 2-247 How many ABCD input words are in the truth table? Which input words does the circuit recognize? Because of the historical connection between bool- ccan algebra and logic, some people use the words “urue™ and “false” instead of “high” and “low” when discussing logic circuits. For in- stance, here's how an AND gate can be described. If any input is false, the output is false; if all inputs are true, the output is true a. IF both inputs are false in Fig. 2-23, what is the output? , What is the output in Fig. 2-23 if one input is false and the other true? ©. In Fig. 2-23 what is the output if all inputs are true? 2b. Wall 223, 224, 2.28, 2:26, 227, Figure 2-25 shows a I-of-16 decoder. The signals ‘coming out of the decoder are labeled LDA, ADD, SUB, and so on. The word formed by the 4 leftmost register bits is called the OP CODE. As an equation, OP CODE = Iyshulishs a. IfLDA is high, what does OP CODE equal? If ADD is high, what does it equal? c. When OP CODE = 1001, which of the output signals is high? d. Which output signal is high if OP CODE = me In Fig. 2-25, list the OP CODE words and the corresponding high output signals. (Start with (0000 and proceed in binary to 1111.) In the following equations the equals sign means “is equivalent to."" Classify each of the following as positive or negative logic: a 0 = 0Vand1 = +5V b. O= +5Vand 1 = OV. © 0 = ~SVand1 =0V, d. 0 =0Vand1 = SV. In Fig, 2-25 four output lines come from the decoder. Is it possible to add more op codes without increasing the number of output ines? How many output lines from the decoder would Chapter? Gates 31>| 3 |e} MoRrE LOGIC GATES This chapter introduces NOR and NAND gates, devices that are widely used in industry. You will also learn about De “Morgan's theorems: they help you to rearrange and simplify logic circuits 3-1 NOR GATES “The NOR gate has two or more input signals but only one output signal. All inputs must be low to get a high output In other words, the NOR gate recognizes only the input word whose bits are all Os. Fig. 3-1 sow gate: (2) logical meaning; (6) standard symbl ‘Two-Input Gate Figure 3-1a shows the logical structure of # Nok gate, which is an oR gate followed by an inverter. Therefore, the final output is NoT the OR of the inputs. Originally called a NOT-OR gate, the circuit is now referred to as a NOR gate. Figure 3-10 is the standard symbol for a NoR gate, Notice that the inverter triangle has been deleted and the small circle or bubble moved to the O8-gate output. The bubble. is a reminder of the inversion that follows the oring, With Fig. 3-1a and b the following ideas are clear. If both inputs are low, the final output is high. If one input is low and the other high, the output is low. And if both inputs are high, the output is low. ‘Table 3-1 summarizes the circuit action, As you see, the Nor gate recognizes only the input word whose bits are all 0s. In other words, all inputs must be low to get a high output 32 TABLE 3-1. TWO- INPUT Nor GATE B\ A+B 0 1 0 L --ool> entally, the boolean equation for a 2-input No gate y=A3B G1) Read this as ““Y equals Nor A oR B.” If you use this ‘equation, remember that the ORing is done first, then the Fig. 32 son (a) input: (6) 4-input Three-Input Gate Regardless of how many inputs a NOR gate has, it is still logically equivalent fo an oR gate followed by an inverter. For instance, Fig. 3-2a shows a 3-input Nok gate. The 3 inputs are ORed, and the result is inverted. Therefore, the boolean equation is ABTC B. ‘The analysis of Fig. 3-2a goes like this. If all inputs are low, the result of oRing is low; therefore, the final output‘TABLE 3-2. THREE-INPUT Nox GATE is high. If one or more inputs are high, the result of oning is high; so the final output is low. Table 3-2 summarizes the action of a 3-input NOR gate. ‘As you see, the circuit recognizes only the input word whose bits are Os. In other words, all inputs must be low to get a high output Four-Input Gate Figure 3.26 is the symbol for a 4-input NoR gate. The inputs are oRed, and the result is inverted. For this reason, the boolean equation is =A5BFCtD G3) The corresponding truth table has input words from 0000 fo 1111, Word 0000 gives a 1 output; all other words produce a 0 output. (For practice, you should construct the truth table of the 4-input NoR gate.) 3-2 DE MORGAN'S FIRST THEOREM Most mathematicians ignored boolean algbebra when it fist appeared; some even ridiculed it. But Augustus De Morgan saw that it offered profound insights. He was the first to acclaim Boole’s great achievement. Always a warm and likable man, De Morgan himself hhad paved the way for boolean algebra by discovering two important theorems. This section introduces the first theo- ‘The First Theorem Figure 3-3a is a 2-input nok gate, analyzed earlier. As you recall, the boolean equation is ‘and Table 3-3 is the truth table. a Fig. 33 De Morgan's first theorem: (a) Now gate; (b) AND gate ‘with inverted inputs. Figure 3-30 has the inputs inverted before they teach the AND gate. Therefore, the boolean equation is y=AB I both inputs are low in Fig. 3-3h, the AND gate has high inputs; therefore, the final output is high. If one or more inputs are high, one or more AND-gate inputs must be low and the final output is low, Table 3-4 summarizes these ideas TABLE 33 TABLE 34 A Bl Ave A B| 4B oo; oof a oi} 0 01] 0 10} 0 io} o ii} o nr) Compare Tables 3-3 and 3-4, They're identical. This ‘means that the two circuits are logically equivalent; given the same inputs, the outputs are the same. In other words, the circuits of Fig. 3-3 are interchangeable. De Morgan discovered the foregoing equivalence long before logic circuits were invented. His first theorem says A¥B =A G4) The left member of this equation represents Fig. 3-3a; the right member, Fig. 3-36, Equation 3-4 says that Fig. 3-3a and 6 are equivalent (interchangeable), Bubbled anp Gate Figure 3-4a shows an AND gate with inverted inputs. This circuit is so widely used that the abbreviated logic symbol of Fig. 3-46 has been adopted. Notice that the inverter triangles have been deleted and the bubbles moved to the Chapter 3 More Logic Gates 3Baaa —D-: Fig. 34 ano gate with inverted inputs: (a) circuit; (b) abbreviated symbol AND-gate inputs. From now on, we will refer to Fig, 3.4b as a bubbled AND gate; the bubbles are a reminder of the inversion that takes place before aNDing. q>- - =D- Fig. 35 De Morgan’s fist theorem, Figure 3-5 is a graphic summary of De Morgan theorem, A NoR gate and a bubbled AND gate are equivalent. AAs shown later, because the circuits are interchangeable, you can often reduce complicated logic circuits to simpler forms. More than Two Inputs ‘When 3 inputs are involved, De Morgan's first theorem is written 65) For 4 inputs A¥BF CHD = ABCD 66) In both cases, the theorem says that the complement of suum equals the product of the complements, 2>-- => Fig. 3-6 De Morgan's fist theorem: (a) 2-input circuits: (6) 4 input circuits 34 Digital Computer Electronics Here's what really counts. Equation 3-5 says that a 3 input Nor gate and a3-input bubbled AND gate ae equivalent (see Fig. 3-64), Equation 3-6 means that a 4-input NOR gate and a 4-input bubbled AND gate are equivalent (Fig. 3-66), Memorize these equivalent eieuits; they are a visual statement of De Morgan's first theorem, Notice in Fig. 3-6b how the input edges of the NOR gate and the bubbled AND gate have been extended. This is common drafting practice when there are many input signals The same idea applies to any type of gate EXAMPLE 3-1 Prove that Fig. 3-7a and ¢ are equivalent. 1, a D- Fig. 37 Equivalent De Morgan circuits. SOLUTION The final NOR gate in Fig. 3-7a is equivalent to a bubbled AND gate. This allows us to redraw the circuit as shown in Fig. 3-76. Double inversion produces noninversion; therefore, each double inversion in Fig. 3-7 cancels out, leaving the simplified circuit of Fig, 3-7e. Figure 3-7a and ¢ are therefore equivalent. Remember the idea. Given a logic circuit, you can replace ‘any NOR’ gate by a bubbled AND gate. Then any double inversion (a pair of bubbles in a series path) cancels out Sometimes you wind up with a simpler logic circuit than you started with; sometimes not ‘But the point remains. De Morgan's first theorem enable you to rearrange a logic circuit with the hope of finding a ‘Simpler equivalent circuit or perhaps getting more insight into how the original circuit works. 3-3 NAND GATES “The NAND gate has two or more input signals but only one ‘output signal, All input signals must be high to get a low output(a 1 Fig. 38 Nawp gate: (a) logical meaning; (4) standard symbol ‘Two-Input Gate Figure 3-8a shows the logical structure of a NAND gate, an AND gate followed by an inverter. Therefore, the final ‘output is NOT the AND of the inputs. Originally called a NOT-AND gate, the circuit is now referred to a8 a NAND gate. Figure 3-8b is the standard symbol for a NAND gate, ‘The inverter triangle has been deleted and the bubble moved to the AND-gate output. If one or more inputs are low, the result of ANDing is low; therefore, the final inverted output is high. Only when all inputs are high does the aNDing produce a high signal; then the final output is low. Table 3-5 summarizes the action of a 2-input NAND gate. AAs shown, the NAND gate recognizes any input word with ‘one or more 0s. That is, one or more low inputs produce @ high output. The boolean equation for a 2-input NAND gate is v=a8 on Read this as “Y equals Not AB.” If you use this equation, remember that the ANDing is done first then the inversion, 0 ) ig. 39 Nas gates: (a) input; (6) 4-input Three-Input Gate Regardless of how many inputs & NAND gate has, logically equivalent to an AND gate followed by an inverter. For example, Fig. 3-9a shows a 3-input NAND gate. The inputs are ANDed, and the product is inverted, Therefore, the boolean equation is Y = ABC (3-8) Here is the analysis of Fig. 3-9a. If one or more inputs are low, the result of anbing is low; therefore, the final ‘output is high. If all inputs are high, the ANDing gives a high signal; so the final output is low. Table 3-6 is the truth table for a 3-input NAND gate, As indicated, the circuit recognizes words with one of more 0, This means that one or more low inputs produce a high ‘output TABLE 3.5. TABLE 3-6. THREE- TWO-INPU' Nanp GATE, AB 00 Ori 0 Li Four-Input Gate Figure 3-9b is the symbol for a 4-input NaND gate. The inputs are aNDed, and the result is inverted. Therefore, the boolean equation is y = ABCD 69) If you construct the truth table, you will have input words from 0000 to 1111. All words from 0000 through 1110 produce @ I output; only the word L111 gives @ 0 output 3-4 DE MORGAN'S SECOND THEOREM ‘The proof of De Morgan’s second theorem is similar to the proof given for the first theorem, What follows is a brief explanation, ‘The Second Theorem When two inputs are used, De Morgan's second theorem says that AB = A+B -10) In words, the complement of a product equals the sum of the complements. The left member of this equation repre- semls a NAND gate (Fig. 3-10a); the right member stands Fig, 3.10 Do Morgan’s second! theorem: (a) Nant gate; (6) Om gate with inverted inputs; (c) bubbled om gate Chapter 3 More Logic Gates 35for an on gate with inverted inputs (Fig. 3-106). Therefore, De Morgan's second theorem boils down to the fact that Fig. 3-10d and b are equivalent. EXAMPLE 3-2 Prove that Fig. 3-134 and ¢ are equivalent, aD - Fig. 3-11 De Morgan's second theorem. Bubbled or Gate The circuit of Fig. 3-10b is so widely used that the abbreviated logic symbol of Fig. 3-10c has been adopted, From now on we will refer to Fig. 3-10c as a bubbled oR ‘gate; the bubbles are a reminder of the inversion that takes. place before oRing, Figure 3-11 is a visual statement of De Morgan's second theorem: a NAND gate and a bubbled or gate are equivalent ‘This equivalence allows you to replace one circuit by the other whenever desired. This may lead to a simpler logic circuit or give you more insight into how the original circuit works, More than Two Inputs ‘When 3 inputs are involved, De Morgan’s second theorem is writen ABC =A+B+C GID 1f4 inputs are used, ABCD =A+B+C+D G12) These equations say that the complement of a product ‘equals the sum of the complements o Fig, 3:12 De Morgan's second theorem: (a) 3-input circuits: (6) ‘input circuits, Figure 3-12 is @ visual summary of the second theorem, Whether 3 or 4 inputs are involved, a NAND gate and a bubbled on gate are equivalent (interchangeable), 36 digital Computer Blectronics dO dn yp o oy ca Fig. 3:13 Equivalent circuits SOLUTION Replace the final NaND gate in Fig. 3-13a by a bubbled on gale. This gives Fig. 3-130. The double inversions cancel out, leaving the simplified circuit of Fig. 3-13c. Figure 3-13a and c are therefore equivalent. Driven by the same inputs, either circuit produces the same output as the other. So if you're loaded with NanD gates, build Fig. 3-134. If your shelves are full of AND and OR gates, build Fig. 3-13c. Incidentally, most people find Fig. 3-13b easier to analyze than Fig. 3-13a. For this reason, if you build Fig. 3-134, draw the circuit like Fig. 3-13. Anyone who sees Fig. 3-136 on a schematic diagram knows that the bubbled OR gate isthe same as a NaND gate and that the buill-up circuit is two NAND gates working into a NAND gate. EXAMPLE 3-3 Figure 3-14 shows a circuit called a control matrix. At fist, it looks complicated, but on closer inspection its relatively simple because ofthe repetition of NANO pates. De Morgan's theorem tells us that NAND gates diving NAND gates are equivalent to AND gates driving OR gates. ‘The upper Set of inputs T; to Te are called timing signals; only one of them is high ata time. 7, goes high first then Tz, then Ts, and so on. These signals control the rate and sequence of computer operations. The lower set of inputs LDA, ADD, SUB, and OUT are computer instructions; only one of them is high ata time The outputs Co, Ep. Lay +» 10 Lo control different registers in the computer. “Answer the following questions about the control matrix: a. Which outputs are high when 7, is high? b. IFT, and LDA are high, which outputs are high? c. When 7, and SUB are high, which outputs are high?hh Te Te Te To i ; a Hi ; i il yy Ley — I Sp Fig. 3414 Control matrix. tu Eq SOLUTION a. Visualize T, high. You can quickly check out each gate and realize that Ey and Ly are the only high outputs. b. This time 7, and LDA are high. Check each gate and you can see that Ly, and are the only high outputs. ©. When 7, and SUB are high, the high outputs are L,, So and E, 8-5 EXCLUSIVE-OR GATES ‘An oR gate recognizes words with one or more Is. The EXCLUSIVE-OR gate is different; it recognizes only words that have an odd number of Is. ‘Two Inputs Figure 3-15a shows one way to build an EXCLUSIVE-OR gate, abbreviated xoR, The upper aND gate forms the product AB, and the lower AND gate gives AB, Therefore, the boolean equation is G13) SU Ey ty bo Fig. 3:15 (a) excrustve-on gute (6) A 2input excLusIvE-on ae, Here's. what the circuit does. In Fig. 3-15a two low inputs mean both AND gates have low outputs; so the final output is low. IF A is low and B is high, the upper AnD. gate has a high output; therefore, the final output is high, Likewise, a high 4 and low B result in @ final output that is high. If both inputs are high, both AND gates have low ‘outputs and the final output is low. Table 3-7 shows the truth table for a 2-input EXCLUSIVE: on gate. The output is high when A or B is high but not both; this is why the circuit is known as an EXCLUSIVE-OR gate. In other words, the output is 2 1 only when the inputs are different. Chapter 3 More Logic Gates 37TABLE 3-7. TWO- INPUT xor GATE. Logic Symbol and Boolean Sign Figure 3-15b i the standard symbol for a 2-input xR gate. Whenever you see this symbol, remember the action: the inputs must be different to get a high output ‘A word equation for Fig. 3-15b is Y= AxoRB G14) In boolean algebra the sign © stands for xoR addition, This means that Eq. 3-14 can be writen y A@B G15) Read this as “*Y equals A xoR B.”” Given the inputs, you can substitute and solve for the output. For instance, if both inputs are low, y=0@0=0 because 0 xORed with O gives 0. If one input is low and the other high, y=0@1=1 because O xoRed with 1 produces 1. And so on. Here's a summary of the four possible xOR additions: 0@0= 0@1 1@0 181 0 1 I 0 Remember these four results; we will be using xoR addition when we get to arithmetic circuits Four Inputs In Fig. 3-160 the upper gate produces A ® B, while the lower gate gives C © D. The final gate xoxs both of these sums t0 get Y¥-A@HOC@D G-16) BB __igitat Computer Electronics Fig. 316 A 4-input excrusive-ow gate: (a) cireuit with 2-input OR gates; (B) logic symbol. It’s possible to substitute input values into the equation and solve for the output, For instance, if A through C are low and D is high, 0@HG0en =061 ‘One way to get the truth table is to plow through all the Input possibilities. ‘Alternatively, you can analyze Fig. 3-16a as follows. If all inputs are Os, the first two gates have O outputs; so the final gate has a 0 output. If to C are Os and D isa 1, the upper gate has a 0 output, the lower gate has a 1 output, and the final gate has a 1 output. In this way, you can analyze the circuit action for all input words. Table 3-8 summarizes the action. Here is an important property: each input word with an odd number of Is produces a 1 output. For instance, the first input word 10 produce a 1 output is 0001; this word has an odd number of Is, The next word with | output is 0010; again an odd number of 1s. A 1 output also occurs for these words: 0100, O111, 1000, 1011, 1101, and 1110, all of which hhave an odd number of 1s. The circuit of Fig. 3-16a recognizes words with an odd number of 1s; it disregards words with an even number of Is, Figure 3-16a is a 4-input xoR gate. In this book, we will use the abbreviated symbol of Fig. 3-16b to represent ‘a 4-input Xor gate, When you see this symbol, remember the action: the circuit recognizes words with an odd number of Is. Any Number of Inputs Using 2-input xox gates as building blocks, we can make XOR gates with any number of inputs. For example, Fig.TABLE xor GATE FOUR-INPUT Comment Even od Odd Even Odd Even Even Oda ad Even Even odd Even Odd Odd Even ae eee HH -coccccoe | ee eee Bo eeeenes 0 1 Fig. 3417 ow gates: (@) 3input; (6) 6input. 3-1a shows the abbreviated symbol for a 3-input xoR gate, and Fig. 3-17b is the symbol for a 6-input xoR gute, The final output of any XoR gate is the XOR sum of the inputs: Y=A@Bec- G7 What you have to remember for practical work is this fan XOR gate, no matter how many inputs, recognizes only. words with an odd number of Is. Parity Even parity means a word has an even number of 1s. For instance, 110011 has even parity because it contains four 1s. Odd parity means a word has an odd number of Is. AS an example, 110001 has odd parity because it contains three Is, Here are two more examples: 11110000 1111 0011 1111 0000 1111 0111 (Even parity) (Odd parity) The first word has even parity because it contains ten Is; the second word has odd parity because it contains eleven Is. XOR gates are ideal for testing the parity of a word, xOR gates recognize words with an odd number of Is, Therefore, even-parity words produce a low output and odd-parity words produce a high output EXAMPLE 3-4 What is the output of Fig. 3-18 for each of these input words? a. 1010 1100 1000 1100 b. 1010 1100 1000 1101 4 reuie Fig, 318 Ode-parity tester SOLUTION a. The word has seven Is, an odd number. Therefore, the output signal is, opp =1 . The word has eight Is, an even number. Now opp = 0 This is an example of an odd-parity tester. An even- parity word produces @ low output. An odd-parity word results in a high output. EXAMPLE 3-5 ‘The 7-bit register of Fig. 3-19 stores the letter A in ASCIL form, What does the 8-bit output word equal? Chapter 3 More Logic Gates 39t cnt pity —_—_—_~ Fig. 3:19 Odd-parity generator. SOLUTION ‘The ASCII code for letter A is 100 0001 (see Table 1-6 for the ASCH code). This word has an even parity, which means that the xor gate has a 0 output. Because of the inverter, the overall output of the circuit is the 8-bit word 1100 0001 Notice that this bas odd parity ‘The circuit is called an odd-parity generator because it produces an 8-bit output word with odd parity. Ifthe register ‘word has even parity, 0 comes out of the XOR gate and the ‘odd-parity bit is 1. On the other hand, if the register word hhas odd parity, a 1 comes out of the xOR gate and the odd: party bit is 0. No matter what the register contents, the ‘odd-parity bit and the register bits form a new 8-bit word that has odd parity ‘What is the practical application? Because of transients, noise, and other disturbances, 1-bit errors sometimes occur jn transmitted data, For instance, the letter A may be transmitted over phone Tines in ASCII form: 100 0001 (A) Somewhere along the line, one of the bits may be changed. Ifthe X, bit changes, the received data will be 1000011 ©) 40 Digital Computer Electronics Because of the L-bit error, we receive letter C when letter A was actually sent, (One solution is to transmit an odd-parity bit along with the data word and have an XOR gate test each received word for odd parity. For instance, with a circuit like Fig 3-19 the letter A would be transmitted as 1100 0001 ‘An xOR gate will test this word when it is received. If no error has occurred, the XOR gate will recognize the word, On the other hand, if @ L-bit error has crept in, the xOR gate will distegard the received word and the data can be rejected ‘A final point. When errors come, they are usually 1-bit errors. This is why the method described catches most of the errors in transmitted data EXAMPLE 3-6 What does the circuit of Fig. 3-20 do? iNverT y Fig. 3:20 SOLUTION When INVERT = 0 and A = 0, y=0@0=0 When INVERT = 0 and A = 1, y=0@1=1 In either case, the output is the same as A; that is, yaa for a low INVERT signal On the other hand, when INVERT = | and A = 0, 1@o=1 When INVERT = 1 and A = 1, 1@1=0‘This time, the output is the complement of A. As an equation, yea for 2 high INVERT signal To summarize, the circuit of Fig. 3-20 does either of two things. It transmits A when IYVERT is 0 and A when INVERT is | 3-6 THE CONTROLLED INVERTER The preceding example suggests the idea of a controlled inverter, a circuit that transmits a binary word of its I's complement. The 1's Complement Complement each bit in a word and the new word you get is the 1's complement. For instance, given 1100 O11 the 1’s complement is 011 1000 h bit in the original word is inverted to get the 1's complement. The Circuit ‘The xoR gates of Fig. 3-21 form a comolled inverter (sometimes called a programmed inverter). This circuit can transmit the register contents or the 1's complement of the register contents. As demonstrated in Example 3-6, each OR gate acts like this. A low INVERT results in and a high INVERT gives y, So each bit is either transmitted or inverted before reaching the final output Visualize the register contents as a word AyAg * «+ Ay and the final output as a word Y,Y, ++» Yq. Then a low INVERT means YoYe> ++ Yo = Ardgs = Ay On the other hand, « high IVVERT results in Yi¥gi+ Yo = Bakes Ry AAs a concrete example, suppose the register word is, Arde +++ Ay = 1110 0110 8 low INVERT gives an output word of YoYe0 + Yo = 100110 and @ high INVERT produces Yi¥,** + Yp = 0001 1001 ‘The controlled inverter of Fig. 3-21 is important. Later you will see how itis used in solving arithmetic and logie problems. For now, all you need to remember is the key ‘dea. The output word from a controlled inverter equals the T * + weer i xt U it y % % % 4 8 KH % 3-21 Controlled inverer. Chapter 3 More Logic Gates 41input word when INVERT is low; the output word equals the 1's complement when INVERT is high, Boldface Notation After you understand an idea, it simplifies discussions and cquations if you use a symbol, letter, or other sign to represent the idea. From now on, boldface letters will stand for binary words. For instance, instead of writing Arg? +> Ay = L110 0110 wwe can write A= 11100110 Likewise, instead of Ys ‘y= 0001 1001 the simpler equation Y = 0001 1001 ccan be used This is another example of chunking. We are replacing long strings like AyAy « *~ Ag and Y;Y« « ** Yp by A and. Y. This chunked notation will be convenient when we get to computer analysis, This is how to summarize the action of a controlled inverter: ‘A. when INVERT = 0 ‘A when JNVERT = | (Note: A boldface letter with an overbar means that each bit in the word is complemented; if A is a word, A is its 1's complement.) ‘3-7 EXCLUSIVE-NOR GATES ‘The EXCLUSIVE-NOR gate, abbreviated xNOR, is logically equivalent to an XoR gate followed by an inverter. For example, Fig. 3-22a shows a 2-input XNOR gate. Figure 3-22b is an abbreviated way to draw the same circuit. De SD oo Fig. 322 A 2-inputxvox gat: (a) circuit (b) abbreviated symbol #2 igitat Computer Electronics TWO-INPUT xNor GATE, Because of the inversion on the output side, the truth table of an xNOR gate is the complement of an xOR truth table. As shown in Table 3-9, the output is high when the inputs are the same. For this reason, the 2-input XNOR gate is ideally suited for bir comparison, recognizing when two input bits are identical. (Example 3-7 tells you more about bit comparison.) > fo ) =a) Fig, 323 non gates: (a) input; (b) input Figure 3-23a is the symbol for a 3-input xNoR gate, and Fig. 3-23b is the 4-input xNor gate. Because of the inversion fon the output side, these xNoR gates perform the comple- mentary function of XOR gates. Instead of recognizing odd: parity words, XNOR gates recognize even-parity words, EXAMPLE 3-7 ‘What dogs the circuit of Fig. 3-24 do? SOLUTION ‘The cireuitis a word comparator; it recognizes two identical words. Here is how it works, The leftmost xNoR gate compares Ay and Bs; if they are the same, ¥, is a 1. The second XNOR gate compares A, and By: if they are the same, Y,is.a 1. In turn, the remaining XNOR gates compare the bits that are left, producing a 1 output for equal bits and a 0 output for unequal bits. If the words A and B are identical, all xno gates have high outputs and the AND gate has a high EQUAL. I words A and B difler in one or more bit positions. the AND gate has a low EQUAL.couse Fig. 3:24 Word comparator. Acai Brose. a A, Ay ; ye GLOSSARY controlled inverter This cicuit produces the 1's comple- ‘ment of the input word. One pplication is binary subtrac- tion. It is sometimes called a programmed inverter. De Morgan’s theorems The first theorem says that a NOR gate is equivalent 10 a bubbled aND gate. The second theorem says that a NAND gate is equivalent to a bubbled or gate. even parity An even number of 1s ina binary word. NAND gate Equivalent to an AND gate followed by an inverter. All inputs must be high to get alow output Nor gate Equivalent to an oR gate followed by an inverter. All inputs must be low to get a high output. odd parity An oxld number of Is in a binary word, arity generator circuit that produces either an odd- or even-parity bit to go along with the data XNOR gate Equivalent to an EXCLUSIVE-OR gate followed by an inverter. The output is high only when the input word hhas even parity XOR gale AN EXCLUSIVE-OR gate. It has a high output only when the input word has odd parity. For a 2-input XOR gate, the output is high only when the inputs are different SELF-TESTING REVIEW Read each of the following and provide the missing words. Answers appear at the beginning of the next question, 1. A.Nor gate has two or more input signals. All inputs must be to get a high output, A NOR gate recognizes only the input word whose bits are The NOR gate is logically equivalent to an oR gate followed by an 2. (low, Os, inverter) De Morgan's first theorem says that a NoR gate is equivalent to a bubbled gate 3. (AND) ANAND gate is equivalent to an AND gate followed by an inverter. All inputs must be to get a low output. De Morgan's second theorem says that a NAND gate is equivalent to a bubbled gate 4. (high, on) An Xo gate recognizes only words with an —_____ number of Is. The 2-input xor gate has a high output only when the input bits are XOR gates are ideal for testing parity because even-parity words produce a output and odd-parity words produce a output (odd, different, low, high) An odd-parity generator produces an odd-parity bit to go along with the data Chapter 3 More Logic Gates 43‘The parity of the transmitted data is An oR gate can test each received word for parity, rejecting words with parity 6. (odd, even) A controlled inverter is a logic circuit that transmits a binary word or its com= plement. 7. (I's) The excLUSIVE-NOR gate is equivalent to an Xor gate followed by an inverter. Because of this, ceven-parity words produce a high output. PROBLEMS: 1. In Fig. 3-25a the two inputs are connected to- gether. If A is low, what is ¥? If A is high, what is ¥? Does the circuit act like a noninverter or an inverter? —t) >>" fa > (oy Fig. 3.25 3-2, What is the output in Fig. 3-25b if both inputs are low? If one is low and the other high? If both are high?” Does the circuit act like an OR gate or an AND gate? 3-3. Figure 3-26 shows a NoR-gate crossbar switch. If all X and ¥ inputs are high, which of the Z outputs is high? IF all inputs are high except X, and ¥,, which Z output is high? If X, and ¥y are Jow and all other inputs are high, which Z output is high? 34, In Fig. 3-26, you want Z, to be 1 and all other Z outputs to be 0. What values must the X and ¥ inputs have? 35. The outputs in Fig. 3-27 are cross-coupled back to the inputs of the NOR gates. If R = 0 and S = 1, what do Q and Q equal? ce of 3.27 Cross-coupled Non gates, 346, FR = Land § = 0 in Fig. 3-27, what does Q equal? Q? Prove that Fig. 3-28a and b are equivalent What is the output in Fig, 3-28a if all inputs are Os. Iall inputs are 1s? 3-9, What is the output in Fig. 3-28 if all inputs are Os. If all inputs are 1s? 3-10. A Nok has 6 inputs. How many input words are {nits truth table? What is the only input word that produces a 1 output? 3411. In Fig. 3-28a how many input words are there in the truth table? 3-12. What is the output in Fig. 3-29 if all inputs are ow? If all inputs are high? Fig. 3-26 son-gate crossbar switch 44 Digital Computer Electronics