Digital Computer Electronics (Malvino), Notas de estudo de Engenharia Informática

Baixe Digital Computer Electronics (Malvino) e outras Notas de estudo em PDF para Engenharia Informática, somente na Docsity! Digital Computer Electronics Third Edition Albert Paul Malvino, Ph.D. Jerald A. Brown GLENCOE McGraw-Hill New York, New York Columbus, Ohio woodland Hills, California Peoria, Illinois  This textbook was prepared with the assistance of Publishing Advisory Service LSI circuit photo: Manfred Kage:Peter Amold Inc. To my wife, Joanna, who encourages me to write. And to my daughters, Joanna, Antonia, Lucinda, Patrícia, and Miriam, who keep me young. —A.P.M. “to my wife Vickie dearest friend fellow adventurer love of my life —J.AB. Library of Congress Cataloging-in-Publication Data Malvino, Albert Paul Digital computer electronics * Albert Paul Malvino, Jerald A. Brown. — 3rd ed Pp em Includes index. ISBN 0-02-800594-5 (hardcover) 1. Electronic digital computers. 2. Microcomputers. 3. Intel 8085 (Microprocessor) |. Brown, Jerald A. Il. Title. TK7688.3.M337 1993 621.39'16-—dc20 92-5895 CIP Digital Computer Etectronies, Third Edition Imprint 1999 Copyright O 1993, 1983 by Glencos/McGraw-Hill. AI rights reserved. Copyright O 1983, 1977 by McGraw-Hill, Inc, AIl rights reserved. Printed in the Uniled States of America. Except as permittod under the United States Copyright Act, no part of fhis publication may be reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without prior written permission of the publisher. SBN 0-02-800594-5 Printed in the United States of America. 456789101112 004045 0302010089 PART 4 Microprocessor Instruction Set Tables 379 A. Expanded Table of 8085/8080 and Z80 (8080 Subset) Instructions Listed by Category 38] Mini Table of 8085/8080 and Z80 (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 (B080 Subset) Instructions Listed by Op Code 417 Condensed Table of 8085/8080 and Z80 (8080 Subset) Instructions Listed Alphabetically by 8085/8080 Mnemonie 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 422 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 444 c. Expanded Table of 8086/8088 Instructions Listed by Category 445 Condensed Table of 8086/8088 Instructions Listed by Category 465 Condensed "Fable of 8086/8088 Instructions Listed Alphabetically 469 D Expanded Table of 6502 Instructions Listed by Category 47 Short Table of 6502 Instructions Listed by Category 478 Condensed Table of 6502 Instructions Listed by Category 480 Condensed Table of 6502 Instructions Listed Alphabeticaly 48] 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 SK Intervals 9. Memory Locations: 4K Intervals 10. Memory Locations: 2K Intervals 1. Memory Locations: IK Intervals 12. Programming Models ANSWERS TO ODD-NUMBERED PROBLEMS 513 INDEX 519 Contents U Preface Textbooks on microprocessors are sometimes hard to un- derstand. This text attempts to present the various aspects of microprocessors in ways that arc understandable and interesting. The only prerequisite to 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 necds. 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 1 to 9. Featured topics include number systems, gates, boolean algebra. (lip-flops, registers, counters. and memory. This information prepares the student for the microprocessor sections which. follow. Part 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. Tt features an instruetion set which is a subset of that of the Intel 8085--leading naturally to à study of that microprocessor. Part 3, Programming Popular Microprocessors (Chapters 13 to 23), simultancously treats the MOS/Rockwell 6502, the Motorola 6800/6808, the Inte! 8080/8085 and Zilog 780, and the 16-hit Intel 8086/8088. Each chapter is divided into two sections, The first section presents new concepts: second section applies the new concepts to each micropro- cessor family. Discussion, programming examples, and problems are provided. The potential for comparative study is excellent This part of the text takes a strong programming approach to the study of microprocessors. Study is centered around the microprocessor's instruction set and programming model. The 8&-bit examples and homework problems can be per- formed by using cither hand assembly or cross-assemblers. The Ló-bit 8086/8088 examples and problems can be per- formed by using cither 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- mitting instructions to be looked up alphabetically. by op code, or by functional category, with varying levels of detail. The same functional categories arc correspondingly used in the chapters in Part 3. This coordination between parts makes the learning process easier and more enjoyable. Additional reference tables arc provided in the appen- dixes. Answers to odd-numbered problems for Chapters 1 to 16 follow the appendixes. A correlated laboratory manual, Experiments for Digital Computer Elecironics by Michacl A. Miller, is available for use with this textbook. Tt contains experiments for every part of the text. It also includes programming problems for each of the featured microprocessors A teachers manual is available which contains answers to all of he problems and programs for every micropro- cessor, In addition, a diskette (MS-DOS 360K 5!4-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 lab manual. And to Thomas Anderson of Speech Technologies Inc. for the use of his cross: mblers. Thanks also to reviewers Lawrence Fryda, Illinois State University; Malachi Me- Ginnis, Technical Institute, Garland Texas; and Ben- jamin Suntag. Albert Paul Malvino Jerald A, Brown A man of true 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 LISA DO DIGITAL PRINCIPLES AD 1 D NUMBER SYSTEMS AND CODES Modem computers don't work with decimal numbers. Instead, they process binary numbers, groups of Os and Is. Why binary numbers? Because electronic devices are most reliable when designed for two-state (binary) operation. This chapter discusses binary numbers and other concepts needed to understand computer operation. 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 try it. The Known Everyone has seen an odometer (miles indicator) in action, When a car is new. its odometer starts with 00000 After 1 mile the reading becomes O0001 Suecessive miles produce 00002, 00003, and so on, up to 00009 A familiar thing happens at the end of the tenth mile. When the units whcel turns from 9 back to O, a tab on this wheel forces the tens wheel to advance by 1. This is why the numbers change to 00010 Reset-and-Carry The units wheel has reset to O and sent a carry to the tens wheel. Lel's call this familiar action reser-and-carry. The other wheels also resct and carry. After 999 miles the odometer shows 00999 What does the next mile do? The units whec] resets and carries, the tens wheel resets and carries, the hundreds wheel rescts and carries, and thc thousands whec] advances by 1, to get 01000 Digits and Strings The numbers on each odometer whec] are called digits. The decimal number system uses ten digits, O through 9. In a decimal odometer, cach time the units wheel runs out of digits, it resets to O and sends a carry to the tens wheel. When the tens wheel runs out of digits, it resets to O and sends a carry to the hundreds wheel. And so on with the remaining whecls. One more point. À string is a group of characters (cither letters or digits) written one after another. For instance, 734 is a string of 7, 3, and 4. Similariy, 2CBA is a string of2,€C,8.andA. 1-2 BINARY ODOMETER Binary means two. The binary number system uses only two digits, O and 1. All other digits (2 through 9) are thrown away. In other words, binary numbers arc strings of Os and Is. An Unusual Odometer Visualize an odometer whose wheels have only two digits, U and 1. When each wheel turns, it displays 0, then 1, then 1 An analogy may help. A phonograph is like hardware and records are 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 are 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 (Bu, Tcos Em etc.) can vary more than 50 percent with temperature change und from one transistor to thc next. Yet these computer [Cs work remarkably well despite the transistor variations. How is it possible? The answer is two-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; cach transistor is forced to operate at either cutoff or saturation. When a transistor is 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-stute design. Figure 1-2 shows a Wwansistor 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 O V. The dark shading symbolizes the cutoff condition. The two transistors on the right have base drives of 5 V. The transistors operate at either saturation or cutoff. A base voltage of O V forces each transistor to cut off, while a base voltage of 5 V drives it into saturation. Because of this two-state action, cach transistor stays in a given state until the base voltage switches it to the opposite state. 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 O. and high voltage stands for binary t. In other words, we use this code: Voltage Binary Low o High 1 For instance, the base voltages of Fig. 1-2 are low-low- high-high, or binary 0011. The collector voltages are high- high-low-low, or binary 1100. By changing the base voltages we can store any binary number from 0000 to 11 1 (decimal Oto 15). Bit Bir is an abbreviation for binary digit. A binary number like 1100 has 4 bits: 110011 has 6 bits; and 11001100 bas 8 bits. Figure 1-2 is a 4-bit register. To store lurger binary numbers, it needs more transistors. Add two transistors and you get a 6-bit register. With four more transistors, you'd have 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 [rom high to low, the transistor cannot come out of saturation until these extra carriers have a chance to leave the base region. The time it takes for these carriers to leave is called the saruration delay time ty. Typically, t, is in nanoseconds. In mest applications the saturation delay time is too short to matter. But some applications require the fastest possible ov Fig. 1-2 Transistor register 4 Digital Computer Electronics +5V 1k82 1kM ov ov (Approx.) (Approx.) 1082 10k2 +5V 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 short of saturation). These nonsaturated circuíts rely on clamping diodes or heavy negative feedback to 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 cutput voltages are easily recognized as low or high, binary O or binary 1. ss2e sos 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 in a core even though the magnetizing current is removed (see Fig. 1-3h). This is why a core register can store binary data indefinitely. For instance, let's use the following code: Flux Binary Counterclockwise 0 Clockwise 1 Then, the core register of Fig. 1-3b stores binary 1001, equivalent to decimal 9. By changing the magnetizing currents in Fig. 1-34 we can change the stored data. To store larger binary numbers, add more cores. Two cores added to Fig. 1-3a result in a 6-bil 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 |; when it's open, it stands for binary O. 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 O. Using a prearranged code, à 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 row 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 à computer. Even the lights on the contro! panel of a large computer are binary; a light that's on stands for binary 1, and one that's off stands for binary O. In a 16-bit computer, for instance, à 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 uscd with computers are based ou 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 00001111 Row 5 NIGO1O Row 2 LOO0OL1O Row 6 01001001 Row 3 FOTO Row 7 NOLL Row d 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 00001 II. The second byte (row 2) is 10000110. The third byte is 1011011]. And so on. A byte is the basic unit of data in computers. Most computers process data in strings of 8 bits or some multiple (16, 24, 32, and so on), Likcwise, 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 leam is how to convert larger binary numbers to their decimal equivalents. slzfojasla 1 1 olola 10º 10? 102 ao! a? 4 prod A fa) tt) Fig. 1-5 (4) Decimal weights: (b) binary weighes. 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 al] digits multiplied by their weights gives the total amount being represented, For instance, Fig. 1-Sa ilustr: a decimal odometer, Below each digit is its weight. The digit on the right has a weight of 10º (units), the second digit bas a weight of 10! (tens), the third digit a weight of 10º (hundreds), and so forth. The sum of all units multiplied by their weights is 6 x 10%) + (7 x 10) + (0 x 102) + (3 x 10!) + (4x 10º) = 50,000 + 7000 + 0 + 30 + 4 = 57,034 Binary Weights Positional notation is also used with binary numbers because each digit position has a weight. Since only two digits are used, the weights are powers of 2 instead of 10. As shown in the binary odometer of Fig. 1-Sb, these weights are 2º (units), 2! (twos), 2? (fours), 2º (eights), and 2º (sixteens). Tf longer binary numbers arc involved, the weights continue in ascending powers of 2, The decimal equivalent of a binary number equals the sum of all binary digits multiplied by their weights. For instance, the binary reading of Fig. 1-5b has a decimal equivalent of 6 Digital Computer Electronics UXIMLAXMDAHOxBA+(Ox2) +(1x2)=16+8+0+0+1=25 Binary 11001 is therefore equivalent to decimal 25. As another example, the byte 11001100 converts to decimal as follows: Ux +(x2)+(0x2) + (0x2) +Ux20)+ dx 2 +(Ox2+(Ox 2) =128+6+0+0+8+4+0+0=0204 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. 2. 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: 1 1 1 0 1 (Write binary number) 28 4 2 1 (Write weights) 38 4 6 1 (Cross out weights) 4 8+4+0+1=13 (Add weights) You can compress the steps even further: L1 01 (Step 1) 84 2 1513 (Steps 2 to 4) As another example, here's the conversion of binary 1110101 in compressed form: Li 10101] 64 32 16 8 4 2 15117 Base or Radix The base or radix of a number system equals the number of digits it has. Decimal numbers have a base of 10 because digits O through 9 arc used. Binary numbers have à base of 2 because only the digits O and 1 are used, (In terms of an odometer, the base or radix is the number of digits on each wheel.) A subscript attached to a number indicates the base of the number. 100, means binary 100. On the other hand, 100, stands for decimal 100. Subscripts help clarify equa- tions where binary and decimal numbers are mixed. For instance, the last two examples o( binary-to-decimal con- version can be written like this: 1-8 HEXADECIMAL NUMBERS Hexadecimal numbers are extensively used in micropro- cessor work. To begin 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. Thc hexadecimal number system has a base or radix of 16. This means that it uses 16 digits to represent all numbers. The digits are O through 9, and A through F as follows: 0, 1,2,3,4,5,6,7,8,9,4,B, C,D, E, and F. Hexadecimal numbers arc 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 on its circumference. As it turns, it displays O 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 odometer. When a wheel turns from F back to 0, it forces the next higher wheet to advance by 1. In other words, when a wheel runs out of hexadecimal digits, it resets and carries. Tf uscd in a car, a hexadecimal odometer would cout as follows. When the car is new, the odometer shows all Os: 0000 (zero) The next 9 miles produce readings of 0001 tone) 8002 (two) 0003 (three) 0004 (four) 0005 (five) 0006 (six) 0007 (seven) 0008 (cight) 0009 (nino) The next 6 miles give OG0A (ten) 000B (eleven) 000€ (twelve) 000D (thirteen) OO0E (fourteen) 000F (fifteen) At this point the least significant wheel has run out of digits. Therefore, the next milc forces a reset-and-carry to get 0010 (sixteen) The next 15 miles produce these readings: O0Lt, 0012, 0013, 0014, 0015, 0016, 0017, 0018, 0019, O01A, 001B, 00IC, OOID, O01E, and OOIF. 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, 0024, 002B, 002C, 002D, 002E, and (O2F. You should have the idea by now. Each mile advances the least significant wheel by L. 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 835F 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. It's essential that you be able to convert instantly from onc system to another. TABLE 1-4, EQUIVALENCES Hexadecimal Binary Decimal o 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 010% 5 6 0110 6 7 OI 7 8 1000 8 9 1001 9 A 1010 10 B 10H q c 1100 12 D 101 13 E HO 14 F Ut 15 Chapter 1 Number Systems and Codes 9  1-9 HEXADECIMAL-BINARY CONVERSIONS After you know the equivalences of Table |-4, you can mentally convert any hexadecimal string to 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 A F Voo 1001 1010 IL As another example, CSE2 converts like this: Cos E 2 Dolo bo 1100 0101 10 0010 Incidentally, for casy reading if's common practice to leave a space between the 4-bit strings. For example, instead of writing CSE2, = 1100010111100010, we can write CSE2Z,, = 1100 0101 1110 0010, Binary to Hexadecimal To convert in the opposite direction, from binary to hexadecimal, you again use Table 1-4. Here are two examples. The byte 1000 1100 converts as follows: 1000 1100 vo 8 c The 16-bit number 1140 1000 1101 0110 converts like this: 110 1000 1101 010 Lodo doq E 8 Di é In both these conversions, we start with a binary number and wind up with the equivalent hexadecimal number. ÃO Digital Computer Electronics EXAMPLE 1-5 Solvc the following equation for x: Xs = 1141 1115 1111 1111, SOLUTION This is the same as asking for the hexadecimal equivalent of binary 1111 1111 1111 1111. Since hexadecimal F is equivalent to 1111, x = FFFF. Theretore, FFFF;, = ITAIM TT, EXAMPLE 1-6 As mentioned carlier, 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 tocations contain these bytes: 0011 1100 1100 1101 0101 0111 0010 1900 1111 0001 0030 1010 1101 0100 0100 0000 0111 0111 1100 0011 1000 0100 0010 1000 0010 0001 0011 1010 GO11 LI1O 0001 1111 Convert these bytes to their hexadecimal equivalents. SOLUTION Here are the stored bytes and their hexadecimal equivalents: Memory Contents Hex Equivalents 0011 1100 3€ 1100 1101 cD 0101 0111 57 0010 1000 28 1111 0001 Fi 0010 1010 2A 1101 0100 D4 0100 0000 40 0311 0111 ” 1100 0011 c3 1000 0100 84 G010 1000 28 0010 0601 2a 0011 1010 3A 0011 1110 3E 0001 1111 1F 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 can say that the first memory location contains QO11 1100, or wc can say that it contains 3C. Either string gives the same information. But notice how much casier it is to say, write, and think 3C than it is to say, write, and think 0011 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 particular bytes. What we have just done is known as chunking. replacing longer strings of data with shorter ones. At the first memory location we chunk the digits 0011 1LOO 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 as A7 28 c3 19 SA ap 2C F8 What are the binary contents of the memory locations”? SOLUTION Convert from hexadecimal to binary to get 1010 6111 0040 1000 1100 6011 0001 1001 0101 1010 0100 1101 BOI1O 1100 H11 1000 The lirst memory location stores the byte 1010 0111, the second memory location stores the byte 0010 1000, and so em. This cxample emphasizes a widespread industrial prac- tice. Microcomputers are programmed to display chunkcd data, often hexadecimal. The user is expected to know hexadecimal-binary conversions. In other words, a computer manufacturer assumes that you know that A7 represents 1010 0111, 28 stands for 0010 1000, and so on. One more point. Notice that each memory location in this example stores 1 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 3€ to its binary equivalent: 3 c b b 0011 1100 Step 2. Convert 0011 1100 to its decimal equivalent: 0 0 1/1 1 00 128 44 32 16 8 Z 1>60 sm Therefore, decimal 60 is equivalent to hexadecimal 3C. As an equation, 3Cj = 0011 1100, = 604 Positional-Notation Method Positional notation is also used with hexadecimal numbers because cach 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 2 9 4 5 Lobo pod 0010 1001 0100 O101 As you see, each decimal digit is coded as a nibble. Here's another example: 9,863, converts like this: 9 8 6 3 Vo Lo lou 101 1000 OLIG 0011 Therefore, 1001 1000 0110 001] is the BCD equivalent of 9,863. The reverse conversion is similar. For instance, 0010 1000 0111 0100 converts as follows: GIO 1000 OL! 0100 LoL Vo q 2 8 7/4 Applications BCD numbers are useful whercver 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 or 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 early computers processed BCD numbers but were slower and more complicated than binary computers. As previously mentioned, a computer is more than a number cruncher because it must handle names and other nonnumeric data. In other words, a modem computer must be able to process alphanumerics (alphabet letters, numbers, and other sym- bols). This why modem 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. Abovc 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 thcy represent the same number of pebbles. Machines have to use long strings of binary or BCD numbers, but people prefer to chunk the data in cither 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 o 0000 UO00 0000 0000 0000 1 1 0000 0001 0000 0000 000 2 2 0000 0010 0000 0000 DOLO 3 3 0000 0011 0000 0000 001 + 4 4 0000 0100 0000 0000 0100 5 5 0000 0101 0000 0000 010% 6 6 0000 0110 0000 0000 0110 7 7 0000 0111 0000 0000 0111 8 8 OD0O 1000 0000 0000 1000 9 9 0000 100? 0000 0000 1001 10 A GO0O 1010 0000 0001 0000 nu B 0000 1011 0000 0001 0001 12 c 0000 1100 0000 0001 0010 13 D 0000 1101 0000 000t 0011 14 E 0000 1110 0000 0001 0100 15 F 0000 11110000 0001 0101 16 10 0001 0000 0000 0001 0110 32 20 0010 0000 0000 011 0010 4 40 0100 0000 0000 0110 0100 128 so 1000 0000 000! 0010 1000 255 FF HI JUL QOIO 0101 0101 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 to use numbers, letters, and other symbols. This implies some kind of alphanumeric code for the I/O 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 Interchange (abbreviated ASCID. This code allows manufacturers to standardize VO hardware such as keyboards, printers, video displays. and so on. The ASCII (pronounced ask'-ee) code is a 7-bit code whose format (arrangement) is XMGK KKK 1Xo where cach X isa O ora |, For instance, the letter A is coded as 1000001 Sometimes, a space is inscrted for easier reading: 100 0001 TABLE 1-6. THE ASCI CODE XçXsk, XXX ——— EH 010 OM 100 101 110 1 0000 Ss: 0 & P p 0001 ! OA Q aq oo1o ro 2 BR bor oo 3 CC Si cos 0100 Ss 4 DD TÕõada t o101 mos EU eu ono & 6 Fo v o fos ou : 7 GG Wo g w 1000 Cos Ho X box 1001 DD To yr dos tO1O * : Jo Zoo jog 1015 + 2 K k 100 Vo 4 L 1 101 - = M m 110 e >» N n mm / 2.0 o Table 1-6 shows the ASCH code, Read the table the same us a graph. For instance, the letter A has an XçXsX, of 100 and an X;X,X,Xy of 0001, Therefore, its ASCII code is 190 0001 (A) Table 1-6 includes the ASCIE code for lowercasc letters. The letter a is coded as 110 0001 (a) More examples arc 1100010 (b) 1100011 (e) 1100100 (dy and so on. Also look at the punctuation and mathematical symbols. Some examples are 0100100 (8) 010101 (+) ONO! (=) In Table 1-6, SP stands for space (blank). Hitting the space bar of an ASCII keyboard sends this into a microcomputer: 010 0000 (space) EXAMPLE 1-11 With an ASCII keyboard, each keystroke produces the ASCII equivalent of the designated character. Suppose you type PRINT X What is the output of an ASCTI keyboard? SOLUTION P (101 0000), R (101 00103, I (100 1001), N (100 1110), T (101 0100), space (010 0000), X (101 1000). GLOSSARY address Each memory location has an address, analogous toa house address. Using addresses, we can tell the computer where desired data is stored. alphanumeric Letters, numbers, and other symbols. base The number of digits (basic symbols) in a number system. Decimal has a base of 10, binary a base of 2, and hexadecimal a base of 16. Also called the radix. bit An abbreviation for binary digit. byte A string of 8 bits. The byte is the basic unit of binary information. Most computers process data with a length of 8 bits or some multiple of 8 bits. central processing unit The control section and the arith- metic-logic section. Abbreviated CPU, chip An integrated circuit. chunking Replacing a longer string by a shorter one. data Names, numbers, and any other information needed to solve a problem. digital Pertains to anything in the form of digits, for example, digital data. hardware The electronic, magnetic. and mechanical de- vices used in a computer. hexadecimal A number system with a base of 16. Hexa- decimal numbers are used in microprocessor work. input-output Abbreviated O. The input and output sec- tions of a computer are often lumped into one unit known as the O unit. microcomputer A computer that uses a microprocessor for its central processing unit (CPU). microprocessor A CPU on a chip. It contains the control and arithmetic-logic sections. Sometimes abbreviated MPU (microprocessor unit). nibble A string of 4 bits. Half of a byte. program A sequence of instructions that tells the computer how to process the data. Also known as software. register A group of electronic, magnetic, or mechanical devices that store digital data. sofiware Programs. string A group of digits or other symbols. Chapter 1 Number Systems and Codes 15 SELF-TESTING REVIEW Read each of the following and provide the missing words. 7. (4,096, 65,536) The hexadecimal number system is Answers appear at the beginning of the next question. widely used in analyzing and programming 1 : Bina bers have é The hexadecimal digits are O to 9 and A to - Binary means —— - Binary numbers have à The main advantage of hexadecimal numbers is the base of 2. The digits used in a binary number case of conversion from hexadecimal to system are and MA mtas int . and vice versa. 2z (mos Ê 2 Dumes, aupper, ne oer information 8. (microprocessors, F, binary) A typical microcom- The ed to solve à Pro em are = e : ha . puter may have up to 65.536 registers in its mem- e Ss a sequence of instructions that ory. Each of these registers, usually called a tells the computer how to process the data. stores 1 byte. Such a memory is specified as a 64- 3. (data, program) Computer ICs work reliably be- kilobyte memory, or simply à memory cause they are based on design. When 9. (memory location, 64K) Binary-coded-decimal a transistor is cut off or saturated, transistor (BCD) numbers express each decimal digit as a 4 u Deve pinos no efiect. . f BCD numbers are useful whenever im . a o aa Esto no ) dat sa Broup o formation is transferred into or out of a digital pbrevi dio oi ter a A byte is à ri as f system. Equipment using BCD numbers includes abreviar O teit. À byte is a string o pocket caiculators, electronic counters, and digital - ES. , , , voltmeters. 5. (register, Bit, 8) The control and arithmetic-logie 10. (nibble, decimal) The ASCII code is a 7-bit code sections are called the (CPU). A micro- tor (letters, numbers, and other sym- processor is a CPU on a chip. A microcomputer bols) . . : is a computer that uses a — for its CPU. 11. (alphanumerics) With the typical microcomputer, 6. (central processing unit, microprocessor) The ab- you enter the program and data with typewriter breviation K indicates units of approximately 1,000 keyboard that converts each character into ASCIE or precisely 1,024. Therefore, LK means 1.024, 2K code - means 2,048, 4K means » and 64K . means PROBLEMS 1-1. How many bytes are there in each of these num- O e O e O O 0 o bers? = . . a 11000101 Fig. 1-8 An 8-bit LED display. TOLDO UH 1010 1.7. Figure 1-8 shows an 8-bit LED display. A light ; : . circle mcans that a LED is ON (binary 1) and a 1-2, What are the equivalent decimal numbers for each dark cirele means a LED is or (binary 0). What of the following binary numbers: 10, 110, 1, : o sr : tOLt, 1100, and 1110? a squi being displayed? The deci- I&. Vias x Me base for ench of these numbers? 18. Convert the following binary numbers to decimal . 10 . b. 11000101, e s dáils b. 11001 do MCh e. 1010 1-4. Write the equation . do HO 24+2=4 1-9, Solve the following equation for x: o xi = 1001001, using binary numbers. 1-5. What is the decimal equivalent of 2/7 What does 1.10. An 8-bit transistor register has this output: 4K represent? Express 8,192 in K units. low-high-low-high-low-bigh-low-high 1.6. A 4-bit register has output voltages of high-low- ow-mgh-low-high-low-high-low-hig high-low. What is the binary number stored in the What is the equivalent decimal number being register? The decimal equivalent? stored? 16 Digital Computer Electronics  GATES For centuries mathematicians felt there was a connection between mathematics and logic, but no onc before George Boole could find this missing link, In [854 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 it to analyze telephone switehing circuits. He let 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) círcuits because the input and output signals are either 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 Vix is low (approximately O V), the transistor cuts off and Vowr is high. On the other hand, a high Viy saturates the transistor, forcing Vour to go low. Table 2-1 summarizes the operation. A low input produces a high output, and a high input results in à low output. Table 2-2 gives the same information in binary form; binary O stands (or low voltage and binary 1 for high voltage. An inverter is also called a NOT gate becausc the output is not the same as the input. The output is sometimes called the complemen: (opposite) of the input. +5V Your hu >10 (00r+5 V) Fig. 2-1 Example of inverter design. TABLE 2-1 TABLE 2-2 Vin Vocr Va Vorr Low High 0 1 High Low 1 o va DO Your Yin « D— “our fal b) fes ta) Fig, 2-2 Logic symbols: (a) inverter; (b) another inverter symbol: (c) double inverter; (d) buffer Inverter Symbol Figure 2-2a is the symbol for an inverter of any design. Sometimes a schematic diagram will use the altemative symbol shown in Fig. 2-2b; the bubble (small circle) is on 19 the input síde. Whenever you see either of these symbols, remember that the output is the complement of the input. Noninverter Symbol If you cascade two inverters (Fig. 2-2c), you get a nonin- verting amplifier. Figure 2-2d is the symbol for a nonin- verting amplificr. Regardless of the 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 buffcring (isolating) two other circuits. More will be said about buffers in a later chapter. EXAMPLE 2-1 o o eb Gta register 1 cegister o fa) tor Fig. 2-3 Example 2-1 Figure 2-3 has an output, A to F, of 100101. Show how to complement cach bit. SOLUTION Easy. Use an inverter on cach signal line (Fig. 2-3b). The final output is now OLLOIO, A hex inverter is a commercially available IC containing six separate inverters. Given a 6-bit register like Fig. 2-3a, we can connect a hex inverter to complement each bit as shown in Fig. 2-3b. One more point. In Fig. 2-3a 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-3 the word 100101 is complemented to get the word OHO10. 2-2 or GATES The OR gate hus two or more input signals but only one output signal. If any input signal is high, the output signal is high. 20 Digital Computer Electronics A0———D— Y pop Fig. 2-4 A 2-input diode OR gate Diode oR Gate Figure 2-4 shows one way to build an OR gate. If both inputs are low, the output is low, If cither 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 O 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. 40H so—D—s Y co—p Fig. 25 A 3-input diode OR gate. More than Two Inputs Figure 2-5 shows à 3-input OR gate. If all inputs arc low, all diodes are off and the output is low. ff 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, . .., 111): this guarantees that all input possibilities will be accounted for. An OR gate can have as many inputs as desired; add one diode foé cach additional input. Six diodes result in a 6- TABLE 2-3. TABLE 2-4. THREE- TWO INPUT INPUT or GATE or GATE — A B Cc Y A B Y Doo F— 0 0 0 0 o 0 o 0 o 1 1 0 1 1 0 1 0 1 1 o 1 0 1 1 1 1 1 1 1 0 o i 1 0 1 1 1 l 0 1 1 1 1 1 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 MOSFETSs can also be used to build or 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. fo tb) tes Fig. 2-6 or-gate symbols. EXAMPLE 2-2 Show the truth table of a 4-input OR gate, SOLUTION Let Y stand for the output bit and 4, B, C, D for input bits Then the truth table has input words of 0000, (001, 0010, “las shown in Table 2-5. As expected, output Y is O for input word 0000; Y is | for all other input words. As a check, the number of input words in a truth table always cquals 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 OR gate has 2? or 8 input words; and a 4-input oR gate has 2* or 16 input words. TABLE 2-5. FOUR-INPUT or GATE Frrmuu no GOSOO DO | rem“ 900C0n4n Soco |ty -o-oro-0o-65-cno-o|y Wonuncceronnn-—o =| -"n0090--99--00--o EXAMPLE 2-3 How many inputs words are in the truth table of an 8-input OR gate? Which input words produce a high output? SOLUTION The input words are 0000 0000, 0000 0001, ..., IIIL 1111, With the formula of the preceding example, the total number of input words is 2" = 28 = 256. In any OR gate, 1 or more high inputs produce a high output. Therefore, the input word of 0000 0000 results in a low output; all other input words produce a high output. EXAMPLE 2-4 +5V | H é + —-+ Er A e——————+ + — e 9 —— [ e Do db di % % Y Y Fig. 2-7 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;YiYo. What does the circuit do? SOLUTION Figure 2-7 is a decimal-to-binary encoder, a circuit that converts decimal to binary. For instance, when push button 3 is pressed, the Y, and Yy OR gates have high inputs: therefore, the output word is YaYaYiYo = 0011 Chapter2 Gates 21 FAiso, Y=NnorO On the other hand, if A is 1, Y=noTl=b0 H In boolean aígebra, thc overbar stands for the NOT operation. This means that Eg. 2-1 can be written VP=A (2-2) Read this as *“Y equals NOT A” 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 o[A, substitute and solve for Y. For instance, il A is O, y=4=D=1 because NoT O is 1. On the other hand, if A is 1, y-4=1-=0 because NOT 1 is 0. A Y 8 Fig. 2-13 OR gate. or Sign A word equation for Fig. 2-13 is V=40RB (23) Given the inputs, you can solve for the output. For instance, i£A = Oand B = 0, Y=00r0=0 because O comes out of an OR gate when both inputs are Os. As another example, if A = OandB = 1, Yr=00r1l=1 because 1 comes out of an OR gate when either input is 1. Similarly, 74 = LandB = 0, Y=loro FA =landB=1, Y=lori=1 24 pigital Computer Electronics In boolean algebra the + sign stands for the OR operation. In other words, Eg. 2-3 can be written V=4A+B (2-4) Read this as “'Y equals A OR 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 A = O and B = 0, Y=A+8=0+0=0 WA =OandB=1, 1 VF=A+B=0+1 because O ored with 1 results in !. ITA = land B = 0, F=A+B=1+0 Tf both inputs are high, Y=A+B=]+1 because 1 ored with 1 gives 1. Don't let the new meaning of the + sign bother you. There's nothing unusual about symbols having more than one meaning. For instance, “pot” may mean a cooking utensil, a flower container, the moncy 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 + sign may stand for ordinary addition or oR 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 OR addition. ; [ Y 8— Fig. 2-14 AND gate AND Sign A word equation for Fig. 2-14 is Y=AANDB (2-5) In boolcan algebra the multiplication sign stands for the AND operation. Therefore, Eq. 2-5 can be written r=A:B or simply Y=AB (2-6) Read this as ““Y cquals 4 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=A48=0:0=0 because O ANDed with O gives 0, IA is low and B is high, Y=A8=0-1=0 because O comes out of an AND gate if any input is O. IF A island Bis 0, Y AB= 1. When both inputs are high. Y=AB=1-1=1 because 1 ANDed with 1 gives 1. Decision-Making Elements The inverter, oR gate, and AND gate are often called decision-making elements because they can recognize somc 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 Os; it recognizes only the word whose bits arc all Is. Notation Tn 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 (4, B, Y, etc.) for ANDed bits and roman (upright) letters (A, B, Y, ctc.) for bits that form a word, For example. YF.Y,Yy stands for the logical product (anDing) of Ps. PY, and Yo ÉY=1,7=0,Y= O, and Yy = 1, the product Y;Y.Y,Y, will reduce as follows: In this case, the italic letters represent bits that are being ANDed. On the other hand, Y;Y,Y,Yo is our notation for a 4-bit word. With the Y values just given, we can write YtoY Yo = 1001 In this equation. we are not dealing with bits that are ANDed; 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 | stands for the morc negative of the two voltage levels. For instance, if the two voltage levels are O and —5 Y, positive logic would have 1 stand for O V and O for —5 V, whereas negative logic would have 1 stand for —5 V and O for O V. Ordinarily, people use positive logic with positive supply voltages and negative logic with negative supply voltages. Throughout this book, we will bc using positive logic. EXAMPLE 2-7 4 8 Y AS Y s+ >» Fig. 2-15 Logic circuits What is the boolean equation for Fig. 2-15a? The output if both inputs are high? SOLUTION A is inverted before it reaches the OR gate; therefore. the upper input to the OR gate is 4. The final output is This is the boolcan eguation for Fig. 2-15a. To find the output when both inputs are high, either of two approaches can be used. First, you can substitute directly into the foregoing equation and solve for Y Alternatively, you can analyze the operation of Fig. 2-154 like this. If both inputs are high, the inputs to the OR gate are O and 1. Now, O orcd with 1 gives 1. Therefore, the final output is high. EXAMPLE 2-8 What is thc boolean equation for Fig. 2-155? If both inputs arc high, what is the output? Chapter2 Gates 25 SOLUTION The AND gate forms the logical product 48, which is inverted to get AB Read this as ““Y equals NOT AB” or “Y equals the complement of AB. Wboth inputs are high, direct substitution into the equation gives y=AB=1-I=1=0 Note the order of operations: the ANbing is done first, then the inversion. Instead of using thc equation, you can analyze Fig. 2-15b as follows. If both inputs are high, the AND gate has a high output. Therefore, the final output is low, EXAMPLE 2-9 8 cc faj sp" tb) Fig. 2-16 Logic cireuits. What is the boolean equation for Fig. 2-164? 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 oR CD.” Next, look at Fig. 2-164. The final output is high if the OR gate has one or more high inputs. This happens when ABisl.CDis 1, or both are Is. In turn, AB is | when A=1 and B=1 26 Digital Computer Electronics TABLE 2-8, TRUTH TABLE FOR Y = AB + CD 4 B c D Y 0 0 o 0 0 o 0 0 1 0 o 0 1 o o o 0 1 1 1 0 1 0 o o 0 1 o 1 0 o 1 1 0 0 0 1 1 1 1 1 0 o 0 0 1 o o 1 o 1 o 1 0 o 1 0 1 1 1 1 1 o 0 1 1 1 o 1 1 1 1 1 0 1 1 1 1 1 1 CD is 1 when C=1 and D=1 Bath products are Is when A=1 B=1 C=1 and D=1 Therefore, the final output is high when A and 8 are Is, when C and D are Is, 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, 1015, 1100, 1301, 1110, and TH. EXAMPLE 2-10 Write the boolean equation for Fig. 2-16h. 1f all inputs are high, what is the output? SOLUTION The OR gate forms the logical sum 8 + €. This sum is ANDed with A to get Y=A(BA+C) (Parentheses indicate ANDing.) One way to find the output when all inputs are high is to substitute and solve as follows: FP=AB+O=KI+D=hH1)=1 +5V Y% Fig. 2-18 Hexadecimal encoder. E-bit register A Y a) ENABLE A Fi A >o— y c G % % Ya Y % r % (by Fig. 2-19 Fig. 2-20 211, The 8-bit register of Fig. 2-19 stores 59. What 2-13. What is the boolean equation for Fig. 2-204? The is the decimal equivalent of the fina! output word output if both inputs are high? if ENABLE = 0? If ENABLE = |? 2-14. If all inputs arc high in Fig. 2-20b, what is the 2-12. Answer these questions: output? The boolean equation for the circuit? a. What input words does a 6-input OR gate What is the only ABC input word the circuit recognize” What word does it disregard? recognizes? b. What input word does an &-input AND gate 2:15. 1 you constructed the truth table for Fig, 2-20b, recognize? What words does it disregard? how many input words would it contain? Chapter2 Gates 29 Instruetion register LDA ADO SsuB Fig. 2-21 STA LDxX me JAM JaL sm A 8— Y cc tb uz Fig. 2:22 JUS DsZ 1sZ Mix oPR Fig. 2-25 A 1-ol-16 decoder. Y Y A - 8 e D Fig. 2-24 30 Digital Computer Electronics 2-16. 217. 2-18. 219. 2-20. 2-21. 222. What is the boolean equation for Fig. 2-214? The output if both inputs arc high? Hall inputs are high in Fig. 2-21b, what is the output? What is the boolean equation of the cir- cuit? What ABC input words docs the circuit recognize? What is the only word it disrcgards? What is the boolcan eguation for Fig. 2-2247 The output if all inputs are 1s? If you were tô con- struct the truth table, how many input words would it have? Write the boolean equation for Fig. 2-22h. Tf all inputs are 1s, what is the output? H both inputs are high in Fig. 2-23, what is the output? What is the boolean equation tor the cir- cuit? Describe the truth table. What is the boolean equation for Fig. 2-24? How many ABCD input words arc in the truth table? Which input words does the circuit recognize? Because of the historical connection between bool- can algebra and logic, some people use the words “true” and “false” instead of “high” and “Jow” 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? b. What is the output in Fig. 2-23 if one input is false and the other true? e. In Fig. 2-23 what is the output if all inputs are true? 2-23. 2-24. 2-25. 2-26. 227. Figure 2-25 shows a 1-0f-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 = Lilly; a. If LDA is high, what does OP CODE equal? b. 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 = 111? In Fig. 2-25, list the OP CODE words and the corresponding high output signals. (Start with 0000 and proceed in binary to Lt.) In the following equations thc eguals sign mcans “is equivalent to.” Classify each of the following as positive or negative logic: a 0=0Vandl=+5YV. b. +5 Vandi = 0V. ce 0= -5Vandl=0V. d 0=0Vandl= 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 lines? How many output lines from the decoder would be needed to have 256 op codes? Chapter2 Gates 31  Da, e ED its Fig, 3-4 Ann gate with invertod 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 anbing. LM Figure 3-5 is a graphic summary of De Morgan's first theorem. A NOR gate and a bubbled AND gate are equivalent. As shown later, because the circuits are interchangeable. you can often reduce complicated logic circuits to simpler forms. Fig, 3-5 De Morgan's first theorem. More than Two Inputs When 3 inputs are involved, De Morgan's first theorem is written A+B+C=ABC (3-5) For 4 inputs ATB+C+D=ABCD (3-6) In both cases, the theorem says that the complement of a sum equals the product of the complements. GD LD Fig. 3-6 De Morgan's first thcorem: (a) 3-input circuits: (b) 4- input circuits. dl Lily 34 Digital Computer Electronics Here's what really counts. Equation 3-5 says that a 3- input NOR gate and a 3-input bubbled AND gate arc equivalent (see Fig. 3-6a). Equation 3-6 mcans that a 4-input NOR gate and a 4-input bubbled AND gate are equivalent (Fig. 3-6b). Memorize these equivalent circuits: 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. 1 EXAMPLE 3-1 Prove that Fig. 3-7a and c are equivalent. (by fel Fig. 3.7 Equivalent De Morgan cireuits. 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-7b. Doubic inversion produces noninversion; therefore, cach double inversion in Fig. 3-7b cancels out, lcaving the simplified circuit of Fig. 3-7c. Figure 3-7a and c 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 enables 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.  [DD é [e fe tb Fig. 3-8 NAN gate: (a) logical meaning; (b) standard symbol. Two-Input Gate Figure 3-84 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 as a NAND gate. Figure 3-8h 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. As shown, the NAND gate recognizes any input word with one or more Os. That is, one or morc low inputs produce a high output. The boolean equation for a 2-input NAND gate is V=AB (3-7) Read this as “Y equais NOT AB.” If you use this equation, remember that the ANDing is done first then the inversion. A : Di c > cc CA 5 — fa) ty Fig. 3-9 NaND gates: (a) 3-input: (b) 4-input. Three-Input Gate Regardless of how many inputs a NAND gate has, it's still logically equivalent to an AND gate followed by an inverter. For example, Fig. 3-94 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-9u. If one or more inputs are low, the result of ANDing is low; therefore, the final output is high. Tf all inputs are high, the ANDing gives a high signal; so the final output is low. Table 3-6 ís the truth table for a 3-input NAND gate. As indicated, the circuit recognizes words wilh one or more Os. This means that one or more low inputs produce a high output. TABLE 3-5, TABLE 3-6, THREE- TWO-INPUT INPUT NaND GATE NAND GATE A B €| ABC A B| AB 0 00 1 0 0 1 o 01 1 01 1 o 10 1 10 1 o 1d 1 Va 0 10 0 1 1 0 1 1 Li o 1 [O o 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 baolcan equation is Y= ABCD (3-9) If you construct the truth table, you will have input words from 0000 to TH. All words from 0000 through [10 produce a 1 output; only the word 1111 gives a O 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 > (3-10) In words, the complement of a product cquals the sum of the complements. The Jefl member of this equation repre- sents a NAND gate (Fig. 3-10a); the right member stands A Y Y Ds ta) tb) A Y 8 te) Fig. 3-10 De Morgan's second tncorem: (2) NAND gate; (b) OR gate with inverted inputs; (c) bubbled OR gate Chapter3 MoreLogic Gates 35 for an OR gate with inverted inputs (Fig. 3-10h). Therefore, De Morgan's second theorem boils down to the fact that Fig. 3-104 and b are equivalent. 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 written C=A+B+C (GD) 1f 4 inputs arc used, ABCD =A+B+C+D (3-12) These equations say that the complement of a product equals the sum of the complements. AP ED D-- o) Fig. 3-12 De Morgan's second theorem: (a) 3-input circuits; (b) 4-input circuits. Figure 3-12 is a visual summary of the second theorem. Whether 3 or 4 inputs arc involved, a NAND gate and à bubbled oR gate arc equivalent (interchangeable). 36 Digita! Computer Electronics EXAMPLE 3-2 Prove that Fig. 3-13a and e are equivalent. tb) Po VA te) Fig, 3-13 Equivalent circuits. SOLUTION Replace the final NAND gate in Fig. 3-134 by a bubbled or gate, This gives Fig. 3-13b. The double inversions cancel out, leaving the simplified circuit of Fig. 3-13c. Figure 3-13a and e 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-13» easier to analyze than Fig. 3-134. For this reason, if you build Fig. 3-134, draw the circuit like Fig. 3-13b. Anyone who sees Fig. 3-13b on a schematic diagram knows that the bubbled OR gate is the same as a NAND gate and that the built-up circuit is two NAND gates working into a NaND gate. EXAMPLE 3-3 Figure 3-14 shows a circuit called a contro! matrix. At first, it looks complicated, but on closer inspection it is relatively simple because of the repetition of NAND gates. De Morgan's theorem tells us that NAND gates driving NAND gates are equivalent to AND gates driving OR gates. The upper set of inputs 7, to Ts are called ziming signats; only one of them is high at a time. T, goes high first, then T>, then 7;, 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 at a time. The outputs Cp, Ep, Lm, -.., to Lo control different registers in the computer. Answer the following questions about the control matrix: a. Which outputs are high when Ty is high? b. JfT, and LDA are high, which outputs are high? e. When T; and SUB are high, which outputs are high? TABLE 3-8. FOUR-INPUT xor GATE Comment Even Odd Odd Even Odd Even Even Odd Odd Even Even Odd Even Odd Odd Even —-"no006/|m =“——“n“-Sooo0o0o00c0 |» r=90-nSo-ros--oa q mr 0" Sor somo-o-o|y orvonconrroç-c-ro|m 0 0 0 1 1 1 1 PD far to) Fig. 3-17 xOR gates: (4) 3-input; (b) 6-imput. 3-17a shows the abbreviated symbol for a 3-input XOR gate, and Fig. 3-17h is the symbol for a 6-input xoR gate. The final output of any XOR gate is the xOR sum of the inputs: VY=AB8BOBC-: (-17) What you have to remember for practical work is this: an XOR gate, no matter how many inputs. recognizes only words with an odd number of Is. Parity Even parity means a word has an cven number of Is. For instance, 110011 has even parity because it contains four ls. Odd parity means a word has an odd number of Is. As an example, 110001 has odd parity because it contains three 1s. Here are two more examples: 11110000 1311 0011 11410000 11110311 (Even parity) (Odd parity) The first word has even parity because it contains ten 1s; the second word has add 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 101 16bits oDD Fig. 3-18 Odd-parity tester SOLUTION a. The word has seven Is, an odd number. Therefore, the output signal is oDDb = 1 b. The word has eight Is, an even number. Now ODD = 0 This is an example of an odd-parity tester. An even- parity word produces a low output. An odd-parity word results in a high output. Doll EXAMPLE 3-5 The 7-bit register of Fig. 3-19 stores the letter A in ASCII form. What does the 8-bit output word equal? Chapter 3 More Logic Gates 39  7bit register Odd-parity DE bit Instruction or data bits ul DS 8-bit word with odd parity Fig. 3-19 Odd-parity generator. SOLUTION The ASCII code for letter A is 100 0001 (see Table 1-6 for the ASCII code). This word has an even parity, which means that the xOR gate has a O output. Because of the inverter, the overall output of the circuit is the 8-bit word 1100 0001 Notice that this has odd parity. The circuit is called an odd-parity generator because it produces an 8-bit output word with odd parity. If the register word has even parity, O comes out of the xoR gate and the odd-parity bit is 1. On the other hand, if the register word has odd parity, a 1 comes out of the XOR gate and the odd- parity bit is O. 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 in transmitted data. For instance, the letter A may be transmitted over phone lines in ASCIT form: 100 0001 (A) Somewhere along the line, one of the bits may be changed. If the X, bit changes, the received data will be 100 0011 (O) 40 Digital Computer Electronics Because of the 1-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 wben it is received. KH no error has occurred, the xOR gate will recognize the word. On the other hand, if a 1-bit error has crept in, the xor gate wili disregard 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 thc circuit of Fig. 3-20 do? A INVERT Y Fig. 3-20 SOLUTION When INVERT = OandA = 0, Y=000=0 When INVERT = OandA = 1, Y=001=1 In either case, the output is the same as A; that is, Y=A for a low INVERT signal. On the other hand, when INVERT = landA = 0, r=100=1 When INVERT = LandA = 1, r=1€1=0 This time, the output is the complement of 4. As an equation, Y=A for a high /NVERT signal. To summarize, the circuit of Fig. 3-20 does either of two things. It transmits 4 when INVERT is O and À when INVERT is 1, 3-6 THE CONTROLLED INVERTER The preceding example suggests the ídea of a controlled inverter, a circuit that transmits a binary word or its 7's complement. The 1's Complement Complement each bit in a word and the new wotd you get is the 1's complement. For instance, given 1100 0111 the 1ºs complement is OOLL 1000 Each bit in the original word is inverted to get the L's complement. The Circuit The xOR gates of Fig. 3-2] form a controlled 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 XoR gate acts like this. A low INVERT results in r, = A, and a high INVERT gives F, So each bit is cither transmitted or invertcd before reaching the final output. Visualize the register contents and the final output as a word Y. INVERT means word AA, Ag 677" Yo. Then a low NY To = AA A On the other hand. a high INVERT results in Yet Yo = AÃo Ao As a concrete example, suppose the register word is AA Ap = MIOONO Then, a low /NVERT gives un output word of YWYe cc Yo = LO ONO and a high INVERT produces YiYe rc Yo = 0001 1001 The controlled inverter of Fig. 3-21 is important. Later you will see how it is used in solving arithmetic and logic problems. For now, all you necd to remember is the key idea. The output word from a controlled inverter equals the E-bit register Av Ao Ag Aa Ay Ay Ay Ay , INVERT Pooh MM MR no Y% Fig. 3-21 Controlled inverter. Chapter 3 More Logic Gates 41  The parity of the transmitted data is XOR gate can test each received word for parity, rejecting words with parity. 6. (odd, even) A controlled inverter is a logic circuit that transmúts a binary word orits— com plement. 7. (J's) The ExciusIvE-NOR gate is equivalent to an xoR gate foltowed by an inverter. Because of this, even-parity words produce a high output. PROBLEMS 3-4, In Fig. 3-25a the two inputs are connected to- gether. 1f A is low, what is Yº? If A is high, what is Y? Does the circuit act like a noninverter or an inverter? ED) —r fa) ao o 8 Y tb) 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. H all X and Y inputs are high, which of the Z outputs is high? If all inputs ave high except X, and Y>, which Z output is high? If X, and Y, are low and all other inputs are high, which Z output is high? 3-4. In Fig. 3-26, you want Z; to be | and all other Z outputs to be O. What values must the X and Y inputs have? 3-5. The outputs in Fig. 3-27 are cross-coupled back to the inputs of the NOR gates. IR = O and S = 1. what do Q and Q equal? “a 01 o s Fig. 3:27 Cross-coupled NOR gates. 36. IfR= landS = OinFig.3-27, what does O equal? Q? 3-7. Prove that Fig. 3-284 and b are equivalent. 3-8. What is the output in Fig. 3-28a if all inputs are Os. 1f all inputs are 1s? 3-9. What is the output in Fig. 3-28b if all inputs are Os. If all inputs are 1s? 3-10. A NOR has 6 inputs. How many input words are in its truth table? What is the only input word that produces a 1 output? 3-11, In Fig. 3-284 how many input words are there in the truth table? 3-12, What is the output in Fig. 3-29 if all inputs are low? H all inputs are high? % " % - Xo 20 2 Z2 x o , 1X Fig. 3-26 NOR-gate crossbar switch. 44 Digital Computer Electronics ED SD ) Fig. 3:28 A 8 + c o Fig. 3.29 3-13, How many words arc in the truth table of Fig. 3-4. 315. 3-29. What is the value of Y for cach of the following? a. ABCD = O011 b. ABCD = 010 e. ABCD = 1001 d. ABCD = 1100 Which ABCD input words does the circuits of Fig. 3-29 recognize? Tn Fig. 3-304 the two inputs are connected to- gether. IFA = O what does Y equal? If A = |, what does Y equal? Does the circuit act like a noninverter or an inverter? a ED ED tb) A Fig. 3-30 3-16. sem 317, What is the output in Fig. 3-30b if both inputs are low? H one input is low and the other high? Tf both arc high? Does the circuit act like an OR gate or an AND gate? Supposc the NOR gates of Fig. 3-26 are replaced by NAND gates. Then you've got a NAND-gate crossbar switch. a. fall X and Y inputs are low, which Z output is low? 3-18. 3:19. 320, 321, b. Tf all inputs are low except X, and Y,, which Z output is low? c. Tf all inputs are low except Xo and Y,. which Z output is low? d. To get a low Z, output, which inputs must be high? Tn Fig. 3-3t, what arc the outputs if R = O and S=19 What is the output in Fig. 3-32a if all inputs are 0s? 1f all inputs are 1s? How many input words are there in the truth table of Fig. 3-320? fa) Fig. 3:32 45 Chapter 3 More Logic Gates  e. All inputs are low except T4, JAZ, and Az. d. The only high inputs are T,, JAM, and Ay. Figure 3-35 shows the control matrix discussed in Example 3-3. Only one of the timing signals T, to Te is high at a time. Also, only one of the instruc- tions, LDA to OUT, is high at a time. Which are the high outputs for each of the following condi- 3-22, Prove that Fig. 3-32a and b are equivalent. 323. What is the output in Fig. 3-33 if all inputs are low? If they are all high? 3-26. 3-24. How many words are in the truth table of Fig. 3-337 What does Y equal for each of the follow- 00111 . 10110 tions? e. 1010 a. Ty high d. ABCDE = 10101 b. To high 3-25. In Fig. 3-34 the inputs are To. JMP, JAM, JAZ, c. Tahigh Ay. and Az: the output is Lp, What is the output d. Ty and LDA high for each of these input conditions? e. T; and LDA high a. All inputs are Os. f. T, and ADD high b. All imputs are low except 7, and JMP. Fig. 3-33 Fig. 3-34 IDA ADD sus: our. nb hn 5 7 Co Ep tm Ep L E ta Fig. 335 Control matrix. 46 Digital Computer Electronics Es Fera su Ey Ts and ADD high T; and ADD high T, and SUB high Ts and SUB high Te and SUB high T, and OUT high tg to 1.6k0 Fig. 4-1 Standard TTL NAND gate Standard TTL Figure 4-1 shows a TTL NAND gate. The multiple-emitter input transistor is typical of all the gates and circuits in the 7400 series. Each emitter acts likc a diode; therefore, Q, and the 4-kf) resistor act like a 2-input AND gate. The test of the circuit inverts the signal; therefore, the overall circuit acts likc a 2-input NAND gate. The output transistors (Q; and Q,) torm a totem-pole connection, typical of most TTL devices, Either one or the other is on. When Q; is on, the output is high; when Q, is on, the output is low. The advantage of a totem-pole connection is its low output impedance. Ideally, the input voltages 4 and B are either low (grounded) or high (5 V). If A or B is low, Q, saturates. This reduces the base voltage of Q, to almost zero. Therefore, Q, cuts oft, forcing Q, to cut off. Under these conditions, Q; acts like an emitter follower and couples a high voltage to the output. On the other hand, when both A and 8 are high, the collector diode of Q, goes into forward conduction; this forces Q, and Q, into saturation, producing a low output. Table 4-1 summarizes all input and output conditions. Incidentally, without diode D, in the circuit, Q, would conduct slightly when the output is low. To prevent this, the diode is inserted; its voltage drop keeps the basc-emitter TABLE 4-1, TWO- INPUT NAND GATE -- 20 |» -o-—o|tm Y 1 1 1 o diode of Q; reverse-biased. In this way, only Q, conducts when the output is low. Totem-Pole Output Why are totem-pole transistors used? Because they produce a low output impedance. Either Q, acts like an emitter foliower (high output) or Q, is saturated (low output). Either way, the output impedance is very low. This is important because it reduces the switching time. In other words, when the output changes from low to high, or vice versa, the low output impedance implies a short RC time constant; this short time constant means that the output voltage can change quickly from one state to the other. Propagation Delay Time and Power Dissipation Two quantities needed for our later discussions are power dissipation and propagation delay time. A standard TTL gate has a power dissipation of about 10 mW. It may vary from this value because of signal levelS; tolerances, etc., but on the average. it's 10 mW per gate. The propagation delay time is the amount of time it takes for the output of a gate to change after the inputs have changed. The propagation delay time of a TTL gate is in the vicinity of 10 ns. Device Numbers By varying the design of Fig. 4-1 manufacturers can alter the number of inputs and the logic function. The multiple- emitter inputs and the totem-pole outputs are still used, no matter what the design. (The only exception is an open collector, discussed later.) Table 4-2 lists some of the 7400-series TTL gates. For instance, the 7400 is a chip with four 2-input NAND gates in one package. Similarly, the 7402 has four 2-input NOR gates, lhe 7404 has six inverters, and so on. TABLE 4-2, STANDARD TTL Device number Description 7400 Quad 2-input NAND gates 7402 Quad 2-input NOR gates 7404 Hex inverter 7408 Quad 2-input AND gates 7410 “Triple 3-input NAND gates 741 Triple 3-input AND gates 7420 Dual 4-input NAND gates 7421 Dual 4-input AND gates 7427 Triple 3-input NOR gates 7430 8-input NAND gate 7486 Quad 2-input XOK gates Chapter 4 TTLCircuits 49  5400 Series Any device in the 7400 series works over a temperature range of 0º to 70ºC and over a supply range of 4.75 to 5.25 V. This is adequate for commercial applications. The 5400 series, developed for the military applications, has the same logic functions as the 7400 series. except that it works over a temperature range of — 55 to 125º€ and over a supply range of 4.5 to 5.5 V. Although 5400-series devices can replace 7400-series devices, they are rarely used commercially because of their much higher cost. High-Speed TTL The circuit of Fig. 4-1 is called standard TTL. By decreasing the resistances a manufacturer can lower the internal time constants; this decreases the propagation delay time. The smaller resistances, however, increase the power dissipa- tion. This variation is known as Aigh-speed TFL. Devices of this type are numbered 74H00, 74H01, 74H02, and so on. À high-speed TTL gate has a power dissipation around 22 mW and a propagation delay time of approximately 6 ns. Low-Power TTL By increasing the internal resistances a manufacturer can reduce the power dissípation of TTL gates. Devices of this type are called Jow-power TTL and are numbered 74100, 74L01, 74L02, cte. These devices are slower than standard TTL because of the larger internal time constants. A low- power TTL gate has a power dissipation of approximately i mW and a propagation delay time around 35 ns. Schottky TTL With standard TIL. high-speed TTL, and low-power TTL. the transistors go into saturation causing extra carriers to flood the base. If you try to switch this transistor from saturation to cutoff, you have to wait for the extra carricrs to flow out of the basc; the delay is known as the saruration delay time. One way to reduce saturation delay time is with Schottky TTL. The idea is to fabricate a Schottky.diode along with cach bipolar transistor of a TTL circuit, as shown in Fig. 4-2. Because the Schottky divde has a forward voltage of only 0.4 V. it prevents the transistor from saturating fully. Fig. 4-2 Schottky diode prevents transistor saturation. 50 Digital Computer Electronics This virtually climinates saturation delay time, which means better switching speed. This variation is called Schortky TIL; the devices are numbered 74800, 74801, 74802, and so forth. Schottky TTL devices arc very fast, capable of operating reliably at 100 MHz. The 74800 has a power dissipation around 20 mW per gate and a propagation delay time of approximately 3 ns. Low-Power Schottky TIL By increasing internal resistances as well as using Schottky diodes manufacturers have come up with the best compro- mise between low power and high speed: low-power Schottky TTL. Devices of this type are numbered 74L800, 74LS01, 74LS02, etc. A low-power Schottky gate has a power dissipation of around 2 mW and a propagation delay time of approximately 10 ns, as shown in Table 4-3. Standard TTL and low-power Schottky TTL are the mainstays of the digital designer. In other words, of the five TTL types listed in Table 4-3, standard TTL and low- power Schottky TTL have emerged as the favorites of the digital designers. You will see them used morc than any other bipolar types. 4-3 TTL CHARACTERISTICS 7400-series devices are guaranteed to work reliably over a temperature range of O to 70ºC and over a supply range of 4.75 to 5.25 V. In the discussion that follows, worst case means that the parameters (characteristics likc maximum input current, minimum output voltage, and so on) are measured under the worst conditions of temperature and voltage-—maximum temperature and minimum voltage for some parameters, minimum temperature and maximum voltage for others, or whatever combination produces the worst values. Floating Inputs When a TTL input is low or grounded, a current 77 (conventional direction) exists in the emitter, as shown in TABLE 4-3. TIL POWER-DELAY VALUES Power, Delay time, Type mW ns Low-power 1 35 Low-power Schottky 2 10 Standard 10 10 High-speed 22 6 Schottky 20 3 +5V ——— +5V - are 4k2 IE .—— +5V — 48 Open Low high) tal bj) +5V =—— Open e Z ' Tor tes, tag Fig. 4-3 Open or floating input is the same as a high input. Fig. 4-3a. On the other hand, when a TTL input is high (Fig. 4-3h), the emitter diode cuts off and the emitter current is approximately zero. When a TTL input is fioating (unconnected), as shown in Fig. 4-3c, no emitter current is possible. Therefore, a floating TTL input is equivalent to a high input. In other words, Fig. 4-3c produces the same output as Fig. 4-3h. This is important to remember. In building cireuits any foating TFL input will act like a high inpur. Figure 4-3d emphasizes the point. The input is floating and is equivalent to a high input; therefore, the output of the inverter is low. O +5V Fig. 4-4 “TIL inverter. Worst-Case Input Voltages Figure 4-4 shows a TTL inverter with an input voltage of V, and an output voltage of Vo. When V, is O V (grounded), the output voltage is high. With TTL devices, we can raise Vito 0.8 V and still have a high output. The maximum low-level input voltage is designated V;. Data sheets list this worst-case low input as Vi =08V Take the other extreme. Suppose V, is 5 Vin Fig. 4-4, This is a high input, therefore, the output of the inverter is low. V, can decreasc all the way down to 2 V, and the output wilt still be low. Data sheets list this worst-case high input as Va=2V In other words, any input voltage from 2 to 5 V is a high input for TTE devices. Worst-Case Output Voltages Ideally, O V is the low output, and 5 V is the high output. We cannot attuin these idea] values because of internal voltage drops. When the output is low in Fig. 4-4, Q, is saturated and has a small voltage drop across it. With TTL devices, any voltage from O to 0.4 V is a low output. When the output is high, Q; acts like an emitter folower. Because of the drop across Q,, D,, and the 130-1) resistor, the output ís less than 5 V. With TTL devices, a high output is between 2.4 and 3.9 V, depending on the supply voltage, temperature, and load. This means that the worst-case output values are Va =04V Vm=24V Table 4-4 summarizes thc worst-case values. Remember that they are valid over the temperature range (O to 70ºC) and supply range (4.75 to 5.25 V). Compatibility The values shown in Table 4-4 indicate that TTL devices are compatible. This means that the output of a TTL device can drive the input of another TTL device, as shown in Fig. 4-54. To be specific, Fig. 4-5b shows a low TTL output (0 to 0.4 V). This is low enough to drive the second TTL device because any input less than 0.8 V is a low input. TABLE 4-4. TTE STATES (WORST CASE) Output, Y Input, V Low 0.4 0.8 High 2.4 2 Chapter 4 TTLCircuits 51  Fig. 4-8 TTL NOR gate. When A and B arc both low, Q, and Q; arc saturated; this cuts off Q, and Q,. Then Q; acts like an emitter foliower and we get a high output. TEA or B or both arc high, Q, or Q; or both are cut off, forcing Q, or Q, or both to tum on. When this happens, Q, saturates and pulls the output down to a low voltage. With more transistors, manufacturers can produce 3- and 4-input NOR gates. (A TTL 8-input NOR gate is not available.) AND and OR Gates To produce the AND function, another common-emitter stage is inserted before the totem-pole output of the basic NAND gate design. The extra inversion converts the NAND gate to an AND gate, Similarly, another CE stage can be inserted before the totem-pole output of Fig. 4-8; this converts the NOR gate to an OR gate. Buffer-Drivers A buffer is a device that isolates two other devices. Typically, a buffer has a high input impedance and a low output impedance. In terms of digital ICs, this means a low input current and a high output current. Since the output current of a standard TTL gate can be 10 times the input current, a basic gate does a certain amount of buffering (isolating). But it's only when the manufacturer optimizes the design for high output currents that we call a device a buffer or driver. As an example, the 7437 is a quad 2-input NAND buffer, meaning four 2-input NAND gates optimized to get high output currents. Each gate has the following worst-case values of input and output currents: lu = —1.6mA fo, = 48 mà Im = 40 p A log = —1.2mA 54 Digital Computer Electronics The input currents are the same as those of a standard NAND gate, but the output curtents are 3 times as high, which means that the 7437 can drive heavier loads. Appendix 3 includes sevcral other bufler-drivers. “3 — 3 d fa) tb! Fig. 4-9 Seven-segment display Encoders and Decoders A number of TTL chips are available for encoding and decoding data. For instance, the 74147 is a decimal-to- BCD encoder. It has 10 input lines (decimal) and 4 output lines (BCD). As another example, the 74154 is a 1-of-16 decoder. It has 4 input lines (binary) and 16 output lines (hexadecimal). Seven-segment decoders (7446, 7447, etc.) are useful for decimal displays. They convert a BCD nibble into an output that can drive a seven-segment display. Figure 4-9 illus- trates the idea behind a seven-segment LED display. It has seven separate LEDs that allow you to display any digit between O and 9. To display a 7, the decoder will tum on LEDs a, b, and c (Fig. 4-9). Seven-segment displays are not limited to decimal num- bers. For instance, in some microprocessor trainers, seven- segment disptays arc used to indicate hexadecimal digits. Digits A, €, E, and F are displayed in uppercase torm: digit B is shown as a lowercase b (LEDs c, d. e, f, 8) and digit D as a lowercase d (LEDs b, c, d, e, 8). Schmitt Triggers When a computer is running, the outputs of gates are rapidly switching from one state to another. Tf you look at these signals with an oscilloscope, you see signals that ideally resemble rectangular waves like Fig. 4-10a. When digital signals are transmitted and later received, they are often cormpted by noise, attenuation, or other factors and may wind up looking like the ragged waveform shown in Fig. 4-10b. If you try to use these nonrectangular signals to drive a gate or other digital device, you get unreliable operation. This is where the Schmitt trigger comes in. lt designed to clean up ragged looking pulses, producing almost vertical  fa) ALAS TA tb) Schmitt trigger fe) Fig, 4-10 Schmitt trigger produces rectangular ontput. ve[=l [2] [ELE ELLE 5 LTL E ta te tel le by fo) Fig. 4-11 (a) Hex Schmitt-trigger inverters; (6) 4-input xaxp Schmitt trigger: (c) 2-input NAND Schmitt trigger. transitions between the low and high state, and vice versa (Fig. 4-10c). In other words, the Schmitt trigger produces a rectangular output, regardless of the input waveform. The 7414 is a hex Schmitt-trigger inverter, meaning six Schmitt-trigger inverters in one package like Fig. 4-Llta, Notice thc hysteresis symbol inside each inverter; it des- ignates the Schmitt-trigger function. Two other TTL Schmitt triggers are available. The 7413 is a dual 4-input NAND Schmitt trigger, two Schmitt-trigger gates like Fig. 4-11b. The 74132 is a quad 2-input NAND Schmitt trigger, four Schmitt-trigger gates like Fig. 4-1lc. Other Devices The 7400 series also includes a number of other devices that you will find useful, such as AND-OR-INVERT gates (discussed in the next section), latches and flip-flops (Chap. 7), registers and counters (Chap. 8), and memories (Chap. 9. 4-5 AND-OR-INVERT GATES Figure 4-12a shows an AND-OR circuit. Figure 4-12b shows the De Morgan equivalent circuit, 4 NAND-NAND network. In either case, the boolean equation is Y=AB+CD (4-1) Since NAND gates are the preferred TTL gates, we would build the circuit of Fig. 4-12b. NAND-NAND cireuits like this are important because with them you can build any desired logic circuit (discussed in Chap. 5). TTL Devices Ts there any TTL device with the output given by Eg. 4-1? Yes, there are some AND-OR gates but they are not easily derived from the basic NaND-gate design. The gate that is easy to derive and comes closc to having an expression like Eq. 4-1 is the AND-OR-INVERT gate shown in Fig. 4-12c. Tn other words, a variety of circuíts like this are available on chips. Because of the inversion, the output has an equation of Y=AB+CD (4-2) A 8—— c fa) by D fe) Fig. 4-12 (4) AND-OR circuit; (b) NAND-NAND circuit; (e) anD- OR-INVERT circuit. Chapter 4 TTL Circuits 55  Fig. 4-13 AND-OR-INVERT schematic diagram. Figure 4-13 shows the schematic diagram of a TTL AND- OR-INVERT gate. Q,, Q», Q:. and Qu form the basic 2-input NAND gate of the 7400 series. By adding Qs and Q, we convert the basic NAND gate to an AND-OR-INVERT gate. Q, and Q; act like 2-input AND gates: Q, and Qg produce oRing and inversion, Because of this, the circuit is logically equivalent to Fig. 4-12c. In Table 4-6, listing the AND-OR-INVERT gates available in the 7400 series, 2-wide means two AND gates across, 4- wide means four AND gates across, and so on. For instance, the 7454 is a 2-input 4-wide AND-OR-INVERT gate like Fig. 4-144; each AND gate has two inputs (2-input) and there are four AND gates (4-wide). Figure 4-14h shows the 7464: it is a 2-2-3-4-input 4-wide AND-OR-INVERT gate. When we want the output given by Eq. 4-1, we can connect the output of a 2-input 2-wide AND-OR-INVERT gate to another inverter, This cancels out the internal inversion, giving us the equivalent of an AND-OR circuit (Fig. 4-124) or à NAND-NAND network (Fig. 4-12b). Expandable AND-OR-INVERT Gates The widest AND-OR-INVERT gate available in the 7400 series is 4-wide. What do wc do when we need a 6- or 8-wide circuit? One solution is to use an expandable AND-OR- INVERT gate. TABLE 4-6. AND-OR-INVERT GATES Description Device 7451 Dual 2-input 2-wide 7454 2-input 4-wide 7459 Dual 2-3 input 2-wide 7464 2-2-3-4 input 4-wide 56 Digital Computer Electronics I [E] Fig. 4-14 Examples of AND-OR-INVERT circuits. Figure 4-154 shows the schematic diagram of an ex- pandable AND-OR-INVERT gate. The only difference between this and the preceding AND-OR-INVERT gate (Fig. 4-13) is collector and emitter tie points brought outside the package. Since Q; and Qs are the key to the oRing operation, we are being given access to the internal oRing function. By connecting other gates to these new inputs we can expand the width of fhe AND-OR-INVERT gate. Figure 4-15b shows the logic symbol for an expandable AND-OR-INVERT gate. The arrow input represents the emitter, and the bubble stands for the collector. Table 4-7 lists the expandable AND-OR-INVERT gates in the 7400 series. Expanders What do we connect to the collector and emitter inputs of an expandable gate? The output of an expander like Fig. 4-164. The input transistor acts like a 4-input AND gate. The output transistor is a phase splitter; it produces two TABLE 4-7. EXPANDABLE AND-OR- INVERT GATES Device Description 7450 Dual 2-input 2-wide 7453 2-input 4-wide 7455 4-input 2-wide a) D; Da O; D, Ds De D; [7 Do Ds Fig, 4-18 A ló-to-l multiplexer. Chapter 4 TTL Circuits 59  ABCO 16t01 data selector/ Y multiplexer o-009009--0000-6 Fig. 4:19 Generating a boolean function. = 0001, the output is 1; when ABCD = 0010, the output is O; and so on. Figure 4-19 shows how to set up a multiplexer with the foregoing truth table. When ABCD = (000, data bit O is steered to the output; when ABCD = 0001, data bit | is steered to the output; when ABCD = 0010, data bit O is steered to the output; and so forth. As a result, thc truth table of this circuit is the same as Table 4-8. Universal Logic Circuit The 74150 is a 16-to-1 multiplexer. This TTL device is a universal logic circuit because you can use it to get the hardware equivalent of any four-variable truth table. Tn other words, by changing the input data bits the same IC can be made to generate thousands of different truth tables. Multiplexing Words Figure 4-20 illustrates a word multiplexer that has two input words and one output word. The input word on the left is LsL,L,L, and the one on the right is R4R;R;Ro. The control signal labeled RIGHT selects the input word that will be transmitted to the output. When RIGHT is low, the four NAND gates on the left are activated; therefore, OUT = Lilly When RIGHT is high, OUT = R;R;R;Ry The 74157 is TTL multiplexer with an equivalent circuit like Fig. 4-20. Appendix 3 lists other multiplexers available in the 7400 series. tz to t to Ba fio Bh Ro AIGHT OUT Fig. 4-20 Nibble multiplexer GLOSSARY bipolar Having two types of charge carriers: free electrons and holes. chip A small piece of semiconductor material. Sometimes, chip refers an IC device including its pins. 60 Digital Computer Electronics fanout The maximum number of TTL loads that a TTL device can drive reliably over the specified temperature range. low-power Schottky TTL A modification of standard TTL in which larger resistances and Schottky diodes are used. The increased resistances decrease the power dissipation, and the Schottky diodes increase the speed. multiplexer A circuit with many inputs but only one output. Control signals select which input reaches the output. noise margin The amount of noise voltage that causes unreliablc operation. With TTL it is 0.4 V. As long as noise voltages induced on connecting lines are less than 0.4 V, the TTL devices will work reliably. saturation delay time The time delay encountered when a transistor tries to come out of the saturation region. When the basc drive switches from high to low, a transistor cannot instantaneously come out of saturation; extra carriers that floodcd the base region must first fow out of the base. Schmitttrigger A digital circuit that produces a rectangular output from any input large enough to drive the Schmitt trigger. The input waveform may be sinusoidal, triangular. distorted, and so on. The output is always rectangular. sink A place where something is absorbed. When satu- rated, the lower transistor in a totem-pole output acts like a current sink because conventional charges flow through the transistor to ground. source A place where something originates. The upper transistor of a totem-pole output acts like à source because charges flow out of its emitter into the load. standard TTL The initial TTL design with resistance values that produce a power dissipation of 10 mW per gate and a propagation delay time of 10 ns. SELF-TESTING REVIEW Read each of the following and provide the missing words. Answers appcar at the beginning of the next question. 1. Small-scale integration, abbreviated re fers to féwer than 12 gates on the same chip. Medium-scale integration (MSI) means 12 to 100 gates per chip. And large-scale integration (LSI) refers to more than gates per chip. 2. (SSI, 100) The two basic technologies for digital 1Cs are bipolar and MOS. Bipolar technology is preferred for. and » Whereas MOS technology is better suited to LSI. The reason MOS deminates the LSI field is that more can bc fabricated on the same chip area. 3. (SSI, MSI, MOSFETS) Some of the bipolar families include DTL, TTL, and ECL. has be- come the most widely used bipolar family. is the fastest logic family: it's uscd in high-speed applications. 4. (TTL, ECL) Some of the MOS fanilies are PMOS, NMOS, and CMOS. dominates the LST field, and used extensively where lowest power consumption is necessary. 5. (NMOS, CMOS) The 7400 series, also called stan- dard TTL, contains a variety of SSI and chips that allow us to build all kinds of di; Circuits and systems. Standard TTL has a multiple- emitter input transistor and a output. The totem-pole output produces a low output impedance in either state. 6. (MSI, totem-pole) Besides standard TTE, there is high-speed TTL, low-power TTL, Schottky TTL, and low-power TTL. Standard TTL and low-power TTL. have become the favor- ites of digital designers, uscd more than any other bipolar families. 7. (Schottky, Schotiky) 7400-series devices are guaran- teed to work reliably over a range of O to 70ºC and over a voltage range of 4.75 to 5.25 V. A floating TTL input has the same effect as a input. 8. (Gemperamre, high) À TTL device can sink up to 16 mA and can source up to 400 pA. The maximum number of TTL loads a TTL device can drive is called the - With standard TTL, the fanout equals . 9. (standard, fanour, 10) A buffer is a device that isolates other devices. Typically, a buffer has a high input impedance and a output imped- ance. In terms of digital ICs, this means a input current and a high output current capability. 10. (fow, low) A Schmitt trigger is a digital circuit that produces à output regardless of the in- put waveform. It is used to clean up ragged looking pulses that have been distorted during transmission from once place to another. 1, (rectangular) A multiplexer is a circuit with many inputs but only one output. It is also called a data selector because data can be steered from one of the inputs to the output. A 74150 is a 16-to-! multi- plexer. With this TTL device you can implement the logic circuit for any four-variable truth table. Chapter 4 TTL Circuits 61  D BOOLEAN ALGEBRA AND KARNAUGH MAPS This chapter discusses boolean algebra and Karnaugh maps, topics needed by the digital designer. Digital design usually begins by specifying a desired output with a truth tabic. The question then is how to come up with a logic circuit that has the same truth table. Boolean algebra and Karnaugh maps are the tools used to transform a truth table into a practical logic circuit. 5-1 BOOLEAN RELATIONS What follows is a discussion of basic relations in boolean algebra. Many of these relations are the same as in ordinary algebra, which makes remembering them casy. Commutative, Associative, and Distributive Laws Given a 2-input OR gate, you can transpose the input signals without changing the output (see Fig. 5-1). In boolean terms Ar+B=B+A (5-1) Similarly, you can transpose the input signals to a 2-input AND gate without affecting the output (Fig. 5-1h). The boolcan equivalent of this is AB = BA (5-2) The foregoing relations are called commutative laws. The next group of rules are called the associative laws. The associative law for oRing is Ar(B+HO=(A+B)4C (5-3) 64 DD DD» fd) 4 DL = a, Y À fe) Fig. 5-1 Comutative, associativo, and distributive laws Figure 5-1c illustrates this rule. The idea is that how you group variables in an ORing operation has no effect on the output. For either gate in Fig. 5-Lc the output is VY=A+B+C Similarly, the associative law for ANDing is A(BC) = (ABJC (5-4) Figure 5-1d illustrates this rule. How you group variables in ANDing operations has no effect on the output. For either gate of Fig. 5-ld the output is Y = ABC The distriburive law states that A(B+ C) = AB + AC (5-5) This is easy to remember because it's identical to ordinary algebra. Figure 5-le shows thc meaning in terms of gates. oR Operations The next four boolean relations are about OR operations. Here is the first: A+0O=A 5-6) This says that a variable oRed with O cquals the variable. For better grasp of this idea, look at Fig. 5-2a. (The solid arrow stands for "““implies.””) The two cases on the left imply the case on the right. In other words, if the variable is 0, the output is O (left gate): if the variable is 1, the output is | (middle gate); therefore, a variable oRed with O eguals the variable (right gate). o and 1 and Fig. 5-2 OR relations Da DD ID DD» > Another boolean relation is A+rA=A (5-7) which is illustrated in Fig. 5-2b. You can see what happens. IF A is O, the output is 0; if A is 1, the output is L; therefore, a variable ored with itself equais the variable. Figure 5-2c shows the next boolean rule: A+1=1 (5-8) ln a nutshell, if one input to an OR gate is 1, the output is 1 regardless of the other input. Finally, we have A+Ã= (5-9) shown in Fig. 5-2d. In this case, a variable ORed with its complement equals 1. AND Operations The first AND relation to know about is ACL=A (5-10) illustrated im Fig. 5-34. TEA is O, the output is 0; if A is 1, the output is |; therefore, a variable ANDed with | equals the variable. Another relation is AA =A (5-11) Chapter 5 Boolean Algebra and Harnough Maps 65  o º and À Fig. 5-3 Ann relations. shown in Fig. 5-3b. In this case, a variable anDed with itself equals the variable. Figure 5-3c illustrates this relation A-0=0 (5-12) The rule is clear. If one input to an AND gate is 0, the output is O regardless of the other input, The last AND rule is A-Ã=0 (5-13) As shown in Fig. 5-3d, a variable ANDed with its comple- ment produces a O output. Double Inversion and De Morgan's Theorems The double-inversion rule is = =A (514) which says that the double complement of a variable equals the variable. Finally, there are the De Morgan theorems discussed in Chap. 3: Bo (5-15) +B (5-16) You should memorize Egs. 5-1 to 5-16 because they are used frequently in design work. 66 Digita! Computer Electronics De o TD > AM [ DS Ar 5 “AD LD 5 A 4 Duality Theorem We state the duulity iheorem without proof. Starting with a boolean relation, you can derive another boolean relation by 1. Changing each OR sign to an AND sign 2. Changing cach AND sign to an OR sign 3. Complementing cach O and 1 For instance, Eg. 5-6 says that A+0=A The dual relation is This is obtained by changing the OR sign to an AND sign, and by complementing the O to geta 1. The duality theorem is useful becausc it sometimes produces a new boolean relation. For example, Eg. 5-5 states that A(B+C)=AB+AC By changing each OR and AND operation we get the dual relation A+BC=(A+BXA+C) This is a new boolean relation, not previously discussed, (Ff you want to prove it, construct the truth table for the  Fig. 5-7 Gate Leads A preliminary guide for comparing the simplicity of one logic circuit with another is to count the number of inpur gate leads; the circuit with fewer input gate leads is usually easier to build. For instance, thc AND-OR circuit of Fig. 5-7a has a total of 15 input gate Icads (4 on each AND gate and 3 on the OR gate). The AND-OR circuit of Fig. 5-7b. on the other hand, has a total of 9 input gate leads. The AND-OR circuit of Fig. 5-7b is simpler than the AND-OR circuit of Fig. 5-7a because it has fewer input gate leads. A bus is a group of wires carrying digital signals. The 8-bit bus of Fig. 5-74 transmits variables 4, B, C, D and their complements A, B, €, and D. In the typical micro- computer, the microprocessor, memory, and LO units exchange data by means of buses. Factoring to Simplify One way to reduce the number of input gate leads is to factor the boolcan equation it possible. For instance, the boolean equation Y=AB+As (5-19) bas the equivalent logic circuit shown in Fig. 5-84. This circuit has six input gate leads. By factoring Eq. 5-19 we get Y=A(B+B) te) Fig, 5-8 The equivalent logic circuit for this is shown in Fig. 5-8b; it bas only four input gate Icads. Recall that a variable oRed with its complement always equals 1; therefore, Y=AB+B)J=A4-|=A To get this output, all we need is a connecting wire from the input to the output, as shown in Fig. 5-8c. In other words, wc don't need any gates at all. Another Example Here is another example of how factoring can simplify a boolean equation and its corresponding logic circuit. Sup- pose we are given Y=AB+AC+ãBDA+cCD (5-20) In this eguation, two variables at a time are being Anbed. The logical products arc then ored to get the final output. Figure 5-94 shows the corresponding logic circuit. It has 12 imput gate leads. We can factor and rearrange Eq. 5-20 as Y=AB+CO +DBA+C) Chapter 5 Boolean Algebra and Karnaugh Maps 69  Fig. 5-9 oras P=(A+DYXB+C) (5-21) Tn this case, the variables are first ORed. then the logical sums are ANDed. Figure 5-9h illustrates the logic circuit. Notice it has only six input gate leads and is simpler than the circuit of Fig. 5-94. Final Example Tn Sec. 5-2 we derived this sum-of-products equation trom a truth table: Y = ABCD + ABCD + ABCD (5-22) Figure 5-74 shows the sum-of-products circuit, Il has 15 input gate leads. We can factor the equation as Y = ACD(B + B) + ABCD oras Y = ACD + ABCD (5-23) Figure 5-7b shows the equivalent logic circuit: it has only nine input gate leads. 70 Digital Computer Etectronics In general, one approach in digital design is to transform a truth table into a sum-of-products equation. which you then simplify as much as possible to get a practical logic circuit. 5-4 KARNAUGH MAPS Many engineers and technicians don't simplify equations with boolean algebra. Instead, they use a method based on Karnaugh maps. This section tells you how to construct a Karnaugh map. BB B B B 8 A A A A Ala als 4 ta) tb) fel 8 8 B 8 Alo o Alo 1 Alia ali o fay ter Fig. 5-10 “Iwo-variable Kamaugh map. Two-Variable Map Suppose you have a truth table like Table 5-5. Here's how to construct the Karnaugh map. Begin by drawing Fig. 5-10a. Note the order of the variables and their complements; the vertical column has À followed by A, and the horizontal tow has B followed by B. Next, look for output Ls in Table 5-5, The first 1 output to appear is for the input of 4 = land B = 0, The fundamental product for this is AB. Now, enter a t on the Kamaugh map as shown in Fig. 5-10. This £ represents the produet AB because the | is in the 4 row and the B column. Similarly, Table 5-5 has an output 1 appearing for an inputof A = landB = 1. The fundamenta! product for this is AB. When you enter a 1 on the Karnaugh map to represent AB, you get the map of Fig. 5-10c. The final step in the construction of the Kamaugh map is to enter Os in the remaining spaces. Figure 5-10d shows how the Kamaugh map looks in its final form. Here's another cxample of a two-variable map. In the truth table of Table 5-6, the fundamental products are AB and AB. When Is are entered on the Karnaugh map for these products and Os for the remaining spaces, the com- pleted map looks like Fig. 5-10€.  TABLE 5-5 TABLE 5-6 A B|Y A B|Y o 0/10 o 00 o1]o oO 1/1 1 0/1 1 o/1 Ltia Laio Cc é c cc AB AB AB| 0 O AB | | AB| 1 As|1 O AB Asi 4 air 4 AB AB aBjo o tal [0] fe) Fig. 5-1 Three-variablo Karnaugh map. Three-Variable Map Suppose you have a truth table like Table 5-7, Begin by drawing Fig. 5-Ila. It is especially important to notice the order of the variables and their complements. The vertical column is labeled AB, AB, AB, and AB. This order is not a binary progression; instead it follows the order of 00, 01, 11, and 10. The reason for this is explained in the derivation of the Kamaugh method; briefly, it's done so that only one variable changes from complemented to uncomplemented form (or vice versa). Next, look for output Is in Table 5-7. The fundamental products for these 1 outputs are ABC, ABC, und ABC. Enter these Is on the Kamaugh map (Fig. 5-11h). The final step is to enter Os in the remaining spaces (Fig. 5-1 lc). This Karnaugh map is useful because it shows thc funda- mental products needed for the sum-of-produets circuit. TABLE 5-7 n--rocoso | -"-S0n“Soo | ty So" o-o|0 [-=cce-==[=| Cc Cc c cõ é é co cd AB AB 1 As AB 1a AB AB 1 AB AB fa) tb cb Cc co co te) Fig. 5-12 Four-variable Karnaugh map. Four-Variable Map Many MSI circuits process binary words of 4 bits each (nibbles). For this reason, logic circuits are often designed to handle four variables (or their complements). This is why the four-variable map is the most important. Here's an example of constructing a four-variable map. Suppose you have the truth table of Table 5-8. The first step is to draw the blank map of Fig. 5-12a. Again, notice the progression. The vertical column is labeled AB. AB, TABLE 5-8 ABC D|Y o 0 0 0/0 00 0 1/1 Do 1 0/0 o o 1 110 o 10 0/0 o 1 o 1/0 o 1 1 0/1 ol rali & 10 0 0/0 10 0 1/0 Lo 1 0/0 Lot 170 11 0 0/0 li o 1/0 Lira o Lia 10 Chapter 5 Boolean Algebra and Karnaugh Maps 71  Cc cc cD cD Cp co cd ABj0 114 ABjo CT 1 As|0 0 01 ÁBj0 o O 481 1 0/4 AB 0 aABl1 1 01 AB º fai fb) Fig. 5-16 represents CD. By ORing these simplified products, you get the boolean equation for the map Y =ABD+AC+CD (5-24) Overlapping Groups When you encirele groups, you are allowed to use the same 1 more than once. Figure 5-17a illustrates the idea. The simplificd equation for the overlapping groups is Y=A+BCD (5-25) It is valid to encircle the 1s as shown in Fig. 5-17b, but then the isolated 1 results in a more complicated equation: Y=A + ABCD This requires a more complicated logic circuit than Eq. 5-25. So always overlap groups if possible; that is, use the 1s more than once to get the largest groups you can. Cc co co cd cd cc co AB|0 0 0 O AB[0 0 0 0 ijo Moo asim yu AB fal (b) Cc co co co c cc cd AB[o 0 0 0 AB|0 0 0 0 AB o 0 AB o 0 f AB 2.0 AB o od ABjo 0 0 0 Bo 0 00 fe) ay Fig. 5-17 Overlapping and rolling. 74 Digital Computer Electronics Rolling the Map Another thing to know about is rolling. In Fig. 5-17c, the pairs result in the equation Y = BCD + BCD (5-26) Visualize picking up the Kamaugh map and rolling it so that the left side touches the right side. If you"re visualizing correctly, you will realize the two pairs actually form a quad. To indicate this, draw half circles around each pair, as shown in Fig. 5-17d. From this viewpoint, the quad of Fig. 5-17d has the equation r=BD (5-27) Why is rolling valid? Because Eq. 5-26 can be simplified to Eg. 5-27. Here's the proof. Start with Eg. 5-26; Y=BCD + sCD This factors into Y=BDC+C) which reduces to This final equation represents a roiled quad like Fig. 5-17d. Therefore, 1s on the edges of a Kamaugh map can be grouped with Is on opposite edges. cD co co cd co C co co Asjo 0 0 0 AB|o 0 0 0 AB| O o o AB| 0 o o AB 0 0 AB o o aB|o 0 o aB|o O o fa) tb) Fig. 5-18 Redundant group Redundant Groups After you finish encircling groups, there is one more thing to do before writing the simplified boolean equation: eliminate any group whosc Is are completely overlapped by other groups. (A group whose Is are all overlapped by other groups is called a redundant group.) Here ís an example. Suppose you have encircled the three pairs shown in Fi; is -18. The boolean equation then Y = BCD + ABD + ACD At this point, you should check to sec if there are any redundant groups. Notice that the 1s im the inner pair are completely overlapped by the outside pairs. Because of this, the inner pair is a redundant pair and can be eliminated to get the simpler map of Fig. 5-18h. The equation for this map is r = BCD + ACD Since this is à simpler equation. it means a simpler logic circuit. This is why you should eliminate redundant groups if they exist. Summary Here's a summary of how to use the Karnaugh map to simplify logie circuits: 1, Entera | on the Karnaugh map for each fundamental product that corresponds to 1 output in the truth table. Enter Os elsewhere. 2. Encircle the octets, quads, and pairs. Remember to roll and overlap to get the largest groups possible. If any isolated 1s remain, encircle them, Eliminate redundant groups if they exist, » Write the boolean equation by oring the products corresponding to the encircled groups. 6. Draw the equivalent logic circuit. neto EXAMPLE 5-1 What is the simplifisd boolean equation for the Karnaugh map of Fig. 5-194? cd Cc c c ABjo 0 0 0 ABj|o 0 0 0 AB[0 0 1.0 ABlo 0 10 ABjo 111 ABjo 1 1/1 fa) fby Fig. 5-19 SOLUTION There are no octets, but there is a quad, as shown in Fig. 5-19h. By overlapping we can find two more quads (Fig. 5-19c). Finally, overlapping gives us the pair of Fig. 5-19d. The horizontal quad of Fig. 5-194 corresponds to a simplified product of AB. The square quad on the right corresponds to AC, while the one on the left stands for AD, The pair represents BCD. By oRing these products we get the simplified equation Y=AB+AC + AD+BCD (5-28) Figure 5-20 shows the equivalent logic circuit. Fig. 5-20 EXAMPLE 5-2 As you know from Chap. 4, the NAND gate is the least expensive gate in the 7400 series. Because of this, AND- OR circuits are usually built as equivalent NAND-NAND circuits. Convert the AND-OR circuit of Fig. 5-20 10 à NAND-NAND circuit using 7400-series devices. SOLUTION Replace each AND gate of Fig. 5-20 by a NAND gate and replace the final OR gate by a NAND gate. Figure 5-21 is the De Morgan equivalent of Fig. 5-20. As shown. wc can build the circuit with a 7400, a 7410, and a 7420. 5-7 DON'T-CARE CONDITIONS Sometimes, it doesn't matter what the output is for a given input word. To indicate this. we use an X in the truth table instead ofa O ora 1. For instance, look at Table 5-9. The Chapter 5 Boolean Algebra and Karnaugh Maps 75 ABCD ne fo]= < I 7420 [ 13 70 Fig. 5-21 NAND-NAND circuit using TTL gates. output is an X for any input word from 1000 through 1111. The X's are called don't cares because they can be treated either as Os or 1s, whichever leads to a simpler circuit. Figure 5-224 shows the Karnaugh map for Table 5 X's are used for ABCD, ABCD, ABCD, ABCD, ABC ABCD, ABCD, and ABCD because these are don't cares in the truth table. Figure 5-22b shows thc most efficient way to encircle the groups. Notice two crucial ideas. First, we visualize all X"s as Is and try to form the largest groups that include the real Is. This gives us three quads. Second, we visualize all remaining X's as Os. In this way. the X's are used to thc best advantage. We arc free to do this because the don't cares can be either Os or Is, whichever wc prefer. 9. TABLE 5-9 ABC D|Y 00 0 0/1 voo tTI|0 00 1 0]0 o 0 1 1/1 010 0/1 o 1 0 1/1 O 11 0/0 O 11 1/1 +10 0 0/]X 10 0 1|X 10 1 0/X 10 1 1]X 11 0 0/X 11 0 1/X 11 1 0/X LLa L|x 76 Digital Computer Electronics cd co co cb ABj1 0 1.0 o AB|1 41 1.0 º AB|X XXX x AB|X XX x x tal tb) > bi » | o o õ vi Fig. 5-22 Don't cares. Figure 5-22h implies the simplificd boolean equation Y=BD+CD+CcD Figure 5-22c is the simplified logic circuit. This AND-OR network has nine input gate leads. EXAMPLE 5-3 Recall that BCD numbers express cach decimal digit as nibble: O to 9 are encoded as 0000 to 1001. Especially important, nibbles 1010 to 1111 are never used in a BCD system. Table 5-10 shows a truth table for use in a BCD system. As you see, don't cares appear for 1010 through HI. Construct the Karnaugh map and show the simplified logic circuit. SOLUTION Figure 5-234 illustrates the Karnaugh map. The largest group we can form is the pair shown in Fig. 5-23h. The boolean equation is Y=BCD Figure 5-23c is the simplified logie circuit.  A 6 > ARITHMETIC-LOGIC UNITS The arithmetic-logic unit (ALU) is the number-crunching part of a computer. This means not only arithmetic opera- tions but logic as well (OR, AND, NOT, and so forth). In this chapter you will learn how the ALU adds and subtracts binary numbers. Later chapters will discuss the logic operations. 6-1 BINARY ADDITION ALUs don't process decimal numbers; they process binary numbers. Before you can understand the cireuits inside an ALU, you must cam how to add binary numbers. There are five basic cascs that must be understood before going on. Case 1 When no pebbles are added to no pebbles, thc total is no pebbles. As a word equation, Nonc + none — none With binary numbers, this equation is written as 0+0=0 Case 2 If no pebbles are added to one pebble, the total is one pebble: None + 0-0 In terms of binary numbers, 0O+1=1 Case 3 Addition is commutative. This means you can transpose the numbers of the preceding case to get C+nmne-0 1+0=1 Case 4 Next, one pebble added to one pebble gives two pebbles: “0. ce As a binary equation, 1l+1L=I0 To avoid confusion with decimal numbers, read this as “one plus one equals one-zero.”” An alternative way of reading the equation is “one plus one equals zero, carry one.” Case 5 One pebble plus one pebble plus onc pebble gives a total of three pebbles: :+0-0-0 The binary equation is l+1 += Read this as '“one plus one plus one equals one-one.”” Altematively, “one plus one plas one equals one, carry one. 79  Rules to Remember The foregoing cases are all you nced for more complicated binary addition. Therefore. memorize these five rules: 0+0=0 (6-1) 0+1=1 (6-2) 1+0=1 (6-3) L+1=1 (6-4) I+41+41=1 (6-5) Larger Binary Numbers Column-by-colunm addition apphies to binary numbers as well as decimal. For example, suppose you have this problem in binary addition: [LIGO + 11010 9 Start with the least significant column to get ELIOO + TOLO o Here, O + O gives 0, Next, add Lhe bits of the second column as [ollows: HIOO + MOO 10 This time, O + 1 results in 1. The third column gives 11100 + 11010 HO To this case, 1 + O produces 1. The fourth column results in 11100 + 11010 oo (carry 1) As you see, 1 + 1 equals O with a carry of 1. Finally, the last column gives 1IGO + 11010 MOTO Here, | + 1 + 1 (carry) produces IL, recorded as ! with a carry to the next higher column. 80 Digital Computer Etectronios EXAMPLE 6-1 Add the binary numbers 0101011] and 00110101 SOLUTION This is the problem: 01010117 + 00110101 ) Il you add the bits column by column as previously demonstrated, you will get OIOLOLI + 90110101 10001100 Expressed in hexadecimal numbers. the foregoing addi- tion is 57 +35 8c For clarity, we can use subseripts: 57 + 35 SC In microprocessor work, it is more convenient to use the letter H to signify hexadecimal numbers. In other words, the usual way to express the foregoing addition is s7H + 35H 8CH 6-2 BINARY SUBTRACTION To subtract binary numbers, we need to discuss four cases. Case 1: 0-0=0 Case 2: 1-0=1 Case 3: L>-1=0 Case 4: 10 -1=1 The last result represents o -0.-o which makes sense. To subtract larger binary numbers, subtract column by column, borrowing [rom the next higher column when necessary. For instance. in subtracting 101 from UI, proceed like this; 7 11 =5 = 01 2 010 Starting on the right, | — 1 gives O; then, 1 — O is l; finally, 1 — Lis O. Here is another example: subtract 1010 from L101. 13 no! = 10 = Jo1O 3 00H In the least significant column, 1 — O is 1. Tn the second column, we have to borrow from the next higher column; then, 10 — Lis 1. In the third column, O (after borrow) — 0is O. In the fourth column, | —- | = 0. Direct subtraction like the foregoing has been used in computers: however, it is possible to subtract in a different way. Later sections of this chapter will show you how. 6-3 HALF-ADDERS Figure 6-1 is a half-adder, a logie circuit that adds 2 bits Notice the outputs: SUM and CARRY. The boolean equations for these outputs are SUM =A0B (6-6) CARRY = AB (6-7) The SUM output is A XOR B: the CARRY output is À AND B. Therefore, SUM is a 1 when 4 and B are different; CARRY isa | when 4 and B are Is. Table 6-1 summarizes the operation. When A and B are Os, the SUM is O with a CARRY o[ 0. When A is O and B is £, the SUM is 1 with a CARRY of 0, When A is | and Bis O. the SUM equals 1 with a CARRY of O. Finally, when A is | and B is 1, the SUM is O with a CARRY of 1. The logic circuit of Fig. 6-1 does electronically what we do mentally when we add 2 bits. Applications for the half- adder are limited. What we need is a circuit that can add 3 bits at a time. cagar —] QE sum Fig. 6-1 Half-adder. TABLE 6-1. HALF-ADDER A B CARRY SUM 0.0 0 o 0 1 o 1 1 0 o 1 1 1 1 0 6-4 FULL ADDERS Figure 6-2 shows a full adder, a logic circuit that can add 3 bits. Again there are two outputs, SUM and CARRY. The boolean equations are SUM =ADBDC (6-8) CARRY = AB +AC+ BC (6-9) A Bo O O] e = sum Fig. 6-2 Full adder. In this case, SUM equals A xOR B xOR €; CARRY cquals AB OR AC OR BC. Therefore, SUM is | when lhe number of input Is is odd; CARRY is a | when two or more inputs are Is. Table 6-2 summarizes the circuit action. 4, B, and € are the bits being added. If you check each entry, you will see that the circuit adds 3 bits at a time and comes up with the correct answer. TABLE 6-2. FULL ADDER A B Cc CARRY SU; 0 vo o 0 o 0 1 o 1 0 1 0 o 1 0 1 1 1 o 1 0 0 o 1 1 o : I o 1 1 o 1 o 1 1 1 I I Chapter 6 ArithmeticLogic Units 81 the 1's complement is A = 1000 and the 2's complement is A" = 1001 In terms of a binary odometer, the 2's complement is the next reading after the 1's complement, Another example. 1f A = 0000 1000 then À = NILO and A” = UI 1000 Double Complement 1f you takc the 2's complement twice, you get the original word back, For instance, if A = 01 the 2's complement is A" = 1001 If you take the 2's complement of this, you get A" = 01 wbich is the original word. Tn general, this means that A"=A (6-12) Read this as “the double complement of A equals A,” Because of this property, the 2's complement of a binary number is equivalent to the negative of a decimal number. Back to the Odometer Chapter | used an odometer to introduce binary numbers. The discussion was about positive numbers only. But odometer readings can also indicate negative numbers. Here's how. Jf a car has a binary odometer, all bits eventually reset to Os. A few readings before and after a complete reset look like this: 1101 mão nm 0000 (RESET) 0001 00 0011 101 is the reading 3 miles before reset, 1110 occurs 2 miles before reset, and 1111 indicates 1 mile before reset. Then. 0001 is the reading 1 mile after reset, 0010 occurs 2 miles after reset, and 0011 indicates 3 miles after reset. “Before” and “after” are synonymous with “negative” and “positive.” Figure 6-6 illustrates this idea with the number line learned in basic algebra: O marks the origin, positive decimal numbers arc on the right, and negative decimal numbers arc on the left. The odometer readings are the binary equivalent of positive and negative decimal numbers: 1101 is the binary equivalent ot —3, 11 LO stands for —2, [IL for — 1; 0000 for 0; 0001 for + 1; 0010 for +2, and 0011 for +3. The odometer readings of Fig. 6-6 demonstrate how positive and negative numbers arc stored in a typical microcomputer. Positive decimal numbers are expressed in sign-magnitude form, but negative decimal numbers are represented as 2's complements. As before, positive num- bers have à leading sign bit of O, and negative numbers have a leading sign bit of 1. 2's Complement Same as Decimal Sign Change Taking the 2's complement of a binary number is the same as changing the sign of the equivalent decimal number. For example, if This idea is explained in the following discussion. A = 0001 (+lin Fig. 6-6) 10% 110 mm 0001 ooo 011 e— - + ——s — +— e— 3 -2 - ” + +3 Fig. 6-6 Decimal numbers and odometer readings 84 Digital Computer Etectronies taking thc 2's complement gives A" = (=1 in Fig. 6-6) Similarly, if A = 0010 (+2 in Fig. 6-6) then the 2ºs complement is A" = IO —2 in Fig. 6-6) Again, if A = 0011 (+3 in Fig. 6-6) the 2's complement is A" = 101 (—3 in Fig. 6-6) The same principle applies to binary numbers of any length: taking the 2's complement of any binary number is the same as changing the sign of the equivalent decimal number. As will be shown later, this property allows us to use a binary adder for both addition and subtraction Summary Here are the main things to remember about 2's complement representation: 1. The Icading bit is the sign bit; O for plus, 1 for minus. 2. Positive decimal numbers are in sign-magnitude form. 3. Negative decimal numbers are in 2's-complement form. EXAMPLE 6-5 What is the 2's complement of this word? A = 0011 0101 1004 1100 SOLUTION The 2's complement is A" = 1100 1010 010 0100 EXAMPLE 6-6 What is the binary form ot +5 and —5 in 2's-complement representation? Express the answers as 8-bit numbers. SOLUTION Decimal +5 is expressed in sign-magnitude form: +5 = 0000 0101 On the other hand, — 5 appears as the 2's complement: —5 = 1 1011 EXAMPLE 6-7 What is the 2's-complement representation of —24 in à 16-bit microcomputer? SOLUTION Start with the positive form: +24 = 0000 0000 0001 1000 Then take the 2's complement to get the negative form: —24 = MILL ITIO 1000 EXAMPLE 6-8 What decimal number does this represent in 2's-complement representation? HI11 0001 SOLUTION Start by taking the 2's complement to get 0000 1H This represents + 15. Therelore, thc original number is 111 0001= —i5 6-8 2's-COMPLEMENT ADDER- SUBTRACTER Early computers uscd signed binary for both positive and negative numbers. “Lhis led to complicated arithmetic cir- cuits. Then, engincers discovered that the 2's-complement representation could greatly simplify arithmetic hardware. Chapter 6 ArithmeticLogic Units 85  “This is why 2's-complement adder-subtracters are now the most widely used arithmetic circuits, Addition Figure 6-7 shows a 2's-complement adder-subtracter, a logic circuit that can add or subtract binary numbers. Here's how it works. When SUB is low, the B bits pass through the controlled inverter without inversion. Therefore, the full addcrs produce the sum S=A+B (6-13) Incidentally. as indicated in Fig. 6-7, the final CARRY is not used. This is because S; is the sign bit and S, to Sy are the numerical bits. The final CARRY therefore has no significance at this time, Subtraction When SUB is high, the controlled inverter produces the 1's complement. Furthermore, the high SUB adds a 1 to the first full adder. This addition of | to the 1ºs complement forms the 2's complement of B. In other words, the controlled inverter produces B, and adding 1 results im B'. The output of the full adders is S=A+B' (6-14) which is equivalent to S=A-B (6-15) because the 2's complement is equivalent to a sign change. EXAMPLE 6-9 A 7483 is a TTL circuit with four full adders. This means that it can add nibbles (4-bit numbers). Figure 6-8 shows a TTL adder-subtracter. The CARRY out (pin 14) of the least significant nibble is used as the CARRY in (pin 13) for the most significant nibble. This allows the two 7483s to add 8-bit numbers. Two 7486s form the controlled inverter needed for subtraction. As A, A, Ag B, [ D* [o + SUB CARRY not FA [a FA FA used S 8 Ss So Fig, 6:7 A 2's-complement addcr-subtracter A; Ag As Aq By 8g Bs Bq Az Az A Ag 83 8, 8 &g LI,| [| su 1/2/44t5|9 10/12]13 1|]2/4 519 [10/12/13 7486 7486 3 6 8 n 3 & 8 n 1 3 8 10 16 4 7 n 1 3 B 10 16 4 7 n 5 +5V— +5V—s 13 14 7483 7483 12 12 = ['s [2 E IE 5 SS SS S% Fig. 6-8 TTL adder-subtracter. 86 Digital Computer Electronics = |'s P fe IE 8 Sa Si So  Ay Ag Ag As By Bo Bs 84 As Ay Ay do Es 1 l2lals|e [iofiz)ia 1 7486 3 Te Te fu r da fe fo je ja Jo du r Jo je ho 5 sv sv 13 14 7483 7483 12 12 T's IR Tê IE = ['s IE IE [e S Se SS SS SS S Fig. 69 After you have the 2's complements. convert them to hexadecimal form. 6-9, An 8-bit microprocessor uses 2's-complement rep- 6-12, resentation. How do thc following decimal num- bers appear: a. —19 b —48 ce +37 d. —33 6:13. Express your answers in binary and hexadecimal form. 6-10. The output of an ALU is BEH. What decimal number does this represent in 2's-complement G-14. tepresentation? 6-11. Suppose the inputs to Fig. 6-9 are À = 3CH and B = 5FH. What is the output for a low SUB? A high SUB? Express your final answers in hexa- decimal form. In Fig. 6-9 which of the following inputs cause an overflow when SUB is low? a. 2DH and 4BH b. 8FH and C3H c. SEH and B8H d. 23H and 14H Why are applications for thc half-adder limited, what does the full adder do which makes it more useful than the half-adder, and what can be done with a full adder as a result of this feature? Since sign-magnitudc numbers are fairly easy to understand, why has the 2's-complement system become so widespread? Chapter 6 ArithmeticLogic Units 89  FLIP-FLOPS Gates are decision-making elements. As shown in the preceding chapter, they can perform binary addition and subtraction. But decision-making elements are not enough. A computer also needs memory elements, devices that can store a binary digit. This chapter is about memory elements called flip-fops. 7-1 RS LATCHES A Mp-flop is a device with two stable states; it remains in one of these states until triggered into the other. The RS latch, discussed in this section, is one of the simplest Mlip- flops. Transistor Latch In Fig. 7-1a each collector drives the opposite base through a 100-K£) resisitor. In a circuit like this, one of the transistors is saturated and the other is cut off. For instance, if the right transistor is saturated, its colector voltage is approximately O V. This means that there is no base drive for the left transistor, so it cuts off and its collector voltage approaches +5 V. This high voltage produces enough base current in the right transistor to sustain its saturation. The overall circuit is fatched with the left transistor cut off (dark shading) and the right transistor saturated. Q is approximately O V. By a similar argument, if the left transistor is saturated, the right transistor is cut off. Figure 7-1h illustrates this other state. Q is approximately 5 V for this condition. Output Q can be low or high. binary O or 1. Tf lutched as shown in Fig. 7-la, the circuit is storing a binary O becausc Q=0 On the other hand, when latched as shown in Fig. 7-1b, the circuit stores a binary | because Q=1 so Control Inputs To control the bit stored in the latch, we can add the inputs shown in Fig. 7-1c. These control inputs will be either low (0 V) or high (+5 V). A high set input $ forces the left transistor to saturate. Ás soon as the left transistor saturates, the overall circuit latches and 9=1 Once set, the output will remain a 1 even though the $ input goes back to O V. A high reset input R drives the right transistor into saturation, Once this happens, the circuit latches and 2=0 The output stays latched in the O state, even though the R input returns to a low. In Fig. 7-1c, Q represents the stored bit, A complementary output Q is available trom the colector of the left transistor. This may or may not be used, depending on the application. Truth Table Table 7-1 summarizes the operation of the transistor latch. With both control inputs low. no change can occur in the output and the circuit remains latched in its last state. This condition is called the inactive state because nothing changes. TABLE 7-1. TRANSISTOR LATCH RS q Comments 0 0 NC No change 21 1 Set 1 0 0 Reset i 1 * Race BK SR 100kS Fig. 7-1 (a) Latched state; (b) altemative state; (7) trigger inputs. When R is low and S is high, the circuit sets the Q output to a high. On the other hand, if R is high and S is low, the Q output resets to a low. Race Condition Look at the last entry in Table 7-1. R and S are high simultaneously. This is called a race condition; it is never used because it leads to unpredictable operation. Here's why. If both control inputs are high, both tran- sistors saturate. When the R and S$ inputs return to low, both transistors try to come out of saturation. 1t is a race between the transistors to sec which one desaturates first. The faster transistor (the onç with the shorter saturation delay time) will sin the race and latch the circuit. Tf the faster transistor is on the left side of Fig. 7-1c, the Q output will be low. If the faster transistor is on the right side, the O output will go high. In mass production, either transistor can be faster; therefore, the Q output is unpredictable. This is why the race condition must be avoided. Here's how to recognize a race condition. If simultane- ously changing both inputs to a memory element leads to an unpredictable output, you"ve got a race condition. With the transistor latch, R = land S = 1isa race condition fo) because simultaneously returning R and S to O forces O into a random state. From now on, an asterisk in a truth table (see Table 7-1) indicates a race condition, sometimes called a forbidden or invalid state. NOR Latches A discrete circuit like Fig. 7-1c is rarely uscd because we are in the age of integrated circuits. Nowadays, you build RS latches with NOR gates or NAND gates. Figure 7-24 shows how it's done with NOR pates. Figure 7-2b is the De Morgan equivalent. As shown in Table 7-2, a low R and a low S give us the inactive state; the circuit stores or remembers, A low R and a high S represent the set state, while a high R and a low S give the reset state. Finally, a high R and a high S produce a race condition; therefore, we must avoid R = landS=1 when using a NOR latch. Figure 7-2c is a timing diagram; it shows how the input signals interact to produce the output signal. As you see, the Q output goes high when S goes high. Q remains high after S goes low. Q returns to low when R goes high, and stays low after R returns to low. Chapter 7 FlpFlops 91