0:04

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.

Â