YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 17.1 - Combinational Logic Blocks: Data Multiplexors

[CS61C FA20] Lecture 17.1 - Combinational Logic Blocks: Data Multiplexors — Transcript

by CS 61C Departmental · 2,401 words · 373 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

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 is
0:06all the umbrella of
0:07synchronous digital systems combination
0:09logical blocks say
0:10let's see if we can build larger blocks
0:13out of combinational logic elements that
0:15are powerful
0:16and really useful for our data path so
0:18we're going to start with
0:19data multiplexers and what they mean
0:22data multiplexer is very much like a
0:24flag person
0:25whose job it is to take n lanes of you
0:28draw this here
0:29n lanes of uh of highway from from this
0:33area of
0:33the 101 and maybe n lanes of highway
0:36from
0:37the five i have to do southern
0:39california vernacular and there's only
0:41one bridge
0:42and all of 101 and root five have to
0:44take one bridge
0:45and this signal line is going to tell
0:48you
0:48which of those drives when the signal
0:50line is zero then
0:51a drives the bridge when this thing line
0:54is one then
0:55b drives the bridge and c is either one
0:56or zero never both okay so that's the
0:58idea of a mux
1:01so way we can think about it that was an
1:04n-bit input much so the n-channel input
1:06box with one different
1:07one signal line you can think of this as
1:09being n
1:10instances of a one bit wide much so
1:12let's actually talk about it one bit
1:13wide mux and how to build that and then
1:15maybe you can learn how to build
1:16the larger one i showed you in the
1:17previous slide of the end bit wide mucks
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
1:24two seconds all right welcome back
1:28number of rows how many inputs do i have
1:30i'm counting one
1:32two three that's three inputs three bits
1:35is eight rows okay there's my a rows
1:39which basically says the following it
1:41says well let's look at this well i've
1:42got
1:43when s is zero s is zero what is c
1:47let's look at c is essentially whatever
1:49a
1:50is look at that that's exactly the same
1:51as the output when s is one
1:54c is whatever b is really useful right
1:56so
1:57see how this is the same thing okay so
1:59that's pretty cool so that's a way to
2:01think about this but
2:02let's say we don't see that that's that
2:03way let's try to borrow this down to the
2:05simplest logic that'll actually make
2:07this work
2:07we're going to try to eventually try to
2:08make the simplest formal logic fewest
2:10gates to
2:11implement our one bit wide marks okay
2:13well
2:14canonical form says summer products okay
2:17so let's do this
2:18every row that's review every road
2:21that's a one
2:22we say what term is it that's a one when
2:25it's not
2:26s and a and not b there's that first
2:29term and you do this for all four terms
2:31to give you four terms then you put your
2:33get your dip your hands into your
2:34boolean massage
2:35lotion and start working that equation
2:38work that equation
2:39all right here we go well i can already
2:42pull the s
2:42out here here's the sorry the not s pull
2:45that guy out
2:46maybe i'll use my pen to do that for me
2:48so that
2:49here what what's the law that allows me
2:51to go from here
2:53this term to that term distribution i
2:56call reversed it because you're kind of
2:57reverse distributing out there but it's
2:58a lot of distribution okay
3:00same thing here okay same idea here
3:04and how about this how about this inner
3:05term how do you go from there to there
3:07the same thing i'm just just reverse
3:10distributing out
3:11a and b out of that term well how about
3:14this one what's this one remember this
3:17what's this b or not b yeah the law of
3:20complementarity
3:21okay so that tells me that that's one
3:23now how about what how do you go from
3:24here
3:26to here that's the identity property
3:28that because you remember
3:29hopefully you remember that from from
3:30algebra yielding
3:32is really simple not s a or
3:36s and b now let's think about that not s
3:39then you're a or when s is high
3:43it's b it's almost like you're learning
3:45from it's almost like you could go
3:47straight from here
3:49to this it's what's what's the output c
3:52well if not s mean s is 0 meaning not s
3:55then it's a or when s is one
3:59it's b so actually you almost don't need
4:02any of this stuff
4:03you could go straight from here to here
4:05and in fact
4:07as we go to the next one you're kind of
4:08you i was kind of talking my way through
4:10this already
4:10you could almost go straight from here
4:12really to this one which is when s is
4:14zero it's a
4:15s wanted to b to here to there so
4:17actually there is a shortcut really this
4:18way
4:19to that way to think about that okay so
4:22s is zero it's a s is one it's b and
4:25that's the same thing
4:26think about that take if you don't see
4:27that one-to-one connection between these
4:29two things take some time to think about
4:30that before you move on
4:31kind of neat right that's kind of cool
4:34all right
4:35so how do we build one bit wide box none
4:38of this is new this is all review
4:40not sna or s and b there it is piece of
4:43cake
4:43pretty simple not s and a or s
4:47and b seen that before nothing really
4:48special there
4:50okay now let's throw a little curve ball
4:53put a spit on this ball and throw a
4:55curveball down all right
4:57how about a four to one mux huh how do
5:00you do four wheel box let's think about
5:01this well
5:02now my signal line has two bits because
5:05i've got to choose from among four
5:06inputs
5:06i didn't tell you this is a four by one
5:08four to one one bit
5:10mucks each of these guys are one bit
5:12wide
5:13well what do i have well look at this
5:14i've indicated here and do this yourself
5:17indicate if you ever write a mux what
5:19the value of the signal is for each of
5:21these guys you notice i didn't the last
5:22one as well i wrote a zero and one there
5:23same thing here so it's unambiguous
5:25who wins or s is one one it's gonna be d
5:28so as i
5:29as s has the numbers values zero through
5:30three you know who's gonna win
5:32and here's a little table here you know
5:34e the output is gonna be
5:36a b c or d depending on whether s has a
5:37value zero one two or three respectively
5:40okay so that's nothing special how do
5:42you build this one
5:44first of all let's ask ourselves how
5:45many rows of the truth table pause
5:50thought about it right okay well i count
5:53six input lines
5:54i count four guys there total
5:57and two here that's six lines two to the
6:00six is
6:0164. okay so i count 64. boy really
6:05i got a truth table that's 64 long
6:09and it's like six inputs over there and
6:11then one i mean really
6:13that's a lot of numbers 64 times seven
6:15numbers it's like six input lines i want
6:17to output at seven
6:18for everyone 764 i don't want to do that
6:20sorry
6:21i ain't doing it is there another way to
6:25do it
6:26by the way here is here okay by the way
6:28i'll just give you a
6:29freebie i could do that or i could go
6:31straight to
6:32the answer what's the answer you saw
6:35that before before it was
6:37not s and a or s and b can you go
6:40straight to the answer here
6:42yes and bam check this out
6:47this is saying e the output is
6:51not s and not
6:54not s1 and not s 0 and a
6:57or not s 1 and s 0
7:01and b etc isn't that cool
7:04so kind of the aha we got from the last
7:06slide yields us
7:08lets us save our time rather than having
7:10to make any truth table and had to do
7:12any bullying algebra massaging put that
7:14boolean algebra lotion way
7:15i'm ready to go straight from the idea
7:17of a mux to its
7:19equivalent not necessarily canonical
7:21form but pretty tight form
7:23uh to describe a four to one one output
7:25mux
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 truth
7:30tables because i got to slog through
7:32that one
7:32it's like any game i just got to grind
7:34through to get those points stop
7:35grinding just go straight to the output
7:37if you can't there's a shortcut
7:38jump right here ikea is great they have
7:40this special path where you can go
7:42straight to the register rather than
7:43have to wind your valve away
7:44do the ikea you know trip do the kind of
7:46optimization like that
7:48and if you wanted to see this here's the
7:50equivalent look at this here's about
7:52basically look at this this is the
7:53connection straight from here to that so
7:55i can go here i can go from here to that
7:58or i can go here to this
7:59there i can go straight from here to
8:00there because i know how to do this now
8:02i'm fluent now enough with this so
8:03think about how to go straight to the
8:05answer it's pretty cool
8:07now how 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
8:14you know making the the the product of
8:17the sum of those four terms
8:19or is there a way to think about another
8:21way to think about
8:23how i mean when i have i don't know
8:24let's say four basketball teams and i
8:26have one national championship
8:28how do i do that how do i get those four
8:30basketball teams
8:32you know to have a final winner do i do
8:34this were the mucks and a table
8:36no they play against each other you have
8:38these two teams play and there's a
8:39winner from the western region
8:41and these two play and then there's a
8:42winner from the eastern region they play
8:43in the championship game right
8:45hopefully cal comes up the winner on top
8:48so
8:49hierarchically that's the aha the aha is
8:52this recursive or hierarchical way you
8:54could wire them can you see it can you
8:56already see it
8:58isn't that cool so you can think of
9:01s0 and s1 as wiring together
9:04three two three of these
9:08two to one muxes and there's my four to
9:11one mux this whole by the way
9:12if i draw a box out here look folks
9:15that's my four to one mux
9:17but inside of it are three two to one
9:19muxes isn't that cool i think this is
9:21really neat so then we're going to see
9:22this there's a lot of ahas here
9:24and the heart here is you can make use
9:25of other blocks rather than going well
9:27got to make 64 rows
9:29and do some algebra to build you could
9:30do that or you could just wire this
9:32together and
9:33obviate the need for touching a truth
9:34table at all no truth table just wire
9:36like this
9:37what's great about this if you play with
9:39this is you've got
9:41here's my s0 s1 watch when s
9:45these guys are s 0 is 0 0 who's going to
9:47win that's right
9:48should be a well s0 says well that's
9:51going to come through a
9:52is going to be on that line and this one
9:54says c is on that line
9:57and s1 determines who wins of that
10:00tournament
10:01well if that's zero then a gets to win
10:03so when it's zero
10:04zero it's a etc let's just see how about
10:07one minute let's just do a one one test
10:09say one one one one so that means d wins
10:12so d is here and b wins that's a
10:14different whole different tournament
10:15hold it from final
10:16final final game and then s1 is one so
10:19d comes through so when it's one one
10:22it's d
10:23isn't that neat so this is a powerful
10:25idea that says
10:27one we don't have to go through the
10:29pedantic slogging through grinding our
10:31way through to make a 64
10:33row truth table i can say wait you know
10:35i could actually build this
10:37build this block out of smaller blocks i
10:39know about and as you get
10:41more and more fluent in digital logic
10:43and combinational circuits and
10:44and boolean algebra you can realize you
10:46don't have to always go back to
10:48the back to the beginning to build your
10:50truth tables and do i mean that was
10:51crazy that's crazy so
10:53we like the idea of being smart about
10:55things sometimes
10:56and and cascading things in this way
10:58which is really really nice turns out
11:00that i mean
11:00when a is going to be chosen there's
11:02still work done over here but it's
11:03hardware these things are always moving
11:05always doing it they just don't don't
11:06get chosen you know it's like the uh
11:08the person who doesn't get chosen to to
11:10to win i mean that's
11:12a is going to come through this is zero
11:13and that's a zero a is going to go in
11:15i don't even care they're doing work but
11:17they never get c they never see the
11:18light of day
11:19it's almost like the you know the
11:21whoever doesn't win the presidency did
11:23all that work and didn't matter anyway
11:24you weren't chosen same idea right a lot
11:26of people
11:27put work into it and then at the end of
11:29the day
11:30nobody won by the way vote i don't care
11:33what year this is what year this video
11:35gets played make sure you vote make sure
11:36you put in your
11:37uh you apply your democratic rights
11:41um please make use of that and vote have
11:43your representation known
11:44very important all right we'll see the
11:45next 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,401 words across 373 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.