[CS61C FA20] Lecture 15.1 - State, State Machines: Accumulator — Transcript

Full transcript

1. 0:00and welcome back now
2. 0:03we've seen combinational logic circuits
3. 0:05and state circuits as the
4. 0:06two kinds of circuits we'll look at so
5. 0:08this lecture's going to be about state
6. 0:09the next lecture is going to be about
7. 0:12combinational logic circuits so let's
8. 0:13jump right in
9. 0:14let's first start by trying to build an
10. 0:15accumulator
11. 0:17so here's the idea
12. 0:20i've got state circuits they're used to
13. 0:22remember values that we have um
14. 0:24we're going to use them for registers
15. 0:26really fast small and fast
16. 0:28or memory which is bigger and a little
17. 0:29slower but still the same idea same
18. 0:31principle still part of the memory
19. 0:32hierarchy
20. 0:33and they're going to help control the
21. 0:34flow of information between these
22. 0:36these combinational logic blocks so
23. 0:38let's try to let's see if we can build
24. 0:40something without them let's actually
25. 0:41try to say i don't need you
26. 0:42mr state circuit let's try to build
27. 0:44something without them and see what
28. 0:46happens and then we'll realize we kind
29. 0:47of need them
30. 0:48so let's jump in i want to build an
31. 0:51accumulator i want to build see this
32. 0:52loop this beautiful
33. 0:53piece of piece of c code i want to have
34. 0:55i mean i'm basically try to do this i
35. 0:58want to have
36. 0:59s is zero and for i equals
37. 1:02zero to you know n minus one
38. 1:05s gets gets accumulated by the value of
39. 1:08x of i
40. 1:09so i've got an array of n numbers
41. 1:12and i add them all up that's all i'm
42. 1:14trying to do simple stuff it's a one
43. 1:15liner
44. 1:16you know this is like some of array one
45. 1:18liner in python some of this
46. 1:20array just some that's all i want i want
47. 1:22some array this is how you're going to
48. 1:23do this as a loop
49. 1:25and i want to be able to build a circuit
50. 1:26to do that for me that's the idea
51. 1:28so i want to have x of i coming in and
52. 1:31some sum magic happens and s is at the
53. 1:33output okay
54. 1:35and by the way here's how because we
55. 1:36know about signals we saw the signals
56. 1:38lecture before each
57. 1:40x of i is going to be applied in
58. 1:41succession one per cycle so here's the
59. 1:43first one here's x of zero
60. 1:45here's x of one here's x of two x sub
61. 1:47two okay
62. 1:48and after n cycles in theory the value
63. 1:51is done
64. 1:52after i've done this n times s now is
65. 1:54holding my
66. 1:55output and it'd be great actually if all
67. 1:57along s we're holding the sum so far
68. 1:59we can call this the sum so far in fact
69. 2:01s should have been called sum so far for
70. 2:02that
71. 2:03okay let's try it here we go
72. 2:07there's our atom we saw an adder just
73. 2:09combinational logic right
74. 2:10we saw a nibble adder before we saw an
75. 2:12n-bit adder two n-bit adders here's my
76. 2:14adder i don't even care how many bits
77. 2:15wide this is
78. 2:16but you're getting around to just single
79. 2:17bit i don't care so
80. 2:19does this work i've got i've got come on
81. 2:22this looks pretty good right
82. 2:23let's look here i've got the input
83. 2:24coming in this is my input here
84. 2:27and now the output has to be added s
85. 2:30right it has to be added to that somehow
86. 2:33so i like it this is really good right
87. 2:35yeah not so much
88. 2:37this by the way we're going to call
89. 2:38feedback whenever you have some output
90. 2:40feeding back into the input we call that
91. 2:42feedback not always bad feedback is like
92. 2:44a record
93. 2:46that's bad feedback but this is good we
94. 2:48actually use feedback
95. 2:49all the time in our circuit so feedback
96. 2:51is fine
97. 2:53this work doesn't work not so much
98. 2:56number one
99. 2:57how do we control the next iteration how
100. 2:59do we tell this circuit that
101. 3:01okay now this is x of zero but then
102. 3:04now it's x of one how does it even know
103. 3:06it's just like this
104. 3:07feedback that goes really fast and and
105. 3:09two how do we initialize it how do we
106. 3:11reset this thing to say all right s is
107. 3:14zero initially well no
108. 3:15i can't ever give it because it's always
109. 3:17a function of this whatever it was and i
110. 3:18don't know how to set that so how do i
111. 3:19ever set that line
112. 3:20how do i ever like assign a value to
113. 3:22this line i don't even know how to do
114. 3:24that
115. 3:24so the two reasons doesn't work this is
116. 3:26just the naive way
117. 3:28we said we tried to go we tried to go it
118. 3:29alone no state devices that ain't going
119. 3:32to work so
120. 3:33let's actually introduce a circuit that
121. 3:35may work
122. 3:36we're going to introduce our register
123. 3:38and this is a register that has another
124. 3:40input we didn't talk about this last
125. 3:41time
126. 3:42this is going to be a reset line okay
127. 3:44when that reset line
128. 3:46is asserted or goes one that's gonna
129. 3:48reset the register well there's our s
130. 3:50equals zero we reset it initially
131. 3:52and then this is gonna be the loader
132. 3:55that says and by the way this is drawn
133. 3:56as the input
134. 3:58and the output typically things are
135. 4:00drawn
136. 4:01signals always go left to right okay
137. 4:03unless they're part of the feedback
138. 4:04which you should
139. 4:05zip right around but we're gonna assume
140. 4:06any block comes in either comes in
141. 4:08comes in on the left goes out on the
142. 4:09right or comes out of the top goes out
143. 4:11of the bottom that's gonna that's the
144. 4:12flow of like things
145. 4:14kind of like how you should play 2048
146. 4:16down right down right okay that's how
147. 4:17that works
148. 4:19so look we've got this here's my loader
149. 4:23or clock okay which is only on the
150. 4:26rising edge of these clocks going to do
151. 4:27something
152. 4:28and the rough timing look the rough
153. 4:29timing is x is going to have its value
154. 4:31of x 0 over time
155. 4:33and then x 1 and x remember that's the
156. 4:34vector we talked about clustering those
157. 4:36signals in that
158. 4:37grouping them and the output roughly is
159. 4:40here's my cumulator
160. 4:41x0 gets initialized somehow and then
161. 4:44it's going to have
162. 4:45x0 plus x1 and look at it it's actually
163. 4:47working
164. 4:48x0 plus x1 plus x2 i love this as time
165. 4:51goes on
166. 4:51so we're going to actually take a deeper
167. 4:53dive into this that's the last slide
168. 4:54here
169. 4:55we're gonna take a deeper dive into
170. 4:56actually how this works but we're really
171. 4:58close
172. 4:58this is actually gonna work we're really
173. 5:00excited about that we'll see the next
174. 5:01lecture