[CS61C FA20] Lecture 16.1 - Combinational Logic: Truth Tables — Transcript

Full transcript

1. 0:00and welcome back now we're at our third
2. 0:02series
3. 0:03of this sds series four lecture series
4. 0:05where we talked about
5. 0:06combination logic so far we've seen
6. 0:08introduction to synchronous digital
7. 0:10systems
8. 0:11state registers how those work timing
9. 0:13that's a really important piece of it
10. 0:14now we're part of
11. 0:15now we're kind of at the don't worry
12. 0:17about the analog element of it let's
13. 0:18just talk about the logic part of it
14. 0:20this is a little bit more fun a little
15. 0:21bit more digital
16. 0:22and thinking about the analog real you
17. 0:24know the realities of the analog world
18. 0:26are not as much
19. 0:26as not as present here in the
20. 0:27combinational logic world so let's talk
21. 0:29about combinational logic and jump on it
22. 0:31we start with truth tables and maybe
23. 0:33you've seen truth tables before
24. 0:34maybe you haven't um in terms of that's
25. 0:38funny i learned truth tables
26. 0:39how to do them i think i was in
27. 0:43fifth grade we were doing basic truth
28. 0:44tables i think i saw them again in
29. 0:46eighth and ninth grade
30. 0:47this is just me i went to my school
31. 0:48different places across the world from
32. 0:50from here
33. 0:50but hopefully you've seen this before if
34. 0:52not i'll try to go slowly with this
35. 0:54here's a box here's a truth tables are
36. 0:57on combinational logic if you remember
37. 0:58from a lecture or two ago
38. 1:00combinational logic circuits are those
39. 1:01that have no state and no memory
40. 1:03in some set of inputs the output will
41. 1:05always be the same if i go back and
42. 1:07put them back again it'll still be the
43. 1:09same there's no memory to these things
44. 1:10this is just pure combinational logic
45. 1:12pure functions if you will in the 621a
46. 1:14and cs10 sense
47. 1:15so this is a four input one output box
48. 1:18um i've got a y here on the right
49. 1:21you're going to see these this is kind
50. 1:24of how we typically draw this and back
51. 1:26in the days when you're doing truth
52. 1:27tables you might have drawn t
53. 1:28and f's stop doing that you want to use
54. 1:30zeros and ones and in fact
55. 1:32as you're counting them you want to
56. 1:34basically count up from
57. 1:36like a nibble his four bits count them
58. 1:38up zero all zeroes to all ones you don't
59. 1:40want to put like i've seen people draw
60. 1:42these
61. 1:42where they write t and f's first or t
62. 1:44nets look too close together
63. 1:45and also they write all t's first no the
64. 1:47first row should be all zeros always
65. 1:49and the last row should be all ones
66. 1:51however many however many bits you have
67. 1:52okay
68. 1:54so this is a box i can buy this box at
69. 1:57fry's electronics
70. 1:58and this is whatever that box does for
71. 2:01all zeros what does that box do for all
72. 2:02zeros and a one
73. 2:04so what's actually interesting about
74. 2:05this i'm going to ask you a question
75. 2:07how many of these boxes does fry's have
76. 2:09to sell
77. 2:10that's a fun question think about how
78. 2:12many different
79. 2:13of these boxes that's a stock i mean if
80. 2:16they have to have one each
81. 2:17for all the different ones that have a
82. 2:19different pattern here
83. 2:21i'll give you example the and gate which
84. 2:23is true only when all of them are ones
85. 2:25has a one down here and all a big old
86. 2:28zero for everybody else
87. 2:29that's one of the boxes they said they
88. 2:31have an and okay
89. 2:33so how many other devices do they have
90. 2:35to sell if they want to cover
91. 2:36every single possible case i give you
92. 2:39think about it
93. 2:40and i'll give you an answer in a second
94. 2:43and welcome back here's how here's how
95. 2:46many
96. 2:47it's kind of cool turn your head
97. 2:49sideways so you're looking at this
98. 2:51number with your
99. 2:52left side here and your right side there
100. 2:55how many different bits do you have
101. 2:56there i count 16. two to the four is 16.
102. 3:00each possible bit pattern is a different
103. 3:04box
104. 3:05how many different bits is that we call
105. 3:07that the signature of the box
106. 3:09how many bit patterns are there with 16
107. 3:10bits 2 to the 16.
108. 3:13that's 64 000. so you have to have
109. 3:1764 kibi
110. 3:20this is mean 64k different f boxes if
111. 3:24you're going to have this
112. 3:25for every one if you have if fry's is
113. 3:27going to stock every possible
114. 3:28combination is that kind of cool
115. 3:3064 000 ish that's a lot
116. 3:33okay so that's pretty cool what do you
117. 3:36think about that
118. 3:37here's another two-table example this is
119. 3:39going to be one
120. 3:41if one but not both of a and b are one
121. 3:44by the way
122. 3:44i love this i love this example this
123. 3:47example if i said
124. 3:48um halloween is coming up where the fall
125. 3:51here so halloween is coming up
126. 3:52if a kid comes to your door and they say
127. 3:55trick or treat
128. 3:57they mean this table this table is for
129. 4:00trick-or-treat this is a halloween table
130. 4:02why it says trick or treat
131. 4:06trick or treat but not both
132. 4:09here's here's trick or treat
133. 4:13but not both okay so
134. 4:17they mean it's a one if one or the other
135. 4:19is true but not both
136. 4:20what it means in halloween if you know
137. 4:22if you give the person a treat you
138. 4:23expect them not to toilet paper your
139. 4:25house
140. 4:25it's the idea is it's a contract right
141. 4:27if i give you the treat you're not going
142. 4:29to do a trick on me
143. 4:30so this it means this table this is the
144. 4:32halloween table so remember
145. 4:34see this link always remember this table
146. 4:36as the halloween table is an example of
147. 4:37that pretty cool right
148. 4:39by the way i want to show you another
149. 4:41way to think about this table no one
150. 4:43this is rarely taught it's like pro tip
151. 4:46if you think about it when a is 0
152. 4:49how does b relate to the output
153. 4:52is exactly the same when a is one
154. 4:56how does b relate to the output it flips
155. 4:59it
156. 5:00it's like not b so in fact i can
157. 5:03summarize this table by saying
158. 5:04this is a two element two row table when
159. 5:07a is zero
160. 5:08output is y is just b what output is one
161. 5:11output of y is
162. 5:12not b it's a kind of tighter way of
163. 5:14thinking about the table i want you to
164. 5:15get used to that and comfortable with
165. 5:16that
166. 5:16if i change this to any pattern of four
167. 5:18things by the way how many
168. 5:20i get to that how many of these would
169. 5:22fry's have to have for every one of
170. 5:24those
171. 5:24i should be able to kind of reduce this
172. 5:26into this kind of table when a is zero
173. 5:28what is it when a is one what is it okay
174. 5:31so
175. 5:31that's kind of neat by the way if these
176. 5:33were both zero i would have written a
177. 5:34zero here
178. 5:35these are both one i would have written
179. 5:37a one here if it's zero one i write b
180. 5:39here if it's one zero i write not b so
181. 5:41that's how you kind of compress this
182. 5:42table to that way
183. 5:43kind of neat right all right
184. 5:47here's an example for the truth table of
185. 5:48a two bit adder
186. 5:50okay we've seen this before we used
187. 5:51adders before in our last series of
188. 5:53lectures
189. 5:53this again is a two bit adder where the
190. 5:55output now i was saying before while the
191. 5:57two matter without overflow
192. 5:59because sometimes you put some numbers
193. 6:00in and it's bigger than that right n and
194. 6:02n
195. 6:02and output saying well somehow we don't
196. 6:03worry about that at this early stage
197. 6:05whether it's overflow
198. 6:06but in fact if i had two bit adder i
199. 6:08mean you can think about this
200. 6:10the biggest number of this guy can be
201. 6:11one one that's three the biggest number
202. 6:13this guy can be is one one three plus
203. 6:14three is six
204. 6:15that's one one zero i kind of knew that
205. 6:17because i'm doubling this
206. 6:19and you double it you just add a zero
207. 6:21there so there's no way to think about
208. 6:22binary numbers in that way so i have to
209. 6:23have three can be able to handle all the
210. 6:25cases
211. 6:26c is really is the fun thing c is really
212. 6:29should be three bits
213. 6:30and by the way i've been shocked before
214. 6:32this slash tells you
215. 6:34how many bits wide that line is if you
216. 6:36haven't talked about it before that's
217. 6:37the way to think about this
218. 6:39so this is a two bit adder this is all
219. 6:41the logic of a two bit adder
220. 6:43again i think of the grouping of a
221. 6:44really being a one and a zero
222. 6:46here's b really meaning b1 and b0 and
223. 6:49here's c being c2 through c0
224. 6:52so let's ask a question how many rows
225. 6:55does this have
226. 6:57well just like before the number of
227. 7:00inputs
228. 7:00is four bits of inputs therefore that's
229. 7:03a nibble input
230. 7:04therefore i have to handle all the cases
231. 7:06of 16 different cases for that
232. 7:08okay well that's nice i can do that if
233. 7:11you need me to build that i could
234. 7:12probably
235. 7:13build that that's not that's not a
236. 7:14problem except that when i extend that
237. 7:16to 32 bits
238. 7:18and now i've got two 32-bit inputs and i
239. 7:21have and this is an unsigned adder we
240. 7:22have to worry about anything other than
241. 7:2410 values and i've got this guy maybe
242. 7:26this is 30 you know maybe this is 32
243. 7:28and this sorry 32 and 32 and this might
244. 7:32be 33 again
245. 7:33what's the biggest output here the
246. 7:35biggest output is there this better be
247. 7:3733 bits
248. 7:37because i've got all ones with a zero
249. 7:39because i've doubled all ones all ones
250. 7:41are zero
251. 7:42okay well you might ask the question
252. 7:45again
253. 7:46how many rows do i have anybody figure
254. 7:49that out
255. 7:50was that the right way to do this is the
256. 7:52right way to build a 32-bit adder by
257. 7:53looking at the truth table for it that's
258. 7:55i'm kind of
259. 7:55revealing that revealed that that might
260. 7:57not be the right way to do it well how
261. 7:58wide is this
262. 7:59that's an input 32 bits that's simple 32
263. 8:01bits well before it was the total number
264. 8:03of bits is my input that's how many rows
265. 8:05i have two to that
266. 8:07i i counted the 64.
267. 8:10that's a lot at 16 eggs be rows
268. 8:15too many rows way too many rows
269. 8:18so this is not the way to do this so
270. 8:20let's let's actually take a step back
271. 8:22at some point we'll talk about how to do
272. 8:23that another way i'll give another
273. 8:25example
274. 8:26here is a three input majority circuit
275. 8:29i say majority it's almost like three
276. 8:31people are all deciding should we
277. 8:32should we go that way or that way that's
278. 8:34all one two three one two three
279. 8:36shoot and the majority wins so for all
280. 8:38zeros let's do it let's see
281. 8:40let's see if this actually adheres to
282. 8:41that they're all zeros
283. 8:43majority wins zero if there's two zeros
284. 8:46and a one
285. 8:46zero wins again two zeros and a one zero
286. 8:49wins
287. 8:50two zeros and a one zero wins every
288. 8:53other case there's more ones than zeros
289. 8:55two ones two ones two ones three ones
290. 8:59and then one wins okay
291. 9:00we call this the majority circuit that's
292. 9:02kind of neat this is like breaking a tie
293. 9:04you know picking a tie for that
294. 9:05so that's kind of fun so that's the i
295. 9:09gave you a couple of examples of truth
296. 9:10table
297. 9:11and uh that's the basics of this
298. 9:14sometimes we don't use the truth table
299. 9:15to build
300. 9:16circuits like for the adder we might
301. 9:17have to find a better way to do that
302. 9:18we'll actually talk about that
303. 9:19later but this is the way to think about
304. 9:21this you want to be writing zeros to
305. 9:23ones
306. 9:23you want to be counting from all zeros
307. 9:25to all ones in a way don't use t's and
308. 9:27f's
309. 9:27and that's it thank you so much we'll
310. 9:29see you at the next lecture