[CS61C FA20] Lecture 16.2 - Combinational Logic: Logic Gates — Transcript

Full transcript

1. 0:00and welcome back we're still in the
2. 0:02lecture series on combinational logic
3. 0:04let's talk about
4. 0:05logic gates so here are basic three
5. 0:09logic gates that we're going to use as
6. 0:10building blocks for larger circuits
7. 0:13the first you've seen before probably
8. 0:15you're releasing the truth table for it
9. 0:17and this truth table says it's an and
10. 0:19gate it's an and gate
11. 0:20this is the truth table for and by the
12. 0:22way remember you're always going to draw
13. 0:24this
14. 0:24as the counting from however many bits
15. 0:26of input just from all zeros to all ones
16. 0:28so make sure you do that when you do
17. 0:29throw these
18. 0:30and and if that's the case you're always
19. 0:32going to see and have this signature
20. 0:34zero zero zero one or in general for
21. 0:36even inputs all zeros and only one one
22. 0:38at the end which is
23. 0:39all of them have to be true this is the
24. 0:41block diagram we use for that
25. 0:43so as we look at this we'll say it and
26. 0:45and that has a
27. 0:46it's like a half circle in a way so
28. 0:48here's a straight line with the half
29. 0:49circle there for my and
30. 0:51or is similar to the logical or you
31. 0:54probably have you've seen this before in
32. 0:55a lot you've done this in cs 10 or
33. 0:57b you've done this bitwise does not bid
34. 0:59wise this is a
35. 1:00single bit this is this would be this
36. 1:02would be double and okay that's my and
37. 1:04this is or we're talking about a single
38. 1:06bit we're talking about not
39. 1:07bitwise all right or says i'm a one
40. 1:11if and only if uh
41. 1:14at least one of them are a one so this
42. 1:16is all of them this is
43. 1:17any of them okay this is the any block
44. 1:19any of them any of these guys is a one
45. 1:22then i'm a one here okay
46. 1:25link and the shape looks like this kind
47. 1:28of a curve here and then a curve there
48. 1:30and then a curve there and then be
49. 1:31really pretty
50. 1:33a not gate is drawn like a triangle with
51. 1:35a circle at the end of it and that
52. 1:36basically does the invert
53. 1:38of that okay the inverse if it's a if a
54. 1:41is high then its output is low a is low
55. 1:43output is high so that's the block for
56. 1:44this
57. 1:46now when i'm thinking about an versus or
58. 1:48those two shapes are brand new and
59. 1:49you're going to forget them
60. 1:50so here's again ann's truth table here's
61. 1:52the and's gate symbol
62. 1:54how do we remember them i want to give
63. 1:56you a way to never forget that so turn
64. 1:58your memory on high resolution
65. 2:00to never forget this
66. 2:02[Music]
67. 2:03isn't that cool a and d has the shape d
68. 2:07and nobody taught this i don't know i
69. 2:08came up with this i know when you taught
70. 2:10this to me but i'm not sure if i ever
71. 2:11came up with this but this is a way to
72. 2:12a mnemonic for you this d looks exactly
73. 2:15like the shape
74. 2:16if you use the right font of the gate
75. 2:18symbol so please remember that from now
76. 2:20on never get and or
77. 2:21confused because or has nothing
78. 2:23equivalent but and has this d
79. 2:25that looks exactly like the and symbol
80. 2:27again back to the logic gates
81. 2:29we talked about before or i should have
82. 2:32mentioned
83. 2:33that that should be called inclusive or
84. 2:35because inclusive or means you're one of
85. 2:37the other or both
86. 2:38exclusive or says one or the other
87. 2:42but not both okay so exclusive or is
88. 2:45special
89. 2:46and says if they're by the way from now
90. 2:48on i would like
91. 2:49every halloween people to say trick x or
92. 2:52treat
93. 2:53cause this is what they meant they meant
94. 2:55exor so from now on tell all your
95. 2:57friends and kids and
96. 2:58cousins and brothers and sisters to say
97. 3:00trick x or treat
98. 3:01because i don't want anybody because
99. 3:02really it's not trick or treat if i give
100. 3:04you a treat i don't want a trick
101. 3:05that's the idea that's the contract i'm
102. 3:07getting
103. 3:08nand is almost identical to and except
104. 3:10it's this little bubble at the end says
105. 3:12invert the output so and would have had
106. 3:14a 0 0 0
107. 3:151 here i say you know the bubble means
108. 3:17invert all of those
109. 3:19and exactly the same as nor nor is 0 1 1
110. 3:221
111. 3:22and i invert all of those guys to give
112. 3:24me my
113. 3:25nor value by the way this is exactly the
114. 3:28same as saying a
115. 3:29and b here pass through an or
116. 3:33passed into a not gate so basically
117. 3:37whenever you see this bubble
118. 3:38this bubble really means i took this
119. 3:40picture and shrunk it down
120. 3:42just to its essence just to the circle
121. 3:44at the end and you can do this to the
122. 3:45input too i could also have
123. 3:46if i had an if i had a not gate here on
124. 3:48the input it was not getting the input
125. 3:50i would have drawn a circle here on the
126. 3:52input so you can convert these not gates
127. 3:54and push them into the both touching the
128. 3:55bigger blocks either at the input or the
129. 3:57outputs
130. 3:58output side and you can know that we'll
131. 3:59see that a little later but that's the
132. 4:00idea of
133. 4:01that circle now let's think about if you
134. 4:04have logic gates
135. 4:05extending them to n dimensions to n
136. 4:07dimensions and inputs
137. 4:09um most of them make sense if i have an
138. 4:11and if i have a
139. 4:12tan input and it means you're a one only
140. 4:14if all ten are one if you have a ten
141. 4:16input or if it's a one if
142. 4:17any of the ten inputs is is one that's
143. 4:20the same thing
144. 4:21xor is the only one that isn't so clear
145. 4:23what happens just to make sure you
146. 4:25understand what an
147. 4:25input xor does what really xor is doing
148. 4:27is counting the number of
149. 4:29ones and when the number ones is odd
150. 4:32it's a one
151. 4:32let's go through it here we go let's
152. 4:34count number of ones
153. 4:36zero one one two
154. 4:39one two two three which of these are odd
155. 4:43numbers
156. 4:43i'm gonna circle all the odd numbers oh
157. 4:45look it's working
158. 4:48it's working palm olive it works look at
159. 4:50that okay
160. 4:51so every time you have an odd number of
161. 4:54ones on
162. 4:55all your input input lines on an xor
163. 4:57your output is a high
164. 4:58high high high otherwise you have an
165. 5:01even number
166. 5:02two zero and two here and it's a zero
167. 5:03and this works for n inputs so think of
168. 5:05xor with n inputs as doing that counting
169. 5:07the number of ones
170. 5:08and really saying are the number ones
171. 5:10odd odd yes that's what it's doing okay
172. 5:13good now here is a truth table for our
173. 5:17majority circuit
174. 5:18and by the way i mentioned before when i
175. 5:20have two lines that aren't crossing i i
176. 5:22like to do this
177. 5:23okay and that says they're not the same
178. 5:24but even if i did this
179. 5:26if i don't draw a circle here the circle
180. 5:29means they are connected they are really
181. 5:30the same line they are touching
182. 5:32if i do this even though i prefer and
183. 5:34the best way to draw it like this
184. 5:36if you see this you should be able to
185. 5:38live with it to say well it doesn't have
186. 5:39a big circle so therefore they're not
187. 5:41connected therefore i'm drawing like
188. 5:42this because it's
189. 5:43too many lines to draw this thing
190. 5:44underneath but i'm going to say that
191. 5:45they are not connected
192. 5:47so this is connected connected and these
193. 5:49are not connected okay
194. 5:52so here's a picture and if you see let
195. 5:55me actually
196. 5:55bold here see look at this guy that's a
197. 5:57big one that's a connection
198. 6:00that's a connection the rest of them are
199. 6:01not connected so even though they're
200. 6:02crossing they're not connected make sure
201. 6:03you know that
202. 6:04all right what is this doing i can go
203. 6:06from truth table to gates
204. 6:08well let's see how this works let's see
205. 6:09if this is true i haven't shown you kind
206. 6:10of
207. 6:11pedantically how to do it step by step
208. 6:13but let's see if this actually is
209. 6:14consistent with what
210. 6:15this is right so i claim this this is
211. 6:18these are i claim these are one in the
212. 6:19same let's see let's test it
213. 6:21well this first guy is saying a
214. 6:24and b if it is b and that line and
215. 6:27here's an
216. 6:28a in that line so it's saying
217. 6:31this is an or of a and b so the output
218. 6:34is an or so let's try
219. 6:35so when is a and b true only here that's
220. 6:38a and b
221. 6:39well it's one the output is a one
222. 6:43or meaning ors is true if any of them
223. 6:44are one so it's true if that's true
224. 6:46or b and c so now let's do that let's go
225. 6:50to b and c now
226. 6:51when does b and c go high well here and
227. 6:54here
228. 6:55yep it's a one there it's or
229. 6:59or when a and c and
230. 7:02by the way these it doesn't matter
231. 7:04whether a and c are here or here this
232. 7:05commutative operation
233. 7:06and a and c is the same as c and a
234. 7:09useful
235. 7:10so here's a and c when are they high
236. 7:14here and here right there's my a
237. 7:17and c and a and c and it's high there so
238. 7:20this actually works
239. 7:21this is really cool this simple circuit
240. 7:25covers my majority so that's kind of
241. 7:27neat i can see i can now think about how
242. 7:28to go from truth table to gates
243. 7:30that's kind of fun we even saw this
244. 7:33before
245. 7:33this was our remember what this was i
246. 7:36just showed you a sec a lecture ago
247. 7:38this is my truth table for my three
248. 7:40input
249. 7:41it's going to go high when i have three
250. 7:43ones in a row right i'm trying to be
251. 7:44kind of a three one detector that will
252. 7:47go high for every three ones i get and
253. 7:49then it'll reset itself
254. 7:50and wait for the next three ones in a
255. 7:51row so if i get four it goes low again
256. 7:53until i get six
257. 7:54it goes high again well take a look
258. 7:58here's my output line what's my output
259. 8:00line is only look my output line is only
260. 8:02one
261. 8:03i only have three bits when let's think
262. 8:05about this
263. 8:06when p by the way here's his ps line
264. 8:09this is important to talk about this now
265. 8:11it's really nice
266. 8:13if i have a single letter for each of as
267. 8:16i'm talking about
268. 8:18boolean algebra which i'll talk about a
269. 8:20little bit later it's really nice when i
270. 8:21have only a single letter for each input
271. 8:23but sometimes i have
272. 8:24multiple letters in like a word here's
273. 8:27ps is to an acronym previous state
274. 8:29but i also have a word input it's a
275. 8:31little bit harder
276. 8:32to then write the boolean out lot the
277. 8:34boolean algebra form for that
278. 8:36so for now you don't have to worry about
279. 8:37it because they're just lines here but
280. 8:39this ps is a grouping there's ps
281. 8:43sub one which is that set of bits
282. 8:46here's this guy is p s sub one
283. 8:50and they can imagine that this is p s
284. 8:53sub zero so this this circuit to
285. 8:55determine the output
286. 8:56only has three inputs p s of one p s of
287. 8:59zero and input
288. 9:00okay so this output is true
289. 9:04only in the single case now if i only
290. 9:07have single case
291. 9:08what is that case what's the case where
292. 9:11this guy's a one
293. 9:12this guy's a zero and this guy's a one
294. 9:14let's do it
295. 9:16ps is a one this is a zero but
296. 9:19i inverted it becomes a one look at that
297. 9:21bloop
298. 9:22and input so you can see a way to map
299. 9:25a connection from a single row and how
300. 9:28to make
301. 9:29that row always true you make it an and
302. 9:31it's true only in an and of case let's
303. 9:33say i had 20 inputs
304. 9:34when this is high i just write the term
305. 9:38if it's ever low i invert the term see
306. 9:41that i put invert the term
307. 9:43so this is i can read this this is high
308. 9:46remember
309. 9:46here's an example of me pushing my not
310. 9:48gate up to that little bubble there okay
311. 9:50up to
312. 9:51there's my bubble there okay so it's
313. 9:53only high
314. 9:54when ps1
315. 9:58and and not
316. 10:02ps0
317. 10:04input this output is high only with a
318. 10:06single gate this single gate which is
319. 10:08really kind of two gates it's an and
320. 10:09a three input and and a knot in the
321. 10:12front of it
322. 10:13i can cover this that's kind of cool so
323. 10:15we've kind of shown
324. 10:16i haven't really shown you again step by
325. 10:18step how to do this but we've kind of
326. 10:18shown how we can think about a truth
327. 10:20table
328. 10:20being mapped to gates and thinking of
329. 10:22this as again
330. 10:24one-to-one equivalent to this it's
331. 10:26really very beautiful in that way
332. 10:27kind of neat all right we'll learn more
333. 10:29about this in the next lecture see you
334. 10:30there