YouTube2Text

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

by CS 61C Departmental · 2,428 words · 346 segments · language en · Watch on YouTube

Full transcript

  1. 0:00And welcome back. In this last series of
  2. 0:03lectures, we're going to talk about
  3. 0:04combinational logic blocks. Again, this
  4. 0:06is all the umbrella of synchronous
  5. 0:07digital systems. Combinational logical
  6. 0:09blocks said, let's see if we can build
  7. 0:11larger blocks out of combinational logic
  8. 0:14elements that are powerful and really
  9. 0:16useful for our data path. So, we're
  10. 0:18going to start with
  11. 0:20data multiplexers and what they mean.
  12. 0:23Data multiplexer is very much like a
  13. 0:24flag person whose job it is to take N
  14. 0:26lanes of
  15. 0:28I'll draw this here. N lanes of of
  16. 0:31highway from from this area of the 101
  17. 0:35and maybe N lanes of highway from the 5.
  18. 0:38I have to do Southern California
  19. 0:39vernacular. And there's only one bridge
  20. 0:42and all of 101 and Route 5 have to take
  21. 0:44one bridge. And this signal line is
  22. 0:47going to tell you which of those drives.
  23. 0:49When this signal line is zero, then A
  24. 0:52drives the bridge. When this signal line
  25. 0:54is one, then B drives the bridge. And C
  26. 0:56is either one or zero, never both, okay?
  27. 0:58So, that's the idea of a mux.
  28. 1:01So,
  29. 1:02way we can think about an That was an
  30. 1:04N-bit input mux, so the N-channel input
  31. 1:06mux with one different one signal line.
  32. 1:08You can think of this as being N
  33. 1:10instances of a 1-bit wide mux. So, let's
  34. 1:12actually talk about it 1-bit wide mux
  35. 1:14and how to build that and then maybe you
  36. 1:15can learn how to build the larger one I
  37. 1:17showed you in the previous slide of the
  38. 1:18N-bit wide mux.
  39. 1:20So, how many rows in this truth table?
  40. 1:21Okay, pause for a second and see if you
  41. 1:23can figure out the answer and I'll tell
  42. 1:24you in 2 seconds.
  43. 1:27All right, welcome back. Number of rows,
  44. 1:29how many inputs do I have? I'm counting
  45. 1:311
  46. 1:322 3. That's three inputs. Three bits is
  47. 1:35eight rows, okay? There's my eight rows.
  48. 1:39Which basically says the following. It
  49. 1:41says, well, let's look at this. Well,
  50. 1:42I've got when S is zero,
  51. 1:45S is zero, what is C? Let's look at it.
  52. 1:47C is essentially whatever A is. Look at
  53. 1:50that. That's exactly the same as the
  54. 1:52output. When S is one, C is whatever B
  55. 1:55is. Really useful, right? So, see how
  56. 1:57this is the same thing, okay? So, that's
  57. 1:59pretty cool. So, that's a way to think
  58. 2:01about this. But, let's say we don't see
  59. 2:03that that's that that way. Let's try to
  60. 2:04boil this down to the simplest logic
  61. 2:06that will actually make this work. We
  62. 2:07can try to eventually try to make the
  63. 2:09simplest form of logic, fewest gates to
  64. 2:11implement our one-bit wide mux, okay?
  65. 2:13Well,
  66. 2:14canonical form says sum of products,
  67. 2:17okay? So, let's do this.
  68. 2:18Every row that's review, every row
  69. 2:21that's a one,
  70. 2:22we say what term is it that's a one when
  71. 2:25it's not S and A and not B. There's that
  72. 2:29first term. And you do this for all four
  73. 2:30terms to give you four terms. Then you
  74. 2:32put your get your dip your hands into
  75. 2:34your Boolean massage lotion and start
  76. 2:36working that equation. Work that
  77. 2:38equation. All right, here we go. Well, I
  78. 2:41can already pull the S out have it here
  79. 2:43as here's Sorry, the not S. Pull that
  80. 2:45guy out. I Maybe I use my pen to do that
  81. 2:47for me. So, that here what what's the
  82. 2:50law that allows me to go from here this
  83. 2:53term to that term?
  84. 2:55Distribution. I call it reversed it cuz
  85. 2:56you're kind of reverse distributing out
  86. 2:58there, but it's a lot of distribution,
  87. 2:59okay? Same thing here.
  88. 3:02Okay, the same idea here.
  89. 3:04And how about this? How about this inner
  90. 3:05term? How do you go from there to there?
  91. 3:07It's the same thing. I'm just distribute
  92. 3:09reverse distributing out A and B out of
  93. 3:12that term.
  94. 3:14Well, how about this one? What's this
  95. 3:16one? Remember this rule or what's this?
  96. 3:18B or not B? Yeah, the law of
  97. 3:20complementarity, okay? So, that tells me
  98. 3:23that that's one. Now, how about what How
  99. 3:24do you go from here
  100. 3:26to here?
  101. 3:27That's the identity property. That How
  102. 3:29do you remember that? Hopefully you
  103. 3:30remember that from from algebra.
  104. 3:31Yielding this really simple not S A or S
  105. 3:36and B. Now, let's think about that.
  106. 3:38Not S, then you're A.
  107. 3:41Or when S is high, it's B. It's almost
  108. 3:44like you're learning from It's almost
  109. 3:47like you could go straight from here to
  110. 3:49this.
  111. 3:50It's What's What's the output C? Well,
  112. 3:53if not S means S is zero, meaning not S,
  113. 3:55then it's A.
  114. 3:57Or when S is one, it's B. So, actually
  115. 4:01you almost don't need any of this stuff.
  116. 4:03You could go straight from here to here.
  117. 4:05And in fact, as we go to the next one,
  118. 4:08you're kind of you I was kind of talking
  119. 4:09my way through this already. You could
  120. 4:11almost go straight from here really to
  121. 4:12this one, which is when S is zero, it's
  122. 4:15A, S is one, it's B, to here to there.
  123. 4:17So, actually, there is a shortcut really
  124. 4:18this way to that way. Think about that,
  125. 4:21okay? So,
  126. 4:22S is zero, it's A. S is one, it's B. And
  127. 4:25that's the same thing Think about that.
  128. 4:26Think if you don't see that one-to-one
  129. 4:28connection between these two things.
  130. 4:29Take some time to think about that
  131. 4:30before you move on. Kind of neat, right?
  132. 4:32That's kind of cool.
  133. 4:34All right.
  134. 4:35So,
  135. 4:36how do we build a one-bit wide mux? None
  136. 4:38of this is new. This is all review. Not
  137. 4:40S and A or S and B. There it is.
  138. 4:43Piece of cake. Pretty simple. Not S and
  139. 4:45A or S and B. Seen that before. Nothing
  140. 4:48really special there.
  141. 4:50Okay.
  142. 4:51Now, let's uh put a throw a little
  143. 4:52curveball. Put a spit on this ball and
  144. 4:54throw a curveball now.
  145. 4:56All right. How about a four-to-one mux?
  146. 4:59Huh? How do you do a four-to-one mux?
  147. 5:01Let's think about this. Well, now my
  148. 5:02signal line has two bits cuz I've got to
  149. 5:05choose from among four inputs. I didn't
  150. 5:07tell you this is a four-by-one
  151. 5:08four-to-one one-bit mux. Each of these
  152. 5:11guys are one-bit wide.
  153. 5:13Well, what do I have? Well, look at
  154. 5:14this. I've indicated here And do this
  155. 5:16yourself. Indicate, if you ever write a
  156. 5:18mux, what the value of the signal is for
  157. 5:20each of these guys. You know I did that
  158. 5:22in the last one as well. I wrote a zero
  159. 5:23and a one there. Same thing here. So,
  160. 5:24it's unambiguous who wins. So, if S is
  161. 5:26one one, it's going to be D. So, as I as
  162. 5:29S has the numbers value zero through
  163. 5:30three, you know who's going to win. And
  164. 5:32here's a little table here. You know, E,
  165. 5:34the output, is going to be A, B, C, or D
  166. 5:36depending on whether S has a value zero,
  167. 5:38one, two, or three, respectively, okay?
  168. 5:40So, that's nothing special. How do you
  169. 5:42build this one?
  170. 5:44First of all, let's ask ourselves, how
  171. 5:45many rows in the truth table? Pause.
  172. 5:50Thought about it, right? Okay. Well, I
  173. 5:52count six input lines. I count four guys
  174. 5:56there total, and two here. That's six
  175. 5:59lines. Two to the six is
  176. 6:0164. Okay, so I count 64 Boy, really?
  177. 6:05I got a a truth table that's 64 long.
  178. 6:09And it's like six inputs over there and
  179. 6:11then one I mean, really? It's a lot of
  180. 6:13numbers. 64 * seven numbers. It's like
  181. 6:16six input lines and one output at seven
  182. 6:18for everyone 7 * 64. I don't want to do
  183. 6:20that. Sorry. I ain't doing it.
  184. 6:24Is there another way to do it?
  185. 6:26So by the way, here is here I got By the
  186. 6:27way, I'll just give you a freebie. I can
  187. 6:29do that or I can go straight to the
  188. 6:32answer.
  189. 6:34How What's the answer? You saw that
  190. 6:35before. Before it was not S and A or S
  191. 6:39and B. Can you go straight to the answer
  192. 6:41here?
  193. 6:42Yes, and bam. Check this out.
  194. 6:47This is saying
  195. 6:49E the output is not S
  196. 6:53and not not S1 and not S0 and A
  197. 6:57or
  198. 6:59not S1 and S0 and B, etc. Isn't that
  199. 7:04cool? So we kind of the aha that we got
  200. 7:06from the last slide yields us lets us
  201. 7:08save our time rather than having to make
  202. 7:10any truth table and have to do any
  203. 7:12Boolean algebra massaging. Put that
  204. 7:14Boolean algebra lotion away. I'm ready
  205. 7:16to go straight from the idea of a mux to
  206. 7:18its equivalent not necessarily canonical
  207. 7:21form but pretty tight form uh to
  208. 7:23describe a four-to-one one output mux.
  209. 7:26That's pretty cool, okay? So think about
  210. 7:28ways you can do shortcuts rather than
  211. 7:29having to go, "Well, I know how to do
  212. 7:30truth tables cuz I got to slog through
  213. 7:32that one." It's like any game, I just
  214. 7:33got to grind through to get those
  215. 7:34points. Stop grinding. Just go straight
  216. 7:37to the output if you can. There's a
  217. 7:38shortcut, jump right in. IKEA is great.
  218. 7:40They have the special path where you can
  219. 7:41go straight to the register rather than
  220. 7:43have to wind your way away. Do the IKEA,
  221. 7:45you know, trip. Do that kind of
  222. 7:46optimization like that.
  223. 7:48And if you wanted to see this, here's
  224. 7:50the equivalent. Look at this. Here's the
  225. 7:52value Basically, look at this. This is
  226. 7:53the connection straight from here to
  227. 7:54that. So, I can go I can go from here to
  228. 7:57that or I can go here to this to there.
  229. 7:59I can go straight from here to there cuz
  230. 8:01I know how to do this now. I'm I'm
  231. 8:02fluent think about how to go straight to
  232. 8:05the answer. It's pretty cool.
  233. 8:07Now,
  234. 8:09how do I wire this up though?
  235. 8:11I could as I said, I could either think
  236. 8:12about that way to wire it up. I could
  237. 8:14think about, you know, making the the
  238. 8:16the the product of it's the the sum of
  239. 8:17those four terms.
  240. 8:19Or is there a way to think about another
  241. 8:21way to think about how I mean when I
  242. 8:23have I don't know, let's say four
  243. 8:25basketball teams and I have one national
  244. 8:27championship. How do I do that? How do I
  245. 8:30get those four basketball teams, you
  246. 8:32know, to have a final winner? Do I do
  247. 8:34this where they mux in a table? No, they
  248. 8:36play against each other. You have these
  249. 8:38two teams play and then there's a winner
  250. 8:40from the western region and these two
  251. 8:41play and then there's a winner from the
  252. 8:42eastern region. They play in the
  253. 8:43championship game, right? Hopefully Cal
  254. 8:45comes up
  255. 8:46the winner on top. So,
  256. 8:49hierarchically, that's the aha. The aha
  257. 8:52is this recursive or hierarchical way
  258. 8:54that you can wire them. Can you see it?
  259. 8:56Can you already see it?
  260. 8:58Isn't that cool?
  261. 8:59So, you can think of S0 and S1 as wiring
  262. 9:03together
  263. 9:04three
  264. 9:06two three of these two to one muxes. And
  265. 9:10there's my four to one mux. This whole
  266. 9:12By the way, if I draw a box out here,
  267. 9:14look,
  268. 9:15folks, that's my four to one mux. But
  269. 9:17inside of it are three two to one muxes.
  270. 9:20Isn't that cool? I think this is really
  271. 9:21neat. So, then we're going to see this
  272. 9:23There's a lot of ahas here. And the aha
  273. 9:24here is you can make use of other blocks
  274. 9:26rather than going, well, got to make 64
  275. 9:28rows and do some algebra to build it.
  276. 9:30You could do that or you could just wire
  277. 9:32this together and then and obviate the
  278. 9:33need for touching a truth table at all.
  279. 9:35No truth table needed. Just wire them
  280. 9:36like this.
  281. 9:37What's great about this, if you play
  282. 9:39with this, is you've got Here's my S0
  283. 9:42S1. Watch. When S
  284. 9:45Okay, these guys are S0 is 0 0. Who's
  285. 9:47going to win? Let's try. Should be A.
  286. 9:50Well, S0 says, well, that's going to
  287. 9:52come through. A is going to be on that
  288. 9:53line. And this one says C's on that
  289. 9:55line.
  290. 9:57And
  291. 9:58S1 determines who wins of that
  292. 10:00tournament. Well, if it's zero, then A
  293. 10:02gets to win. So, when it's 0 0, it's A.
  294. 10:06Etcetera. Let's just see How about 1 1?
  295. 10:07Let's just do a 1 1 test. Say 1 1 1 1.
  296. 10:10So, that means D wins. So, D's here and
  297. 10:13B wins. That's a different whole
  298. 10:14different tournament, whole different
  299. 10:15final final final game. And then S1 is
  300. 10:18one, so D comes through. So when it's
  301. 10:2111, it's D.
  302. 10:23Isn't that neat? So this is a powerful
  303. 10:25idea that says one, we don't have to go
  304. 10:28through the pedantic slogging through
  305. 10:30grinding away through to make a 64 row
  306. 10:33truth table. I can say, wait, you know
  307. 10:35what? I can actually build this build
  308. 10:37this block out of smaller blocks I know
  309. 10:39about. And as you get more and more
  310. 10:41fluent in digital logic and
  311. 10:43combinational circuits and and and
  312. 10:44Boolean Boolean algebra, you can realize
  313. 10:46you don't have to always go back to the
  314. 10:48back to the beginning to build your
  315. 10:50truth tables and do I mean that was
  316. 10:51crazy. That's crazy. So we like the idea
  317. 10:54of being smart about things sometimes
  318. 10:56and and cascading things in this way, uh
  319. 10:58which is really really nice. Turns out
  320. 11:00that that I mean when A is going to be
  321. 11:01chosen, there's still work done over
  322. 11:03here, but it's hardware. These things
  323. 11:04are always moving always doing it. They
  324. 11:06just don't don't get chosen, you know,
  325. 11:07it's like the the person who doesn't get
  326. 11:09chosen to to to to win. I mean that's
  327. 11:11that's A is going to come through. This
  328. 11:13is a zero and that's a zero. A is going
  329. 11:14to go in. I don't even care. They're
  330. 11:16doing work, but they never get see they
  331. 11:17never see the light of day.
  332. 11:19It's almost like the you know, the
  333. 11:21whoever doesn't win the presidency, did
  334. 11:23all that work and it didn't matter
  335. 11:24anyway. You weren't chosen. Same idea,
  336. 11:26right? A lot of people put work into it
  337. 11:28and then at the end of the day
  338. 11:30nobody won. By the way, vote.
  339. 11:33I don't care what year this is, what
  340. 11:34year this video gets played. Make sure
  341. 11:36you vote. Make sure you put in your
  342. 11:38uh you apply your democratic um
  343. 11:40rights and please make use of that and
  344. 11:42vote. Have your representation known.
  345. 11:44Very important. All right. We'll see you
  346. 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.