Optional: Building a processor from scratch In this assignment we are going build a computer processor from the ground up, starting with transistors, and ending with a small but powerful processor. The purpose of this assignment is to make you more familiar with the notion of logical circuits and the boolean functions which they implement. It also illustrates the principle of modularity. Starting with very simple transistor-level circuits, we will work our way up to a complete processor. At each level of the processor design, we will use the circuits that we have designed at the lower levels as black boxes, ignoring their implementation details. To aid in the clarity of your solution as well as the clarity of your thinking, you should design your circuits modularly. Once you have shown how to build a piece of circuitry (such as an adder) it is never again necessary to draw the details of its implementation: simply use an appropriately labelled box to represent it. Similarly, you may wish to bundle parallel bunches of wires together into a single appropriately labelled “n-bit wide” wire. With these techniques, you should be able to describe very complicated circuits with very simple and elegant circuit diagrams. Note: This is an optional assignment. It was designed to help you understand the internal nature of a computer – an important task for engineers and computer scientists alike. Nothing but NAND The basic building block of our computer will be a two-input NAND gate. The truth table for a two-input NAND gate is shown below. The output z is 1 if and only if at least one of the two inputs x and y is 0. (Which is the same as saying that the two outputs are not both 1.) x y 0 0 1 0 1 1 1 0 1 1 1 0 z = x y· As we shall see below, any other gate can be constructed using nothing but NAND gates. Because of this, we say that NAND gates are complete. It is interesting to note that not all gates have this property: for example, AND gates are incomplete—that is, there is no way to construct all the other gates using only AND gates. A NAND gate is drawn schematically as shown below. zxyFor this assignment, the NAND gate is the lowest level you ever need to worry about. However, f or the curious we will include a little information about how gates are actually built from transistors. In particular, we will use Complementary Metal Oxide Semiconductor (CMOS) transistors, one of the several different types available. A NAND gate can be implemented in CMOS using four transistors, as shown below. T he horizontal line at the very top of the figure represents a high voltage value (Vdd), say 5 volts, while the three horizontal lines at the bottom of the figure represent the ground voltage, 0 1volts. The high voltage value represents a binary 1, while the low voltage value represents 0. The inputs x and y are each connected to the gates of two transistors. A transistor is basically a door. Each of the bottom two transistors in this figure is “open” when the voltage on its gate is high, and “closed” when it is low. Each of the top transistors is open when the voltage on its gate is low, and closed when it is high. When either of x or y is 0, the path from the ground to the output z is closed, but at least one path from Vdd to z is open, so z takes on the high voltage. When both x and y are one, there is no path from Vdd to z, but there is a path from the ground to z, so z takes on the low voltage. yxgroundvddzProblem 0 (5 points): Using a NAND gate as your basic building block, show how to construct circuits that perform the following functions: NOT, AND, OR, and XOR. You should not draw any transistors— begin with the NAND gate schematic. You may design the circuits in any order that you want, and once you have designed a circuit, you may use it in the construction of other circuits (using the appropriate schematic). The truth tables for these functions, along with their schematics are shown below. 1. NOT gate x z = x 0 1 0 1 1 zx0 1 0 2. AND gate x y z = x · y 0 0 0 0 1 0 1 0 0 1 1 1 xyz3. OR gate x y z = x + y 0 0 0 0 1 1 1 0 1 1 1 1 xyz24. XOR gate x 0 y 0 z = x ⊕ y 0 0 1 1 1 0 1 1 1 0 xyzBuilding an adder Problem 1 (8 points): Now that you have designed a collection of useful gates, you can use them to construct more sophisticated circuits. Using your collection of gates, draw a circuit that implements 4-bit grade school addition, which should be able to do calculations like 0110 + 0100 = 1010. You do not need to deal with overflow (for example, 0110 + 1100 = 0010 is OK). You should proceed by first constructing a 1-bit adder (that takes as input two bits and outputs a sum bit and a carry bit: e.g., adding 0 and 1 produces sum = 1 and carry = 0, where as 1 and 1 produces sum = 0 and carry = 1). Then, show how to combine 1-bit adders to construct a 4-bit adder. 3Multiplexers and Demultiplexers Two types of circuits will come in very handy as we design our processor: multiplexers and demultiplexers. Intuitively, a multiplexer (mux) takes a binary number n and selects the nth one of its inputs to forward on. A demultiplexer (demux) takes a number n and sends its input out on the nth output line. a0 a1x01x10x00x11ya0 a1y00y01y02y03xFigure 1: At left, a four-way one-bit mux. At right, a four-way one-bit demux. The schematic for a 4-way 1-bit mux is shown in Figure 1 (Left). It has four data inputs, x00, x01, x10, x11, two control inputs a0, a1, and one output, y. The value of y is equal to the input specified by the binary number a0a1, i.e., y = xa0a1 . As an example, if x00 = 1, x01 = 1, x10 = 0, x11 = 1 and a0a1 = 10, then y = x10 = 0. A mux is also called a selector because the control lines select from among the possible inputs. The schematic for a 4-way 1-bit demux is shown in Figure 1 (Right). This circuit has a 1-bit data input x, a 2-bit control input a0, a1, and 4 1-bit outputs, y00, y01, y10, y11. A demux works as follows. The value of x is transferred to the output line specified by a0 and a1, i.e., ya0a1 = x. The value on all of the other outputs is 0. As an example, if x = 1, and a0a1 = 01, then y01 = 1 and y00 = y10 = y11 = 0. As another example, if x = 0, then independent of the …