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. This is now the last in a series of combinational logic lectures in which we talk about canonicalization forms.
So canonical forms is a way to describe — the word, canonical, means it's like the one representative thing of something.
So it says, there are lots of ways to take this truth table and transfer it into a series of Boolean algebra expressions, but there is only one canonical form.
And so let's talk about what that canonical form is. And that actually helps us think about how to do this, in general, with any truth table.
So this is the part that I was talking about. I didn't really tell you how to do this in general. Now we're going to go very slowly and make sure we do this.
So the way you do this in canonical form is you take a look at your truth table and you say, where is there a 1 in my output?
Let's now bap back for every 1 — I kind of hinted to how to do this, but now I'm telling you formally — every time you have a 1, this is a 1 if and only if this is a 0 and that is a 0 and that is a 0.
And another example — this is the 1 when this is a 0, this is a 0, and that's a 1. So what expression would be true for just that row?
Every time you have a 0, you put a "not" in front of that term. Every time there's a 1, you just leave that term there.
So in general, let's pick a term that has 1's and 0's in it.
So this term, for that 1, only that 1, would be when a is true and b is false and c is false, otherwise known as a not-b not-c.
If you do this for all the rows, now I have a term for here, a term for there, a term for there, a term for there.
You then take that and say, well, it's a 1 when this is the case or when that's the case, or when that's the case, or that's the case.
And so what we're going to see is this canonical form is called the sum of products. And that's the idea.
It's saying it's that row or that row or that row, et cetera, or that row, until you're all done. And that's the canonical form for taking a truth table.
And you can do this now for any truth table. You have an infinitely long truth table, and I just go over every one in the outputs, for however many outputs I have.
That one for that particular bit is true when — and I go through, and I make a product. And I somehow have to have negate some of these terms.
And it's like a and b and not-c, which is the last term in this example. So that's the canonical form part 1.
Then I take the canonical form and I bring it into my world of Boolean algebra. I dip my hands in Boolean algebra massage oil and I started working it.
I start working that expression. So let's do this together.
And I'm here showing you exactly — I had to do this, by the way, when I was taking my geometry lessons back in high school, where I had to kind of make the rule, this is side angle side, and then move it to the next level.
And I'd always have to label it with what is the rule I'm applying there. We could ask you to do that. So make sure you know what the rules are.
We'll always let you bring the table of that slide of all the rules with you. But I don't tell you how to use them. So here we go.
Well, I got these three terms. I see a common not-a not-b here. So I could reverse-distribute not-a not-b into this. So I have this term out.
The same thing with a and not-c. That's also commutativity. I'm switching that so the a not-c is in the front, so a not-c not-b, or a not-c b.
That gives you these two terms. Now c or not-c. Well, I'm either happy or I'm not happy. Folks, you're always going to be a 1 there.
I'm either happy or not. I either have pizza or I don't have pizza. You either have a burrito or no burrito. Folks, that's a 1.
So that's the complementarity rule we saw there. And this is the easy one. You know this from algebra. That's just identity.
And that gives you the simplest form here. So this is not-a not-b or a and not-c. And we can now transfer this into a gate diagram. And so I now have — watch here.
I try to make use of the fact that I've got to have — actually, this is all unique. There's not a single doubling up here.
So I've got a not-b I need, I've got Not-A and an a I need, and I had a not-c. I don't need c and I also don't need b.
Because no c and b terms in here. And this is in or of that. So I can already see this. I can already see there's going to be one or.
And I'm going to see an AND here, and I see here an AND here. And I probably need some NOTs for these guys. Each of these guys map to those NOTs.
And if I then remove the NOT gates and push those bubbles up to the front or the output, you push — if I had a NOT at the end, if I had a NOT at the end, I would push that bubble there.
So you take the NOTs and then push those in as another way of thinking. And this is kind of what everyone — pro tip — draws, is we don't draw any NOT gates.
We always draw them as bubbles, and you push them into either the input of the output of the gates of AND and OR — or XOR, or whatever you have it.
Okay, that's pretty cool. So truth table, massage truth table sum of products to get canonical form. And now I take that to then bubble it down to be the simplest form I can.
Okay? Very good. In conclusion, we're going to pipeline big delay combination logic for a faster clock. We saw that.
We love finite-state machines. They're able to describe a brain of a system, how to do something, a Turing machine.
A universal Turing machine is basically a finite-state machine driving how a tape moves left and right.
And we can see this beautiful graph to describe how we move from truth tables to Boolean expressions to gate diagrams. I can go back and forth from a truth table to a Boolean expression.
No problem. I can go back and forth from a truth table from a gate diagram to a Boolean expression and back.
But it's not immediately clear how I go from a truth table to a gate diagram. That's hard to do. We say, you know, I can't get there to here.
I want you to go to a Boolean expression and then maybe simplify it, and then go to the gate diagram. So this is not something we say it's easy to do.
We want to go to a Boolean expression, and then massage it to get the simplest gate diagram. Because again, you want the simplest gate diagram you can. That's it.
That's the end of this lecture. We'll see you at the next one. Take care.
Đă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.