[CS61C FA20] Lecture 16.5 - Combinational Logic: Canonical Forms — Transcript

Full transcript

1. 0:01and welcome back this is now the last in
2. 0:03a series of combinational logic lectures
3. 0:05in which we talk about
4. 0:06canonical forms so canonical forms is
5. 0:10a way to describe the word canonical
6. 0:12means it's like the one representative
7. 0:13thing of something
8. 0:15so it says there are lots of ways to
9. 0:16take this truth table and
10. 0:18transfer it into a series of boolean
11. 0:21algebra expressions
12. 0:22but there is only one canonical form and
13. 0:24so let's talk about that canonical form
14. 0:26is and that actually helps us think
15. 0:27about
16. 0:27how to do this in general with any truth
17. 0:29table so this is the part that i was
18. 0:30talking about i didn't really tell you
19. 0:31how to do this in general
20. 0:32now we're going to go very slowly and
21. 0:33make sure we do this so the way you do
22. 0:36this in canonical form is you take a
23. 0:37look at your truth table
24. 0:39and you say where is there a 1
25. 0:43in my output okay
26. 0:46let's now back back for every one i kind
27. 0:48of hinted to this how to do this but now
28. 0:50i'm
29. 0:50telling you formally every time you have
30. 0:52a one this is a one
31. 0:54if and only if this is a zero
32. 0:57and that is a zero and that is a zero
33. 1:00and
34. 1:00another example this is a one when this
35. 1:02is a zero this is a zero and that's a
36. 1:04one
37. 1:05so what expression would be true for
38. 1:08just
39. 1:08that row just that row every
40. 1:12time you have a zero you put a not in
41. 1:14front of that term every time there's a
42. 1:15one
43. 1:16every time there's a one you just leave
44. 1:18that term there
45. 1:20so in general let's pick a term that has
46. 1:21ones and zeros in it
47. 1:23so this term would be for that one only
48. 1:26that one would be when
49. 1:28a is true and b is false
50. 1:31and c is false otherwise otherwise known
51. 1:34as
52. 1:34a not b not c
53. 1:37if you do this for all the rows now i
54. 1:39have just a term for here a term for
55. 1:41there a term for there a term for there
56. 1:43then you then take that and say well
57. 1:46it's this
58. 1:47it's a one where this is the case or
59. 1:50when that's the case or when that's the
60. 1:53case or
61. 1:54that's the case and so we're going to
62. 1:56see is this canonical form
63. 1:58is called the sum of products
64. 2:01and that's the idea it's saying it's
65. 2:04that row
66. 2:04or that row or that row or etc or that
67. 2:07row until you're all done
68. 2:09and that's the canonical form for taking
69. 2:11a truth table
70. 2:12and you can do this now for any truth
71. 2:13table i can have an infinite long truth
72. 2:14table and i just go over every one
73. 2:16in the outputs for however many outputs
74. 2:18i have that one for that particular bit
75. 2:20is true when
76. 2:21and i go through and i make a product
77. 2:23and i somehow have to negate some of
78. 2:24these terms
79. 2:25and it's that there you know it's like a
80. 2:27and b and not c
81. 2:29which is the last term in this example
82. 2:30okay so that's canonical form part one
83. 2:34then i take the canonical form and i
84. 2:37bring it into my world of boolean
85. 2:38algebra
86. 2:39i dip my hands in building algebra
87. 2:41massage oil and i start working it i
88. 2:43start working that mess
89. 2:44i start working that expression so let's
90. 2:46do this together and i'm here showing
91. 2:48you exactly this is
92. 2:49i had to do this by the way when i was
93. 2:50taking my geometry uh
94. 2:52lessons back in high school where i had
95. 2:54to kind of make the rule the trend
96. 2:56oh this is a side angle side and then
97. 2:57move it to the next level and i always
98. 2:58have to label it with
99. 3:00what is the rule i'm applying there we
100. 3:02could ask you to do that so make sure
101. 3:03you know what the rules are
102. 3:04we always let you bring your you know
103. 3:05bring the table of that slide
104. 3:07of all the rules with you but i don't
105. 3:09tell you how to use them so here we go
106. 3:11well i've got these three terms i see a
107. 3:14common not a not b
108. 3:16here so i could reverse distribute
109. 3:19not a not b into this so i have this
110. 3:21term out the same thing with
111. 3:23a and not c that's also
112. 3:26that's also communicativity i'm
113. 3:28switching that so the a not c
114. 3:30is in the front so a not c not b
115. 3:33or a not c b that gives you these two
116. 3:36terms
117. 3:37now c or not c well
118. 3:40i'm either happy or i'm not happy folks
119. 3:43you're always going to be a 1 there
120. 3:45i'm either happy or not i either have
121. 3:47pizza i don't have pizza either burrito
122. 3:48or no burrito
123. 3:49folks that's a one so that's the
124. 3:51complementarity rule we saw there
125. 3:54and this is the easy one you know this
126. 3:55from algebra that's just identity and
127. 3:57that gives you
128. 3:58the simplest form here so this is not a
129. 4:01not b
130. 4:02or a and not c and we can now
131. 4:05transfer this into a gate diagram and so
132. 4:08i now have
133. 4:09i take my watch here i try to make use
134. 4:12of the fact that
135. 4:13i've got to have um actually this is all
136. 4:15unique there's not a single doubling up
137. 4:17here
138. 4:17so i've got a not b i need i've got a
139. 4:19not a and an a i need
140. 4:21and i need not c i don't need c and i
141. 4:23also don't need b
142. 4:24there's no c and b terms in here and
143. 4:26this is an or of that so i can already
144. 4:28see this i can already see there's going
145. 4:29to be one
146. 4:30ore and i'm going to see an and here and
147. 4:32i see an and here
148. 4:34and i probably need some knots for these
149. 4:35guys each of these mapped to those
150. 4:37knots and if i then remove the not gates
151. 4:40and push those bubbles up to the front
152. 4:41or the output
153. 4:43uh so you know you push the if i had a
154. 4:44knot at the end if i had if i had a knot
155. 4:46at the end i would have pushed that
156. 4:47bubble there so
157. 4:48you take the knots and then push those
158. 4:50in as another way of thinking this is
159. 4:52kind of what everyone
160. 4:53pro tip draws is we don't draw any knot
161. 4:55case we always draw them as bubbles and
162. 4:57you push them into the either the input
163. 4:58of the output of the gates of and and or
164. 5:00or x or whatever whatever you have it
165. 5:02okay
166. 5:03that's pretty cool so truth table
167. 5:07massage truth table sum of products to
168. 5:09get canonical form
169. 5:11and now i take that to then bubble it
170. 5:13down to be the simplest form i can
171. 5:16okay very good
172. 5:19in conclusion
173. 5:23we're going to pipeline big delay
174. 5:25combination logic for a faster clock we
175. 5:27saw that
176. 5:28we love finite state machines they're
177. 5:30able to describe a brain of a system
178. 5:32how to do something a turing machine a
179. 5:34universal turing machine is basically a
180. 5:35finite state machine drive
181. 5:36driving how a tape moves left and right
182. 5:39and we can see these
183. 5:40this beautiful graph to describe how we
184. 5:43move
185. 5:43from truth tables to boolean expressions
186. 5:45to gate diagrams
187. 5:47i can go back and forth from a truth
188. 5:48table to a boolean expression no problem
189. 5:50i can go back and forth from a truth
190. 5:52table from a gate diagram
191. 5:54to a bully expression and back but
192. 5:57it's not immediately clear how i go from
193. 6:00a truth table
194. 6:01to a date gate diagram that's hard to do
195. 6:03we say
196. 6:04you know i can't get there to hear i
197. 6:06want you to go to a balloon expression
198. 6:08and then maybe simplify it and then go
199. 6:10to the date guided so this is not
200. 6:11something we
201. 6:12we say it's easy to do you want to go to
202. 6:14a bully expression and then massage it
203. 6:15to that the simplest decay diagram
204. 6:17because again you want the simplest
205. 6:18driving gate diagram you can that's it
206. 6:21that's the end of this lecture
207. 6:22we'll see the next one take care