Digital Design and Computer Architecture 2nd Edition PDF

From Zero to One 1 1.1 The Game Plan...

From Zero to One 1 1.1 The Game Plan 1.2 The Art of Managing Complexity 1.3 The Digital Abstraction 1.4 Number Systems 1.5 Logic Gates 1.1 THE GAME PLAN 1.6 Beneath the Digital Abstraction Microprocessors have revolutionized our world during the past three dec- ades. A laptop computer today has far more capability than a room-sized 1.7 CMOS Transistors* mainframe of yesteryear. A luxury automobile contains about 100 micro- 1.8 Power Consumption* processors. Advances in microprocessors have made cell phones and the 1.9 Summary and a Look Ahead Internet possible, have vastly improved medicine, and have transformed Exercises how war is waged. Worldwide semiconductor industry sales have grown Interview Questions from US $21 billion in 1985 to $306 billion in 2013, and microprocessors are a major segment of these sales. We believe that microprocessors are not only technically, economically, and socially important, but are also Application >”hello Software world!” an intrinsically fascinating human invention. By the time you finish read- ing this book, you will know how to design and build your own micro- Operating processor. The skills you learn along the way will prepare you to design Systems many other digital systems. We assume that you have a basic familiarity with electricity, some Architecture prior programming experience, and a genuine interest in understanding what goes on under the hood of a computer. This book focuses on the Micro- architecture design of digital systems, which operate on 1’s and 0’s. We begin with digital logic gates that accept 1’s and 0’s as inputs and produce 1’s and Logic + 0’s as outputs. We then explore how to combine logic gates into more complicated modules such as adders and memories. Then we shift gears Digital to programming in assembly language, the native tongue of the micropro- Circuits cessor. Finally, we put gates together to build a microprocessor that runs these assembly language programs. Analog + Circuits − A great advantage of digital systems is that the building blocks are quite simple: just 1’s and 0’s. They do not require grungy mathematics Devices or a profound knowledge of physics. Instead, the designer’s challenge is to combine these simple blocks into complicated systems. A microproces- sor may be the first system that you build that is too complex to fit in Physics Digital Design and Computer Architecture, Second Edition. DOI: 10.1016/B978-0-12-394424-5.00001-X 3 © 2013 Elsevier, Inc. All rights reserved. 4 CHAPTER ONE From Zero to One your head all at once. One of the major themes weaved through this book is how to manage complexity. 1.2 THE ART OF MANAGING COMPLEXITY One of the characteristics that separates an engineer or computer scientist from a layperson is a systematic approach to managing complexity. Mod- ern digital systems are built from millions or billions of transistors. No human being could understand these systems by writing equations describing the movement of electrons in each transistor and solving all of the equations simultaneously. You will need to learn to manage com- plexity to understand how to build a microprocessor without getting mired in a morass of detail. 1. 2. 1 Abstraction The critical technique for managing complexity is abstraction: hiding details when they are not important. A system can be viewed from many different levels of abstraction. For example, American politicians abstract the world into cities, counties, states, and countries. A county contains multiple cities and a state contains many counties. When a politician is running for president, the politician is mostly interested in how the state as a whole will vote, rather than how each county votes, so the state is the most useful level of abstraction. On the other hand, the Census Application >”hello Programs Bureau measures the population of every city, so the agency must con- Software world!” sider the details of a lower level of abstraction. Operating Device Figure 1.1 illustrates levels of abstraction for an electronic computer Systems Drivers system along with typical building blocks at each level. At the lowest level Instructions of abstraction is the physics, the motion of electrons. The behavior of Architecture Registers electrons is described by quantum mechanics and Maxwell’s equations. Micro- Datapaths Our system is constructed from electronic devices such as transistors (or architecture Controllers vacuum tubes, once upon a time). These devices have well-defined con- Adders nection points called terminals and can be modeled by the relationship Logic + Memories between voltage and current as measured at each terminal. By abstracting Digital AND Gates to this device level, we can ignore the individual electrons. The next level Circuits NOT Gates of abstraction is analog circuits, in which devices are assembled to create Analog Amplifiers components such as amplifiers. Analog circuits input and output a contin- + Circuits − Filters uous range of voltages. Digital circuits such as logic gates restrict the vol- tages to discrete ranges, which we will use to indicate 0 and 1. In logic Transistors Devices Diodes design, we build more complex structures, such as adders or memories, from digital circuits. Physics Electrons Microarchitecture links the logic and architecture levels of abstraction. The architecture level of abstraction describes a computer from the pro- Figure 1.1 Levels of abstraction grammer’s perspective. For example, the Intel x86 architecture used by for an electronic computing system microprocessors in most personal computers (PCs) is defined by a set of  1.2 The Art of Managing Complexity 5 instructions and registers (memory for temporarily storing variables) that the programmer is allowed to use. Microarchitecture involves combining logic elements to execute the instructions defined by the architecture. A particular architecture can be implemented by one of many different microarchitectures with different price/performance/power trade-offs. For example, the Intel Core i7, the Intel 80486, and the AMD Athlon all imple- ment the x86 architecture with different microarchitectures. Moving into the software realm, the operating system handles low- level details such as accessing a hard drive or managing memory. Finally, the application software uses these facilities provided by the operating sys- tem to solve a problem for the user. Thanks to the power of abstraction, your grandmother can surf the Web without any regard for the quantum vibrations of electrons or the organization of the memory in her computer. This book focuses on the levels of abstraction from digital circuits Each chapter in this book through computer architecture. When you are working at one level of begins with an abstraction abstraction, it is good to know something about the levels of abstraction icon indicating the focus of the immediately above and below where you are working. For example, a chapter in deep blue, with computer scientist cannot fully optimize code without understanding the secondary topics shown in architecture for which the program is being written. A device engineer lighter shades of blue. cannot make wise trade-offs in transistor design without understanding the circuits in which the transistors will be used. We hope that by the time you finish reading this book, you can pick the level of abstraction appro- priate to solving your problem and evaluate the impact of your design choices on other levels of abstraction. 1. 2. 2 Discipline Discipline is the act of intentionally restricting your design choices so that you can work more productively at a higher level of abstraction. Using interchangeable parts is a familiar application of discipline. One of the first examples of interchangeable parts was in flintlock rifle manufactur- ing. Until the early 19th century, rifles were individually crafted by hand. Components purchased from many different craftsmen were carefully filed and fit together by a highly skilled gunmaker. The discipline of inter- changeable parts revolutionized the industry. By limiting the components to a standardized set with well-defined tolerances, rifles could be assembled and repaired much faster and with less skill. The gunmaker no longer con- cerned himself with lower levels of abstraction such as the specific shape of an individual barrel or gunstock. In the context of this book, the digital discipline will be very impor- tant. Digital circuits use discrete voltages, whereas analog circuits use con- tinuous voltages. Therefore, digital circuits are a subset of analog circuits and in some sense must be capable of less than the broader class of analog circuits. However, digital circuits are much simpler to design. By limiting 6 CHAPTER ONE From Zero to One ourselves to digital circuits, we can easily combine components into sophisticated systems that ultimately outperform those built from analog components in many applications. For example, digital televisions, com- pact disks (CDs), and cell phones are replacing their analog predecessors. 1. 2. 3 The Three-Y’s In addition to abstraction and discipline, designers use the three “-y’s” to manage complexity: hierarchy, modularity, and regularity. These princi- ples apply to both software and hardware systems. ▶ Hierarchy involves dividing a system into modules, then further sub- dividing each of these modules until the pieces are easy to understand. Captain Meriwether Lewis of ▶ Modularity states that the modules have well-defined functions and the Lewis and Clark interfaces, so that they connect together easily without unanticipated Expedition was one of the side effects. early advocates of interchangeable parts for ▶ Regularity seeks uniformity among the modules. Common modules rifles. In 1806, he explained: are reused many times, reducing the number of distinct modules that must be designed. The guns of Drewyer and Sergt. Pryor were both out of order. To illustrate these “-y’s” we return to the example of rifle manufac- The first was repared with a turing. A flintlock rifle was one of the most intricate objects in common new lock, the old one having use in the early 19th century. Using the principle of hierarchy, we can become unfit for use; the second break it into components shown in Figure 1.2: the lock, stock, and barrel. had the cock screw broken The barrel is the long metal tube through which the bullet is fired. which was replaced by a The lock is the firing mechanism. And the stock is the wooden body that duplicate which had been pre- pared for the lock at Harpers holds the parts together and provides a secure grip for the user. In turn, Ferry where she was manufac- the lock contains the trigger, hammer, flint, frizzen, and pan. Each of tured. But for the precaution these components could be hierarchically described in further detail. taken in bringing on those extra Modularity teaches that each component should have a well-defined locks, and parts of locks, in function and interface. A function of the stock is to mount the barrel addition to the ingenuity of and lock. Its interface consists of its length and the location of its mount- John Shields, most of our guns ing pins. In a modular rifle design, stocks from many different manufac- would at this moment be turers can be used with a particular barrel as long as the stock and entirely unfit for use; but barrel are of the correct length and have the proper mounting mechanism. fortunately for us I have it in A function of the barrel is to impart spin to the bullet so that it travels my power here to record that more accurately. Modularity dictates that there should be no side effects: they are all in good order. the design of the stock should not impede the function of the barrel. See Elliott Coues, ed., The Regularity teaches that interchangeable parts are a good idea. With History of the Lewis and regularity, a damaged barrel can be replaced by an identical part. The Clark Expedition… (4 vols), barrels can be efficiently built on an assembly line, instead of being pains- New York: Harper, 1893; takingly hand-crafted. reprint, 3 vols, New York: Dover, 3:817. We will return to these principles of hierarchy, modularity, and regu- larity throughout the book.  1.3 The Digital Abstraction 7 Barrel Lock Stock Figure 1.2 Flintlock rifle with a close-up view of the lock (Image by Euroarms Italia. www.euroarms.net © 2006.) Flint Cock String Spring Pan Expanded view of Lock 1.3 THE DIGITAL ABSTRACTION Most physical variables are continuous. For example, the voltage on a Charles Babbage, 1791–1871. wire, the frequency of an oscillation, or the position of a mass are all con- Attended Cambridge University tinuous quantities. Digital systems, on the other hand, represent informa- and married Georgiana tion with discrete-valued variables—that is, variables with a finite number Whitmore in 1814. Invented the of distinct values. Analytical Engine, the world’s An early digital system using variables with ten discrete values was first mechanical computer. Also Charles Babbage’s Analytical Engine. Babbage labored from 1834 to invented the cowcatcher and the 1871, designing and attempting to build this mechanical computer. The universal postage rate. Interested in lock-picking, but abhorred Analytical Engine used gears with ten positions labeled 0 through 9, much street musicians (image courtesy like a mechanical odometer in a car. Figure 1.3 shows a prototype of the of Fourmilab Switzerland, Analytical Engine, in which each row processes one digit. Babbage chose www.fourmilab.ch). 25 rows of gears, so the machine has 25-digit precision. 8 CHAPTER ONE From Zero to One Figure 1.3 Babbage’s Analytical Engine, under construction at the time of his death in 1871 (image courtesy of Science Museum/Science and Society Picture Library) Unlike Babbage’s machine, most electronic computers use a binary (two-valued) representation in which a high voltage indicates a '1' and a low voltage indicates a '0', because it is easier to distinguish between two voltages than ten. The amount of information D in a discrete valued variable with N distinct states is measured in units of bits as D = log2 N bits (1.1) A binary variable conveys log22 = 1 bit of information. Indeed, the word bit is short for binary digit. Each of Babbage’s gears carried log210 = 3.322 bits of information because it could be in one of 23.322 = 10 unique positions. A continuous signal theoretically contains an infinite amount of information because it can take on an infinite number of values. In practice, noise and measurement error limit the information to only 10 to 16 bits for most con- George Boole, 1815–1864. Born to working-class parents and unable tinuous signals. If the measurement must be made rapidly, the information to afford a formal education, content is lower (e.g., 8 bits). Boole taught himself This book focuses on digital circuits using binary variables: 1’s and 0’s. mathematics and joined the George Boole developed a system of logic operating on binary variables faculty of Queen’s College in that is now known as Boolean logic. Each of Boole’s variables could be Ireland. He wrote An TRUE or FALSE. Electronic computers commonly use a positive voltage Investigation of the Laws of to represent '1' and zero volts to represent '0'. In this book, we will use Thought (1854), which the terms '1', TRUE, and HIGH synonymously. Similarly, we will use '0', introduced binary variables and FALSE, and LOW interchangeably. the three fundamental logic The beauty of the digital abstraction is that digital designers can focus operations: AND, OR, and NOT on 1’s and 0’s, ignoring whether the Boolean variables are physically repre- (image courtesy of the American Institute of Physics). sented with specific voltages, rotating gears, or even hydraulic fluid levels. A computer programmer can work without needing to know the intimate  1.4 Number Systems 9 details of the computer hardware. On the other hand, understanding the details of the hardware allows the programmer to optimize the software better for that specific computer. An individual bit doesn’t carry much information. In the next section, we examine how groups of bits can be used to represent numbers. In later chapters, we will also use groups of bits to represent letters and programs. 1.4 NUMBER SYSTEMS You are accustomed to working with decimal numbers. In digital systems consisting of 1’s and 0’s, binary or hexadecimal numbers are often more convenient. This section introduces the various number systems that will be used throughout the rest of the book. 1. 4. 1 Decimal Numbers In elementary school, you learned to count and do arithmetic in decimal. Just as you (probably) have ten fingers, there are ten decimal digits: 0, 1, 2, …, 9. Decimal digits are joined together to form longer decimal num- bers. Each column of a decimal number has ten times the weight of the previous column. From right to left, the column weights are 1, 10, 100, 1000, and so on. Decimal numbers are referred to as base 10. The base is indicated by a subscript after the number to prevent confusion when working in more than one base. For example, Figure 1.4 shows how the decimal number 974210 is written as the sum of each of its digits multi- plied by the weight of the corresponding column. An N-digit decimal number represents one of 10N possibilities: 0, 1, 2, 3, …, 10N − 1. This is called the range of the number. For example, a three-digit decimal number represents one of 1000 possibilities in the range of 0 to 999. 1. 4. 2 Binary Numbers Bits represent one of two values, 0 or 1, and are joined together to form binary numbers. Each column of a binary number has twice the weight of the previous column, so binary numbers are base 2. In binary, the 1000's column 100's column 10's column 1's column Figure 1.4 Representation of a decimal number 974210 = 9 × 10 3 + 7 × 102 + 4 × 10 1 + 2 × 100 nine seven four two thousands hundreds tens ones 10 CHAPTER ONE From Zero to One column weights (again from right to left) are 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, and so on. If you work with binary numbers often, you’ll save time if you remember these powers of two up to 216. An N-bit binary number represents one of 2N possibilities: 0, 1, 2, 3, …, N 2 − 1. Table 1.1 shows 1, 2, 3, and 4-bit binary numbers and their decimal equivalents. Example 1.1 BINARY TO DECIMAL CONVERSION Convert the binary number 101102 to decimal. Solution: Figure 1.5 shows the conversion. Table 1.1 Binary numbers and their decimal equivalent 1-Bit 2-Bit 3-Bit 4-Bit Binary Binary Binary Binary Decimal Numbers Numbers Numbers Numbers Equivalents 0 00 000 0000 0 1 01 001 0001 1 10 010 0010 2 11 011 0011 3 100 0100 4 101 0101 5 110 0110 6 111 0111 7 1000 8 1001 9 1010 10 1011 11 1100 12 1101 13 1110 14 1111 15  1.4 Number Systems 11 16's column 8's column 4's column 2's column 1's column Figure 1.5 Conversion of a binary number to decimal 10110 2 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21+ 0 × 2 0 = 2210 one no one one no sixteen eight four two one Example 1.2 DECIMAL TO BINARY CONVERSION Convert the decimal number 8410 to binary. Solution: Determine whether each column of the binary result has a 1 or a 0. We can do this starting at either the left or the right column. Working from the left, start with the largest power of 2 less than or equal to the number (in this case, 64). 84 ≥ 64, so there is a 1 in the 64’s column, leaving 84 − 64 = 20. 20 < 32, so there is a 0 in the 32’s column. 20 ≥ 16, so there is a 1 in the 16’s column, leaving 20 − 16 = 4. 4 < 8, so there is a 0 in the 8’s column. 4 ≥ 4, so there is a 1 in the 4’s column, leaving 4 − 4 = 0. Thus there must be 0’s in the 2’s and 1’s column. Putting this all together, 8410 = 10101002. Working from the right, repeatedly divide the number by 2. The remainder goes in each column. 84/2 = 42, so 0 goes in the 1’s column. 42/2 = 21, so 0 goes in the 2’s column. 21/2 = 10 with a remainder of 1 going in the 4’s column. 10/2 = 5, so 0 goes in the 8’s column. 5/2 = 2 with a remainder of 1 going in the 16’s column. 2/2 = 1, so 0 goes in the 32’s column. Finally 1/2 = 0 with a remainder of 1 going in the 64’s column. Again, 8410 = 10101002. 1. 4. 3 Hexadecimal Numbers “Hexadecimal,” a term coined Writing long binary numbers becomes tedious and prone to error. A group by IBM in 1963, derives from of four bits represents one of 24 = 16 possibilities. Hence, it is sometimes the Greek hexi (six) and Latin decem (ten). A more proper more convenient to work in base 16, called hexadecimal. Hexadecimal term would use the Latin sexa numbers use the digits 0 to 9 along with the letters A to F, as shown (six), but sexadecimal sounded in Table 1.2. Columns in base 16 have weights of 1, 16, 162 (or 256), too risqué. 163 (or 4096), and so on. Example 1.3 HEXADECIMAL TO BINARY AND DECIMAL CONVERSION Convert the hexadecimal number 2ED16 to binary and to decimal. Solution: Conversion between hexadecimal and binary is easy because each hexa- decimal digit directly corresponds to four binary digits. 216 = 00102, E16 = 11102 and D16 = 11012, so 2ED16 = 0010111011012. Conversion to decimal requires the arithmetic shown in Figure 1.6. 12 CHAPTER ONE From Zero to One Table 1.2 Hexadecimal number system Hexadecimal Digit Decimal Equivalent Binary Equivalent 0 0 0000 1 1 0001 2 2 0010 3 3 0011 4 4 0100 5 5 0101 6 6 0110 7 7 0111 8 8 1000 9 9 1001 A 10 1010 B 11 1011 C 12 1100 D 13 1101 E 14 1110 F 15 1111 256's column 16's column 1's column Figure 1.6 Conversion of a hexadecimal number to decimal 2ED 16 = 2 × 16 2 + E × 16 1 + D × 16 0 = 74910 two fourteen thirteen two hundred sixteens ones fifty six's Example 1.4 BINARY TO HEXADECIMAL CONVERSION Convert the binary number 11110102 to hexadecimal. Solution: Again, conversion is easy. Start reading from the right. The four least significant bits are 10102 = A16. The next bits are 1112 = 716. Hence 11110102 = 7A16.  1.4 Number Systems 13 Example 1.5 DECIMAL TO HEXADECIMAL AND BINARY CONVERSION Convert the decimal number 33310 to hexadecimal and binary. Solution: Like decimal to binary conversion, decimal to hexadecimal conversion can be done from the left or the right. Working from the left, start with the largest power of 16 less than or equal to the number (in this case, 256). 256 goes into 333 once, so there is a 1 in the 256’s col- umn, leaving 333 − 256 = 77. 16 goes into 77 four times, so there is a 4 in the 16’s column, leaving 77 − 16 × 4 = 13. 1310 = D16, so there is a D in the 1’s column. In summary, 33310 = 14D16. Now it is easy to convert from hexadecimal to binary, as in Example 1.3. 14D16 = 1010011012. Working from the right, repeatedly divide the number by 16. The remainder goes in each column. 333/16 = 20 with a remainder of 1310 = D16 going in the 1’s column. 20/16 = 1 with a remainder of 4 going in the 16’s column. 1/16 = 0 with a remainder of 1 going in the 256’s column. Again, the result is 14D16. 1. 4. 4 Bytes, Nibbles, and All That Jazz A group of eight bits is called a byte. It represents one of 28 = 256 possi- bilities. The size of objects stored in computer memories is customarily measured in bytes rather than bits. A group of four bits, or half a byte, is called a nibble. It represents one of 24 = 16 possibilities. One hexadecimal digit stores one nibble and two hexadecimal digits store one full byte. Nibbles are no longer a com- monly used unit, but the term is cute. A microprocessor is a processor Microprocessors handle data in chunks called words. The size of a built on a single chip. Until the word depends on the architecture of the microprocessor. When this chap- 1970’s, processors were too ter was written in 2015, most computers had 64-bit processors, indicat- complicated to fit on one chip, ing that they operate on 64-bit words. At the time, older computers so mainframe processors were handling 32-bit words were also widely available. Simpler microproces- built from boards containing sors, especially those used in gadgets such as toasters, use 8- or 16-bit many chips. Intel introduced the words. first 4-bit microprocessor, called Within a group of bits, the bit in the 1’s column is called the least the 4004, in 1971. Now, even significant bit (lsb), and the bit at the other end is called the most the most sophisticated significant bit (msb), as shown in Figure 1.7(a) for a 6-bit binary supercomputers are built using microprocessors. We will use the number. Similarly, within a word, the bytes are identified as least terms microprocessor and significant byte (LSB) through most significant byte (MSB), as shown in processor interchangeably Figure 1.7(b) for a four-byte number written with eight hexadecimal throughout this book. digits. 14 CHAPTER ONE From Zero to One 101100 DEAFDAD8 Figure 1.7 Least and most most least most least significant bits and bytes significant significant significant significant bit bit byte byte (a) (b) By handy coincidence, 210 = 1024 ≈ 103. Hence, the term kilo (Greek for thousand) indicates 210. For example, 210 bytes is one kilobyte (1 KB). Similarly, mega (million) indicates 220 ≈ 106, and giga (billion) indicates 230 ≈ 109. If you know 210 ≈ 1 thousand, 220 ≈ 1 million, 230 ≈ 1 billion, and remember the powers of two up to 29, it is easy to estimate any power of two in your head. Example 1.6 ESTIMATING POWERS OF TWO Find the approximate value of 224 without using a calculator. Solution: Split the exponent into a multiple of ten and the remainder. 224 = 220 × 24. 220 ≈ 1 million. 24 = 16. So 224 ≈ 16 million. Technically, 224 = 16,777,216, but 16 million is close enough for marketing purposes. 1024 bytes is called a kilobyte (KB). 1024 bits is called a kilobit (Kb or Kbit). Similarly, MB, Mb, GB, and Gb are used for millions and bil- lions of bytes and bits. Memory capacity is usually measured in bytes. Communication speed is usually measured in bits/sec. For example, the maximum speed of a dial-up modem is usually 56 kbits/sec. 1. 4. 5 Binary Addition Binary addition is much like decimal addition, but easier, as shown in Figure 1.8. As in decimal addition, if the sum of two numbers is greater than what fits in a single digit, we carry a 1 into the next column. Figure 1.8 compares addition of decimal and binary numbers. In the right-most column of Figure 1.8(a), 7 + 9 = 16, which cannot fit in a sin- gle digit because it is greater than 9. So we record the 1’s digit, 6, and carry the 10’s digit, 1, over to the next column. Likewise, in binary, if the sum of two numbers is greater than 1, we carry the 2’s digit over to the next column. For example, in the right-most column of Figure 1.8(b), 11 carries 11 Figure 1.8 Addition examples 4277 1011 showing carries: (a) decimal + 5499 + 0011 (b) binary 9776 1110 (a) (b)  1.4 Number Systems 15 the sum 1 + 1 = 210 = 102 cannot fit in a single binary digit. So we record the 1’s digit (0) and carry the 2’s digit (1) of the result to the next column. In the second column, the sum is 1 + 1 + 1 = 310 = 112. Again, we record the 1’s digit (1) and carry the 2’s digit (1) to the next column. For obvious reasons, the bit that is carried over to the neighboring column is called the carry bit. Example 1.7 BINARY ADDITION 111 0111 Compute 01112 + 01012. + 0101 1100 Solution: Figure 1.9 shows that the sum is 11002. The carries are indicated in blue. We can check our work by repeating the computation in decimal. 01112 = 710. Figure 1.9 Binary addition 01012 = 510. The sum is 1210 = 11002. example Digital systems usually operate on a fixed number of digits. Addition is said to overflow if the result is too big to fit in the available digits. A 4-bit number, for example, has the range [0, 15]. 4-bit binary addition overflows if the result exceeds 15. The fifth bit is discarded, producing an incorrect result in the remaining four bits. Overflow can be detected by checking for a carry out of the most significant column. Example 1.8 ADDITION WITH OVERFLOW Compute 11012 + 01012. Does overflow occur? 11 1 Solution: Figure 1.10 shows the sum is 100102. This result overflows the range of 1101 + 0101 a 4-bit binary number. If it must be stored as four bits, the most significant bit is 10010 discarded, leaving the incorrect result of 00102. If the computation had been done using numbers with five or more bits, the result 100102 would have been Figure 1.10 Binary addition correct. example with overflow 1. 4. 6 Signed Binary Numbers So far, we have considered only unsigned binary numbers that represent positive quantities. We will often want to represent both positive and negative numbers, requiring a different binary number system. Several schemes exist to represent signed binary numbers; the two most widely employed are called sign/magnitude and two’s complement. Sign/Magnitude Numbers Sign/magnitude numbers are intuitively appealing because they match our custom of writing negative numbers with a minus sign followed by the magnitude. An N-bit sign/magnitude number uses the most significant 16 CHAPTER ONE From Zero to One The $7 billion Ariane 5 rocket, bit as the sign and the remaining N−1 bits as the magnitude (absolute launched on June 4, 1996, value). A sign bit of 0 indicates positive and a sign bit of 1 indicates veered off course 40 seconds negative. after launch, broke up, and exploded. The failure was Example 1.9 SIGN/MAGNITUDE NUMBERS caused when the computer controlling the rocket Write 5 and −5 as 4-bit sign/magnitude numbers overflowed its 16-bit range and crashed. Solution: Both numbers have a magnitude of 510 = 1012. Thus, 510 = 01012 and The code had been extensively −510 = 11012. tested on the Ariane 4 rocket. However, the Ariane 5 had a faster engine that produced larger Unfortunately, ordinary binary addition does not work for sign/ values for the control computer, magnitude numbers. For example, using ordinary addition on −510 + 510 leading to the overflow. gives 11012 + 01012 = 100102, which is nonsense. An N-bit sign/magnitude number spans the range [−2N−1 + 1, 2N−1 − 1]. Sign/magnitude numbers are slightly odd in that both +0 and −0 exist. Both indicate zero. As you may expect, it can be troublesome to have two different representations for the same number. Two’s Complement Numbers Two’s complement numbers are identical to unsigned binary numbers except that the most significant bit position has a weight of −2N−1 instead of 2N−1. They overcome the shortcomings of sign/magnitude numbers: zero has a single representation, and ordinary addition works. In two’s complement representation, zero is written as all zeros: 00…0002. The most positive number has a 0 in the most significant posi- tion and 1’s elsewhere: 01…1112 = 2N−1 − 1. The most negative number has a 1 in the most significant position and 0’s elsewhere: 10…0002 = −2N−1. And −1 is written as all ones: 11…1112. Notice that positive numbers have a 0 in the most significant position and negative numbers have a 1 in this position, so the most significant (Photograph courtesy of bit can be viewed as the sign bit. However, the overall number is inter- ESA/CNES/ARIANESPACE- preted differently for two’s complement numbers and sign/magnitude Service Optique CS6.) numbers. The sign of a two’s complement number is reversed in a process called taking the two’s complement. The process consists of inverting all of the bits in the number, then adding 1 to the least significant bit position. This is useful to find the representation of a negative number or to determine the magnitude of a negative number. Example 1.10 TWO’S COMPLEMENT REPRESENTATION OF A NEGATIVE NUMBER Find the representation of −210 as a 4-bit two’s complement number.  1.4 Number Systems 17 Solution: Start with + 210 = 00102. To get −210, invert the bits and add 1. Inverting 00102 produces 11012. 11012 + 1 = 11102. So −210 is 11102. Example 1.11 VALUE OF NEGATIVE TWO’S COMPLEMENT NUMBERS Find the decimal value of the two’s complement number 10012. Solution: 10012 has a leading 1, so it must be negative. To find its magnitude, invert the bits and add 1. Inverting 10012 = 01102. 01102 + 1 = 01112 = 710. Hence, 10012 = −710. Two’s complement numbers have the compelling advantage that addition works properly for both positive and negative numbers. Recall that when adding N-bit numbers, the carry out of the Nth bit (i.e., the N + 1th result bit) is discarded. Example 1.12 ADDING TWO’S COMPLEMENT NUMBERS Compute (a) −210 + 110 and (b) −710 + 710 using two’s complement numbers. Solution: (a) −210 + 110 = 11102 + 00012 = 11112 = −110. (b) −710 + 710 = 10012 + 01112 = 100002. The fifth bit is discarded, leaving the correct 4-bit result 00002. Subtraction is performed by taking the two’s complement of the sec- ond number, then adding. Example 1.13 SUBTRACTING TWO’S COMPLEMENT NUMBERS Compute (a) 510 − 310 and (b) 310 − 510 using 4-bit two’s complement numbers. Solution: (a) 310 = 00112. Take its two’s complement to obtain −310 = 11012. Now add 510 + (−310) = 01012 + 11012 = 00102 = 210. Note that the carry out of the most significant position is discarded because the result is stored in four bits. (b) Take the two’s complement of 510 to obtain −510 = 1011. Now add 310 + (−510) = 00112 + 10112 = 11102 = −210. The two’s complement of 0 is found by inverting all the bits (produ- cing 11…1112) and adding 1, which produces all 0’s, disregarding the carry out of the most significant bit position. Hence, zero is always repre- sented with all 0’s. Unlike the sign/magnitude system, the two’s comple- ment system has no separate −0. Zero is considered positive because its sign bit is 0. 18 CHAPTER ONE From Zero to One Like unsigned numbers, N-bit two’s complement numbers represent one of 2N possible values. However the values are split between positive and negative numbers. For example, a 4-bit unsigned number represents 16 values: 0 to 15. A 4-bit two’s complement number also represents 16 values: −8 to 7. In general, the range of an N-bit two’s complement num- ber spans [−2N−1, 2N−1 − 1]. It should make sense that there is one more negative number than positive number because there is no −0. The most negative number 10…0002 = −2N−1 is sometimes called the weird num- ber. Its two’s complement is found by inverting the bits (producing 01…1112) and adding 1, which produces 10…0002, the weird number, again. Hence, this negative number has no positive counterpart. Adding two N-bit positive numbers or negative numbers may cause overflow if the result is greater than 2N−1 − 1 or less than −2N−1. Add- ing a positive number to a negative number never causes overflow. Unlike unsigned numbers, a carry out of the most significant column does not indicate overflow. Instead, overflow occurs if the two numbers being added have the same sign bit and the result has the opposite sign bit. Example 1.14 ADDING TWO’S COMPLEMENT NUMBERS WITH OVERFLOW Compute 410 + 510 using 4-bit two’s complement numbers. Does the result overflow? Solution: 410 + 510 = 01002 + 01012 = 10012 = −710. The result overflows the range of 4-bit positive two’s complement numbers, producing an incorrect negative result. If the computation had been done using five or more bits, the result 010012 = 910 would have been correct. When a two’s complement number is extended to more bits, the sign bit must be copied into the most significant bit positions. This process is called sign extension. For example, the numbers 3 and −3 are written as 4-bit two’s complement numbers 0011 and 1101, respectively. They are sign-extended to seven bits by copying the sign bit into the three new upper bits to form 0000011 and 1111101, respectively. Comparison of Number Systems The three most commonly used binary number systems are unsigned, two’s complement, and sign/magnitude. Table 1.3 compares the range of N-bit numbers in each of these three systems. Two’s complement num- bers are convenient because they represent both positive and negative integers and because ordinary addition works for all numbers. Subtrac- tion is performed by negating the second number (i.e., taking the two’s  1.5 Logic Gates 19 Table 1.3 Range of N-bit numbers System Range Unsigned [0, 2N – 1] Sign/Magnitude [–2N–1 + 1, 2N–1 – 1] Two’s Complement [–2N–1, 2N–1 – 1] –8 –7 –6 –5 –4 –3 –2 –1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Unsigned 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 Two's Complement 0000 1111 1110 1101 1100 1011 1010 1001 1000 0001 0010 0011 0100 0101 0110 0111 Sign / Magnitude Figure 1.11 Number line and 4-bit binary encodings complement), and then adding. Unless stated otherwise, assume that all signed binary numbers use two’s complement representation. Figure 1.11 shows a number line indicating the values of 4-bit num- bers in each system. Unsigned numbers span the range [0, 15] in regular binary order. Two’s complement numbers span the range [−8, 7]. The nonnegative numbers [0, 7] share the same encodings as unsigned num- bers. The negative numbers [−8, −1] are encoded such that a larger unsigned binary value represents a number closer to 0. Notice that the weird number, 1000, represents −8 and has no positive counterpart. Sign/magnitude numbers span the range [−7, 7]. The most significant bit is the sign bit. The positive numbers [1, 7] share the same encodings as unsigned numbers. The negative numbers are symmetric but have the sign bit set. 0 is represented by both 0000 and 1000. Thus, N-bit sign/ magnitude numbers represent only 2N − 1 integers because of the two repre- sentations for 0. 1.5 LOGIC GATES Now that we know how to use binary variables to represent information, we explore digital systems that perform operations on these binary vari- ables. Logic gates are simple digital circuits that take one or more binary inputs and produce a binary output. Logic gates are drawn with a symbol showing the input (or inputs) and the output. Inputs are usually drawn on 20 CHAPTER ONE From Zero to One the left (or top) and outputs on the right (or bottom). Digital designers typically use letters near the beginning of the alphabet for gate inputs and the letter Y for the gate output. The relationship between the inputs and the output can be described with a truth table or a Boolean equation. A truth table lists inputs on the left and the corresponding output on the right. It has one row for each possible combination of inputs. A Boolean NOT equation is a mathematical expression using binary variables. A Y 1. 5. 1 NOT Gate Y=A A NOT gate has one input, A, and one output, Y, as shown in Figure 1.12. A Y The NOT gate’s output is the inverse of its input. If A is FALSE, then Y is 0 1 TRUE. If A is TRUE, then Y is FALSE. This relationship is summarized by 1 0 the truth table and Boolean equation in the figure. The line over A in the Figure 1.12 NOT gate Boolean equation is pronounced NOT, so Y = A is read “Y equals NOT A.” The NOT gate is also called an inverter. Other texts use a variety of notations for NOT, including Y = A′, Y = ¬A, BUF Y = !A or Y = ~A. We will use Y = A exclusively, but don’t be puzzled if you A Y encounter another notation elsewhere. Y=A 1. 5. 2 Buffer A Y The other one-input logic gate is called a buffer and is shown in Figure 1.13. 0 0 1 1 It simply copies the input to the output. From the logical point of view, a buffer is no different from a wire, so Figure 1.13 Buffer it might seem useless. However, from the analog point of view, the buffer might have desirable characteristics such as the ability to deliver large AND amounts of current to a motor or the ability to quickly send its output A to many gates. This is an example of why we need to consider multiple Y levels of abstraction to fully understand a system; the digital abstraction B Y = AB hides the real purpose of a buffer. The triangle symbol indicates a buffer. A circle on the output is called A B Y 0 0 0 a bubble and indicates inversion, as was seen in the NOT gate symbol of 0 1 0 Figure 1.12. 1 0 0 1 1 1 1. 5. 3 AND Gate Figure 1.14 AND gate Two-input logic gates are more interesting. The AND gate shown in Figure 1.14 produces a TRUE output, Y, if and only if both A and B According to Larry Wall, are TRUE. Otherwise, the output is FALSE. By convention, the inputs inventor of the Perl are listed in the order 00, 01, 10, 11, as if you were counting in binary. programming language, “the The Boolean equation for an AND gate can be written in several ways: three principal virtues of a Y = A B, Y = AB, or Y = A ∩ B. The ∩ symbol is pronounced “intersec- programmer are Laziness, Impatience, and Hubris.” tion” and is preferred by logicians. We prefer Y = AB, read “Y equals A and B,” because we are lazy.  1.5 Logic Gates 21 1. 5. 4 OR Gate OR A The OR gate shown in Figure 1.15 produces a TRUE output, Y, if either B Y A or B (or both) are TRUE. The Boolean equation for an OR gate is writ- Y=A+B ten as Y = A + B or Y = A ∪ B. The ∪ symbol is pronounced union and is preferred by logicians. Digital designers normally use the + notation, A B Y 0 0 0 Y = A + B is pronounced “Y equals A or B.” 0 1 1 1 0 1 1. 5. 5 Other Two-Input Gates 1 1 1 Figure 1.16 shows other common two-input logic gates. XOR (exclusive Figure 1.15 OR gate OR, pronounced “ex-OR”) is TRUE if A or B, but not both, are TRUE. The XOR operation is indicated by ⊕, a plus sign with a circle around it. Any gate can be followed by a bubble to invert its operation. The NAND gate performs NOT AND. Its output is TRUE unless both inputs A silly way to remember the are TRUE. The NOR gate performs NOT OR. Its output is TRUE if OR symbol is that its input side is curved like Pacman’s neither A nor B is TRUE. An N-input XOR gate is sometimes called a mouth, so the gate is hungry parity gate and produces a TRUE output if an odd number of inputs and willing to eat any TRUE are TRUE. As with two-input gates, the input combinations in the truth inputs it can find! table are listed in counting order. XOR NAND NOR A A A Y Y Y B B B Y=A + B Y = AB Y=A+B A B Y A B Y A B Y 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 Figure 1.16 More two-input logic gates Example 1.15 XNOR GATE Figure 1.17 shows the symbol and Boolean equation for a two-input XNOR gate XNOR that performs the inverse of an XOR. Complete the truth table. A Y Solution: Figure 1.18 shows the truth table. The XNOR output is TRUE if both B inputs are FALSE or both inputs are TRUE. The two-input XNOR gate is sometimes Y=A + B called an equality gate because its output is TRUE when the inputs are equal. A B Y 0 0 0 1 1. 5. 6 Multiple-Input Gates 1 0 1 1 Many Boolean functions of three or more inputs exist. The most common are AND, OR, XOR, NAND, NOR, and XNOR. An N-input AND gate Figure 1.17 XNOR gate 22 CHAPTER ONE From Zero to One A B Y produces a TRUE output when all N inputs are TRUE. An N-input OR 0 0 1 gate produces a TRUE output when at least one input is TRUE. 0 1 0 1 0 0 1 1 1 Example 1.16 THREE-INPUT NOR GATE Figure 1.18 XNOR truth table Figure 1.19 shows the symbol and Boolean equation for a three-input NOR gate. Complete the truth table. NOR3 Solution: Figure 1.20 shows the truth table. The output is TRUE only if none of A B Y the inputs are TRUE. C Y=A+B+C Example 1.17 FOUR-INPUT AND GATE A B C Y 0 0 0 0 0 1 Figure 1.21 shows the symbol and Boolean equation for a four-input AND gate. 0 1 0 Create a truth table. 0 1 1 1 0 0 Solution: Figure 1.22 shows the truth table. The output is TRUE only if all of the 1 0 1 inputs are TRUE. 1 1 0 1 1 1 Figure 1.19 Three-input NOR gate 1.6 BENEATH THE DIGITAL ABSTRACTION A digital system uses discrete-valued variables. However, the variables are A B C Y represented by continuous physical quantities such as the voltage on a 0 0 0 1 0 0 1 0 wire, the position of a gear, or the level of fluid in a cylinder. Hence, 0 1 0 0 the designer must choose a way to relate the continuous value to the dis- 0 1 1 0 crete value. 1 0 0 0 1 0 1 0 For example, consider representing a binary signal A with a voltage on 1 1 0 0 a wire. Let 0 volts (V) indicate A = 0 and 5 V indicate A = 1. Any real sys- 1 1 1 0 tem must tolerate some noise, so 4.97 V probably ought to be interpreted Figure 1.20 Three-input NOR truth as A = 1 as well. But what about 4.3 V? Or 2.8 V? Or 2.500000 V? table 1. 6. 1 Supply Voltage AND4 Suppose the lowest voltage in the system is 0 V, also called ground or GND. A The highest voltage in the system comes from the power supply and is usually B C Y called VDD. In 1970’s and 1980’s technology, VDD was generally 5 V. As D chips have progressed to smaller transistors, VDD has dropped to 3.3 V, Y = ABCD 2.5 V, 1.8 V, 1.5 V, 1.2 V, or even lower to save power and avoid overload- Figure 1.21 Four-input AND gate ing the transistors. 1. 6. 2 Logic Levels The mapping of a continuous variable onto a discrete binary variable is done by defining logic levels, as shown in Figure 1.23. The first gate is called the driver and the second gate is called the receiver. The output of the driver is  1.6 Beneath the Digital Abstraction 23 connected to the input of the receiver. The driver produces a LOW (0) out- A B C D Y put in the range of 0 to VOL or a HIGH (1) output in the range of VOH to 0 0 0 0 0 VDD· If the receiver gets an input in the range of 0 to VIL, it will consider 0 0 0 1 0 0 0 1 0 0 the input to be LOW. If the receiver gets an input in the range of VIH to 0 0 1 1 0 VDD, it will consider the input to be HIGH. If, for some reason such as noise 0 1 0 0 0 or faulty components, the receiver’s input should fall in the forbidden zone 0 1 0 1 0 0 1 1 0 0 between VIL and VIH, the behavior of the gate is unpredictable. VOH,VOL, 0 1 1 1 0 VIH, and VIL are called the output and input high and low logic levels. 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1. 6. 3 Noise Margins 1 0 1 1 0 1 1 0 0 0 If the output of the driver is to be correctly interpreted at the input of the 1 1 0 1 0 receiver, we must choose VOL < VIL and VOH > VIH. Thus, even if the 1 1 1 0 0 1 1 1 1 1 output of the driver is contaminated by some noise, the input of the recei- ver will still detect the correct logic level. The noise margin is the amount Figure 1.22 Four-input AND truth of noise that could be added to a worst-case output such that the signal table can still be interpreted as a valid input. As can be seen in Figure 1.23, the low and high noise margins are, respectively NML = VIL − VOL (1.2) NMH = VOH − VIH (1.3) Driver Receiver Output Characteristics Input Characteristics VDD Logic High Output Range Logic High V OH Input Range NMH VDD stands for the voltage on Forbidden VIH the drain of a metal-oxide- Zone VIL semiconductor transistor, used VOL NML Logic Low to build most modern chips. Logic Low Input Range The power supply voltage is Output Range also sometimes called VCC , GND standing for the voltage on the Figure 1.23 Logic levels and noise margins collector of a bipolar junction transistor used to build chips in an older technology. Example 1.18 CALCULATING NOISE MARGINS Ground is sometimes called VSS because it is the voltage on Consider the inverter circuit of Figure 1.24. VO1 is the output voltage of inverter I1, the source of a metal-oxide- and VI2 is the input voltage of inverter I2. Both inverters have the following charac- semiconductor transistor. teristics: VDD = 5 V, VIL = 1.35 V, VIH = 3.15 V, VOL = 0.33 V, and VOH = 3.84 V. See Section 1.7 for more What are the inverter low and high noise margins? Can the circuit tolerate 1 V of information on transistors. noise between VO1 and VI2? 24 CHAPTER ONE From Zero to One Noise Figure 1.24 Inverter circuit V O1 VI2 I1 I2 Solution: The inverter noise margins are: NML = VIL − VOL = (1.35 V − 0.33 V) = 1.02 V, NMH = VOH − VIH = (3.84 V − 3.15 V) = 0.69 V. The circuit can tolerate 1 V of noise when the output is LOW (NML = 1.02 V) but not when the output is HIGH (NMH = 0.69 V). For example, suppose the driver, I1, outputs its worst- case HIGH value, VO1 = VOH = 3.84 V. If noise causes the voltage to droop by 1 V before reaching the input of the receiver, VI2 = (3.84 V − 1 V) = 2.84 V. This is less than the acceptable input HIGH value, VIH = 3.15 V, so the receiver may not sense a proper HIGH input. DC indicates behavior when 1. 6. 4 DC Transfer Characteristics an input voltage is held To understand the limits of the digital abstraction, we must delve into the constant or changes slowly analog behavior of a gate. The DC transfer characteristics of a gate enough for the rest of the describe the output voltage as a function of the input voltage when the system to keep up. The term’s input is changed slowly enough that the output can keep up. They are historical root comes from direct current, a method of called transfer characteristics because they describe the relationship transmitting power across a between input and output voltages. line with a constant voltage. An ideal inverter would have an abrupt switching threshold at VDD/2, as In contrast, the transient shown in Figure 1.25(a). For V(A) < VDD/2, V(Y) = VDD. For V(A) > VDD/2, response of a circuit is the V(Y) = 0. In such a case, VIH = VIL = VDD/2. VOH = VDD and VOL = 0. behavior when an input A real inverter changes more gradually between the extremes, as voltage changes rapidly. shown in Figure 1.25(b). When the input voltage V(A) is 0, the output Section 2.9 explores transient voltage V(Y) = VDD. When V(A) = VDD, V(Y) = 0. However, the transi- response further. tion between these endpoints is smooth and may not be centered at exactly VDD/2. This raises the question of how to define the logic levels. A reasonable place to choose the logic levels is where the slope of the transfer characteristic dV(Y) / dV(A) is −1. These two points are called the unity gain points. Choosing logic levels at the unity gain points usually max- imizes the noise margins. If VIL were reduced, VOH would only increase by a small amount. But if VIL were increased, VOH would drop precipitously. 1. 6. 5 The Static Discipline To avoid inputs falling into the forbidden zone, digital logic gates are designed to conform to the static discipline. The static discipline requires that, given logically valid inputs, every circuit element will produce logi- cally valid outputs. By conforming to the static discipline, digital designers sacrifice the freedom of using arbitrary analog circuit elements in return for the simpli- city and robustness of digital circuits. They raise the level of abstraction  1.6 Beneath the Digital Abstraction 25 V(Y) V(Y) A Y Unity Gain Points VOH VDD VDD Slope = –1 VOH VOL VOL 0 V(A) V(A) 0 VDD/ 2 VDD VIL VIH VDD VIL, VIH (a) (b) Figure 1.25 DC transfer characteristics and logic levels from analog to digital, increasing design productivity by hiding needless detail. The choice of VDD and logic levels is arbitrary, but all gates that com- municate must have compatible logic levels. Therefore, gates are grouped into logic families such that all gates in a logic family obey the static dis- cipline when used with other gates in the family. Logic gates in the same logic family snap together like Legos in that they use consistent power supply voltages and logic levels. Four major logic families that predominated from the 1970’s through the 1990’s are Transistor-Transistor Logic (TTL), Complementary Metal- Oxide-Semiconductor Logic (CMOS, pronounced sea-moss), Low Vol- tage TTL Logic (LVTTL), and Low Voltage CMOS Logic (LVCMOS). Their logic levels are compared in Table 1.4. Since then, logic families have balkanized with a proliferation of even lower power supply voltages. Appendix A.6 revisits popular logic families in more detail. Table 1.4 Logic levels of 5 V and 3.3 V logic families Logic Family VDD VIL VIH VOL VOH TTL 5 (4.75−5.25) 0.8 2.0 0.4 2.4 CMOS 5 (4.5−6) 1.35 3.15 0.33 3.84 LVTTL 3.3 (3−3.6) 0.8 2.0 0.4 2.4 LVCMOS 3.3 (3−3.6) 0.9 1.8 0.36 2.7 26 CHAPTER ONE From Zero to One Table 1.5 Compatibility of logic families Receiver TTL CMOS LVTTL LVCMOS a Driver TTL OK NO: VOH < VIH MAYBE MAYBEa CMOS OK OK MAYBEa MAYBEa LVTTL OK NO: VOH < VIH OK OK LVCMOS OK NO: VOH < VIH OK OK a As long as a 5 V HIGH level does not damage the receiver input. Example 1.19 LOGIC FAMILY COMPATIBILITY Which of the logic families in Table 1.4 can communicate with each other reliably? Solution: Table 1.5 lists which logic families have compatible logic levels. Note that a 5 V logic family such as TTL or CMOS may produce an output voltage as HIGH as 5 V. If this 5 V signal drives the input of a 3.3 V logic family such as LVTTL or LVCMOS, it can damage the receiver, unless the receiver is specially designed to be “5-volt compatible.” 1.7 CMOS TRANSISTORS* This section and other sections marked with a * are optional and are not necessary to understand the main flow of the book. Robert Noyce, 1927–1990. Born Babbage’s Analytical Engine was built from gears, and early electrical in Burlington, Iowa. Received computers used relays or vacuum tubes. Modern computers use transis- a B. A. in physics from tors because they are cheap, small, and reliable. Transistors are electri- Grinnell College and a Ph.D. cally controlled switches that turn ON or OFF when a voltage or in physics from MIT. current is applied to a control terminal. The two main types of transistors Nicknamed “Mayor of Silicon are bipolar junction transistors and metal-oxide-semiconductor field effect Valley” for his profound influence on the industry. transistors (MOSFETs or MOS transistors, pronounced “moss-fets” or Cofounded Fairchild “M-O-S”, respectively). Semiconductor in 1957 and In 1958, Jack Kilby at Texas Instruments built the first integrated cir- Intel in 1968. Coinvented the cuit containing two transistors. In 1959, Robert Noyce at Fairchild Semi- integrated circuit. Many conductor patented a method of interconnecting multiple transistors on a engineers from his teams went single silicon chip. At the time, transistors cost about $10 each. on to found other seminal Thanks to more than four decades of unprecedented manufacturing semiconductor companies advances, engineers can now pack roughly three billion MOSFETs onto a (photograph © 2006, Intel 1 cm2 chip of silicon, and these transistors cost less than 1 microcent apiece. Corporation. Reproduced by The capacity and cost continue to improve by an order of magnitude every 8 permission). years or so. MOSFETs are now the building blocks of almost all digital  1.7 CMOS Transistors 27 systems. In this section, we will peer beneath the digital abstraction to see how logic gates are built from MOSFETs. 1. 7. 1 Semiconductors MOS transistors are built from silicon, the predominant atom in rock and sand. Silicon (Si) is a group IV atom, so it has four electrons in its valence shell and forms bonds with four adjacent atoms, resulting in a crystalline lattice. Figure 1.26(a) shows the lattice in two dimensions for ease of drawing, but remember that the lattice actually forms a cubic crystal. In the figure, a line represents a covalent bond. By itself, silicon is a poor conductor because all the electrons are tied up in covalent bonds. How- ever, it becomes a better conductor when small amounts of impurities, called dopant atoms, are carefully added. If a group V dopant such as arsenic (As) is added, the dopant atoms have an extra electron that is not involved in the bonds. The electron can easily move about the lattice, leaving an ionized dopant atom (As+) behind, as shown in Figure 1.26(b). The electron carries a negative charge, so we call arsenic an n-type dopant. On the other hand, if a group III dopant such as boron (B) is added, the dopant atoms are missing an electron, as shown in Figure 1.26(c). This missing electron is called a hole. An electron from a neighboring silicon atom may move over to fill the missing bond, forming an ionized dopant atom (B−) and leaving a hole at the neighboring silicon atom. In a similar fashion, the hole can migrate around the lattice. The hole is a lack of nega- tive charge, so it acts like a positively charged particle. Hence, we call boron a p-type dopant. Because the conductivity of silicon changes over many orders of magnitude depending on the concentration of dopants, sili- con is called a semiconductor. 1. 7. 2 Diodes The junction between p-type and n-type silicon is called a diode. The p-type region is called the anode and the n-type region is called the cath- ode, as illustrated in Figure 1.27. When the voltage on the anode rises above the voltage on the cathode, the diode is forward biased, and current Free electron Free hole Si Si Si Si Si Si Si Si Si - + + - Figure 1.26 Silicon lattice and Si Si Si Si As Si Si B Si dopant atoms Si Si Si Si Si Si Si Si Si (a) (b) (c) 28 CHAPTER ONE From Zero to One flows through the diode from the anode to the cathode. But when the p-type n-type anode voltage is lower than the voltage on the cathode, the diode is anode cathode reverse biased, and no current flows. The diode symbol intuitively shows that current only flows in one direction. Figure 1.27 The p-n junction diode structure and symbol 1. 7. 3 Capacitors A capacitor consists of two conductors separated by an insulator. When a voltage V is applied to one of the conductors, the conductor accumulates C electric charge Q and the other conductor accumulates the opposite charge −Q. The capacitance C of the capacitor is the ratio of charge to Figure 1.28 Capacitor symbol voltage: C = Q/V. The capacitance is proportional to the size of the con- ductors and inversely proportional to the distance between them. The symbol for a capacitor is shown in Figure 1.28. Capacitance is important because charging or discharging a conduc- tor takes time and energy. More capacitance means that a circuit will be slower and require more energy to operate. Speed and energy will be dis- cussed throughout this book. 1. 7. 4 nMOS and pMOS Transistors A MOSFET is a sandwich of several layers of conducting and insulating Technicians in an Intel clean materials. MOSFETs are built on thin flat wafers of silicon of about 15 to room wear Gore-Tex bunny 30 cm in diameter. The manufacturing process begins with a bare wafer. suits to prevent particulates The process involves a sequence of steps in which dopants are implanted into from their hair, skin, and the silicon, thin films of silicon dioxide and silicon are grown, and metal is clothing from contaminating deposited. Between each step, the wafer is patterned so that the materials the microscopic transistors on silicon wafers (photograph appear only where they are desired. Because transistors are a fraction of a © 2006, Intel Corporation. micron1 in length and the entire wafer is processed at once, it is inexpensive Reproduced by permission). to manufacture billions of transistors at a time. Once processing is complete, the wafer is cut into rectangles called chips or dice that contain thousands, millions, or even billions of transistors. The chip is tested, then placed in a plastic or ceramic package with metal pins to connect it to a circuit board. The MOSFET sandwich consists of a conducting layer called the gate on top of an insulating layer of silicon dioxide (SiO2) on top of the silicon wafer, called the substrate. Historically, the gate was constructed from A 40-pin dual-inline package metal, hence the name metal-oxide-semiconductor. Modern manufactur- (DIP) contains a small chip ing processes use polycrystalline silicon for the gate because it does not (scarcely visible) in the center melt during subsequent high-temperature processing steps. Silicon dioxide that is connected to 40 metal is better known as glass and is often simply called oxide in the semicon- pins, 20 on a side, by gold ductor industry. The metal-oxide-semiconductor sandwich forms a capa- wires thinner than a strand of citor, in which a thin layer of insulating oxide called a dielectric separates hair (photograph by Kevin the metal and semiconductor plates. Mapp. © 2006 Harvey Mudd College). 1 1 μm = 1 micron = 10–6 m.  1.7 CMOS Transistors 29 source gate drain source gate drain The source and drain terminals Polysilicon are physically symmetric. SiO2 However, we say that charge flows from the source to the drain. In an nMOS transistor, n n p p the charge is carried by electrons, which flow from p n substrate substrate negative voltage to positive voltage. In a pMOS transistor, gate gate the charge is carried by holes, source drain source drain which flow from positive voltage to negative voltage. If we draw schematics with the (a) nMOS (b) pMOS most positive voltage at the top Figure 1.29 nMOS and pMOS transistors and the most negative at the bottom, the source of (negative) charges in an nMOS There are two flavors of MOSFETs: nMOS and pMOS (pronounced transistor is the bottom “n-moss” and “p-moss”). Figure 1.29 shows cross-sections of each type, terminal and the source of made by sawing through a wafer and looking at it from the side. The (positive) charges in a pMOS n-type transistors, called nMOS, have regions of n-type dopants adjacent transistor is the top terminal. to the gate called the source and the drain and are built on a p-type semi- conductor substrate. The pMOS transistors are just the opposite, consist- ing of p-type source and drain regions in an n-type substrate. A MOSFET behaves as a voltage-controlled switch in which the gate voltage creates an electric field that turns ON or OFF a connection between the source and drain. The term field effect transistor comes from this principle of operation. Let us start by exploring the operation of an nMOS transistor. The substrate of an nMOS transistor is normally tied to GND, the low- est voltage in the system. First, consider the situation when the gate is also at 0 V, as shown in Figure 1.30(a). The diodes between the source or drain and the substrate are reverse biased because the source or drain voltage is nonnegative. Hence, there is no path for current to flow between the source and drain, so the transistor is OFF. Now, consider when the gate is raised to VDD, as shown in Figure 1.30(b). When a positive voltage is applied to the top plate of a capacitor, it establishes an electric field that attracts posi- tive charge on the top plate and negative charge to the bottom plate. If the voltage is sufficiently large, so much negative charge is attracted to the underside of the gate that the region inverts from p-type to effectively A technician holds a 12-inch wafer containing hundreds become n-type. This inverted region is called the channel. Now the transis- of microprocessor chips tor has a continuous path from the n-type source through the n-type chan- (photograph © 2006, Intel nel to the n-type drain, so electrons can flow from source to drain. The Corporation. Reproduced by transistor is ON. The gate voltage required to turn on a transistor is called permission). the threshold voltage,Vt , and is typically 0.3 to 0.7 V. 30 CHAPTER ONE From Zero to One source drain source gate drain gate