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ả.
DAN GARCIA
And welcome back. Now we're at our third series of this STS series, four lecture series where we talk about combinational logic.
So far we've seen introduction to synchronous digital systems, state, registers, how those work, timing. That's a really important piece of it.
Now we're kind of at the don't worry about the analog element of it. Let's just talk about the logic part of it.
This is a little bit more fun, a little bit more digital, and thinking about the analog — the realities of the analog world are not as present here in the combinational logic world.
So let's talk about combinational logic and jump on in. We start with truth tables. And maybe you've seen truth tables before. Maybe you haven't.
In terms of how it's funny, I learned truth tables, how to do them, I think I was in fifth grade. We were doing basic truth tables.
I think I saw them again in eighth and ninth grade. This is just me. I went to my school different places across the world from here. But hopefully, you've seen this before.
If not, I'll try to go slowly with this. Here's the box. Truth tables are on combinational logic.
If you remember from a lecture or two ago, combinational logic circuits are those that have no state and no memory. Some set of inputs, the output will always be the same.
If I go back and put them back again, it'll still be the same. There's no memory to these things.
This is just pure combinational logic, pure functions, if you will, in the 621A and CS10 sense. So this is a four-input, one-output box. I've got a y here.
On the right, you're going to see this is kind of how we typically draw this. Back in the days when you were doing truth tables, you might have drawn T and Fs.
Stop doing that. You want to use zeros and ones. And in fact, as you're counting them, you want to basically count up from a nibble. Here's 4 bits.
Count them up all zeros to all ones. You don't want to put — I've seen people draw these where they write T and Fs. First of all, T and Fs look too close together.
And also, they write all Ts first. No, the first row should be all zeros always, and the last row should be all 1s, however many bits you have.
So this is a box. I could buy this box at Fry's Electronics. And this is whatever that box does for all zeros. What does that box do for all zeros and a one?
So it's actually interesting about this. I'm going to ask you a question. How many of these boxes does Fry's have to sell? That's a fun question.
Think about how many different of these boxes they have to stock.
I mean, if they had to have one each for all the different ones that have a different pattern here — I'll give you an example.
The AND gate, which is true only when all of them are ones, has a one down here. And a big old zero for everybody else. That's one of the boxes they have to sell.
They have an AND. So how many other devices do they have to sell if they want to cover every single possible case? Think about it. And I'll give the answer in a second.
And welcome back. Here's how many. It's kind of cool. Turn your head sideways so you're looking at this number with your left side here and your right side there.
How many different bits do you have there? I count 16. 2 to the fourth was 16. Each possible bit pattern is a different box.
How many different bits? We call that the signature of the box. How many a bit patterns are there with 16 bits? 2 to the 16th.
That's 64,000.
So you have to have 64 kb — this just means 64 K — different F boxes if you're going to have this for every one, if Fry's is going to stock every possible combination.
Isn't that kind of cool? 64,000-ish. That's a lot. So that's pretty cool.
What do you think about that? Here's another truth table example. This is going to be 1 if one, but not both of a and b are 1. By the way, I love this example.
This example, if I said, Halloween is coming up — we're in the fall here, so Halloween is coming up.
If a kid comes to your door and they say, trick or treat, they mean this table. This table is for trick or treat. This is a Halloween table.
Why? It says, trick or treat. Trick OR treat, but not both. Here's trick OR treat, but not both.
So they mean it's a 1 if one or the other is true, but not both.
What that means on Halloween, if you give the person a treat, you expect them not to toilet paper your house. The idea is it's a contract.
If I give you the treat, you're not going to do a trick on me. So it means this table. This is the Halloween table! So remember to see this thing.
Always remember this table as the Halloween table as an example of that. Pretty cool, right? By the way, I want to show you another way to think about this table.
This is rarely taught. It's like, pro tip. If you think about it, when a is 0, how does b relate to the output? It's exactly the same!
When a is 1, how does b relate to the output? It flips it. It's like not b. So in fact, I can summarize this table by saying this is a two-element, two-row table.
When a is 0, the output y is just b. When output is 1, the output of y is not b. It's a kind of tighter way of thinking about the table.
I want you to get used to that and comfortable with that. If I change this to any pattern of four things — by the way, how many — I'm going to get to that.
How many of these would Fry's have to have? For every one of those, I should be able to kind of reduce this into this kind of table. When a is 0, what is it?
When a is 1, what is it? So that's kind of neat. By the way, if these were both 0, I would have written a 0 here.
If these were both 1, I would have written a 1 here. If it's 0, 1, I write b here. If it's 1, 0, I write not b.
So that's how you kind of compress this table to that way. Kind of neat, right? Here's an example for the truth table of a 2-bit adder. We've seen this before.
We used adders before in our last series of lectures.
This again, is a 2-bit adder where the output now — I was saying before, well, those 2-bit adders without overflow, because sometimes you put some numbers in, and it's bigger than that.
So I had n, and n, and n output saying, well, somehow we don't worry about that at this early stage, whether it's overflow.
But in fact, if I had a 2-bit adder, I mean, you can think about this. The biggest number this guy can be, 1, 1. That's three.
The biggest number this guy can be is 1, 1. 3 plus 3 is 6. That's 1, 1, 0. I kind of knew that, because I'm doubling this.
And you double it. You just add a 0 there. So there's no way to think about binary numbers in that way.
So I have to have three to be able to handle all the cases. C is really — this is the fun thing — C is really should be 3 bits.
And by the way, I've instructed it before. This slash tells you how many bits wide that line is. If you haven't talked about it before, that's the way to think about this.
So this is a 2-bit adder. This is all the logic of a 2-bit adder. Again, I think of the grouping of a really being A1 and A0. Here's B really meaning B1 and B0.
And here's C being C2 through C0. So let's ask a question. How many rows does this have? Well, just like before, the number of inputs is 4 bits of inputs.
Therefore, that's a nimble input. Therefore, I have to handle all the cases of 16 different cases for that. Well, that's nice. I can do that.
If you need me to build that, I could probably build that. That's not a problem. Except I want to extend that to 32 bits. And now I've got two 32-bit inputs.
And this is an unsigned adder. We don't have to worry about anything other than unsigned values. And I've got this guy. Maybe this is 32.
And this is 32 and 32. And this might be 33. Again, what's the biggest output? Here, the biggest output is there.
This better be 33 bits, because I've got all ones with a zero, because I've doubled all ones and a zero. Well, you might ask the question again, how many rows do we have?
Can anybody figure that out? Is that the right way to do this? Is the right way to build a 32-bit adder by looking at the truth table for it?
I'm kind of revealing that that might not be the right way to do it. Well, how wide is this? That's an input 32 bits. That's input 32 bits.
Well, before it was the total number of bits is my input. That's how many rows I have. 2 to the that. I count it in the 64.
That's a lot. That's 16 xb rows.
Too many rows, way too many rows. So this is not the way to do this. So let's actually take a step back. At some point, we'll tell you how to do that another way.
I'm giving another example. Here is a three-input majority circuit. I say majority. It's almost like three people are all deciding, should we go that way or that way?
Let's all 1, 2, 3. 1, 2, 3, shoot. And the majority wins. So for all zeros, let's do it.
Let's see if this actually adheres to that. There are all zeros. Majority wins, zero. If there's two zeros and a one, zero wins.
Again, two zeros and a one, zero wins. Two zeros and a one, zero wins. Every other case, there's more ones than zeros. Two ones, two ones, two ones, three ones, and then one wins.
We call this the majority circuit. That's kind of neat. This is like breaking a tie. Breaking a tie for that.
So that's kind of fun. I gave you a couple of examples of truth table. And that's the basics of it.
Sometimes we don't use the truth table to build circuits, like for the adder, we might find a better way to do that. We'll actually talk about that later.
But this is the way to think about this. You want to be writing zeros to ones. You want to be counting from all zeros to all ones in that way.
Don't use Ts and Fs. And that's it. Thank you so much. We'll see you at the next lecture.
Đă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.