Nand2Tetris Unit 1 Boolean Logic

So today we're starting our journey of actually building a computer. You've probably all heard that computers internally only have 0s and 1s. And the reason that they only have 0s and 1s is because that's what they can get away with. It's simplest to have only two possible values that you need to maintain. And that's going to be enough as we will see today. We're starting with actual, the completely theoretical logical kind of analysis of how to deal with 0s and 1s. And later in this later in unit three we'll actually talk about how these abstract 0 and 1 signals directly are implemented as chips inside a computer. So let's talk about the abstract 0 and 1. On and off, true or false, not, no and yes, 0 and 1. In general, we can use all these names to refer to each one of two different physical values. That are maintained somewhere in the system. We will use 0 and 1 for the rest of this the rest of this unit, but that's completely general. So what can we do with kind with, if we only have 0s and 1s? Well, we can do some kind of basic operations on them. For example, the AND operation takes two 0 1 signals, and returns 1 only if both of them were 1. So if you have 0 and 1, the result is 0, but if you have 1 and 1, the result is 1. We can actually see all of the different possibilities for combining two values of 0s and 1s into the result, which is the end of them, in a little table that is called the Truth Table. Because it actually gives all the different possibilities of the inputs, of x and of y, and for each one of these possibilities, it lists what is the output, what is x and y. So AND is a one of the possible operations. Here's another very popular one, OR. It returns 1 if any one of the two inputs is true. Is one. Or even if both of them are one. The only time to return to 0 is if both x and y are 0. And here's a third interesting operation. This one is a unary operation. It only takes a single input. Bit as input, x, and returns the opposite of it. So returns for, if the input is 0 the output is 1. If the input is 1 the output is 0. So these are possible, very simple operations and Boolean numbers. Sort of like addition and multiplication, and maybe other kind of operations, or operations on integers or on real numbers. These are operations on Boolean numbers. Once we have operations, we can start combining them, just like we combine arithmetic operations in arithmetic formulas. So for example, let us try to evaluate what would be the expression of NOT 0 OR 1 AND 1? Notice that we have parenthesis to gi, to give us the priority here. So the way we value it is very simple. We know how to evaluate 1 AND 1, which is 1. So the whole thing simplifies to NOT 0 AND 1 OR 1. We know how to evaluate 0 OR 1. That's going to be 1 because it's an OR operation so that's equal to NOT 1. And now we know how to evaluate NOT 1, that's simply 0. All very simple and we can do that. Now once we know how to evaluate a Boolean expression over values, over 0, 1 values, then we can actually get general expressions, general functions that takes indeterminates, XYZ as inputs, and for each value of XYZ, produce an output. So for example, I can define a function, a function of three inputs, XY and Z. That basically turns x AND y OR NOT x AND z and look in the parenthesis to see the priority that I was thinking about. Of course I could use, I could define any other function by any other Boolean formula and that would give me a function. If we want to know what kind of function is that, well we can actually list all the possible values of x, y and z. And for each one of them, try to write down what is the value of the function? The really nice thing about Boolean values is the fact there are only a finite number of possible inputs and we can actually list each one of them. This is completely different from functions that you've learned in third grade. Where you have function from integer through integer, then there are infinitely many integers. So you can never write down the function in a complete specification of all the possible values. But here, we can actually write down all the possible values that x, that the triplet x,y,z can have. We can have x 0, y 0 and z 0 that corresponds to the first row in the table and so on. Until the last row of the table that corresponds to all three of them being 1. Now for each one of these rows, we can just evaluate the function. What is the function f of x, y, z defined by the previous formula for these values? For example let's look at the second row. In the second row we have x equals 0, y equals 0, z equals 1 and we can just plug in the numbers 0, 0 1 into the formula. Every time we have an x we put a 0 there. Every time we have a y we put a 0 there. Every time we have a z we put a 1 there. And now we just get formula with constants in it and we can evaluate it just like we did in the previous slide. And we can figure out that is 1, that the second row should get a value of 1. We can do this similarly for each one of the possible rows and we get a, we can completely fill the table. And now notice that this table of values completely gives you the same information as the previous expression did. It completely specifies the functions, the Boolean function that we just had. The first day, the first way we described the function was as a formula. The second way we describe the function was as a Truth Table. These are two completely identical, def, def, eh, definitions. Ways to describe the same Boolean function. So now, eh, once we know we can describe Boolean functions using formulas and we are thinking we have general Boolean expressions, we can actually try to find what are a bunch of Boolean identities that always give us equality. For example, we can always see that x AND y, whatever the values of x and y is, is exactly equal to y AND x. This is called the Commutative Law. We have the same similar phenomena for x OR y equals y OR x. So these are like commutative laws that hold for this Boolean algebra, in this, in this Boolean algebra. There are a bunch of other kind of identities. For example, the use, the use, the well-known Associative Law. If you have x AND y AND z, it's the same thing if you first do x AND y, or whether you first do y AND z. Similar thing happens for all. Another well-known law, well-known law is the Distributive Law. If you have x AND y OR z, that turns out to be exactly equal, equal to x AND y, all that, OR x and z. Now as opposed to the usual arithmetic, where we only have the Distributive Law of multiplication over addition, here we have both of the Distributive Law of multi, AND over OR and the dual law of Distributive Law of OR over AND. The same trick works if you want to do x OR y AND z. That x OR y AND x OR z. [COUGH] Now there are also laws called De Morgan laws, that govern how NOTs work. How they interrelate with AND and OR. These are called loo, laws are called De Morgan laws, and they say the following into, interesting thing. If you take x AND y and do a NOT on all of that, that's equivalent to first doing NOT of x and ORing that to NOT of y. And we have the dual one that if you have NOT of x OR y, that's exactly equal to NOT of x AND NOT of y. Now all these laws can be easily proved, if you wish. Not if you wish. Really proved by simply listing all the possibilities in a Truth Table. And verifying that they get the same Truth Table for the left-hand side and the right-hand side. Now there are a bunch of other laws and we can use them to actually do manipulations and Boolean algebra. So for example, once we have a formula. For example the formula that you see here. NOT of, NOT x, AND NOT x OR y. For example, it could be any other formula. We can now start applying some of these identities to change its form to simplify it or to just bring it into a different format. So for example the first thing we can do here is look at the second part of last sub expression, the NOT x OR y. We can use De Morgan Law here and basically convert it to NOT x AND NOT y. Now if you look what we have here, we can use Associative Law. Because we have NOT x AND NOT x AND NOT y we can change the order of doing the AND. And we get another expression which is identical using the Associative Law. At this point we have something really interesting at the beginning. We have NOT x AN NOT x. That can be just simplified to NOT x. Why is that? Because we can know, we can actually see, also that's another identity that we didn't explicitly list. But it's easy to verify in the same way that, if you take any value, w. In our case, w is NOT x. And do w AND w, that's completely equivalent to w. Now this is called the Idempotence Law and we can thus simplify the previous expression by simply removing one of these w's, one of these NOT x's. Now we are ready to use De Morgan Law again, and now we got into NOT NOT x OR NOT NOT y. Now again, here's another law that we didn't list explicitly, but you obviously all know, that NOT NOT x is always equal to x. So using Double Negation Law, we can simplify that to x OR y. So that just gives you some kind of a demonstration that you can basically, just manipulate Boolean expressions, sort of like you manipulate arithmetic expressions in elementary school. There's another way to get the same conclusion, the same equivalence, without actually going through these algebraic manipulations, simply by actually looking at the Truth Table. We take the expression, we build the Truth Table for it. And we've already seen how to take an expression and find its Truth Table. And then we get the Truth Table that you see on the board. Now, once you have this Truth Table, you can say I know this Truth Table. This is exactly the Truth Table of the OR function. And then that immediately proves that the expression on the top is completely equivalent to x OR y as we've derived using an algebraic methods previously. Now of course it's not completely eh, you won't always be so lucky to do some kind of big Truth Table and recognize what it is and immediately see a better and nicer and simpler expression give, that gives you the same table. Eh, sometimes you will have to algebraic manipulations, but on the other hand it's not always true that algebraic manipulations are easy to do in the sense of finding a very simple expression. So, but in general, in principle, you can use both of these methods to actually simplify Boolean expressions or find alternative forms that give you the same Boolean expressions. So we've just finished our first unit describing how to man, how to eh, manipulate logical values. Notice that we are still keeping our abstract point of view of just logical values and not thinking about any physical realization that we will have inside our computer. In the third unit, we'll actually switch our point of view and start talking about the same kind of phenomena but from the point of view of real chips and real gates that we have inside a computer. But before we get to that, in the next unit, we'll keep maintaining [COUGH] our theoretical point of view and start talking about the following problem. How can we construct a function from basic operations? How does that, this is exactly the kind of thing we will need to do when constructing hardware. We know what it wants to do, but we'll have to actually construct it from Boolean operations. And we'll try to see how that is done, first from a theoretical point of view, in the next unit.

So, in the last unit we talked about what are Boolean functions, Boolean values, Boolean algebra, Boolean formulas. What we want to do now is actually talk about how we can construct Boolean functions from more primitive operations. So, we already saw two ways to represent the Boolean function, a Boolean expression, and a truth table. We also know how, already know how to go from the expression to the truth table. You take the expression, evaluate it for each possible, possible value of the input bits, and then you get the, and then you can fill the truth table. What we want to do now is exactly the opposite. You start with a description of a function, let's say given as a truth table, and our challenge is to come up with a formula that computes the same boolean function. Why do we need to do that? Well, that's exactly what we have to do when we come to design a computer. We know what we want to do, we know what we want a certain unit to do, but then we actually have to actually compose it from primitive gates, from primitive operations. So let's see how we can do it. So again, we continue with our abstract treatment. We're trying to see what is a basic logical way we can actually construct such a Boolean function from primitive operations. Later, once we actually talk about practically constructing them, we will be more practical oriented. We'll go step-by-step and so on. At this point, we just want to make sure, what are the principles? So let us start with a specification of a Boolean function given as a truth table. How can we construct it? Well, here's what I'm going to describe to you as a standard way of what's called constructing a disjunctive normal form formula for it, and it goes like this. We actually go row by row in the truth table. We focus only on the rows that have a value of 1. For example, the first row here has a value of 1. Now, what we can do is, we write an expression that basically gets a value of 1 only at this row. For example, so, in particular, since here in this row, the values of x, y, and z are 0, 0, and 0, if we look at the expression not x and not y and not z, that is going to be a Boolean function, the green Boolean function, that only gets a value 1 on this row. So now we have one Boolean function. We do the same thing, we construct another Boolean function, another clause for each row that has the value of 1. So for example, there's another second row with a value of 1. This time, in here, this row, y equals to 1 while x and z equal to 0. So the clause we write here is not x and y and not z. Again, this is something that completely gets a value of 1 only on this row and gets a value of 0 everywhere else. We do that for every possible row that has a value of 1, Now the purple row. Now we have a bunch of different functions that each one of them gets a value of 1 only in its row and gets a value of 0 in all other rows. But we desire a single function, a single expression, that gets exactly the value 1 exactly on all of these rows and 0 on the other rows. How do we do that? Well, that's very simple. We just or them together. And now we get a single expression, a single Boolean function that gets value 1 exactly on the rows for which we built clauses for, and gets 0 everywhere else. And now we've basically constructed our function as a Boolean expression only using ands, nots, and ors. Now, of course, once we have this expression, we can start manipulating it in varied ways. This is one way to write the function as an expression, but if you actually look at it, you can see that we can start changing, start changing its format. For example, if you look at the first two clauses, you can see that one of them is not x and not y and not z, while the other is not x and y and not z. Notice that the, what we have both possibilities for y and exactly the same fixed value for x. So instead of these two, two clauses, we can combine them into one clause which does not ask about y, and only asks about not x and not z. So we get an equivalent expression that's slightly shorter. There are more manipulations that we can do. Let's not go into them, but we can actually write the same expression in many different ways. Some of them will be shorter than others, some, some of them might be, might be more efficient in terms of when we actually go implement them in a computer. But the point is, logically, they're all completely equivalent. Now, you might wonder, how do you actually find the shortest or most efficient formula that's equivalent to the one we've just derived? Well, that's not an easy problem in general. It's not easy for humans, nor is there any algorithm that can do that efficiently. In fact, this is an NP-hard problem to actually find the shortest expression that's equivalent to a given one, or even to verify if the expression that you're given is just a constant 0 or 1. What's more interesting, what I really want to focus at this point, is that we've really prove the really remarkable mathematical theorem that any Boolean function, it doesn't really matter on how many variables and what the boolean function is, can be represented in an expression using only the operations AND, OR, and NOT. Now, to notice how remarkable that is, just think about, just think about functions on integers. Integer functions that you've learned in elementary school. Not every element, not every function and integer numbers can be represented using let's say, addition or multiplication. In fact, most functions cannot be represented just by arithmetic operations. Yet, because of the finite world that we're living in, the Boolean algebra, ever Boolean function can just be represented with ANDs, ORs, and NOTs. And that is what exactly gives us the basic power to actually construct computers only with these possible gates, only with these possible operations, AND, OR, NOT. But do we really need all of them? Well, here's a better theorem, if you wish. We don't really need OR gates. Just with ANDs and NOTs, we can construct any Boolean function. How can we prove that? Well, we already know that if we have ORs, we can do everything. We've just seen that. And now the only thing that we need to show is that we can actually compute an OR with AND and NOT gates. But we know how to do that already, we remember, we recall De Morgan formula that exactly give us a formula for OR that only uses NOT and AND gates. So now we have a really more remarkable theorem, that we only need these two basic operations to actually compute every, every Boolean function. Can we go even less? Can we give up, let's say, the AND gate? Well, that doesn't make sense, because not only it takes one value to one value, it doesn't even allow us to combine anything. Can we give up the NOT gate? Well, not really, because ANDs has this property that if you only feed it zeroes it will always have zero as output. And there are Boolean functions that when you feed 0 give you 1 as output, so AND by itself wouldn't suffice. But it turns out that there is yet another operation that by itself does suffice to actually compute everything, so let me introduce the NAND function. So the NAND function, here is a truth table. It gives 0 only if both of its inputs are 1. And every other possibility it gives 1. Logically, x NAND y is defined to be the negation of x and y. So what's so remarkable about this Boolean function? Well, the nice thing is that we can prove the following theorem, that if you only have NAND gates, you can already compute every Boolean function, you can already represent every Boolean function as an expression using just these NAND gates. How do we prove that? Well, we know that if you can do NOT and if you can do AND, you can do everything. So we just have to show how to do NOT with NAND gates and how to do AND with NAND gates. So here's how you do NOT. If you just look what happened when you feed x to both inputs of the NAND gate, you plug it into the truth table in the previous slide and you can see that NOT x is really represented by x NAND x. That's part one. The second part we need to show, how do we do AND. Well, x AND y turns out to be NOT of x NAND y. But how do we have NOT, well, we've just seen that you can do NOT with NAND itself. So now we've basically reduced the fact instead of using NOTs and ANDs, we're just using NAND gates. And we got an amazing theorem that just if you have a NAND gate, you can compute every, everything. And this is exactly what is going to be our approach when we actually go to build a computer. We will give you a basic, a primitive NAND gate operation, and you will basically build the whole computer, all the complicated logic that we'll actually ask you to build, using just from these basic NAND operations. So at this point, we've just finished our abstract point of view about Boolean logic. And now we're doing a really interesting shift of perspective from the abstract logical operations to the actual gates and, the actual gates from which we build computers. This switch really has no, there's no actual difference between the two, two different things in terms of the kind of thing that we do. But it's just in the way that we're thinking about them. Until now, we ask you to think about everything as abstract Boolean logic. From now, we're going to start asking you to think about everything as actual little pieces in a computer that compute the functionality that we want.

In the previous two units in this week, we talked about Boolean functions, and most of this discussion has been theoretical. Starting with this unit we are going to talk about how we actually implement these Boolean functions using hardware. In particular, we're going to talk about a general technique called Gate Logic, which, you know, loosely speaking, it's a technique for implementing Boolean functions using logic gates. Now, what is a logic gate? Well, a logic gate is a stand alone chip or a, you know a very simple chip or an elementary chip which is designed to deliver a well-defined functionality. You know, something like NaN functionality, and functionality or, and so on. What is a composite logic gate? A composite logic gate is one which is made up from elementary logic gate and other composite logic gates. Or simply, it's, it's a more complex gate than the elementary ones. And in this course, we'll develop things like multiplexes and adders. And, obviously, most of you don't what the, what these terms mean. Don't worry about it. You will get acquainted with them and actually build them in the next few weeks of the course. All right, so let us begin with the most fundamental logic gate that we use in the course called, Nand. Here is the definition of a Nand. You know, this is actually the standard diagram that we use to describe a Nand gate. It has two inputs and a single output. Everything here is binary so a, b and out are either 0 and or 1. Here is the functional description of this of this gate. If both inputs are 1, we output 0. Under any other circumstance we output 1. And here is also a truth table description of the same functional specification. Any one of these descriptions is fine. Taken together, what we have here is an obstruction of the Nand gate. We didn't say a word about how this thing is actually working. We just describe what kind of functionality we can expect it to deliver. Okay, moving forward, here are, three classical gates that, pop up in every, digital design, project. We have an And gate which outputs 1, when both its inputs are 1 and 0 elsewhere. We, we have an Or gate which outputs 1 when either one of its inputs are 1 and 0 elsewhere. And we have a, a Not gate that operates as a converter. And we can put these gates together to create more complex functionality as we'll illustrate later on. In particular, we can use these gates to composite composite ones. So for example, here's a three-way And, which is an extension, if you will, of the of the simple two-way And. And one way to build it is to use this trick here. We can take the output of one And and feed it into one of the inputs of another And gate. And if we wire everything correctly this gate is supposed to deliver the required functionality. What we see in the dashed line rectangle around the implementation is a documentation of the interface of this chip. So the user lives outside the dashed rectangle. So, and, and so the user sees only the three inputs and the output, as you see in the left-hand side of of the gate description. If you want to go in, or to sort of open up the black box you have to see what is documented and done inside the dashed rectangle. So with that, I would like to say a few words about the notion of interface and implementation. The gate interface is the gate obstruction. You know, this is how the user thinks about what the gate is supposed to do. Interface answers the question, what. At the same time, if you want to understand how the chip is doing, what it's doing, you have to, go deeper and go int, well I'm not sure that deeper is the right word. But you have to go to another level of detail in which you actually, the black box opens up and you see how the chip is actually constructed. Or you do it yourself, you know, if, if your job is to be the person who, who is actually realizing this, obstruction. Now, the interface of the gate is unique. There's only one way to describe the gate's, functionality. Otherwise, you know, if there's more than one way, either you're not describing it well or you're confusing the user because, you know, there should be only one unique way to describe what the gate is supposed to do. At the same time, there may be several different implementations that realize the same obstruction. And some implementations may be, you know, more elegant, they may use less energy, they maybe less or more expensive, and so on. So one obstruction, many different implementations. This is very typical in in computer science, whenever you build a large system, you have this this duality. All right. Now moving along, so we talked about the gate interface and the gate implementation. Let's talk about something known as circuit implementations. If I want, I can realize these gates using hardwired circuits like, like this one. And there's a certain sort of graphical language here that describes what's going on. When we want to represent the fact that the gate outputs 1, we assume that a light bulb will be turned on. And when the gate delivers output 0, the light bulb will be off. So if we look at this implementation of an And circuit, we see that because of the architecture of this circuit the light bulb will will be on only if the two relays, both relays are latched. Under any other circumstance the light bulb will go off. And, that's, that's exactly what I want to do when I represent the And logic. What about Or logic? Well, once again, if I'm, if I have to build circuit, circuit implementation of Or, I can realize it using this particular architecture. In here it takes only one latch to close the circuit and turn on the light bulb. And once again, this is consistent with the desired obstruction of an Or circuit. Moving along, here is a circuit implement, implementation of a three-way And. And you can easily, I think, convince yourself that it will deliver the the required functionality. And yet I want to remind you that earlier in this unit we also presented this implementation of, of an And gate if you recall. So I'd like to say a few words about these two, different, approaches to, designing hardware. And, I want to start by saying that, in this particular course, we don't deal with physical implementations. And therefore, this whole discussion of circuits, transistors, relays, and so on, you know, all this stuff, and what you see in the top left corner of the screen here, this is electrical engineering. It's not computer science. And the people who build these gates using circuits and, and similar technologies, some of them are far more advanced and sophisticated. Well, these people are called electrical engineers, God bless their souls. You know, we have problems in computer science to worry about. So we are not going to worry at all about physical implementations, and all the designs that we are going to use in our course are going to be similar to what we did here at the bottom right of the screen. We are going to take existing logic gates beginning with Nand, and, and beginning with Nand only, and we're going to piece them together in some clever ways in order to generate and, and produce the required functionality. So this has been a unit in which we we gave you a first brief introduction of logic gates. And in the next unit we are going to introduce to you a language some sort of a programming language called HDL or Hardware Description Language, with which you can actually build logic gates like the ones you saw in this unit, and the far more complex logic gates and chips down the road.

In previous units, we talked about how Boolean functions can be realized using logic gates. And in this unit, we are going to talk about how we can actually build and implement the logic gates using a formalism called Hardware Description Language or HDL. Once you build a logic gate in HDL, you can actually simulate it, test it. And finally, build it in hardware as we now turn to describe. All right. So let's begin this journey from obstruction to implementation. The first thing that you have to do as a gate architect is demand a full and complete description of the desired gate's behavior. And in this case, what we need is some sort of a truth table. In the case of Xor, it's a very simple truth table. And the truth table along with a gate diagram, gives you everything that you need in order to understand what this chip is supposed to do. And what we see here is also sometimes called the chip's interface. And indeed, using this information, you can start writing an HDL file that will look something like this example here. So we start the HDL program or the HDL file with some documentation, free-form, you know, you can write whatever you want there, which describes what the gate is supposed to do. And then we specify the name of the chip. The names of the inputs of the chips and the names of chip's output. And all this information, by the way, the name of the chip and the names of its inputs and outputs is typically given to you. You know, it's not something that you decide. It's something which is part of the chip's contract, if you will. So you simply write it up using this syntax and then you write the magic word parts, which describes that here begins the segment of your program in which you're going to describe how this chip is actually designed. Now when you use such a chip, such Xor chip, what we've seen so far is called a gate interface. And notice that this is everything that I need in order to use Xor gate. However, if I have to build this gate, well, that's a different story. Now, I have to open up the black box and actually design it. So when we use chips, we always wear two different hats. There's the hat of the programmer who uses the chip, the chip part and for this, all we need to know is the chip interface. And there is the other hat of the chips builder, which is what we're going to do now. So moving alone, let's discuss how we actually build this chip from scratch. All right. So, actually we are not going to build it from scratch, we can if we, if we need if we need to we can build it from a NAND gates only. However, let us assume that we, we've already built an and gate an or gate and, and not gate. Well, if we built these gates or if someone gave us these gates that we can freely use. Here's what we can do. We can inspect the truth table and figure out from the truth table that the Xor functionality can be described as follows. I mean, look at Xor, look at the truth table. The gate outputs one in two cases only. If if a and not b or if b and not a. That is if a is true and b is false or if b is true and and a is false. This sort of comes out, jumps out from the truth table. You can either see it on your own or as Noam described in one of the previous units, you can synthesize this this insight or this, Boolean function from the table itself. So, once you come up with this insight, the next thing that you do is you think about it for a little while and you come up with a gate logic diagram that describes how we can build this Boolean function using basic logic gates that we already have to our disposal. Now developing such diagrams is a matter of experience and the only way to, to gain this expertise is to see many, many examples like, like this one. So let's take this example and and explain it in in detail. So the first thing that we can do is draw the boundary of the chip diagram or the or the gate diagram. So we use this dash to outline for this purpose and what remains outside the boundary is the user's view of this gate. In other word, the, the gate interface. All the users knows is that he or she has a gate that has two inputs, a and b, an output called out and altogether. They somehow, this chip as if by magic, delivers Xor functionality. So we draw this diagram and and this interface and now we can delve more into the into the inner architecture. So notice how the a signal is being copied and sent simultaneously into two different destinations. One of them is the and gate and the other one is and not gate. This is perfectly okay in chip diagram. And we see that the b signal undergoes the same the same treatment. And in general, when you write HDL code, you are allowed to take any signal. And distribute as many copies as you want of this signal into as many destinations as you want. This this wiring or these dispatching is done simultaneously. So to use formal language HDL has unlimited thin out. You can, you can thin out any given signal to as many destinations as you want. And we do it we always do it when we write HDL code. All right. Moving along, notice that we're using some off the shelf gates and not and or. Now whenever you use an off, off the shelf gate, you are bound to use the names of the gate's input and output as advertised, so to speak. In other words, when you take the gate, gate off the shelf, the gate comes along with what can be called the gate's signature or the gate's API. So we have no degrees of freedom here. We have to use the official names of the the inputs and outputs of, of every one of our chip parts. Now the next thing that we do is let's focus on the red connections that we see here. These are the connections that we draw in order to connect the different chip parts together. Now the rule is that every one of these connections has to be named and it's our responsibility to come up with sensible names, so that's what we do. We can call this particular connection not a, which is a sensible name, I think a self-descriptive name. We'll do the same thing with the not b. We call this one a and not b. We can call this one not b not a and b and, and that's it. We, we, we have named all the internal connections in our architecture. And we can actually now move on to describe this diagram in HDL. So now we can actually move on and implement this diagram using HDL. So we return to the HDL stub file that we had before. And I use the term stub file to describe a partial HDL implementation, so to speak that actually describes only the chip's interface. And typically, it comes with the statement implementation missing or put your code here and so on and so forth. So this is the contract that we actually have to implement. And now, indeed, we are going to focus on the implementation section of this file. And basically, what we do is we begin to describe the gate diagram one chip part at a time. And for each one of the chip parts that we have, we write a single HDL statement that describes the chip along with all its connections. So we have two we happen to have two not chip parts. So we describe them. The first not has n equals a. This is the input. You know, the, the n input of the chip receives the a signal. And the out, output of of the chip goes into not a. We do similar with the, with the other not chip. Then we described the two and chips. And finally, we described the other or chip. Notice by the way that they use the words gate and chip interchangeably and that's perfectly okay. A gate for me is simply a simple chip. All right. So this HDL diagram is nothing more than a textural description of the gate diagram. Did I say, HDL diagram, I, I meant the HDL file is a textural description of, of the gate diagram that we see at the top of the slide. Now, I'd like to to notice that once again, we have interface, we have implementation. And also note that the interface of the chip is unique, you know? There's only one way to describe this chip and this is typically given to us by whoever, you know, commissioned us to implement this chip. At the same time, the implementation is not unique and the same interface can be implemented in typically in many, many different ways. For example, in the case of Xor, we can implement the Xor chip using three logic gates only. So and it doesn't really matter how exactly we do it. We can, you can think about it on your own if you want. But in general, there may be different implementations and some of them will be less expensive. They will contain less chip box, less connections. Consume less energy and so on and so forth. So the interface is unique and implementation varies. Now, I'd like to use this opportunity to make some general observations about, about HDL. And for ease of reference I have placed in front of you what we saw earlier in this unit. The the gate diagram on the right-hand, hand side and its HDL description on the left. So what, what can we say about, about HDL? First of all, we see that there are certain issues in HDL, which are very similar to what we normally do in other programming languages. We have to worry about good documentation of our HDL program, just like we do when we write the program in Java or Python. We have to come up with good descriptive names. Both to the chips that we use and to the connections that we that we create within the architecture. So readability is terribly important. You know, we have to make sure that our HDL code is self-descriptive and readable. And in order to do it, we also use indentation. You know and and make the code look real nice. So, all of these things are expected from you when you write your own HDL programs. In addition, there are certain things which are really unique to HDL. First of all, HDL is a functional or declarative language. There is no procedure going on. There's no program execution going on. It is nothing more than a static description of the gate diagram. At the same time, you know, we assume that at some point this descriptive code will go into some interpreter. You know, it will go into, in our case into harder simulator that, that can actually take this description and start to sort of pipe values from the bottom all the way to the end. So we assume there is some agent that will turn this implementation into something that, that is actually working. But this procedural part is not part of the HDL code, you know, it's external to the HDL code. So because HDL is a functional language, we can actually write those HDL statements in any order that we wish. You know, it doesn't matter if you begin to describe the not gate or the or gate, it's completely up to you. But it is typically it's customary to begin to describe your diagram from left to right and this also makes the code more readable. Also, note that each time we use an off the shelf gate, we commit ourself to using the gate interface, that is the names of the input and outputs that come along with the gate documentation. Now, in the HEC computer that we're going to build in this course. We decided as a matter of convention to almost always use the letters and b for a two input chip and out for a single output chip. And therefore, we are going to have many chip connections that look like a equals a and out equals out. Now, at the beginning, you know, this formalism these conventions will look a little bit strange. You know, what does it mean, a equals a, out equals out? If you think about it a little bit and if you go back to consult these diagrams, you will see that these connections make a lot of sense. And actually, they are very convenient from a programming perspective. You will realize that once you get your hands dirty and write some HDL code of your own. So, I'd like to end with some some comments about hardware description languages in general. There are many of them out there and yet, the two most popular HDLs that at least I know of are VHDL are Veri, Verilog. These are the languages which are used, I think in 90% of hardware design projects. But there are many other HDLs that are out there that can be used, as well. Our own HDL is very similar in its spirit to the industrial strength HDLs that I mentioned earlier, VHDL and Verilog. And yet, it is a very minimal and simple version of these HDLs. And for this reason, you can master it in something like one hour of reading a tutorial and and beginning to write some HDL code of of your own. And most importantly, our HDL along with our hardware simulator gives you everything that you need in order to build the computer described in this course. And actually, any other computer that you may want to build using the knowledge that you will gain in the Nand2Tetris course. So if you want read more about HDL and, and you should,. Take a look at a Appendix A in the textbook and also read the HDL Survival Guide in our Nand2Tetris website. Both are, are actually available in, in the website. And you may want to also take the hardware simulator tutorial and, and learn how to actually read HDL descriptions and, and execute the underlying logic of these HDL using simulation. So this has been the unit in which we gave you a primer of HDL. And in the next unit, we'll describe, once again, how you can take your HDL designs and bring them to life within the context of the hardware simulator.

In the previous unit, we learned how to implement the gate logic using HDL. However, nothing in what we did guarantees that the HDL code that we wrote is actually correct. We have no idea if this architecture that we put together delivers the intended results of the chip that we seek to design. So in this unit, we will close this gap and we will learn how we can take an HDL program and verify to the best of our ability that the program or the HDL file delivers the intended functionality of the underlying chip. Now here is the big picture of what we're going to do. Given that we have a particular HDL file and we want to test it, we can load it into a special program called hardware simulator. We have written such program and made it available to you, in our website. This program happens to to to be written in, in Java. And this program is designed to simulate and test HDL files. So we load it into this program. We interactively test all sorts of operations in this chip and we call this mode of testing interactive simulation. Alternatively we can write another file and using a special language that we designed, which we call the testing language, something that you can learn in a few minutes. We can put together a set of replicable tests that are predetermined. So we don't have to do things interactively. We can think ahead of how we can systematically test the underlying chip. We write in what is called a test script and then we load into the simulator two separate files. We load the HDL code. We load the test script and then we send the simulator to work. The simulator goes through every step in the test script and subjects the HDL code to the to the specified tests in this supplied script. We call this mode of operation script-based simulation. And finally, if we want, we can record the output of the simulation on something called an output file. And we can even compare the results of the simulation to a desired output, which is stored in, in yet another file called compare file. So as you see, there are many new concepts and techniques involved in this practice of hardware simulation. And the purpose of this unit is to make, you know, all this new information concrete by walking you through a step-by-step process of testing a working example that will accompany us throughout this unit. Now, throughout this unit, we are going to present several software tools. Actually only one software tool, the hardware simulator, and you are more than welcome to stop the video. Invoke this hardware simulator on your own computer and make sure that what we do can be done also on your machine. You can do all of this if you have downloaded the software suite at the beginning of the course and if so, the hardware simulator should be available on your computer. And everything that we do in the lecture can be done by by you as well. So we encourage you to kick tires as much as you please. So let's go on and and start with the with some concrete examples. So here's the example that I'm going to use throughout this unit. It's an HDL file describing the score chip that we talked about in the previous unit so the code itself should be familiar to you even though it's not terribly important for understanding this particular unit. All right. So once again the fact that we wrote this very nice piece of code does not imply in any way that the code is actually correct. In fact most likely it contains some errors, either syntax errors or logical errors or, or whatnot. So how do we test it? Well, here's what we can do. We can invoke the hardware simulator. Program starts running. We can load the HDL file into this simulator and we can then enter zeroes and ones into the a and b inputs and observe what is going on inside the chip. Now, how do we observe what is going on? Well, we have to tell the simulator to evaluate the chip's logic. The simulator will not do anything until we, we tell it to actually consider the new inputs that we entered and evaluate the chip's logic. And if we do this, the simulator will take these values, these zeroes and ones, or whatever we entered, and will kind of pipe them through the architecture. And at some point, something will come out from the from the output pin of the chip, so at that point, we can inspect what actually materialized. So we can observe the outputs of the chip and in this particular case, the value of the out pin and if we want, we can also inspect the values of the internal pins. Pins like not b, not a and so on, and the simulator gives us all these all these nice capabilities. In particular, here's an example or screenshot of the hardware simulator in action and the simulator contains features, several different panes. So, let's talk about each one of these panes in isolation. First of all, at the bottom-left of the screen, we see the HDL code that we have loaded into the simulator. This is a static view. We cannot manipulate or edit this code. If we want to edit anything, we have to use an external text editor, change the HDL code and reload it. So this pane you know, gives us an idea of what is it, what is it exactly that we loaded into the simulator. Here we can actually interact with the input panes of the simulator. We can click them and change the values. We have four different possibilities of zeroes and ones in, in this particular example. Now this is very simple chip. And once we do this, we can click this icon. Which looks like a calculator, and once we click it, we basically tell the simulator to evaluate the chip's logic on the supplied inputs. At this point the simulator will spin its wheels. It will take a fraction of a second and something will come out. We can then evaluate the output of the chip. In this particular case we have only one output called out. And once again if we want we can also inspect the the current values of the internal pins. So altogether this GUI gives us everything that we need. In order to carry out sort of hands on interactive simulation of of exalt chip or any other chip for this matter. All right, moving along I would like now to give you actually a hands on example of of the hardware simulator in action. So let's do that and then go back to the to the lecture. This is the hardware simulator. And, in order to use it, we have to first of all, load an HDL program into the simulator. And, we do it by clicking this icon here. So, let us do it. And, we see that we are in the nand2tetris folder, so within this folder, we're going to select Projects. And within Projects, we'll select Project 0. And we see that we have a single HDL file here, so let us select it. This is Xor file that we discussed before. And we loaded the chip into the simulator. [COUGH] Now the pane at the bottom left, right here gives me a display of the file that I just loaded. I can scroll back and forth. It's not separate, it's not terribly useful but this pane is actually just a read only display. There's no way to actually change the code when you are inside the simulator. If you want to change the code, you have to do it using an external text editor and then you have to reload, of course, the file that you changed and saved elsewhere. So, let us assume that we are happy with this file and I want to actually simulate the chip logic. Well I do this by first of all looking at the current input values and we see that the default values of the a and b inputs of Xor chip happen to be 0. So if I want, I can go ahead and change one of them, or both of them to some other values. So let us change A to 1 and let us change and let us also change b to one. And I noticed that nothing yet happened in order to, to see how the chip responds to these changes. I have to reevaluate the chip logic and I do it by. By clicking this icon here, the calculator icon. So let us do it and we see that once we click this icon, the output becomes 0. And [COUGH] indeed Xor of 1 and one is 1. If you want to see some other possibilities, we can once again manipulate one of the input panes. Click the calculator, and we see that Xor now emits, 1 instead of 0. Another thing that we can do is, inspect the values of the internal pins which gives us yet another level of scrutiny in particular when we, when we try to debug the chip and understand why it is misbehaving for some reason. So this has been a very brief description of the first thing that we do when you use a simulator, you load the chip, you play with the input panes, you inspect the outputs and the internal pins, and and this is the ABC of of chip debugging and testing. I wish to remind you in closing that if you want to change the chip logic,. You have to edit the HDL file using some external text editor. Save the new file, reload it into the simulator and rerun the tests in order to test the new chip design. Now, interactive simulation is, is very nice indeed, but at some point it can become rather tedious, especially if you have you know, lots of bugs in your design and and each time you have to, you know, go through the same set of tests and so on and so forth. So, with that in mind. We are fortunate that we also have the notion of a test script available to us. So here once again is the tested chip. And by the way, I allow myself to use the words chip and gate interchangeably for me, a gate is simply a, a simple chip. So this is the tested chip. And here is an example of a test script designed to test a Xor gate. Now let us go through the test script kind of line by line. The first command in the test script instruct the simulator to load the Xor.hdl file into the program. So even this step is, is taken care of. We don't have to do it ourselves. The test script will, will load the program for us. By the way, this is terribly important if you do repetitive debugging, because how do you debug a gate? You use an external text editor you know, to change the gate, and then you, you click Save, and you go back to the simulator. So, it's important to remember to reload the new version of the edited chips. So, that's why we added this command that to, to the test script. Now, once the test once the hdl is loaded into the simulator, the test grid begins a process of subjecting the chip to to four different tests. The semicolon represents you know, the ending of of one particular test if you will. And so, we set the input values of the chip to 0 and 0. We evaluate the chip logic and observe the results and then we go through the next test and and so on and so forth until we complete all the possible all, all the input possibilities for this particular chip. So this is how we carry out script ba, script-based testing. And it has many benefits. And far and foremost is the fact that we don't have to do anything laboriously, you know, using our own sort of intuition. Because everything is pre-determined. We have a set of rep, replicable tests and we just. Use the same tests over and over whenever we we debug the chip which can be you know, two weeks or two months from now. So it's good to know that you can always repeat the same set of tests. So, altogether, we will try to always use a test script. And the good news is that you don't really have to worry about how to write test scripts because we are going to supply to you all the test scripts that you need in order to test the the chips that, that you are going to design in hdl. So you worry about the hdl and we are going to worry about the the testing of of your work. Another thing that we can do is keep track of the outputs of the simulation. So in particular we can augment our basic test scripts with something like the following commands. We can at the beginning of the of the test when we initialize things, we can. Instruct the simulator to create an output file, which in this example, we happen to call Xor.out. And as we go through the through the testing. At the end of each test, we tell the simulator to output to the output file a set of values, which is determined in the preamble of the script. So, as you see the third line with script says, the output placed is a, b, and out. And so whenever the simulator would see the directive output, it will write to the output file, the current values of a, b and out. And at the end of the simulation, we can simply inspect the result of the output file and convince our self that the chip has actually behaved according to expectations. In fact, in this particular example, if you will inspect the output file that emerged from the simulation, you will notice that it is completely identical to the truth table of Xor gate. So it looks like the gate is well behaving. So here's a snapshot of the hardware simulation in action using a test script. And once again, we have the HDL code as, as we did before at the bottom left of, of the screen. But we, but we now have something new. We have a test script, which can be seen on the right pane. Which is some sort of a multipurpose GUI area, which we use for for different purposes. And after we load the script, we can instruct the simulator to actually execute the script. We do it by clicking this control and the simulator the simulator goes to work. And at the end, if we want, we can inspect the resulting output file. And here is also a demo of of the same thing with, with an actual how do simulations session. We will now show how to use the how to simulator in order to test an HDL program using a test script. So the first thing that we can do is load the HDL program into the simulator. So let us choose the same Xor.hdl chip that we used before and then instead of playing with the input pins interactively. We can use this icon here to open a test script and we see that in the project zero folder, we have one test script called Xor.tst. So let us load it into the simulator environment. Once we do it this pane in the interface shows us the contents of the currently loaded test script and we see that it begins with a few comments. And then following that, we see the actual testing commands. And the first command or the next command to be executed, is highlighted by a yellow bar, we can call it the cursor of the of the test script. Now we see that each command ends either with a comma or a semicolon and when we click the play icon, the simulator is going to execute all the testing commands until the next semicolon is encountered. Now the first four commands in this test strip set up the simulation so to speak. And so let us, let us execute them. So I click this icon here. And we see that the cursor moved to the next batch of commands. And this batch says, set a to 0, set b to 0. These are the input pins of this particular chip. And then evaluate the chip logic and output the result into the output file. So let us execute this batch of commands and we see that indeed, the a and b inputs are now 0 and the out of the chip happens to be 0, which seems to be right. Because as we know, Xor of and zero and zero should be zero. So let us execute the next batch of test script commands. This batch sets a to 0 and b to 1, evaluates the shapes and outputs the result and indeed, we see that Xor of 0 and 0 ended up being 1, which seems to be correct. So executing the next batch of commands sets a to 0, I'm sorry. Sets a to 1 and b to 0 giving the result 1, which also seems to be correct. And then moving along, we execute the next and final batch of commands, which set both a and b to one. And we see that the Xor response by emitting the value zero, which once again seems to be correct. Now the test script for Xor gate is relatively simple, because basically, it simply executes every possible input combination as stated by the chip truth table. In more complex shapes such an exhaustive testing is is less feasible. And therefore, the test, testing scripts will likely be more complex. Now, as we tested this script the script has also written the results of every test script batch into the output file. You know, this is the the result of saying output in, in the I'm sorry. This is the result of, of the output command. Now, if we want to inspect the output file, we can do so by going to this control here and selecting Output. So let's do that. And once we do it, we see that the output file, indeed looks exactly, like the truth table of Xor and this gives us yet another indication that the chip has operated to a specification. Before we go on with this step by step working example, I would like to stop for a minute or two and say some general things about the general concept of hardware simulators. So first of all, there are many of them. Some of them are free and open source. Others are proprietary and very sophisticated and very expensive. And in this course, we use a simple hardware simulator, which at the same time, gives you everything that you need in order to build the head computer and any other computer that you want to build using the techniques described in the course. So the supplied hardware simulator, which you have on your computer now is a, is a tool that once again, gives you everything you need. And if you want to learn how to use it, there are several places to consult with available documentation. If you go to the nand2tetris .org website you can find a full chapter, I think it's appendix a and appen, actually appendix and appendix b. In our book describe how to use the hardware simulator and these, these chapters are also available freely on the website and another thing that you should do is go for the hardware simulator tutorial, which is a stack of interacting slides that that explain how to use the simulator as well as all of the examples that you saw in this particular lecture. So that's the end of of the commercial break about hardware simulators and we return to our ongoing example. So let us revisit what we have done so far. We looked at a particular HDL file, which records the logic of Xor. We have supplied the simulator with a test script designed to test this particular code. And we also looked at the resulting output file and convinced ourself that the HDL file is actually correct. Now this privilege of looking at an output file and saying, yeah, it works is something which is rarely available in real life testing. Why? Because the chips that we normally build are far more complex than Xor gate. And there is no way to look at an output file of let's say an ALU or, or a CPU chip or something like that. And, and say, yeah, it works correctly. You know, it's we, we have to do it in, in a far more systematic and planned way. So is there a way to do it? Well, you bet. And that's, that's what we're going to do next. In particular, we can carry out the simulation with yet another tool which is called a compare file. So here's an example of a compare file. It looks exactly like an output file. And in fact, in its previous incarnation, the compare file was a, a, an output file of a well-behaving Xor chips. So someone, and we'll talk about this someone momentarily, someone has written an Xor chip correctly. Ran it thru the simulator, generated an output file. Renamed it compare file and gave it us. And said, now you go and build your chip and, and compare it to what I did. So basically, we can take the compare file and load it into the simulator and then start to do the simulator as the simulation as we did before. And now, in each step of the simulation, whenever we output a set of selected pin values, the simulator will compare the output set of values to the respective line in the compare file. And if the two lines will not agree with each other. The simulator will not throw a comparison error. So this gives us that ability to not only record the outputs of the chip, but also compare them to desired results. So you probably asked yourself once again, how do we generate these compare files to begin with? Right? Well, we, we could have left it as as a mystery, but there is no need to to leave anything unexplained. So here's how we do it. We do it using something called behavioral simulation. In particular, consider this Xor gate that we saw before. And let us assume, once again that this implementation is correct and we put it into the simulator along with the script. We run it, we generate results and then we simply rename it to be Xor.cmp and it becomes the official compare file of this shape. So what is special about this slide, didn't, didn't you say, everything that we said here before. Well, we did, but there's one detail which is, which is remarkably interesting in this in this notion of behavioral simulation. And, and the thing which is interesting is that the chip logic can be implemented in any way that the designer wishes. So we can write this chip logic in Java or some other high-level language. We can run the program. We can generate an output file and then once again, supply it as, as a compare file. So this technique of writing gate logic using or implementing gate logic using high-level language, gives you the ability to plan and test your hardware before you even write a single line of HDL code, which is, you know quite sophisticated way to do things. So we, you know, we can do everything in a high-level and only once the overall design of our machine works properly, we can begin to implement each chip at the time in in HDL. All right. So this has been the notion of behavioral simulation and I want to go on and talk about how we actually carry out hardware construction projects. So the cast of characters in any hardware construction project consists of several players of which, I would like talk about two. First, we have the system architect. Now the system architect is, is the person who is told, you know, go build a chip that supports a certain function of a digit, digital camera or something like that or go build a chip that monitors a certain medical device. So the architect has the exact sort of user-level specifications of the chip and and the other member in the team is a developer or, you know, more than one developer or more than one architects and together, they have to design this chip. So how do they do it? Well, the system architect looks at the overall desired operation of of the chip. And then he or she makes some decisions about how to break this overall behavior into a set of smaller chips if you will or sort of lower-level chips. And then for each one of these chips, the architect, the architect creates a chip API, which consists of the name of the chip, the names of its input and output pins. A test script and a compare file. Now, all these things are prepared by the system architect who, you know, may, may or may not have some people to help him or her in his work. And finally, given these resources, the developers can actually go out and build the chip. So the architecture can do behavioral simulation or they can do whatever they want in order to test that everything fits together nicely. And at some point, the developers actually build this thing using HDL. So, once again, that's, that's an example of well planned modular design and gives another example of divide and conquer. You know, taking something very complicated and breaking into something more, you know, a set of more manageable modules. Each of which can be created and tested in isolation. So for example, the HEC computer I could've told you something like go build yourself a computer and actually that's what we do in this course. But we split this job into the construction of something like 30, you know 30 different shapes that together comprise the HEC chip set. So we, Norm and I, the course instructors, we play the role of the system architects and you guys are playing the roles of the actual hardware developers. All right. So the developer's view, your view of a particular chip. You know, when we tell you to build a chip, here's what you get. You're going to get a stub file that contains the documentation of the chip that you have to build, along with its interface. You're also going to get a test script that we have written for you. You're going to get a compare file and then, you know, taken together, what you've basically got is everything that you need in order to number one, understand the interface. Understand what the chip is supposed to do, the compare file and we'll also tell you how we are going to test it. All right. So what do you do with all these resources? Well what you have to do is write the missing implementation. The missing implementation is the HDL code that should actually drive this entire show. So that's exactly what we're going to do in unit 1.7. But before we go onto this unit, we also have to say a few things about Multi-Bit Buses, which is a gap that we still have to close in in the general description of HDL programming.

In this unit, we'll deal with a question, how to deal with a bunch of bits together. Really this shouldn't really be a whole unit, because it's almost trivial. But still, because there is a little bit of technical details attached to it, it's probably worthwhile to spend five or six, six minutes on this thing in a short unit. So the basic thing we want to point out is the following thing. When we design hardware, a lot of times we need to manipulate a bunch of bits together. First of all, it's going to be convenient, conceptually convenient to think about the bunch of bits that are manipulated together as one entity. And allow ourselves to think about it in a slightly higher abstraction level, not of the single bits but of a bunch of bits together is one entity. The second thing is, that of course sense we are going to describe our chips, our hardware in, in hardware description language, of course we will need some kind of support for that, in the hardware description language. So a bunch of bits together that are manipulated together and have one meaning are sometimes called busses. From, come, coming from some Latin word meaning many or multiple, something like that. So here is an example of how we can, of how we can think about that. So when we want to add two numbers, and we will build in the next, week, we will build some kind of chip that adds two binary numbers. Each one of these binary numbers will have a bunch of bits. Actually, 16 bits in our implementation. But we want to, to think about them as numbers. So our our chip that adds two numbers will be described as having two inputs. An a input, which is 16 bits. And the B input, which is 16 bits, and one output, which is out, which also has 16 bits. So in reality, our chip has 32 wires feeding into it, and 16 wires going out of it, but still it's convenient to think about it as two numbers feeding in and one number feeding out. In this way we can actually also think about these kind of numbers when we want to use them. So this is how the same chip will be described in HDL. I'm only giving the interface here, the API, and omitting all the internal structure, which is exactly what you'll learn next week. So we have simply eh, defined eh, our inputs as a and b. And we have in square brackets the number 16 which means that each one of these is 16 bits. Very much like the syntax for arrays in programming languages. Now once we have this kind of notation, we can think about these numbers and entities and manipulate them in higher level chips. So suppose we need to ba, to build chips that now add three numbers. Each one of them 16 bits. Logically, we of course know how we can do that. We can just add two of them and then add the third one to the sum. So how do we do that? So we get them into, we get in our interface, three inputs, first, second, and third, each one of them 16 bits. And, we have it to, n, need to have an output which is fo, just out of those 16 bits. And we want to manipulate it to this level of av, of abstraction. Not looking at all the separate bits themselves. This is how we do that in HDL. We have two inert internal chips. One of them adds two 16 bits. Juh, Add16 chips that we've just seen. And we add the first and the second inputs and plugs the result into a temporary variable called temp, which is also 16 bits. And then we take this temporary variable and add it to the temporary wire if you wish, or temporary bus 16 wires and add it to the third, getting our final output. And this is why how we can just manipulate inside HDL eh, the busses as entities. Now of course we should also be able to actually eh, manipulate and get access to separate bits in a bus because at the end of the day a bus is just a bunch of bits together. So here's an example of suppose we want to have a chip that gets us an input. A bus of 4 bits in this case. And outputs a single bit which is the AND of all the bits in the bus. How do we do that? To do that we will need to access bit after bit. And then simply add them one after another. And this is how we do that. And notice the syntax. That's an important thing, the syntax here. And when we put an index inside the name of a pin of a bus, we just mean the specific bit that we're talking about. We're using the convention in our HDL that is common to most programming languages nowadays, that a 4-bit bus has bits number 1, 0, 1, 2, and 3. So the indices go from 0 to the bus width minus 1. And this is how we do that. You're going to, in the next project, in this project, you're going to have a bunch of chips that actually, that's what they do. They take a bunch of bits in the bus and just converge them and, and just mash them together into a single value. And we call this multi-way chips. So this, we call this kind of chip here, And4Way. Takes four bits and adds them together. Here's another example showing how we can manipulate bits inside buses. And in the context of another thing we'll do commonly in this, in this week's project, basically taking a bunch of operations and doing them in parallel to each one of the, the bits in a bunch of buses. So, in this example, we have two input buses, and we simply want to do a bitwise AND of them. Take the first bit of a and b, AND it together, and that should produce the first bit of out. Similarly, doing the same for the second bit, and so on. So here's how we do that. We simply have, we need to have four AND gates. Each one of that AND gates performs operation on one of the corresponding pairs of bits. And we access the bits one after another simply listing the 0s bit, first bit, second bit, and putting the AND gate on these inputs and producing the correct output. Immediately notice that the four bits of the out that we just produced, go out as, as a single bus because that's how it was defined in the API. So there are a bunch of technical [COUGH] bunch of technical conveniences sometimes that you want to use when dealing with buses. For example, you may sometimes want to break a bus into sub-buses. So the first example here shows, what happens if we want to compose a bus, a 16-bit bus. From two eight bit buses. So we, so this example shows that we have in our input two 8-bi, bus, two 8-bit buses called lsb, least significant byte, and msb, most significant byte. And if we want to plug them together into an AND 16 gate, we can just take the first 8 bits of the bus and plug the lsb into it. And the second 8-bit bits and plug the msb into it. And notice the co, the, notice the syntax for doing that. If we specify a sub-range intise, inside the square brackets, in exactly this format, with the dot dot notation, then we just get the bus being plugged into the correct sub-bus that we want to do it. We can do that on the input and we can do that on the output. And we can break them in different ways. Now different hardware description languages deal with all these issues and have different syntactic conventions. And of course for our, our hardware description language which you, which you will need to work with in the project. You can find the exact specification on the website. I would like to say just a one, a few words about some peculiarities if you wish on our HDL that you may find convenient to use. First of all, we do allow, [COUGH] we do allow overlaps of sub buses, so you can take say bit 0 to 5. And out them, output them as one bus of 6 bits. And then again take bits, let's say, 3 to 7 and output them with another bus. So simply outputting the same bus in multiple ways that may be overlapping sub-buses. We allow that. Another convention that we have is internal buses. Are just their widths is completely deduced by what you plugged into them. So you don't need to specify the width of an internal, bu, internal pin. It's just if it was connected to a bus, it just gets a correct width that it was connected to. And the third syntactic convention that I would like to mention is the fact that if you want to plug lots of zeroes or lots of ones into a bus, you can do it and together in one command by using true or false as constants, and in all or both of these cases, you get, are multiplied. So if you plug true into some bus, each one of the bits gets a value 1. And similarly for false, where each one of the bits gets zero. So now we've finished this very simple, [COUGH] this very simple unit about handling lots of bits together, and now we're ready to actually completely specify the project of this week.

So now that you are familiar with HDL and hardware simulation, we are ready to get our hands dirty and actually go and develop some chips. So in this unit we're going to give you all the information that you need in order to design the chips that we have to build in Project 1. Before we go on, let us remind ourself, what is the general spirit of this course? Well, the story that we're telling you is that God told us, here's a logic gate, Nand, now go and build a computer. And when we asked how can we possibly do that, God said one step at a time. And in particular, the hack computer that we are going to build in this course consists of something like 30 different chips. And we are going to build them one step at a time. And in the first project we start with Nand, which is God given, or given by us, or you can think about it as some sort of an axiom that you can assume. And using Nand, we want you to build the following gates. Not, And, Or, Xar, and so on and so forth. So that's what you have to do for Project 1. And why these particular 15 gates? That's a good thing to ask, and the answer is two fold. First of all, every one of these gates is widely used in almost any construction of a digital device or some version of these gates. And the second answer, which is more practical, is that these gates comprise all the elementary logic gates which are needed in order to build our computer. So Project 1 lays out the foundation that we are going to use in subsequent projects, because in other projects, we're going to use these chips, in order to build more complex and more interesting functionality. So, once again, here are the chips that we have to build, and I have separated them into three categories, just that we can discuss it in a more organized fashion. So we have some elementary logic gates, widely familiar: Not, And, Or, and so on. We have 16-bit variants of some of the logic gates. And we have some multi-way, and also multi-way 16-bit variants of the previous gates. And in order to make all these new concepts more familiar, I will focus on some gates in every one of these categories and say few words about them. And this, once again, will give you everything that you need In order to build any one of the gates in Project 1. So without further ado, let's start to talk about multiplexors and demultiplexors. So what is a multiplexor? A multiplexor is a gate that operates as follows. There are two inputs coming in, and we know them a and b. And there's a sel input coming in, so-called, from the bottom. Of course in reality there's no bottom and left, but I'm talking about this gate diagram here. So three inputs come in, a, b, and sel. What does the multiplexor do? Well, if sel = 0, the multiplexor outputs a. If sel = 1 the multiplexor outputs b. That's it, that's the desired behavior of a multiplexor. And here is the truth table of the mulitplexor. We have three inputs, so we have eight different possibilities. And you can convince yourself that the truth table is consistent with what we described before. We can also provide an abbreviated truth table of the multiplexor operation, and once again if sel is 0, the multiplexor outputs a, otherwise it outputs b. So a 2-way multiplexor enables us to select and output one out of two incoming inputs. And this is a fundamental operation that is being used over and over again, both in digital design projects as well as in communications networks. So here's an example of how Mux logic comes to play in the context of building what is sometimes called a programmable gate. Now what is a programmable gate? It's a gate that can behave in one of several different ways according to our will. So here's a simple programmable gate that can act either as an And gate or as an Or gate. If the select bit is zero, the gate acts as And. If the select gate is one, the gate acts as Or. And here is the truth table of the gate, and you can convince yourself that it's consistent with what I said earlier. And here is how I can actually build it. I can use two gates, an And and an Or, provided of course that I have developed them previously. And I can feed the a and b inputs simultaneously to both And and Or. And we called this, before, fanning out. So the a input is fanned out into both And and Or, and the same treatment is done with the b signal. And then I use a single multiplexor to decide if I want to output the result of the And or the result of the Or. So the user of this gate that sees only the interface of the gate, gets exactly what he or she wanted, a programmable gate. Here is the HDL code that implements this particular architecture, and if you want, you can stop the video and inspect this code, and make sure that it's consistent with the gate diagram. So here's an example of a Mux in the context of a digital design application. How do we build a multiplexor? Well we get all this information from the system architect and we also get a stub file, and what we have to do, of course, is to write the HDL code. And it turns out that we can build a multiplexor using three gates, And, Or and Not, which we wire in a certain clever way, and the result is the desired Mux logic. So it's up to you to figure out how to do the wiring and actually implement the desired multiplexor. All right, moving along, let us talk about demultiplexor. A demultiplexor looks like the inverse of a multiplexor. It receives a single input, and based on the selection bit, it either channels the input to an a output, or to a b output. Okay, so it's kind of a distributor of a value into one of several possible channels. In this example we have, it's a two way multiplexor, so it's a relatively simple example. All the other channels get 0. Okay, and so the DMux is basically an inverse of a Mux, DMux is an inverse of a Mux. If you don't like my pronunciation, and once again it distributes a single input into one of several possible output channels. Once again, just like we said about the multiplexor, demultiplexing is also something which is widely used in digital design projects, as well as in communication networks. And we're going to get, or you're going to get the stub file, and you actually have to implement the logic in HDL. All right, I'd like to give you an example of how multiplexing and demultiplexing can come to play in the context of communications networks. So here's a typical situation in building a network. And the situation is such that we may have several channels coming in. Let's say channels of music or several movies that we want to send over a single communications line. So the single line that goes here in the middle of the slide can be 5,000 kilometers long. And it may be sort of an under water line, and or satellite line, and through this single line, I want to send multiple messages. How can I possibly do it. Well if everything is digital, I can put a Mux in the sending end of our story. And I can feed the Mux and ongoing train of 0101010. This can be done using what is known as an oscillator. And because the Mux is going to get a repetitive frame of 0101, it is going to output blue, red, blue, red, blue, red. In every cycle the Mux will output one bit from one of the two inputs. At the receiving end of this story I once again I put a different oscillator and therefore the dmux is going to distribute the incoming inputs according to the DMux logic. It will output blue, red, blue, red, blue, red, blue, red and so on. So this logic here, the DMux and the Mux logic taken together enable me to braid or interleave several messages over a single communications line, which may be very expensive and therefore, it pays off to use it for multiple messages. And by the way, another attractive thing about this scheme here is that it can be completely asynchronous, right? They don't have to operate according to a master clock. Every one of these two operations, the encoding and the decoding operations can be done separately. All right, so we talked about Mux and DMux which were, by far, the most complicated shapes in the elementary logic gates that you have to build. And let's go on and talk about one example of out of the four 16-bit chips that you have to build. So we'll talk about And16, and And16 looks as follows. We have two inputs coming in, both of them are 16-bit buses, and we have a single 16-bit bus coming out. And basically what we have to implement is a 16-bit And operation. So, it looks like this. One and zero should give us one, I'm sorry, zero, zero and zero is zero. One and one finally gives us one. And so on and so forth. We're going to get one if and only if both inputs are one in the respective index that we are looking at. Now, there's something which is a little bit deceiving in this example here because the calculation of the logic here is not sequential, everything is being outputed, boom, in pollen. And this also gives you some tip on how to actually build it, okay. This is a straightforward extension of Elementary endgates, you can read more if you want about how to handle buses of data in HTML. And basically once you get this sub file we can implement an endgate using a set of two way endgates. All right, so this has been what I wanted to say about the 16-bit variants that you have implement. And finally I want to discuss one example of the multi-way variants which happens to be actually quite a straight forward notion. Here's an example of Mux 4-way 16. It has four inputs coming in, everyone of them is a 16-bit bus. We have 2-bit selection coming in and that is because you need 2-bits in order to select four different possibilities. And we have the stub file and we can build this thing using several Mux 16 gates as well as perhaps some other gates as needed. So what do we have to do in project one? Once again, we have to implement all these gates starting with nothing more Then NAND and previously designed gates. So once you build Not, you're welcome to use it. Once you go Not and And, you're welcome to use any one of these two gates and so on and so forth. So how do we actually do it? How do we actually build every one of these gates? Well, we're going to give you some building materials and we're going to use soar as an example. So we have, you have the gray diagrams from the book or from the lecture we're going to give you this HDL file which is available to you and you can open it up In a text editor. And we also going to give you a text script and a compare file. And here is the contract that we want you to play with, or to play by the rules of this contract. When you run your Xor HDL. That is, once you take this Xor file and implement it and add your own HDL. When you run the resulting Xor HDL file on the supplied Xor test, the test we provide, your output file should be the same as the supplied compare file. If this will happen you have built a chip to our satisfaction. Once again if your chip generates the expected behavior that we have specified then you were done with this chip and you can go on to develop the next one. So for every chip that you have to develop, we're going to give you stub file, test script, and a compare file. All right, so the resources of Project 1 are listed in the nand2tetris website. You can look at the different files if you want and there's no need to download anything. Because if you've downloaded the course software suite, then all the necessary files that you need for this project are available in your projects/01 directory. And you're welcome to start working with these files and build Project 1, if you need some additional resources, you can look at what we did in the first week just to sort of get you warmed up for this project. There is the HDL Survival Guide, tutorial, and the Q & A forum, you can consult with any of these resources in order to gain some confidence and actually go out and build Project 1. In closing, I would like to say a few words about what we call the hack chipset API. When you build a particular gate diagram like this one, you're going to use all sorts of chip parts. In this case, two end gates a single or gate and a two converters or two not gates. And the question is how are you supposed to know what are the names of the input and output files, I'm sorry the input and output pins of every one of the gates that you want to use? Well, the answer is that if the gates that you use are so-called off the shelf gates, or if they are part of the hack chipset API, we provide all the necessary information about how to use them. And in particular, there is a document on the nand2tetris website that gives you the API of all the chips in the Hack chipset. This document is actually part of the HDL Survival Guide, so whenever you're not sure, what are the names of the inputs and outputs pins of a particular chip part. Please consult this document and you will know how to use them, another thing that I'd like to say in closing before we end this unit is that you can always use what we call built-in chips. For example suppose you implement some chip called Foo and you want to use a chip part called Bar. How can you do it if you haven't written Bar before? It sounds a little bit impossible but in fact, it is possible, so once again, if you don't implement some chips that are part of the chip of the Hack chipset, you can still use them as chip-parts. All you have to do, if we gave you the stub file of Bar, you have to change the name of this file to something else. For example, instead of calling it Chipname.hdl, you can rename it chipname.hdl1. Once you do this, when you load Foo into the hardware simulator, the simulator will look for and hdl file that corresponds to the missing chip part, and if it will not find it It will by default revert to using the built in implementation of the missing chip. So this gives us tremendous flexibility because it means that in principle we can build these chips in any order that we please although we recommend that you build the chips in the given order that they are listed in Project 1. So here are some general best practice advice for Project 1 and subsequent projects as well. Once again, we recommend that you build the chips in the given order because they are specified from the simpler to the more complex. If you don't implement something you can put it aside and if you want get back to it later, and you can if you want design some helper cheats. You know cheats that we haven't specified which will act like private methods in high level programming. However this is really not necessary, and we advise that you don't do it, there's no need to invent any new chips, just use the chips that we provided and you should be fine in completing this project. And in general and just like we always do in computer science, strive to use as few parts as possible, try to create an implementation which is elegant, readable, and well done. Now, I'd like to end this unit with a few notes about frequently asked problems and questions that students raised when working on Project 1. First of all, you have to realize that when you create your HDL program, you have to use some external text editor like notepad or whatever editor of your liking. You cannot create HDL code using our tools, in particular, you cannot write code inside the simulator. Once again do it in an external editor and once you save your HDL file you can load it into our simulator. The next point that confused some students is that you cannot use a chip as a chip part in its own implementation, there's no recursion in HDL. All right, so all the chips to use when implementing a new chip has to be some other chips that you've implemented before, or some built in chips, which are always available as well. Now, when you run your HDL in a simulator if everything works well you will get a message at the bottom left of the simulation saying something like simulation completed successfully. If something goes wrong and if there's a syntax problem with their HDL code or anything like that, you will get an error message printed in red. So once again, some students tended to miss these messages so pay attention to the bottom left of the simulator when you simulate your chips. Now, in unit 1.6, Norm explained the whole notion of multi-bit busses, and one thing I would like to add to this discussion is that, these busses are indexed from right to left. So if A is a 16 bit bus, then A[0] stands for the right-most bit, sometimes called the least significant bit or the LSB. And A[15] stands for the left-most bit, also called the most significant bit or the MSB. So, this is just a convention that you have to keep in mind when you index your multi-bit busses, and finally we want to emphasize once again that we provide all sorts of resources with which you can consult. When you write HDL code, in particular, the book has whole appendix dedicated to HDL programming and this appendix is also available online in the nand2tetris website. And there is an excellent document called HDL Survival Guide, which was written by Mark Armbrust, and this is the first place that you have to go to when you get stuck with something and you need some advice. So this has been the end of our unit about Project 1 overview and we are ready to go onto the last unit of this week, in which we are going to talk about some general observations, about elementary logic gates. [BLANK AUDIO]

During the first week of this course, we built a suite of 15 elementary logic gates. And in the next week of the course, we're going to take this basic functionality and use it in order to build some more interesting and powerful chips like adders and arithmetic logic unit. Now whenever we teach this course every week of instruction, there's a whole set of issues and questions that come up about different aspects of building hardware and software systems. So we've decided to devote the last unit of each week to answer such questions. And we are calling this unit this last unit every week a perspective unit. So here are the questions that typically come up at the end of this unit in which we deal with elementary logic gates. So the first question of the day is is it possible to build a computer starting with a logic gate other than NAND? Well I'll take this question and the answer is indeed yes, it's possible. For example, you can use another elementary gate called NOR, which stands for not or, and base your entire computer on this atomic building block. Likewise, it is quite natural to start with the suite consisting of and, or and not gates and use them to build a system. And there are a number of other possibilities. And in fact it's quite similar to the way geometry can be founded on different sets of axioms. And each one of them can be yet another point of departure to build, you know, all the power and theorems of geometry. This is not such a bad analogy. However, it turns out that NAND gates are very popular in physical implementations of hardware systems. Because there are many integrated circuit technologies in which it is quite cheap or relatively cheap to build NAND gates. As you well know during the course during the first week, we treated these NAND gates as black box abstractions. So, the next question, which is directly related to the first one, is well, if you actually had to build a, a NAND gate, how would you go about it? Norm, maybe you can answer this question. >> Okay so, in this course we sort of made a point of not going into this question. Because we feel that is already physics or electronics, rather than computer science. But still, let us see an example. There are of course many different technologies to implement and navigate and as in any other gate. But let me show you, let me show you the simplest example, if you wish, of such an implementation. So here is an NMOS implementation of a NAND gate. [NOISE] We have a plus voltage, which is going to be one, our logical one. And the minus voltage, which is our logical zero, and we're going to connect them as follows. A little resistor here which is a wi connection, and then two nice transistors, NMOS transistors, which we connect this way. This is going to be our a input, and this is going to be our b input. And this is going to be our output. So these are the two transistors that we have. So how does this implementation work? The basic functionality of one of these endmost transistors, is that whatever that input gate has, gets high voltage, then it connects the two other terminals. If it gets a negative voltage inside, it disconnects the two terminals. So let's see what happens. If both a and b are one, then we get the high voltage here, high voltage here. These two terminals are connected by this transistor. These two terminals are connected by this transistor. So we get the connection all the way from the output, to negative. And since this is a weak connection and this is a strong connection, our output is going to be negative or zero. As we want in a NAND gate, because when a NAND gets one and one as inputs, it gets zero as output. In any other case, one of these two inputs is going to be negative, which means a low voltage. That when these two connected to the low variable of voltage input, it's going to disconnect the two terminals. In which case, there is not going to be a connection from the minus sign to the output. And so, this weak connection to the plus is the one that's going to rule, and we're going to get the plus output, which is exactly what we want in a NAND gate, which is two. So, this is a NMOS implementation of a NAND gate. There are many other technologies. This one is not used so much anymore, since the 70s or 80s. And the important thing in this course is, we do not care about the technology. We do not care neither about this implementation or if there are any other implementation. We want to abstract that away, away inside of gates that get true and false and output true and false and we don't care how exactly. >> So welcome back from the world of resistors and transistors. And once again, this is a level of detail that we are not going to get into in this course. So here's the next question that we have. And it's about hardware description languages, and, the question is. How does the HDL that we used in this course, and in this week, how does it compare to real HDL languages that hardware engineers normally use? Well first of all, our HDL is a very real language, because you can use it to design computers and simulate computers, and that's what HDLs are all about. At the same time obviously, industrial strength HDL languages like Verilog and VHDL are far more complex and powerful than our HDL. Typically they have a syntax which is some mix of the HDL that we use and something that looks like the C programming language. And they feature all sorts of high level programming constructs, like For and While, which eliminate the need to write a lot of repetitive HDL code. So it's very nice to use these capabilities. And they also feature like our language does, they feature the ability to model and simulate the notion of time and clocks. Without which, you wouldn't be able to build sequential logic. You know, logic that ends up with which, with which you end up building things like memories and and counters, and so on. So these languages are very nice. At the same time, they are quite complicated and would, it would take you at least a month or so to master the these languages in order to begin writing some code for this course. So as an alternative, Norm and I decide to, decided to design a very simple dialect or very simple version of HDL and offer it to you. It has all of the capabilities that we need in order to build the computer that we will build in this course, and you can learn it in one hour. The next question, which is for Norm, is as follows the chips that we built so far were quite simple. How does one go about designing complex chips containing hundreds of parts and connections? >> Well, the truth is [COUGH] that there is no simple general way of designing complex circuits. It's really a complicated design challenge, and you need human ingenuity to do it well. Now there are many techniques that you learn in in digital circuit digital circuit construction courses. For example, there are techniques for card no maps that allows you to optimize a gate with a small number of inputs. Sometimes you can use various tools. For example, there are so-called silicon compilers, where you specify what the functionality is that you want. And the silicon compiler already has inside it a lot of logic and a lot of algorithms that can optimize gates for you. But again, this is, it is not perfect algorithms. These are all heuristics because the general problem of so-called NP complete, you cannot find a computer program that does it perfectly. The real answer is, is that after all these tools and all these techniques and so on, at the end of the day, you use the usual tools of computer science modularity and abstraction. You break a complex problem into simpler parts, and the simpler parts are simpler to optimize and to construct. And at the end of the day, after you use all your tools, after you use all your techniques, you go back and use this modularity at the idea. >> So these were the questions that we chose to focus on in this first perspective unit of week one. As you can see, this particular format of the perspective unit is open-ended. There are numerous questions that can come up. Once again, we don't want to deal with the level of transistors and resistors. You know, this is something that belongs to electrical engineering. We want to focus on computer science. And when it comes to hardware technologies and so on, there are many questions that Norm and I cannot answer either. So we are we welcome any questions that can come up. You can post these questions on the course Q&A forum. And if there are other students who are who have some knowledge about these areas you are perfectly welcome to go to the Q & A forum of the website of this course and answer these questions on your own.