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 so close. We've got an ALU. We don't know about overflow yet.
We know about the adder and subtractor. We know about the AND and the OR box. Let's actually take a deeper dive into the adder and subtractor. We can do the two ways.
We saw this. We can use a truth-table, figure out the canonical form. We can use a little algebra to minimize the terms and then have some big circuit that does that.
Or we could be smarter about it.
We could look into breaking the problem into smaller parts, and see if we have some of the parts that we might actually have existed already on my shelf I can put together, cobble together, and make — and that's actually what we're going to do.
So we're going to do the second one. So let's actually just do an adder and subtractor. Here's a nibble adder. 4 bits plus 4 bits equals 4 bits.
And let's think about what is required to build this nibble adder, and whether we can actually maybe cascade some adders together. So at the lowest level, I'm adding bit a0 and b0.
This is the least significant bit, and I'm adding it to this sum. But I also have a carry, and this carry is like here. There's my c1.
That's the carry that's going to pass in, to be passed into the next guy. So when is that — let's look at the logic of that.
What's the value of s0 and carry 1 based on a and b? It's basically out of these 2 bits. What's the sum of 0 plus 0? 0.
What's 0 plus 0? 1. What's 1 plus 0? 1.
What's 1 plus 1? 2. So guess what? I just literally take this number, and I write it in binary.
This is here, and this is here, but this is flipped. It's like, if I wrote that number but flipped it.
So 2 is really 0, and 1 carries. 1 is just 1 with no carry. 0 is 0 with 0 carries. So this all this is.
That's very simple. So now, once I have that, have you seen this before? Yes, you have. It's called XOR, exclusive or.
Have you seen this before? Yes, you have. It's AND. So that's kind of neat.
Just a very simple truth-table. Not the full 32-bit one. Just 1 bit at a time. Let's have slices at a time.
I get XOR and AND. That's the lowest bit. That's pretty easy. How about the next one?
I'm not going to give you the answer, because that first one's a little bit easy. But this is the next one. Let's actually do it together. This one requires 3 bits.
Why? This is carry-in, and this is carry-in plus 1. And by the way, this calculation is for all the rest of the bits.
So I listed i here, not just 1, because, in general, I'm going to say, what happens on the i-th level? So let's change it to be an i, and an i, and an i.
And this is the truth-table for every other column. Every other 2's column, 4's column, 8's column. Every other column does this. Let's do it together.
We saw this before. All I'm doing is adding together ai plus bi plus ci. Let's do it together on the left. Okay, here we go.
That is 0, 1, 1. I'm just adding up the number 1. That's all I'm doing. 2, 1, 2, 2, 3.
What's the low-order bit? The low-order bit is this one, which is s of i. That's the sum of i. And the carry is carry i — whoops.
Let me clear this up here.
This is sum of i, and this is carry i plus 1. So I take this number, and I flip it. And this is the low bid, and this is the high bid.
So 0, two 0's. 1, 01, 1, 01, 2, 10, 1, 01, 2, 10, 2, 10, 3, 11. So far, not too bad, right? I got confused for a second.
And now, have you ever seen — this is a little harder now. Much easier when you have just four rows, figure out what the pattern is.
Have you ever seen those two in any of the lectures we've shown before?
Take your time. Pause it. Go back. I'm not going to tell you the answer until you think about it.
Take your time. Think about it. Come on back in three seconds, and I'll tell you the answer.
Welcome back. I've seen them before. You know how I've seen them before? Look at this guy.
This guy is, if I count the number of 1's, what's happening? There's some kind of parity thing going here. How many times is the number of 1, 1?
The number of 1 odd. Look at that. That's interesting. Number 1 is odd here.
Interesting. Number 1 is odd here. So I think s of i, to me, looks like an XOR. How about the C column?
You've seen this before. You didn't know you've seen it before. You forgot it, probably. What's happening here?
Look. When I have two 1's, it's a 1. Two 1's, it's a 1. Three 1's, it's a 1.
Otherwise, there's more 0's than 1, and they're all 0's. They're all zeros.
Remember this before? It is the majority circuit. Exactly right. We've seen this before.
We only saw two 3-bit blocks. You can buy fries. Actually, we saw the AND, we saw the OR, we saw XOR. We saw the majority circuit.
This is the majority circuit. And remember what the majority circuit was. Remember, it was ab, ac, and bc. That's it.
So we can now wire this together. So here we go. There's my 1-bit adder. 1-bit adder has how many inputs?
I count three inputs here. Everybody coming in as that. Here's my two outputs. This is the general case.
Not just the LSB adder, but this is the general adder. And what is this? That's the SI. That's the sum.
It's the XOR. What is this? This is the majority, and that is the carry. I just got it.
I'm almost done. How do I take these and put them together? How do I wire them? That's the little harder part.
And now I know how 1-bit adder works. Three inputs, eight rows in the truth-table. How do I take n 1-bit adders and actually make it work? Well, you saw there's this box.
It had, like carry-in, carry-out. They're kind of like left and right. Exactly right. I just cascade them.
I literally just plug them in, side by side by side by side. And that's it. I'm all done. This is pretty magical.
I've got my C0, which is my carry 0. Is there a carry-in? Not really. We're probably going to set this to 0 for now.
We may set it to another value later. Think about it, because I'm not really adding anything in. But again, I can only buy the same box. The box is this three-input thing.
How do I wire that first input on that first guy? The rest of them log in. Now, I've got a carry-out. What do I do with this?
This is certainly the sum. I can make use of that. This is certainly my pairs of inputs. I can make use of that.
I know how to wire that together. But what do I do for my carry-out? Is this always overflow, maybe? I don't know.
We definitely lock this into 0. Let's play with that a little bit. That's pretty cool, right? So what about overflow?
Let's actually answer that question. What about overflow? Well, if I'm doing an unsigned computation — pure unsigned; a and b are unsigned — when does it overflow?
Well, it overflows when I can't store the output here. How do you know I can't store the output here? Because this guy goes high.
So actually, for an unsigned point of view, that is my overflow. For two unsigned numbers, that's my overflow. I'm feeling good about that.
When I can't store it — I stored two 32-bit numbers, and there was one extra thing that bubbled over. Sorry. Overflow means I couldn't store the valid sum in the 32 bits I have.
Once that guy goes high, once c of n goes high, that last guy goes out, it's proof. It's like bluuoop, like water bubbled off the edge of the thing.
It's proof that this thing is full. I can't store it, and that was lost.
I'm supposed to have this big a number, a 33-bit wide number — it's 32 bits wide — but I can't. However wide this is, I'm supposed to have an n-bit wide number.
But actually, I need n plus 1 bits to do that. And that c of n tells me that's what that n plus 1 bit is.
When that's a 0, that says I can fit it in the lower n bits. When it's 1, it says I can't fit it in the lower n bits.
This is complicated. So let's actually take a look at what happens when it's signed computation. Unsigned, easy. It's that carry-out.
But let's look at the signed computation. I spent a lot of time making this slide and a lot of animation. Let's hope this all works.
We're going to start by looking at a single 2-bit number. 2-bit number. If I have a 2-bit number, what are the values of that? Well, 00011011.
That's just the raw bits. What are they really interpreting? What do they mean? Well, you know that all 1's in a signed number — you should know this — all 1's is negative 1.
Always. With 2's complement, all 1's is always negative. I don't care how many bits you're talking about. All 1's is negative 1.
So this is issue. Stay with me. This is fun. Deep breath.
So this is the series of numbers I'm really adding. This is the numbers here. And these are going to be the same numbers for the whole column.
So that's all 0's on the top number. Here's 1, all the top. This is the bottom number. 00011011.
And in a way, I can think of this 2-bit number as kind of being a number, and in a way, it's signed. In a way. So I'm thinking it's a 2-bit number.
And looking at what? Is it always, this output of the upper level, that c2?
Is it always that c2 that's telling me when it overflows? Well, I don't know. First unsigned. So let's actually treat this unsigned for now.
Because it turns out we use the same machinery to add unsigned numbers as I do to add 2's complement numbers. You say machinery. The only thing that's different is how we trigger overflow.
That's all that's different. Everything else is the same. That's really cool. That's one of these we love 2's complement numbers.
Same idea for adding these together. So let's do it together, unsigned numbers. Let's start here. 0 plus anything is anything, right?
Look. Same value. 0001012233. Nothing magical there.
What's 1 plus — these are all, by the way, anything up here is all the same as this triangle. So I don't need to copy that. I only need to do half the triangle.
And by the way, this is a little way I think of this. This is my upper level. I'm looking at c2. Here is c2 here, and this is c1 coming in.
C2 and c1. All right. Let's do this together. 1 plus 1 is 2.
There is a carry, though. This is carry. This is c1. There was a carry 1 there.
That's fine. How by 1 plus 2 is 3? No problem. This is all unsigned so far.
I'm not just thinking unsigned. And by the way, because addition is the same, the only difference is, how do I trigger an overflow? 1 plus 3. Well, that's 4.
So that was both this carry-in — I mean, both this kind of carry-in here, and a carry-out, in that case. This guy only had a carry-in.
This had a carry-in and a carry-out, or c1 and c2. How about 2? Still unsigned. 2 plus 2.
2 plus 2, 4. That only had a carry-out or c2. How about 2 plus 3? That's 5, right?
So this is 5. And again, I only had a carry-out there. How about 3 plus 3? That's 6.
I had a carry-in or a c1, and a carry-out, a c2. Okay. That was unsigned.
Am I right, that unsigned was only that thing? When did it overflow? Let's look at overflow. Everybody that has — circle all the overflows unsigned, because I can't represent 4, 4, 5, or 6.
And guess what? If I just look at — let's look. Those guys that circled overflow, here's my overflow unsigned. And each one of them has the unique pattern that there's a 1 on carry-out.
So I was right. I was right that — at least in 2 bits, and I could extend that to n bits — that when carry-out goes high, then it's an overflow unsigned.
Now let's do a signed computation. So now what I'm really doing, it's the same — by the way, here's the fun part. I'm not going to change any values here.
I still have carry-out, carry-in. None of that's going to change. But when it is, an overflow might change. So let's do this together.
0. This is really 0 plus 01, minus 2 and minus 1, is 01 minus 2 minus 1. That doesn't change.
1. 1 plus 1. 2. 1 plus minus 2.
By the way, what are the values I can store? I can store 01 minus 2 and minus 1. So 1 plus 1. That's 2.
Is 2 something that I can represent in 2's complement with 2 bits? No. That's going to be a problem. So remember that one there.
That's going to be trouble. How about 1 plus minus 2? 1 plus minus 2. That should be minus 1.
Is this minus 1? It is. So stuff still works. That's what's amazing.
Stuff still works. By the way, can I represent minus 1? I can. That's not a problem.
That's good.
This is overflow, even though there was no overflow bit there out of that upper carry. We've got to remember. It's a little different for 2's complement. How about 1 plus minus 1?
Well, that's 0. And it is 0. Look at this. Wait, wait, wait.
This is weird. It's 0 in the lower bits, but it's still saying carry-out. But there's no error there. 1 plus minus 1 is 0.
I get this weird carry-out guy. But that's not an error. That's a fine number. I can represent 0.
And if I just put the lower bits, that's not an overflow. So I kind of need to ignore the — it's kind of weird.
I've got an overflow here, his overflow there, but the carry-out guy didn't tell me anything. I didn't have an overflow here, but the carry-out was high.
So it's not as simple as just treating the carry-out there. Let's do here. Minus 2 plus — actually, minus 2 plus anything. Look at it.
The other two numbers are negative numbers. If I'm already the smallest negative number, anything negative is going to push me past the limit. And that is, is that underflow?
No. It's overflow, otherwise known as negative overflow. So both of these are going to be trouble. Let's try it.
I don't even care what's down here. I can't represent it. It's not minus 2 plus minus 2. It's certainly not 0, and it's certainly not 1, if I just look at those lower bits.
So that's not right. So something's wrong with this guy, this guy, and this guy, so far. How about this? How about minus 1 plus minus 1?
Let's try it. Look at those two bits. What does that encode? That encodes minus 2.
That's fine. So in fact, the only guys that are trouble are 1 and 1. Remember, 1 and 1. So this guy is trouble.
That's overflow. And minus 2 plus anything negative. Which of these two guys? So that's the key.
Remember that, okay? Remember that as we go forward. Everybody else is fine. Here we go.
When can the lowest two bits of the sum not represent the correct sum? You saw that. When 1 adds to 1, or when minus 2 adds to anything negative.
We saw that already in those cases. I circled them before. Here's the official circle from the animation. Is there a pattern?
This is the fun part. You now stare at the slide, pause the video. See if there's a pattern. If you can see when this happens, hint.
Check the carry bit and the sum fourth column bit, which means check this, check c2, and check c1.
Is there anything unique about those three circles that have that that's different from every other circle, every other non-circled expression? Can you see that? Pause it, and then come back.
I'll tell you what it is.
If we look at the highest adder, we're looking at the highest adder. Look at this guy right here. And I look at only these two carries.
And we look at only these blue guys, only the blue guys. What is the pattern when I have — and remember, I'm going to extend this, by the way, to n bits.
I only have to look at the upper level adder. That's, in a way, the signed bit. It's not really signed, unsigned magnitude, but it's signed. When it's 1, it's negative.
When it's 0, it's 0 or positive. So it actually works out pretty well to kind of call it the signed, the highest adder, representing, in a way, the sign of that.
The output is the sign, in a way, that sum. Okay? So here we go. Stay with me.
If I have no c-out or c-in, when is that the case? This means — let's go here. When do I have no blue anywhere? Here, all these guys.
No blue anywhere. You agree? No c-out or c-in. There's no overflow there.
I see no overflow in those cases. That's totally fine. How about if I have c-out and c-in? That's this rare case.
Here is a c-out. Here is a c-in. There's no overflow. I didn't circle.
The guys that are red are the overflows. That's fine.
How about c-in, but no c-out. What does that mean? Here's a c-in, but no c-out. That's an overflow.
That's when I try to add 1 to 1, and I can't do it. That's when two positive numbers are added. Look. A and B are both bigger than 0.
Overflow, okay?
How about — that's this guy. How about c-out, but no c-in? Here's my c-out. Can you see this?
C-out, but no c-in up here. You see that point? That is, they're both negative 2 in this case. So, problem.
All right? Now, what operation is it? I have two bits, c-out and c-in. See if you can remember.
From all that we've learned so far, when do you have one but not the other, or the other, but not the first one? So c-out, c-in, but no c-out.
Or c-out, but no c-in. But not both. When it's both, when it's both, when it's both, it's no overflow. So it's one or the other, but not both.
That's right. XOR. Whoo! That's it.
That's our overflow. 2's complement XOR looks at the upper level adder. This is a 1-bit adder. It's a 1-bit adder.
It's the upper highest bit on both the numbers. N bits. I don't care how many n is. N bits, the upper level adder.
There's a carry coming in from all the other computation, and there's a carry coming out. And only when one or the other is high is that 2's complement going to be overflow.
If it's just unsigned, I only look at c-out. Only look at the guy coming out. This is coming from this way, going that way.
But in the case of a general 2's complement number, it is when this c-in is high, but no c -out, or the c-out is high, but no c-in.
That's the idea. That's it XOR of those two values, and that's the 2's complement overflow. That's pretty cool. So now I've covered that.
We're almost ready to do our put it together, wrap it up. I've got the overflow covered. How do you handle the adder-subtractor part?
That's a little bit — do I have to have a whole box for the adder, whole box for the subtractor? Can I think about that? So that's the next lecture.
We'll close it together. All right, we'll 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.