YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 17.3 - Combinational Logic Blocks: Adder/Subtractor

[CS61C FA20] Lecture 17.3 - Combinational Logic Blocks: Adder/Subtractor — Transcript

by CS 61C Departmental · 3,821 words · 599 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back we're so close we've
0:03got an aou
0:04we don't know about overflow yet we know
0:06about the atom subtractor so we know
0:08about the and and the ore box
0:09let's actually take a deeper dive into
0:11the adder and subtractor
0:13so we can do the two ways right we solve
0:15this we can use the truth table
0:18figure out the canonical form use build
0:20an algebra to minimize the terms and
0:21then have
0:22some big circuit that does that or we
0:24could be smarter about it we could
0:26look into breaking the problem into
0:27smaller parts and see if we have some of
0:29the parts that we might
0:30actually have existed already on my
0:31shelf shelf i can
0:33put together cobble together and make
0:34and that's actually what we're going to
0:35do so we'll do the second one
0:37so let's actually just do a add and
0:39subtractor here's a nibble adder
0:41okay four bits plus four bits equals
0:43four bits and let's think about
0:45what is required to build this nibble
0:47adder and whether we can actually maybe
0:49cascade some adders together
0:51so the lowest level the lowest level
0:54i'm adding bit a0 and b0 this is the
0:57least significant bit
0:58and i need to get to this sum but i also
1:00have a carry
1:02and this carry is like here there's my c
1:051
1:05that's the carry that's going to pass in
1:07to be passed into the next guy
1:08so when is that when is when let's look
1:11at the logic of that when is
1:12what's the value of s0 and carry one
1:15based on a and b
1:17it's basically add up these two bits
1:19what's the sum of zero plus zero
1:21zero what's zero plus one one is one
1:23plus zero one what's one plus
1:25one plus one two okay so guess what
1:28i just i just literally take this number
1:30and i write it in binary
1:32this is
1:36here and this is here but this is
1:38flipped
1:40it's like if i wrote that number but
1:42flipped it okay
1:47so two is really zero and one carries
1:51okay one is just one with no carry
1:54zero is zero with zero carries so this
1:56is all this is that's very simple
1:58so now once i have that have you seen
2:00this before
2:01yes you have it's called xor exclusive
2:04or
2:05have you seen this before yes you have
2:06it's and so that's kind of neat just a
2:09very simple truth table not the full
2:1032-bit one just
2:11one bit at a time let's have slices at a
2:13time i get x or an and
2:15that's the lowest bit that's pretty easy
2:18how about the next one i'm not going to
2:19give you the answer because that first
2:20one's a little bit easy but this is the
2:21next one let's actually do it together
2:23this one requires three bits y this is
2:27carry in
2:30and this is carry in plus one and by the
2:33way
2:33this calculation is for all the rest of
2:36the bits
2:37so i lifted i here not just one because
2:40in general i'm going to say well what
2:42happens on the ith level so let's change
2:44this to be an i
2:45and an i and i okay and this
2:48is the truth table for every other
2:51column every other you know two's column
2:54four's column eight's column every other
2:55column does this
2:56let's do it together we saw this before
3:00all i'm doing is adding together a plus
3:02b a i plus b
3:03i plus c i let's do it together on the
3:05left okay here we go
3:07that is zero one one
3:10i'm just adding up the number one so i'm
3:11doing two
3:14one two two
3:18three okay what's the low order bit the
3:20low order bit is this one
3:22which is s of i that's the sum of i
3:26and the carry is carry i
3:29oops let me clear this up here
3:32the this sorry this is
3:36this is sum of i and this is carry i
3:39plus one okay
3:40so i take this number and i flip it
3:44and this is the low bid and this is the
3:46high bit okay
3:47so zero two zeros one zero one one
3:50zero one two one zero one zero one
3:53two one zero two one zero three one one
3:56okay
3:56so far not too bad right i was i got
3:58confused for a second
4:00and now how do i let's let have you ever
4:03seen
4:04this is a little harder now much easier
4:06when you have just four rows
4:07figure out what the pattern is have you
4:09ever seen
4:10those two in any of the lectures we've
4:14shown before
4:16okay take your time pause it go back
4:19i'm not gonna tell you the answer until
4:20you think about it okay take your time
4:22think about it and come on back
4:24in three seconds i'll tell you the
4:26answer
4:28welcome back i've seen them before you
4:30know how i've seen it before
4:32look at this guy this guy
4:35is if i count the number of ones what's
4:38happening
4:39there's some kind of parody thing going
4:40here how many times is the number of one
4:43one number one odd look at that oh
4:45that's interesting
4:47number one is odd here interesting
4:49number one is odd here
4:51so i think s of i to me looks like
4:55an xor
4:58how about the c column you've seen this
5:00before you didn't know you've seen it
5:01before you forgot it probably
5:03what's happening here look when i have
5:07two ones it's a one when i have two ones
5:10it's a one two ones it's a one three
5:13ones it's a one
5:14otherwise there's more o's than one and
5:15they're all o's they're all zeros
5:19so remember this before it is the
5:23majority circuit exactly right we've
5:25seen this before we only saw two
5:27we only saw two uh three bit blocks
5:30you buy fries and one was well actually
5:32we saw the and we saw the ore we saw xor
5:34we saw the majority circuit this is the
5:36majority circuit and we remember what
5:38the majority circuit was remember it was
5:39a b a c and b c that's it
5:43so we can now wire this together
5:46so here we go there's my one bit adder
5:51one bit adder has how many inputs i've
5:53got i count three inputs here right
5:55everybody coming in is that
5:56here's my two outputs this is the
5:58general case
5:59okay not just the low not just the lsb
6:02editor but this is the general adder
6:04and what is this that's the s
6:07i that's the sum is the xor what is this
6:11this is the majority and that is the
6:13carry
6:14so i just got it i'm almost done
6:19how do i take these and put them
6:21together how do i wire them
6:22that's the little harder part right now
6:23i know how one bit adder works
6:25three inputs eight rows in the truth
6:26table how do i
6:28take and one bit adders and actually
6:30make it work well you saw there's
6:32this box that had like carry and carry
6:33out and they're kind of like left and
6:35right
6:36exactly right i just cascade them
6:39i literally just plug them in side by
6:41side by side by side
6:43and that's it i'm all done this is
6:46pretty magical
6:47i've got my c0 which is my carry zero is
6:49there a carry in
6:50not really so let's we're probably gonna
6:53set this to zero for now
6:54we may set it to another value later
6:56think about it because i'm not really
6:57adding anything in but again
6:59i can only buy the same box the box is
7:01this three input thing what about how do
7:02i wire that first input on that first
7:04guy
7:04the rest of them log in now i got to
7:06carry out what do i do with this this is
7:08certainly the sum i can make use of that
7:10this is certainly my pairs of inputs i
7:12can make use of that
7:14i know how to wire that together but
7:15what do i do for my carryout
7:17is this always overflow maybe i don't
7:20know
7:21we definitely locked this into zero
7:23let's play with that a little bit that's
7:24pretty cool right
7:25so what about overflow let's actually
7:27answer that question what about overflow
7:31well if i'm doing an unsigned
7:35computation
7:36a pure unsigned a and b are unsigned
7:39when does it overflow
7:41well it overflows when i can't store the
7:44output here
7:45how do you know i can't store the output
7:46here because
7:48this guy goes high so actually for an
7:51unsigned point of view
7:52that is my overflow for two unsigned
7:56numbers
7:56that's my overflow i'm feeling good
7:58about that right when i can't store it
7:59oop i stored through 232 but numbers
8:01and there was one extra thing that
8:03bubbled over sorry if
8:05overflow means i couldn't store the
8:07valid sum in the 32 bits i have
8:09well once that guy goes high once sieve
8:11n goes high that last guy
8:13goes out it's proof it's like like water
8:16bubbled off
8:16the edge of the thing it's proof that
8:18this thing is full i can't store it and
8:20that was loss that was i'm supposed to
8:22have this big a number a 33 bit
8:24wide number but if 32 bits wide but i
8:27can't whatever wide this is i'm supposed
8:28to have an n bit wide number but
8:30actually i need n plus one bits to do
8:32that and that c of n tells me that's
8:34what that n plus one bit is
8:35when that's a zero that says i can fit
8:36it in the lower end bits when it's one i
8:38says i can't fit in the lower end bits
8:41this is complicated so let's actually
8:44take a look at
8:46what happens when it's signed
8:49computation
8:50okay so unsigned easy right it's that
8:52carry out
8:53but let's look at the sign computation
8:55and this is i spent a lot of time making
8:57this slide so i hope
8:58and a lot of animation let's hope this
9:00all works
9:01okay we're going to start by looking at
9:04a single two bit number
9:06two bit number if i have a two-bit
9:07number what are the values of that well
9:10zero zero zero one one zero one one
9:12that's just the raw bit bits
9:14what are they really interpreting what
9:15do they mean well you know that all ones
9:17an assigned number you should notice all
9:18ones is negative one
9:20always with two's complement all ones is
9:21always i don't care how many bits you're
9:23talking about
9:24all ones is negative one so
9:28this is an issue okay here stay with me
9:29stay with me this is fun
9:32deep breath so this is
9:35the series of numbers i'm really adding
9:37and this is the numbers here
9:38and these are going to be the same
9:39numbers for the whole column so that's
9:40all zeros on the
9:41on the top number okay here's one
9:45all the top this is the bottom number
9:50zero zero zero one one zero one one
9:53and in a way i can think of this two-bit
9:55number as kind of being
9:56a number and a weight it's sine in a way
9:58okay so i'm thinking about just a
10:00two-bit number
10:00and looking at what is it always this
10:03output of the upper level that's that
10:05that's c2 is it always that is that
10:08sorry is it that c2 is always it's that
10:09c2 that's telling me when this overflows
10:12well i don't know first unsigned okay so
10:15let's actually treat this unsigned for
10:17now because it turns out
10:18we use the same machinery to add
10:21unsigned numbers as i do to add
10:23two's complement numbers you say
10:24machinery the only thing that's
10:26different is how we trigger
10:27overflow that's all that's different
10:29everything else is the same that's
10:30really cool that's one of these we love
10:31two's complement numbers
10:33same idea for adding these together okay
10:36so let's do it together unsigned numbers
10:39let's start here
10:400 plus anything
10:44is anything right look same value zero
10:46zero zero one zero one
10:48two two three three nothing magical
10:50there
10:51what's one plus i don't know these are
10:53all by the way anything up here is all
10:54the same as
10:55this triangle so i don't need to copy
10:57that okay so i don't i only do half the
10:59triangle
11:00and by the way this is a little way i
11:01think of this you know of this is my
11:03upper level i'm looking at c2 here is c2
11:07here and this is c1 coming in
11:10okay c2
11:14and c1 all right
11:17let's do this together one plus one is
11:19two
11:20there is a carry though there's a carrot
11:23this is carry this is c1 there was a
11:25carry one there okay that's fine
11:27how about one plus two is three no
11:29problem this is all unsigned so far i'm
11:31just thinking unsigned okay
11:33and by the way because the addition is
11:34the same the only difference is how do i
11:37trigger an overflow one plus three well
11:40that's four
11:42so that was both this carry in i mean
11:44there's both this kind of carry in here
11:45and a carryout in that case okay this
11:48guy only had to carry in
11:49this guy had a carry in and a carryout
11:51okay or c1 and c2
11:55how about two let's start on sign two
11:57plus two
11:58two plus two four that only had to carry
12:02out or
12:02c two how about two plus three
12:06that's five right so this is five and i
12:08again only had a carryout there
12:10how about three plus three that's six
12:14i had a carry in or a c1 and a carryout
12:17a c2
12:18okay that was unsigned so is it right to
12:22determine
12:22that is am i right that unsigned was
12:24only that thing when when did their
12:25overflow
12:26okay let's look at overflow everybody
12:28that has let's
12:29circle all the overflows unsigned
12:33because i can't represent four four five
12:35or six
12:36and guess what if i just look at let's
12:38look those guys that circle are overflow
12:40these are
12:40here's my overflow unsigned and each one
12:43of them has the unique pattern that
12:45there's a one on carry out so i was
12:47right i was right that at least in two
12:49bits
12:50and i could extend that to n bits that
12:51when carryout goes high
12:53then it's an overflow unsigned now let's
12:56do
12:57a sine computation okay so now what i'm
12:59really doing
13:01it's the same by the way here's the fun
13:03part i'm not going to change any values
13:05here i still have
13:06carry out carry in none of that's going
13:07to change but
13:09when it is an overflow might change okay
13:12so let's do this together
13:130 this is really 0 plus 0
13:161 minus 2 and minus one is
13:20zero one minus two minus one that
13:23doesn't change okay
13:26one one plus one
13:30two one plus minus
13:342. by the way what are the values i can
13:35store i can store
13:37i can store 0 1 minus 2 and minus 1.
13:40okay so 1 plus 1
13:44that's 2 is 2 something that i can
13:47represent
13:48in in two's complement with two bits
13:51no so that's gonna be a problem so
13:53remember that one there that's gonna be
13:55trouble
13:56how about one plus minus two
14:00well one plus minus two that should be
14:02minus one is this minus one
14:04it is so this stuff still works that's
14:06what's amazing this stuff still works
14:08by the way can i represent minus one i
14:09can that's not a problem that's good
14:13how so this by the way this was overflow
14:15even though there was no
14:16overflow bit there out of that upper
14:19carry so something we gotta remember
14:20it's a little different for two's
14:21complement
14:22how about one plus minus one
14:25well that's zero and it is zero look at
14:28this
14:28wait wait wait this is weird it's zero
14:31in the lower bits
14:32but it's still saying carry out but
14:34there's no error there one plus minus
14:36one is zero
14:37i get this weird carry out guy but
14:39that's not an error
14:40that's a fine number i can represent
14:42zero and if i just get the lower bits
14:43that's not an overflow
14:44so i kind of need to ignore the it's
14:46kind of weird i got an overflow here
14:49but it but but his overflow there but
14:52the carryout guy didn't tell me anything
14:55i
14:55didn't have an overflow here but the
14:58carryout was high so kind of it's not as
15:00simple as just
15:01treating the carry out there let's do
15:03here minus 2 plus
15:04actually minus 2 plus anything look at
15:06that the other two numbers are negative
15:07numbers
15:08if i'm already the smallest negative
15:10number anything negative is going to
15:11push me past the limit and that is is
15:13that underflow
15:14no it's overflow otherwise known as
15:16negative overflow so both of these are
15:18going to be trouble
15:18let's try it my i don't even care what
15:20these what these what's down here
15:22i can't represent it it's not minus two
15:25plus minus two
15:26it's certainly not zero and it's
15:28certainly not one if i just look at
15:29those lower bits so that's not right so
15:31something's wrong with this guy
15:33this guy and this guy okay so far
15:36how about this how about minus one plus
15:38minus one let's try it
15:40look at those two bits what does that
15:42encode that encodes minus two
15:45that's fine so in fact the only guys
15:48that are trouble
15:49are one and one remember one and one so
15:52this guy is trouble
15:53that's overflow and minus two plus
15:56anything negative
15:57which are these two guys so that's the
15:58key remember that okay remember that as
16:00we go forward but everyone else is fine
16:02here we go when can the lowest two bits
16:05of the sum not represent the correct sum
16:07you saw that
16:08when one adds to one or when minus two
16:10adds to anything negative okay we saw
16:12that already
16:13in those cases i circled before here's
16:15the official circle from the animation
16:18is there a pattern this is the fun part
16:20you now stare at this
16:22slide pause the video see if there's a
16:24pattern
16:25if you can see when this happens hint
16:29check the carry bit and the sum force
16:31column bit which means
16:32check this check c2 and check c1
16:36is there anything unique about those
16:38three circles that have that
16:40that's different from every other circle
16:42everything
16:43every other non-circled expression
16:46can you see that pause it and then come
16:48back i'll tell you what it is okay
16:52well if we look at the highest adder
16:55we're looking at this highest adder look
16:56at this guy right here
16:58okay and i look at only these two
17:01characters i'm gonna look at only these
17:02blue guys only the blue guys
17:04what is the pattern when i have and
17:07remember this is i'm going to extend
17:08this by the way to end bits
17:10i'm only have to look at the upper level
17:12adder that's in a way the sign bit it's
17:14not really signed inside magnitude but
17:15it's sine when it's one it's negative
17:17when it's zero
17:18it's uh zero or positive so it actually
17:20works out pretty well to kind of call it
17:21the sign the sign
17:22the signed um the highest adder
17:24representing in a way the sign
17:26of that the output is the sign in a way
17:27that's sum
17:29okay so here we go stay with me stay
17:32with me
17:33if i have no c out or c
17:37in okay when is that the case this means
17:40let's go here when do i have no blue
17:42anywhere
17:43here all these guys no blue anywhere you
17:47agree
17:48no cia or cn there's no overflow there
17:51i see no overflow in those cases that's
17:53totally fine
17:55how about if i have c out and c in
17:59that's this rare case here is a c out
18:02here is a cn there's no overflow i
18:05didn't circle the guys that are red are
18:07the overflows
18:08that's fine
18:12how about c in but no c out what's that
18:16mean
18:16here's a c in but no c
18:19out that's an overflow that's when i try
18:21to add one to one and i can't do it
18:23that's when two positive numbers add
18:24look
18:25a and b are both bigger than zero
18:27overflow okay
18:30how about that's this guy how about
18:34c out but no cn here's my c
18:38out can you see this c out but no cn up
18:41here
18:42you see that point that is they're both
18:44negative two in this case
18:46okay so problem
18:49all right now
18:53what operation is it i have two bits
18:57c out and c in see if you can remember
19:00from all that we've learned so far when
19:03do you have
19:04one but not the other or the other but
19:06not the first one so
19:07c out c n but no c out or
19:10c out but no c in but not both
19:13when it's both when it's both when it's
19:16both it's no overflow so it's one of the
19:20other
19:20but not both that's right xor
19:27that's it that's our overflow two's
19:30complement xor
19:31looks at the upper level adder this is a
19:34this is a a two one bit adder it's a one
19:37bit adder
19:38here's the upper highest bit on on both
19:40the numbers however
19:41you got n bits i don't care how many
19:43what n is n bits
19:44the upper level adder there's a carry
19:47coming in from all the other computation
19:49and there's a carry coming out and only
19:50when one or the other
19:53is high is that two's complement
19:56going to be overflow if it's just
19:59unsigned i only look at c
20:00out only look at the guy coming out and
20:02this is like coming from this way going
20:03that way okay
20:04but in the case of in the case of a
20:07general two's complement number
20:08it is when this c in is high but no c
20:12out or the c out is high but no c n
20:14that's the idea that's it
20:16xor of those two values and that's the
20:19two's complement overflow that's pretty
20:20cool
20:21so now i've covered that we're almost
20:22ready to do our put it together
20:25wrap it up i've got the overflow covered
20:27how do you handle the added subtractive
20:28part that's a little bit do i have to
20:29have a whole box for the adder
20:31hold back for the subtractor can i think
20:32about that so that's the next lecture
20:34we'll close it together
20:35alright we'll see you there

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 17.3 - Combinational Logic Blocks: Adder/Subtractor by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 3,821 words across 599 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.