Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
And welcome back. We're still in the lecture series on combination logic. Let's talk about logic gates.
So here are the basic three logic gates that are going to be used as building blocks for larger circuits. The first you've seen before, probably. You've at least seen the truth table for it.
And this truth table says it's an AND gate. It's an AND gate. This is the truth table for AND.
By the way, remember, you're always going to draw this as the counting from however many bits of input, just from all zeros to all ones.
So make sure you do that when you do it for all these. And if that's the case, you're always going to see AND have this signature, 0, 0, 1.
Or in general, for even inputs, all zeros and only one one at the end, which is all of them have to be true. This is the block diagram we use for that.
So as we look at this, we'll say AND. And it's like a half circle in a way. So here's a straight line with the half circle there for my AND.
OR is similar to the logical OR. You've probably seen this before in — you've done this in CS10, or 620, 620B. You've done this bitwise. This is not bitwise.
This is a single bit. This would be double AND. That's my AND. This is OR.
We're talking about a single bit we're talking about, not bitwise. All right. OR says, I'm a one if and only if, at least one of them are a one.
So this is all of them. This is any of them. This is the any block. Any of these guys is a one, then I'm a one here.
And the shape looks like this, kind of a curve here, and then a curve there, and then a curve there. And they meet really pretty.
A NOT gate is drawn like a triangle with a circle at the end of it. And that basically does the invert of that.
The inverse if it's A, if A is high, then it's output is low. A is low. Output is high. So that's the block for this.
Now, when I'm thinking about AND versus OR, those two shapes are brand new, and you're going to forget them. So here's, again, AND's truth table. Here's the AND's gate symbol.
How do we remember them? I want to give you a way to never forget that. So turn your memory on high resolution to never forget this. Ta-da!
Isn't that cool? A-N-D has the shape D. And nobody taught this. I don't know. I came up with this.
And nobody taught this to me. But I'm not sure if I ever came up with this. But this is a way — a mnemonic for you.
This D looks exactly like the shape, if you use the right font, of the gate symbol. So please remember that.
From now on, never get AND and OR confused, because OR has nothing equivalent, but AND has this D that looks exactly like the AND symbol. Again, we're back the logic gates.
We talked about before, or I should have mentioned that that should be called inclusive OR, because inclusive OR means you're one or the other, or both.
Exclusive OR says one or the other, but not both.
So exclusive OR is special, and says — by the way, from now on, I would like every Halloween people to say, trick XOR treat, because this is what they meant.
They meant XOR. So from now on, tell all your friends, and kids, and cousins, and brothers, and sisters to say, trick XOR treat.
Because I don't want anybody — because really, it's not trick or treat. If I give you a treat, I don't want a trick. That's the idea. That's the contract I'm getting.
NAND is almost identical to AND, except it's this little bubble at the end that says, invert the output. So AND would have had a 0, 0, 0, 1 here.
I say, the bubble means invert all of those. And exactly the same as NOR. NOR is 0, 1, 1, 1. And I invert all of those guys to give me my NOR value.
By the way, this is exactly the same as saying A and B here pass through an OR passed into a NOT gate.
So basically, whenever you see this bubble, this bubble really means I took this picture and shrunk it down just to its essence, just to the circle at the end.
And you can do this to the input, too.
I could also have — if I had a NOT gate here on the input, there was a NOT gate on the input, I would have drawn a circle here in the input.
So you can convert these NOT gates and push them until they're both touching the bigger blocks, either the input or the output side. And you can get that.
We'll see that a little later. But that's the idea of that circle. Now, let's think about if you have logic gates extending them to N dimensions — not N dimensions — N-inputs.
Most of them make sense. If I have an AND, if I have a 10-input AND, it means you're a one only if all 10 are one.
If you have a 10-input OR, it's a one if any of the 10 inputs is one. It's the same thing. XOR is the only one that isn't so clear what happens.
I just want to make sure you understand what an N-input XOR does. What really XOR is doing is counting the number of ones. And when the number ones is odd, it's a one.
Let's go through it. Here we go. Let's count. Number of ones, 0, 1, 1, 2, 1, 2, 2, 3.
Which of these are odd numbers? I'm going to circle all the odd numbers. Oh, look. It's working.
Palmolive. It works. Look at that. So every time you have an odd number of ones on all your input lines on an XOR, your output is a high, high, high, high.
Otherwise, you have an even number, your 0 and 2 here. And it's a 0. And this works for N-input.
So think of XOR with N-inputs as doing that, counting the number of ones, and really saying, are the number of ones odd? Odd. Yes, that's what it's doing.
Good. Now, here is a truth table for our majority circuit. And by the way, I mentioned before when I have two lines that aren't crossing, I like to do this.
And that says they're not the same. But even if I did this, if I don't draw a circle here, the circle means they are connected. They are really the same line.
They are touching.
If I do this, even though I prefer in the best way to draw it like this, if you see this, you should be able to live with it to say, well, it doesn't have a big circle.
So therefore, they're not connected. Therefore, I'm drawn like this because it's too many lines to draw this thing under it. But I'm going to say that they are not connected.
So this is connected, connected, and these are not connected. So here's a picture. And you see it. Let me actually bold here.
Look at this guy. That's a big one. That's a connection. The rest of them are not connected.
So even though they're crossing, they're not connected. Make sure you know that. All right. What is this doing?
I can go from truth table to gates. Well, let's see how this works. Let's see if this is true.
I haven't shown you pedantically how to do it step by step, but let's see if this actually is consistent with what this is right. So I claim these are one in the same.
Let's see. Let's test it. Well, this first guy is saying a AND b.
If here's b in that line, and here's an a in that line, so it's saying this is an OR of a and b. So the output is an OR.
So let's try it. So when is a and b true? Only here, that's a and b. Well, it's one.
The output is a one, meaning OR is true if any of them are one. So it's true if that's true, or b and c. So now let's go to b and c now.
When does b and c go high? Well, here and here. Yep, it's a one there.
OR when a and c. And note, by the way, it doesn't matter whether a and c are here or here. This commutative operation a and c is the same as c and a.
Useful. So here's a and c. When are they high? Here and here, right?
There's my a and c, and a and c. And it's high there. So this actually works. This is really cool.
This simple circuit covers my majority. So that's kind of neat. So I can now think about how to go from truth table to gates. That's kind of fun.
We even saw this before. Remember what this was? I just showed you a lecture ago. This is my truth table for my three input.
It's going to go high when I have three ones in a row. I'm trying to be kind of a three one detector.
It will go high for every three ones I get, and then it'll reset itself, and wait for the next three ones in a row.
So if I get four, it goes low again until I get six. It goes high again. Well, take a look. Here's my output line.
What's my output line? Look, my output line is only one. I only have 3 bits. Let's think about this.
By the way, here's this PS line. This is important to talk about this now.
It's really nice if I have a single letter for each of — as I'm talking about Boolean algebra, which I'll talk about a little bit later, it's really nice when I have only a single letter for each input.
But sometimes I have multiple letters and like a word. Here's PS. It's two, an acronym, Previous State. But I also have a word, input.
It's a little bit harder to then write the Boolean algebra form for that. So for now, you don't have to worry about it, because there are just lines here.
But this PS is a grouping. There's PS sub 1, which is that set of bits. Here's this guy is PS sub 1. And you can imagine that this is PS sub 0.
So this circuit to determine the output only has three inputs, PS sub 1, PS sub 0, and input. So this output is true only in the single case.
Now, if I only have a single case, what is that case? What's the case where this guy's a 1, this guy's a 0, and this guy's a 1?
Let's do it. PS is a 1. This is a 0, but I invert it. It becomes a 1.
Look at that. Bloop! And input. So you can see a way to map a connection from a single row and how to make that row always true.
You make it an AND. It's true only in an AND case. Let's say I had 20 inputs. When this is high, I just write the term.
If it's ever low, I invert the term. See that? I invert the term. So I can read this.
This is high. Remember, here's an example of me pushing my NOT gate up to that little bubble there. There's my bubble there.
So it's only high when PS 1 and not PS 0 and input.
This output is high only with a single gate, this single gate, which is really kind of two gates. It's an AND. It's a three-input AND and a NOT in the front of it.
I can cover this. That's kind of cool.
So we've kind of shown — I haven't really shown you, again, step by step how to do this, but we've shown how we can think about a truth table being mapped to gates, and thinking of this as, again, one to one equivalent to this.
It's really very beautiful in that way, kind of neat. We'll learn more about this in that next lecture. See you there.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.