[CS61C FA20] Lecture 17.1 - Combinational Logic Blocks: Data Multiplexors — Transcript
Full transcript
- 0:00And welcome back. In this last series of
- 0:03lectures, we're going to talk about
- 0:04combinational logic blocks. Again, this
- 0:06is all the umbrella of synchronous
- 0:07digital systems. Combinational logical
- 0:09blocks said, let's see if we can build
- 0:11larger blocks out of combinational logic
- 0:14elements that are powerful and really
- 0:16useful for our data path. So, we're
- 0:18going to start with
- 0:20data multiplexers and what they mean.
- 0:23Data multiplexer is very much like a
- 0:24flag person whose job it is to take N
- 0:26lanes of
- 0:28I'll draw this here. N lanes of of
- 0:31highway from from this area of the 101
- 0:35and maybe N lanes of highway from the 5.
- 0:38I have to do Southern California
- 0:39vernacular. And there's only one bridge
- 0:42and all of 101 and Route 5 have to take
- 0:44one bridge. And this signal line is
- 0:47going to tell you which of those drives.
- 0:49When this signal line is zero, then A
- 0:52drives the bridge. When this signal line
- 0:54is one, then B drives the bridge. And C
- 0:56is either one or zero, never both, okay?
- 0:58So, that's the idea of a mux.
- 1:01So,
- 1:02way we can think about an That was an
- 1:04N-bit input mux, so the N-channel input
- 1:06mux with one different one signal line.
- 1:08You can think of this as being N
- 1:10instances of a 1-bit wide mux. So, let's
- 1:12actually talk about it 1-bit wide mux
- 1:14and how to build that and then maybe you
- 1:15can learn how to build the larger one I
- 1:17showed you in the previous slide of the
- 1:18N-bit wide mux.
- 1:20So, how many rows in this truth table?
- 1:21Okay, pause for a second and see if you
- 1:23can figure out the answer and I'll tell
- 1:24you in 2 seconds.
- 1:27All right, welcome back. Number of rows,
- 1:29how many inputs do I have? I'm counting
- 1:311
- 1:322 3. That's three inputs. Three bits is
- 1:35eight rows, okay? There's my eight rows.
- 1:39Which basically says the following. It
- 1:41says, well, let's look at this. Well,
- 1:42I've got when S is zero,
- 1:45S is zero, what is C? Let's look at it.
- 1:47C is essentially whatever A is. Look at
- 1:50that. That's exactly the same as the
- 1:52output. When S is one, C is whatever B
- 1:55is. Really useful, right? So, see how
- 1:57this is the same thing, okay? So, that's
- 1:59pretty cool. So, that's a way to think
- 2:01about this. But, let's say we don't see
- 2:03that that's that that way. Let's try to
- 2:04boil this down to the simplest logic
- 2:06that will actually make this work. We
- 2:07can try to eventually try to make the
- 2:09simplest form of logic, fewest gates to
- 2:11implement our one-bit wide mux, okay?
- 2:13Well,
- 2:14canonical form says sum of products,
- 2:17okay? So, let's do this.
- 2:18Every row that's review, every row
- 2:21that's a one,
- 2:22we say what term is it that's a one when
- 2:25it's not S and A and not B. There's that
- 2:29first term. And you do this for all four
- 2:30terms to give you four terms. Then you
- 2:32put your get your dip your hands into
- 2:34your Boolean massage lotion and start
- 2:36working that equation. Work that
- 2:38equation. All right, here we go. Well, I
- 2:41can already pull the S out have it here
- 2:43as here's Sorry, the not S. Pull that
- 2:45guy out. I Maybe I use my pen to do that
- 2:47for me. So, that here what what's the
- 2:50law that allows me to go from here this
- 2:53term to that term?
- 2:55Distribution. I call it reversed it cuz
- 2:56you're kind of reverse distributing out
- 2:58there, but it's a lot of distribution,
- 2:59okay? Same thing here.
- 3:02Okay, the same idea here.
- 3:04And how about this? How about this inner
- 3:05term? How do you go from there to there?
- 3:07It's the same thing. I'm just distribute
- 3:09reverse distributing out A and B out of
- 3:12that term.
- 3:14Well, how about this one? What's this
- 3:16one? Remember this rule or what's this?
- 3:18B or not B? Yeah, the law of
- 3:20complementarity, okay? So, that tells me
- 3:23that that's one. Now, how about what How
- 3:24do you go from here
- 3:26to here?
- 3:27That's the identity property. That How
- 3:29do you remember that? Hopefully you
- 3:30remember that from from algebra.
- 3:31Yielding this really simple not S A or S
- 3:36and B. Now, let's think about that.
- 3:38Not S, then you're A.
- 3:41Or when S is high, it's B. It's almost
- 3:44like you're learning from It's almost
- 3:47like you could go straight from here to
- 3:49this.
- 3:50It's What's What's the output C? Well,
- 3:53if not S means S is zero, meaning not S,
- 3:55then it's A.
- 3:57Or when S is one, it's B. So, actually
- 4:01you almost don't need any of this stuff.
- 4:03You could go straight from here to here.
- 4:05And in fact, as we go to the next one,
- 4:08you're kind of you I was kind of talking
- 4:09my way through this already. You could
- 4:11almost go straight from here really to
- 4:12this one, which is when S is zero, it's
- 4:15A, S is one, it's B, to here to there.
- 4:17So, actually, there is a shortcut really
- 4:18this way to that way. Think about that,
- 4:21okay? So,
- 4:22S is zero, it's A. S is one, it's B. And
- 4:25that's the same thing Think about that.
- 4:26Think if you don't see that one-to-one
- 4:28connection between these two things.
- 4:29Take some time to think about that
- 4:30before you move on. Kind of neat, right?
- 4:32That's kind of cool.
- 4:34All right.
- 4:35So,
- 4:36how do we build a one-bit wide mux? None
- 4:38of this is new. This is all review. Not
- 4:40S and A or S and B. There it is.
- 4:43Piece of cake. Pretty simple. Not S and
- 4:45A or S and B. Seen that before. Nothing
- 4:48really special there.
- 4:50Okay.
- 4:51Now, let's uh put a throw a little
- 4:52curveball. Put a spit on this ball and
- 4:54throw a curveball now.
- 4:56All right. How about a four-to-one mux?
- 4:59Huh? How do you do a four-to-one mux?
- 5:01Let's think about this. Well, now my
- 5:02signal line has two bits cuz I've got to
- 5:05choose from among four inputs. I didn't
- 5:07tell you this is a four-by-one
- 5:08four-to-one one-bit mux. Each of these
- 5:11guys are one-bit wide.
- 5:13Well, what do I have? Well, look at
- 5:14this. I've indicated here And do this
- 5:16yourself. Indicate, if you ever write a
- 5:18mux, what the value of the signal is for
- 5:20each of these guys. You know I did that
- 5:22in the last one as well. I wrote a zero
- 5:23and a one there. Same thing here. So,
- 5:24it's unambiguous who wins. So, if S is
- 5:26one one, it's going to be D. So, as I as
- 5:29S has the numbers value zero through
- 5:30three, you know who's going to win. And
- 5:32here's a little table here. You know, E,
- 5:34the output, is going to be A, B, C, or D
- 5:36depending on whether S has a value zero,
- 5:38one, two, or three, respectively, okay?
- 5:40So, that's nothing special. How do you
- 5:42build this one?
- 5:44First of all, let's ask ourselves, how
- 5:45many rows in the truth table? Pause.
- 5:50Thought about it, right? Okay. Well, I
- 5:52count six input lines. I count four guys
- 5:56there total, and two here. That's six
- 5:59lines. Two to the six is
- 6:0164. Okay, so I count 64 Boy, really?
- 6:05I got a a truth table that's 64 long.
- 6:09And it's like six inputs over there and
- 6:11then one I mean, really? It's a lot of
- 6:13numbers. 64 * seven numbers. It's like
- 6:16six input lines and one output at seven
- 6:18for everyone 7 * 64. I don't want to do
- 6:20that. Sorry. I ain't doing it.
- 6:24Is there another way to do it?
- 6:26So by the way, here is here I got By the
- 6:27way, I'll just give you a freebie. I can
- 6:29do that or I can go straight to the
- 6:32answer.
- 6:34How What's the answer? You saw that
- 6:35before. Before it was not S and A or S
- 6:39and B. Can you go straight to the answer
- 6:41here?
- 6:42Yes, and bam. Check this out.
- 6:47This is saying
- 6:49E the output is not S
- 6:53and not not S1 and not S0 and A
- 6:57or
- 6:59not S1 and S0 and B, etc. Isn't that
- 7:04cool? So we kind of the aha that we got
- 7:06from the last slide yields us lets us
- 7:08save our time rather than having to make
- 7:10any truth table and have to do any
- 7:12Boolean algebra massaging. Put that
- 7:14Boolean algebra lotion away. I'm ready
- 7:16to go straight from the idea of a mux to
- 7:18its equivalent not necessarily canonical
- 7:21form but pretty tight form uh to
- 7:23describe a four-to-one one output mux.
- 7:26That's pretty cool, okay? So think about
- 7:28ways you can do shortcuts rather than
- 7:29having to go, "Well, I know how to do
- 7:30truth tables cuz I got to slog through
- 7:32that one." It's like any game, I just
- 7:33got to grind through to get those
- 7:34points. Stop grinding. Just go straight
- 7:37to the output if you can. There's a
- 7:38shortcut, jump right in. IKEA is great.
- 7:40They have the special path where you can
- 7:41go straight to the register rather than
- 7:43have to wind your way away. Do the IKEA,
- 7:45you know, trip. Do that kind of
- 7:46optimization like that.
- 7:48And if you wanted to see this, here's
- 7:50the equivalent. Look at this. Here's the
- 7:52value Basically, look at this. This is
- 7:53the connection straight from here to
- 7:54that. So, I can go I can go from here to
- 7:57that or I can go here to this to there.
- 7:59I can go straight from here to there cuz
- 8:01I know how to do this now. I'm I'm
- 8:02fluent think about how to go straight to
- 8:05the answer. It's pretty cool.
- 8:07Now,
- 8:09how do I wire this up though?
- 8:11I could as I said, I could either think
- 8:12about that way to wire it up. I could
- 8:14think about, you know, making the the
- 8:16the the product of it's the the sum of
- 8:17those four terms.
- 8:19Or is there a way to think about another
- 8:21way to think about how I mean when I
- 8:23have I don't know, let's say four
- 8:25basketball teams and I have one national
- 8:27championship. How do I do that? How do I
- 8:30get those four basketball teams, you
- 8:32know, to have a final winner? Do I do
- 8:34this where they mux in a table? No, they
- 8:36play against each other. You have these
- 8:38two teams play and then there's a winner
- 8:40from the western region and these two
- 8:41play and then there's a winner from the
- 8:42eastern region. They play in the
- 8:43championship game, right? Hopefully Cal
- 8:45comes up
- 8:46the winner on top. So,
- 8:49hierarchically, that's the aha. The aha
- 8:52is this recursive or hierarchical way
- 8:54that you can wire them. Can you see it?
- 8:56Can you already see it?
- 8:58Isn't that cool?
- 8:59So, you can think of S0 and S1 as wiring
- 9:03together
- 9:04three
- 9:06two three of these two to one muxes. And
- 9:10there's my four to one mux. This whole
- 9:12By the way, if I draw a box out here,
- 9:14look,
- 9:15folks, that's my four to one mux. But
- 9:17inside of it are three two to one muxes.
- 9:20Isn't that cool? I think this is really
- 9:21neat. So, then we're going to see this
- 9:23There's a lot of ahas here. And the aha
- 9:24here is you can make use of other blocks
- 9:26rather than going, well, got to make 64
- 9:28rows and do some algebra to build it.
- 9:30You could do that or you could just wire
- 9:32this together and then and obviate the
- 9:33need for touching a truth table at all.
- 9:35No truth table needed. Just wire them
- 9:36like this.
- 9:37What's great about this, if you play
- 9:39with this, is you've got Here's my S0
- 9:42S1. Watch. When S
- 9:45Okay, these guys are S0 is 0 0. Who's
- 9:47going to win? Let's try. Should be A.
- 9:50Well, S0 says, well, that's going to
- 9:52come through. A is going to be on that
- 9:53line. And this one says C's on that
- 9:55line.
- 9:57And
- 9:58S1 determines who wins of that
- 10:00tournament. Well, if it's zero, then A
- 10:02gets to win. So, when it's 0 0, it's A.
- 10:06Etcetera. Let's just see How about 1 1?
- 10:07Let's just do a 1 1 test. Say 1 1 1 1.
- 10:10So, that means D wins. So, D's here and
- 10:13B wins. That's a different whole
- 10:14different tournament, whole different
- 10:15final final final game. And then S1 is
- 10:18one, so D comes through. So when it's
- 10:2111, it's D.
- 10:23Isn't that neat? So this is a powerful
- 10:25idea that says one, we don't have to go
- 10:28through the pedantic slogging through
- 10:30grinding away through to make a 64 row
- 10:33truth table. I can say, wait, you know
- 10:35what? I can actually build this build
- 10:37this block out of smaller blocks I know
- 10:39about. And as you get more and more
- 10:41fluent in digital logic and
- 10:43combinational circuits and and and
- 10:44Boolean Boolean algebra, you can realize
- 10:46you don't have to always go back to the
- 10:48back to the beginning to build your
- 10:50truth tables and do I mean that was
- 10:51crazy. That's crazy. So we like the idea
- 10:54of being smart about things sometimes
- 10:56and and cascading things in this way, uh
- 10:58which is really really nice. Turns out
- 11:00that that I mean when A is going to be
- 11:01chosen, there's still work done over
- 11:03here, but it's hardware. These things
- 11:04are always moving always doing it. They
- 11:06just don't don't get chosen, you know,
- 11:07it's like the the person who doesn't get
- 11:09chosen to to to to win. I mean that's
- 11:11that's A is going to come through. This
- 11:13is a zero and that's a zero. A is going
- 11:14to go in. I don't even care. They're
- 11:16doing work, but they never get see they
- 11:17never see the light of day.
- 11:19It's almost like the you know, the
- 11:21whoever doesn't win the presidency, did
- 11:23all that work and it didn't matter
- 11:24anyway. You weren't chosen. Same idea,
- 11:26right? A lot of people put work into it
- 11:28and then at the end of the day
- 11:30nobody won. By the way, vote.
- 11:33I don't care what year this is, what
- 11:34year this video gets played. Make sure
- 11:36you vote. Make sure you put in your
- 11:38uh you apply your democratic um
- 11:40rights and please make use of that and
- 11:42vote. Have your representation known.
- 11:44Very important. All right. We'll see you
- 11:45at the next lecture.
About this transcript
This page contains the full transcript of [CS61C FA20] Lecture 17.1 - Combinational Logic Blocks: Data Multiplexors by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 2,428 words across 346 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 choose a caption track available on the video.
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, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.