With Boolean algebra as a basis, now we're going to take a look at how to build digital circuits. This idea was developed by Claude Shannon at MIT in 1937. It was really an amazing connection between the idea of designing circuits in boolean algebra that Shannon wrote actually as a master's thesis, a paper based on his master's thesis. It's been called probably the most important and also the most famous master's thesis of the 20th century. It's a simple idea but it's a profound idea. People were working with developing circuits for computation without the formal basis that Boolean algebra provides and getting into conceptual difficulty on all dimensions of what Shannon's idea was that we can use boolean algebra to systematically analyze and synthesize circuits and that's the way that computers have been built ever since Shannon articulated this idea. So, we're going to just move up from switches up to a second level of abstraction called Logic Gates. And what we're going to do is develop circuits that implement boolean functions. So for example, if we have the Boolean Function NOT sets x prime, that's the truth table we already looked at that. In classic circuit design, say, before the 1970's and 80's and some people still use these kinds of notations. That's what the circuit element would look like. We're not going to use those classic symbols. We're going to use a simpler symbol that reflects what goes on underneath which is actually our circuit. So, most of the time we're going to work directly with circuits that are built according to our simple rules. And it doesn't matter how they're oriented. We can take this thing and turn it vertical any way you look at it, this is a single controlled switch. If x is zero then the output x prime is connected to power it's one. If x is one then the output x prime is blocked from power. It's zero. So, that circuit implements the NOT function and we use the word gate to refer to a circuit that implements elementary Boolean Function. So, that's a simple proof for the two cases for the NOT function. So, here's a two argument function, the NOR function. And we looked at the truth table for that one and that's the classic symbol for that. Again our symbols is going to be much more geometric. It's just the cover over our actual circuit. And if you take a look at that circuit if X and Y are both zero then there's nothing blocking the connection from power at the left to output at the right. So, the value is going to be one but if either X or Y or both are on, then the output is going to be blocked from the power dot, and the result will be zero. That's an implementation of the NOR function. And in similar manners we can do other boolean functions. So, or is X plus Y, that's the classic symbol. And again we're going to use a geometric one where all we do is negate the output of the NOR. So, that's a little proof with circuits that the OR gate that's drawn in the under the cover column computes the OR function. And similarly for AND, we can use De Morgan's laws to note both inputs to a NOR and from De Morgan's laws that gives an implementation of the end function. In this we can do other things with other boolean functions and we're not going to focus that much at this level. Our circuits are going to be based on understanding how the OR function and the AND function in various generalizations are implemented. And we're just going to use those forms directly. We don't want to get too far away from the physical world because we only have a couple of lectures to show you a real circuit and we're going to skip the abstraction where we work with classic symbols like the one shown in our classic symbol column that are connected by wires that then have to be fit into the geometry in some way. Our circuits are always going to directly tied to the geometry and you can imagine these being built from the drawing by laying materials on substrates as long as you believe in the power of dots and you believe in the automatic switches which are just the terminating lines across a line. Then we believe that we have gates and from gates we're going to build quite a bit more. We often do have gates with multiple inputs but those are easy generalizations of these basic things. So, we might have a multi-way or gate that takes a number of inputs and computes the function of ORing them all together, and that value has value zero if and only if they are all zero. Otherwise it's one and in our under the cover representation. You can see that if all of those inputs are zero, then there's nothing blocking the long power DOT and that's going to block the output and make it zero. If any one of them is one, then it'll block the long power dot and then leave the output free to be one. So, there's an example where the result is one and another example where the result is one. If any input is one then the result is going to be one. That's a multi-way OR gate and usually in our circuit the only way it can be zero if they're all zeros. Usually in our circuits we're going to orient those vertically. So, you should be sure to learn to recognize something like that as a multi-way OR gate. We can also have multi-way AND gates and actually we're going to generalize them in very specific and easy way. So, in AND gate is going to be one if all the input values are one or zero otherwise. And that's similar to the OR gate or undercovers representation. The only way that output is one, is if they're all one. If they're all one then they block all the dots from blocking the long one that's connected to the result. If any one of them is zero then it's going to block the connection to the output. And so that implements a multi-way AND gate and more generally if we have some of the inputs go through a NOT gate and others don't, it just implements a different function where the ones that don't go through a NOT gate are knotted in the function. So, this example, this circuit illustrates U prime VWX prime Y prime Z. If you don't have a knot you put a prime. So again there's only one set of inputs that's going to output one and that's the set of inputs that ensures that the power of dot at the left is not blocked from the output at the right. So, the ones that do not go through a NOT gate, the input has to be zero the ones that do go through NOT gate, the input has to be one. In any other set of inputs, something's going to get through and block the connection from the power data left to the output at right and the result will be zero. In this case we have six gates we're going to have two to six different possible functions we can implement in this way, just by including the NOT gates in the import are knot. Actually a NOR gate is generalizing again in the sense that if we don't have any Xs then the only way that thing is one is if they're are all zeros. And if there's any one in the inputs then it's zero. So, we could have called these generalized NOR gates but we're going to just consistently use AND, because we usually think of, if we want to add another variable, we're going to end in another variable where we put an X on it. And those are going to be the basis for many many of our circuits. So, just a quick pop quiz. You want to be able to recognize the functions that these sorts of circuits compute and it's very easy to do so, with just a little bit of practice. So, what Boolean Function do these gates compute and what inputs is the output one? So again, if there is an X then you don't have a knot. If there's not an X then you do have a knot. So, this first one is U, V prime WXY prime Z. And then from that Boolean Function, if it's not negated you put one if it is to get it you put zero and you get the set of inputs for which the output is one. And if you want, you can check that those of the inputs of the ones that do not block the power dot at left from the output at right. So, again just practice this one, it's U prime VWX prime YZ and the set of inputs for which the output is one for that is zero, one, one, zero, zero, one. Here's all the possible generalized AND gates for three inputs, starting with x prime, y, z prime, where the only inputs for which that is one is there all zero. And then It's counting in binary and you can see the counting in binary and the pattern of Xs in the circuits. And the last one is XYZ, which is one if and only if all the inputs are one. So be sure that you get the idea of how to read these gates. If you're not sure, just replay this slide as if it's flashcards, because we're not going to label these gates from now on. We're going to assume that you can see what Boolean function gates like this implement. Now we're ready for a useful combinational circuit, one that's found in every computer. It's called a decoder. So a decoder takes some input lines, which is an address. This example takes three input lines and it has two to the n upwards. The idea is that the input lines are a binary address that specify an output line. In this example, the inputs are one, one, zero, which is binary for six. And what's that doing is specifying that the sixth output is one. And not only that, all the other outputs are zero. So it's a circuit that translates from binary to, interprets the binary encoding of values on wires to activate the particular addressed wire. So how do we implement it? Well, we just take our inputs and we feed them in to all possible two to the n generalized the AND gates with n inputs. And only one of them is going to match the input address. As we just looked, every one of these gates takes the value one for only one set of inputs. And for a decoder, it's the set of inputs that are found in the input lines that specify in binary, the output line to be lit up. And all the other ones are zero. So in the next lecture, we'll see how we use a decoder to select words in our memory by, and it uses the address bits of a toy instruction, we'll see how that works. But it's a very simple circuit, that's based on the generalized AND gates that we just looked at. Here's a similar one that also is found in every computer. It's called a demux or demultiplexer. That's the same way, it's got the AND address inputs. But it also has a data input that's got some value, say x. What the demux does, it also has two to the n outputs and what it does is gives the address output line the value x. It's like a switch where we specify which line we want to get connected to x. It's not actually a electrical connection, it's got the same value. It's like a virtual electrical connection, and all the others are zero. To implement that, we just use the decoder but we add on index to every one of the gates so it's a very similar circuit to decoder and a very simple circuit. And we'll see the use of the demuxes in the next lecture for implementing instructions, where we use the opcode bits of the instruction in the instruction register to feed into a demux, to activate control lines that implement the change of state of machine called for by the instruction. And then we can combine those into a so-called decoder demux and that has pairs of output lines. And it's just taking back the decoder output, so that each pair of output lines, most of them are zero, but the one that's addressed the top line will be one, and the bottom line will have the same value as the data value x. It's just a combination of the decoder in the demux. We use that to control the memory, as you'll see in the next lecture. And these are all quite simple circuits that take inputs and use gates to get the appropriate function performed. But the real power of Shannon's idea, is that we can create a digital circuit that computes any Boolean function. And let's look, for example, at the majority circuit. And all we're going to do is just follow through the proof of the universality of AND or NOT, but in the context of circuits. It's the same way we're going to identify the rows where the function is one and then for each one of those rows, we're going to create a generalized AND gate that correspond to the terms for which, for that set of values is one and otherwise it's zero, and then we just order all the results together, it's same as we did before. But now we make a circuit, where we use a multiway OR gate to order all the results together, vertically oriented multi multiway OR gate. That's a circuit that computes the majority function. So here's an example where x and y are one and z is zero and the only way that this function computes the value one, is if one of those gates matches the input. In this case, it's the third one down, which is one if and only if x and y are one and z is zero. So that one has one as its output and that output blocks the power dot at the top of the OR gate. It means that the power dot at the bottom produces the output one, but it's just computing an OR function. If any one of those gates is one, then the result will be one. In this case, one, one, zero the input, and that's two ones and a zero. So the majority function can compute one. Now, we can use a majority function as a component in our circuits. We'll represent it like this. It's kind of like, think of it as a cover on the circuit, where we have our inputs running through, and our output computes the majority function. And this works for any function here, it's odd parity for example. So, again, just find the rows where the function is one, use a generalized AND gate for each one of those rows. So one, zero, zero is x, y prime, z prime, where there's the generalized AND gate for that. That's going to be one, if and only if x is one, y is zero, z is zero and then the last one is in an AND gate. And then just OR those results together using a multiway OR gate. You can easily see, after looking at these two examples, that you could implement a circuit for any Boolean function at all. Certainly, if you take a test on this material, you'll find yourself doing that for sure. So here's our example where x is one, y is one and z is zero, then that's not a odd number of ones, so none of those gates match the input. So they're all put zero out, so none of them blocked the power dot at the top of OR gate from blocking the power dot at the bottom, so produces the result zero. Again, now having seen that circuit, we can work at a higher level of abstraction, where we can just run our input lines through a blue box that computes the odd parity function. It's really quite a profound ending that you can design a circuit that computes any given Boolean function. We just have basic gates and we use NOT and OR gates to make these generalized AND gates. We have wire and our method is to represent things with Boolean variables, construct truth tables, identify the rows where the function is one, and immediately build the circuit by having a generalized AND for each place where the function is one and then ORing together the results. It's a very profound idea, that we can get a circuit for any Boolean function. If we have more variables, we have bigger generalized gates. If we have more that are one, we have lots more inputs into the OR gate and so forth. But just the concept that any Boolean function that you can specify, you have a circuit for is a very profound idea. Now there might be more efficient ways to do it, and in fact, there's plenty of applications where we do not use this idea because we want to have a more efficient circuit that uses fewer gates or less real estate and we'll talk about that in just a minute. So again, if you take a test on this material, you'll be asked to design a circuit to implement a Boolean function. So for example, what about the XOR function. Again, you just use the same rules, use the truth table. For every entry where the function is one, use a generalized AND gate, in this case, it's x is zero, y is one or x is one, y is zero. And then OR the results together. That's a circuit for XOR, that now we can use at a higher level of abstraction. Someone might ask to design a circuit to implement the function of four variables, where the number of ones is equal to the number zeros or whatever. Any kind of specification of a Boolean function, we can build a circuit to implement it. It's a very powerful idea. So just a summary of where we are so far. We're familiar in software design with the idea of encapsulation and the same thing holds in hardware design. Our implementation is the circuit from wires and switches. We have an API which defines a circuit by its inputs and its outputs and controls that we'll talk about. And what we do is we encapsulate circuits the same way that we do in software. We build bigger circuits out of small ones just working with the definition of what the circuit is supposed to do. And so far, we've built a bunch of different circuits that actually we'll find useful in putting together to to build the arithmetic unit and CPU of our computer. The idea of encapsulation or building layers of abstraction is essential in this process.
