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. This still series is called combinatorial logic, but we're to learn about Boolean algebra that I've hinted about before.
So I also mentioned a couple of lectures ago that George Boole — Claude Shannon made the connection between transistors and the mathematical work of George Boole to, wow, 1's and 0's and transistors and circuits, that connection was really wonderful and really rich.
And so he named it Boolean algebra in honor of George Boole. There are some primitive functions that Boolean algebra has.
They're and, or, and not, power so that we can use normal mathematics and connections between massaging things in the Boolean algebra world and then making a connection between how the circuit might change and be equivalent as well.
This is the first thing I'm sharing that's brand new. From now on, if I ever say plus, I mean or. If I say times, I mean and.
And, if I draw a bar on top, I mean not. And, if that bar is over a big expression, I mean invert that whole expression.
If the bar is only over a term, I just mean invert that term. Okay, so remember that as we move on to this.
So here is the Boolean algebra — here's the circuit of a majority function. What would that look like in Boolean algebra? Let's take a look.
I'm seeing a and c, which, remember, now is a times c. I'm also seeing b times c. I'm also seeing a times c.
And there's an or with all of that, which means they all have to be grouped with a plus between them.
And that's what I get a times b, a times c, and b times c. And you're going to notice, by the way, I didn't do the same order.
The interesting thing is this order doesn't matter. Why? Because Boolean algebra tells us that addition is commutative. a or b is the same as b or a.
And I can also flip the order of these two as well. a times b is equal to b times because multiplication is also commutative, pretty cool, okay?
Because we do, when we're kind of learning algebra, maybe in ninth grade, we don't have to put a dot in between any two product. We can just say ab.
Now, remember, I don't mean ab, a single line called "ab." And there's a single line called "ac" and a single line called "bc." I don't mean that.
I mean these are three different signals, and the products are themselves. This is a challenge when we go to the next slide where you see that, sometimes, our input names aren't single letters.
They are even more complicated. This input means it's a single — single signal — try saying that 10 times fast — that happens to have five letters describing it.
PS is a two-bit signal. So I have to have PS sub 1 and PS sub 0. Again, this can be complicated, but let's see if we can actually work through this.
We saw this before. Okay, this is our finite state machine encoded as a truth table.
And it's a 1 if and only if the first PS sub 1 is 1, and PS sub 0 is 0, and INPUT is 1.
So there's my circuit. We've seen this before, okay? We also thought we could simplify it into that.
And the interesting thing is, how do I then take this and write this in a Boolean algebra way?
Well, I've got PS sub 1 and or times not PS of 0 and INPUT. So output should be the product of all three of those terms with a bar over PS sub 0.
And that's exactly what I get. Output is PS sub 1 one term and not PS sub 0 and INPUT. And, remember, don't think this is five different inputs, each a single bit long.
And it's I times N times P. That's not what we have.
And so try not to have — you can have a system where there's also an N and a P and a U. Don't do that.
Make sure you're very clear, and don't ever have another bit input. Here's an I input and an N and then some product is INPUT.
And that would be indistinguishable from this input, which is a single line. And you mean five different lines. Don't do that. So keep the naming consistent.
You can get in trouble with that. So try just to be clean with that. We can do a simplification. We're going to — this is our last slide on this.
But we're going to be able to see that I can go from a circuit to then some kind of equation derived from that circuit and then use my Boolean algebra to actually simplify that circuit to get the simplified version.
This is the simplest form of Boolean algebra. Therefore, I've simplified the actual circuits needed too.
So, if I'm going to have to wire these guys or use transistors on a chip, I would much rather have the simplified version that's the fewest number transistors to use that.
This is only one gate. I love that. That's much better than these three gates. This has much more delay.
This has more area on a chip. They have more delays. There's a lot of reasons I don't like this more complicated circuit. I do want the simplest form, fewer delays, all of that.
So we're going to see the power of Boolean algebra is this.
And the next slide, the next lecture, is going to be all talking about what are these identities we're doing to massage these equations down.
They look like — they look like normal — look, ab plus a. Somehow, I distribute like an a out to get b plus 1. How is b plus 1 1?
We're going to show you all of those rules in the next lecture. We'll see you there. There's just one more thing before I close. I almost forgot to mention this.
One of the great ideas about Boolean algebra is that I can say, I've got two circuits. Are they the same or not?
Actually, if I use Boolean algebra to simplify both circuits — so convert the circuits to their Boolean algebra equivalent.
Then massage them down to see if, at the core, they end up at the same simpler equation. And, if they're the same simple equation, they are the same circuit.
So it's a great way to be able to see if two different circuits that look very, very different are actually the same thing.
Once I use my Boolean algebra to simplify them to the simplest form, I can just compare those simplest forms.
It's often hard to kind of figure out what the simplest form is if you count to some metric, fewest gates or something.
But it's really a nice way to be able to compare two different circuits. I just wanted to make sure I added that before I closed. Thanks.
Đă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.