[CS61C FA20] Lecture 16.3 - Combinational Logic: Boolean Algebra — Transcript

Full transcript

1. 0:00and welcome back this still series is
2. 0:02called combinational logic but we're
3. 0:04going to learn about boolean algebra
4. 0:05that i've hinted
5. 0:06about before so i also mentioned a
6. 0:08couple lectures ago that george boole
7. 0:10claude shannon made the connection
8. 0:11between transistors
9. 0:13and the mathematical work of george
10. 0:14boole to wow ones and zeros and and
11. 0:17transistors and circuits
12. 0:18that connection was really wonderful and
13. 0:20really rich and so he named it bowling
14. 0:22algebra in honor of george boole
15. 0:24there are some primitive functions that
16. 0:26boolean algebra has
17. 0:28they're and or and not powers are that
18. 0:30we can use normal mathematics and
19. 0:32connections between
20. 0:33massaging things in the boolean algebra
21. 0:34world and then making a connection
22. 0:35between how the circuit might change and
23. 0:37be equivalent as well
24. 0:38this is the first thing i'm sharing
25. 0:39that's brand new from now on
26. 0:42if i ever say plus i mean or
27. 0:46if i mean if i say times i mean and
28. 0:49and if i draw a bar on top i mean not
29. 0:52and if that bar is over a big expression
30. 0:54i mean invert that whole expression
31. 0:57the bar is only over a term i just mean
32. 0:59invert that term okay so remember that
33. 1:01as we move on
34. 1:02to this so here is the boolean algebra
35. 1:04here's the circuit
36. 1:05of a majority function what would that
37. 1:08look like in boolean algebra let's take
38. 1:09a look
39. 1:10i'm seeing a and
40. 1:14c which remember now is a times c
41. 1:18i'm also seeing b times c
42. 1:21i'm also seeing a times c
43. 1:24and there's an or with all of that which
44. 1:26means they all have to be grouped with a
45. 1:28plus between them and that's what i get
46. 1:30a times b
47. 1:32a times c and b times c
48. 1:36and you're going to notice by the way i
49. 1:37didn't do the same order
50. 1:39the interesting thing is this order
51. 1:41doesn't matter why because boolean
52. 1:42algebra tells us that
53. 1:44that addition is commutative a or b
54. 1:47is the same as b or a and i can also
55. 1:50flip the order of these two as well
56. 1:52a times b is equal to b times a because
57. 1:54multiplication is also commutative
58. 1:56pretty cool okay
59. 1:59because we don't know you know when
60. 2:01we're kind of learning algebra maybe in
61. 2:03ninth grade we don't have to put a dot
62. 2:05between any two product we can just say
63. 2:06a b now remember i don't mean
64. 2:08a b a single line called ab and there's
65. 2:11a single line called act in a single
66. 2:12line called book
67. 2:13i don't mean that i mean these are three
68. 2:15different signals and they're
69. 2:16the products are themselves this is a
70. 2:18challenge where we go to the next slide
71. 2:19where you see
72. 2:20that sometimes our input names aren't
73. 2:23single letters they are
74. 2:24they're even more complicated this input
75. 2:26means it's a
76. 2:27single in a single single sig
77. 2:30single signal that's i say that 10 times
78. 2:33fast
79. 2:34um that that happens to have five
80. 2:37letters describing it
81. 2:38ps is a two-bit signal so i have to have
82. 2:42ps
83. 2:42sub one and ps a sub zero again this can
84. 2:45be complicated but let's see if we can
85. 2:47actually work through this
86. 2:48we saw this before okay this is our
87. 2:50finite state
88. 2:52machine encoded as a truth table and
89. 2:54it's a one
90. 2:55only if and only if the first
91. 2:59ps sub one is one and
92. 3:03ps sub zero is zero
93. 3:06and input is one
94. 3:09so there's my circuit we see this before
95. 3:11okay we also saw we could simplify it to
96. 3:14that
97. 3:15and the interesting thing is how do i
98. 3:16then take this
99. 3:18and write this in a boolean algebra way
100. 3:21well i've got ps sub 1 and
101. 3:24or times not ps of 0
102. 3:30and input so output should be the
103. 3:32product of all three of those terms
104. 3:34with a bar over ps of zero and that's
105. 3:36exactly what i get
106. 3:37output is ps sub one one term and
107. 3:40not ps of zero and input okay and don't
108. 3:43remember don't think this is
109. 3:45five different inputs each a single bit
110. 3:47long and it's i
111. 3:48times n times p that's not what we have
112. 3:50and so try to try not to have you can
113. 3:52have a system where
114. 3:53there's also an n and a p and a u and
115. 3:55that don't do that
116. 3:56make sure you're very clear and don't
117. 3:57ever have another bit input
118. 3:59here's an i input and an n and then some
119. 4:01product is
120. 4:02input and that that would be
121. 4:03indistinguishable from this input which
122. 4:05is a single line and you mean five
123. 4:07different lines don't do that
124. 4:08so keep the naming uh consistent you can
125. 4:10get in trouble with that so try just to
126. 4:11be clean with that
127. 4:13we can do a simplification we're going
128. 4:15to reuse this our last slide on this but
129. 4:16we're going to be able to see that i can
130. 4:18go from a circuit
131. 4:19to then some kind of equation derived
132. 4:21from that circuit and then use my
133. 4:23balloon algebra
134. 4:24to actually simplify that circuit to get
135. 4:27the simplified version this is the
136. 4:29simplest form of boolean algebra
137. 4:31therefore i've simplified the actual
138. 4:33circuits needed to so if i'm gonna have
139. 4:34to wire these guys
140. 4:35or use transistors on a chip i would
141. 4:37much rather have the simplified version
142. 4:39that's the fewest number transistor to
143. 4:41use that this is only one gate
144. 4:43i love that that's much better than
145. 4:44these three gates this has much more
146. 4:46delay
147. 4:47this is more area on a chip i have more
148. 4:49delays there's a lot of reasons i don't
149. 4:50like this
150. 4:51more complicated circuit i do want the
151. 4:52simplest form fewer delays all of that
152. 4:55so
153. 4:55we're going to see the power of blue and
154. 4:57algebra is this and the next slide the
155. 4:59next lecture is going to be
156. 5:00all talking about what are these
157. 5:02identities we're doing to massage these
158. 5:04equations down
159. 5:05they look like you know they look like a
160. 5:06normal look a b plus a
161. 5:08somehow i distribute like an a out to
162. 5:11get b plus one
163. 5:12how is b plus one one we're going to
164. 5:14show you all of those rules
165. 5:15in the next lecture we'll see you there
166. 5:19there's just one more thing before i
167. 5:20close i almost forgot to mention this
168. 5:22one of the great ideas about balloon
169. 5:23algebra is i can say i got two circuits
170. 5:26are they the same or not actually if i
171. 5:28use boolean algebra
172. 5:30to simplify both circuits so convert the
173. 5:33convert the circuits to the
174. 5:34algebraic equivalent then massage them
175. 5:37down to
176. 5:38see if at the core they end up at the
177. 5:40same simpler equation
178. 5:42after the same simple equation they are
179. 5:44the same circuit so it's a great way to
180. 5:45be able to see if two different circuits
181. 5:46that look very very different
182. 5:48are actually the same thing once i use
183. 5:50my building algebra to simplify them to
184. 5:51the simplest form
185. 5:52i can just compare those simplest forms
186. 5:54it's often hard to kind of figure out
187. 5:55what the simplest form is
188. 5:56if you kind of just have magic fewest
189. 5:58gates or something but it's really a
190. 5:59nice way to be able to compare two
191. 6:00different circuits
192. 6:01just want to make sure i added that
193. 6:02before i closed thanks