[CS61C FA20] Lecture 15.5 - State, State Machines: Finite State Machines — Transcript

Full transcript

1. 0:00PROFESSOR: And welcome back.
2. 0:01Now let's actually talk about finite state machines
3. 0:04and what we can use them for.
4. 0:06You might have seen finite state machines
5. 0:07before in other classes.
6. 0:10The idea is you have these series of states
7. 0:12and transitions, and in this particular picture
8. 0:15we have the output is a function of the transition.
9. 0:19So the arrows are the transition.
10. 0:21This says, well when should you make that transition?
11. 0:23I was in state 1.
12. 0:24When should you make that transition?
13. 0:26Well when you get this input, this particular sequence.
14. 0:28And here is my output here.
15. 0:30You can also, by the way, have outputs attached only
16. 0:33to the states.
17. 0:34So I say when I'm in that state, that's my output.
18. 0:39Two ways of doing that-- you either transition on the arrows
19. 0:41or on the states themselves.
20. 0:43And we can see how to use combinational logic
21. 0:47and registers to convert any finite state
22. 0:50machine into a circuit that we can actually build.
23. 0:52Pretty cool.
24. 0:54Let's actually take an example.
25. 0:55So we're going to play with this on a finite state machine
26. 0:58to detect three 1's.
27. 0:59So detectors are really easy to do.
28. 1:02We've used this in exams before.
29. 1:03It's a nice example.
30. 1:05So what it says is when I have three 1's, I
31. 1:08want to output a 1.
32. 1:09And then should I continue to output
33. 1:12a 1 when I get the fourth 1?
34. 1:13No.
35. 1:14In this particular state, this particular idea--
36. 1:16this has to be part of the spec, by the way--
37. 1:18you need to tell me what happens on the fourth 1.
38. 1:20And then usually in this input-output example
39. 1:22tells you what to do on the fourth 1.
40. 1:23The idea is the third 1-- one 1, nothing.
41. 1:26Two 1's, nothing.
42. 1:27Three consecutive 1's-- there's my 1--
43. 1:29four consecutive 1's, you don't want to have that be high.
44. 1:32You want to reset it and be looking for the next three 1's.
45. 1:35So only if you have six, so there's
46. 1:37six will it bleep here for the first three
47. 1:39and there for the second three.
48. 1:40Okay, so let's see if we can actually think about this.
49. 1:43What will the FSM look like for that?
50. 1:45Well we're going to have only three states
51. 1:48for this particular one.
52. 1:49You can have more.
53. 1:50I can have a lot of redundant situations,
54. 1:51but this is the tightest, smallest FSM
55. 1:53that will do this for us.
56. 1:55By the way, every state-- this is an FYI--
57. 1:57every state has to have every possible combination of inputs
58. 2:01exiting from that state.
59. 2:03Which means I mean that state, I have all the possible range
60. 2:06of my inputs, I have to have an exit
61. 2:08arrow for all of these options.
62. 2:10So here I only have one bit.
63. 2:12My one bit is my input, so that bit can have a 0 or 1.
64. 2:15So every one of these states has a 0 exit arrow or 1 exit arrow.
65. 2:21Here's state 1.
66. 2:21I don't even know what this is yet,
67. 2:23but state 1 has a 1 exit arrow.
68. 2:25There's my 0, and here state 2 has my 1 and my 0.
69. 2:28So every state has one of these possibilities,
70. 2:31otherwise it's not valid.
71. 2:33The second thing--
72. 2:34I didn't do this.
73. 2:34I wanted to show you what it is.
74. 2:36Every finite state machine should have an arrow
75. 2:38indicating the initial state.
76. 2:40You just can't have this set of arrows and transitions
77. 2:43to not know where to start.
78. 2:44You got to know where to start.
79. 2:44And usually there's an arrow in, or what they'll often do--
80. 2:47I'll just show you this-- they'll do a double circle.
81. 2:49That's a double circle around that and that says,
82. 2:52okay, that's the initial state.
83. 2:52One of those two ways is fine.
84. 2:54Let's go with the arrow.
85. 2:55So it means we're going to start at state 0.
86. 2:57And in fact, there's a semantic meaning
87. 2:59behind this particular example, the labels of the states.
88. 3:02We're going to actually call state
89. 3:040, state 1, state 2 the number of 1's I've seen so far.
90. 3:07So I'm initialized to have seen no 1 so far.
91. 3:09You could also initialize to say I see one.
92. 3:12But in this particular case, I'm going
93. 3:13to initialize to seeing zero 1's so far.
94. 3:16And then every time I see a 1, notice this,
95. 3:18I'm going to transition to say now I've seen one 1 so far.
96. 3:22Now I've seen two 1's so far.
97. 3:25And when I get the third 1, that's my third 1 in a row--
98. 3:29I'm going to output 1--
99. 3:30that's why this is right here--
100. 3:32and then reset to my initial seeing zero 1's so far.
101. 3:36So I'm not going to say, well I stay there.
102. 3:38So let's play with this.
103. 3:40Here we go.
104. 3:40I'm at 0.
105. 3:41Okay, here we go.
106. 3:42I'm at 0.
107. 3:43And I stay at 0 as long as I keep seeing 0's.
108. 3:45I see my first 1.
109. 3:46Yay, I've seen a 1.
110. 3:48Now I'm at state 1.
111. 3:49And now, oh no, I see a 0.
112. 3:51I'm going to go back to there.
113. 3:52So I reset the number of 1's I've seen so far.
114. 3:54Same idea here.
115. 3:55I've seen one 1.
116. 3:56I've seen two 1's.
117. 3:58Oh, I go back here.
118. 4:00The third was not a 1, it's a 0.
119. 4:02I reset.
120. 4:02I do not output anything.
121. 4:04See how this all makes sense?
122. 4:05Let's do this.
123. 4:06Now I've seen three 1's.
124. 4:07Here we go.
125. 4:08One 1, two 1's, on that third 1 I output 1.
126. 4:13There's my output 1.
127. 4:14Love it.
128. 4:15And I reset having seen zero 1's so far.
129. 4:18So I go here.
130. 4:20See one, after here I'm state 1.
131. 4:23State 2, go back to state 0 seeing one, and there's my 1.
132. 4:27Seen one, seen two, now go back to 0.
133. 4:29There's my second blip.
134. 4:30So all that makes sense.
135. 4:32Ask yourself, how would you modify this diagram
136. 4:36if you want to stay 1 all along?
137. 4:39So if I see four 1's I should output two of these guys.
138. 4:42If here I want to output one solid set.
139. 4:45So I basically keep outputting 1 if I continue to see 1's.
140. 4:49How would you modify this diagram--
141. 4:51think to yourself of how to do that, how to modify the diagram
142. 4:54to make that happen.
143. 4:56And 3, 2, 1, all right, welcome back.
144. 5:01So here's how to do that.
145. 5:03If I wanted to have this continuous, that basically says
146. 5:05rather than reset to state 0, I should reset to, drum roll,
147. 5:10state 2.
148. 5:12So I stay in state 2.
149. 5:14So if I were to change this arrow and say
150. 5:16this now goes this way.
151. 5:18Now I've got the third one.
152. 5:21I output one and I stay in state 2,
153. 5:23because I've seen two in a row.
154. 5:25And the more ones I see, if I see another one,
155. 5:27I'll stay there.
156. 5:28And only when I see a 0 do I reset to 0.
157. 5:31So if all I do is change this one arrow back to there,
158. 5:34that's a great exam question.
159. 5:35What happens when I change just one arrow?
160. 5:36What different language am I interpreting?
161. 5:38Well, it means that rather than three 1's and reset,
162. 5:41three 1's and reset, it's three 1's
163. 5:43and then stay high until I see a 0.
164. 5:44And that's exactly what would happen.
165. 5:46So this arrow would just change back to land in S2.
166. 5:50That's all.
167. 5:51Small change, and you can make a different language
168. 5:53that you're parsing in some sense,
169. 5:54in terms of the number of 1's I'm outputting.
170. 5:57How do we build this?
171. 5:59We've kind of already seen the main structure.
172. 6:01I've got the pieces already.
173. 6:02I've got some combinational logic
174. 6:04that can handle inputs and previous state.
175. 6:09I've got a next state, which tells me where
176. 6:12I'm going to be in the future.
177. 6:13And I've got my output.
178. 6:15I take a register.
179. 6:16This is standard.
180. 6:17I just go off the shelf, grab my register,
181. 6:19and how to handle that.
182. 6:20And that's going to handle my previous state.
183. 6:22And I wire it like this.
184. 6:23This is really cool.
185. 6:25That register remembers what state I'm in.
186. 6:28And all it is is, you've reset it to the 0 state.
187. 6:30It's a nice thing to do, reset to 0.
188. 6:31That's nice to have 0 be the initial state always,
189. 6:34because then you reset it, it's fine.
190. 6:35You don't have to load in whatever
191. 6:36the initial state is at 75.
192. 6:38But make it 0.
193. 6:38That way you load to 0, you reset to 0.
194. 6:40And the combinational logic is used
195. 6:42to store and figure out what the mapping is,
196. 6:44what my next stage should be, and also
197. 6:46what my output should be.
198. 6:47So there's a 1 to 1 connection between what
199. 6:49this combinational logic looks like
200. 6:50and my state diagram we saw before.
201. 6:54So here it is, this is the truth table
202. 6:57for the combinational logic to do that three inputs.
203. 7:00Let's see what happens.
204. 7:01Here we go.
205. 7:03Remember the picture, just to remember the picture before.
206. 7:05My previous state was 0.
207. 7:07If I get 0, I stay in 0, I output 0.
208. 7:09In fact, I only output one in the last case.
209. 7:13Watch, for my state of 0, I get a 1.
210. 7:15Now I've seen 1.
211. 7:16Remember that semantic meaning of the state numbers
212. 7:18is how many 1's I've seen.
213. 7:19I've seen 1.
214. 7:20I still output 0.
215. 7:21And remember, all these are output 0.
216. 7:23If I'm at 1, I want to get a 0.
217. 7:25Oh, I got to reset.
218. 7:26So already you can read this and say, oh, yeah, look,
219. 7:29I reset when I get a 0.
220. 7:30If I happen to be at 2 and I reset, I go back to 0.
221. 7:33But if I get a 1 and another 1, I go to state 2.
222. 7:36So all this is consistent.
223. 7:37And then, when I get a 1, so if I'm in state 2, and I get a 1,
224. 7:42I reset to state 0, and I output a 1, exactly.
225. 7:46So how would I make that change we did?
226. 7:48How would I make the change in this truth table to the idea
227. 7:51that if I get the fourth 1, I want to stay high?
228. 7:54So I figure the one, stay high, and keep out putting a 1
229. 7:56as long as I continue to see 1's.
230. 7:58Ready?
231. 7:58Pause the video and come back.
232. 8:00And I'll give you the answer in 3, 2, 1.
233. 8:04It was only that last state before I was at state 2.
234. 8:10I had a 1 and I went to 0.
235. 8:12The only change we made is, I crossed this off
236. 8:14and I say, bloop, 1.
237. 8:18Now I stay in state 2 and I continue to output 1 as long
238. 8:22as I keep getting 1's.
239. 8:23That very simple change makes the change semantically
240. 8:26and what that circuit is going to be doing for me.
241. 8:29Pretty cool, right?
242. 8:30Good stuff, easy.
243. 8:32So here's the general model for a synchronous system.
244. 8:35I've got this loop.
245. 8:37That same picture you saw before is here.
246. 8:39It's right here.
247. 8:40That's the same picture you saw before.
248. 8:41It's clocked, I've got some stuff.
249. 8:43And the feedback is only within that system.
250. 8:45But you can imagine that following up
251. 8:47with another series of what it's calculating, what it's doing.
252. 8:51And here's the fun thing.
253. 8:52You could have optional feedback from this state
254. 8:55back in there, which means this combinational logic is not only
255. 8:58knowing the next state but the state after that too.
256. 9:00That's fine.
257. 9:01You can have that feedback as well.
258. 9:03And you can imagine many, many more of these
259. 9:05with a lot more lines feeding back
260. 9:07to this very powerful system, doing something very complex.
261. 9:10That's it, synchronous digital systems.
262. 9:12This is what we're trying to say and this is
263. 9:14the general structure for that.
264. 9:16Collections of CL blocks, separated by registers,
265. 9:18I said that.
266. 9:19They may be back to back or the CL
267. 9:21might be back to back as well.
268. 9:22Feedback is optional.
269. 9:23You don't have to have the feedback at all.
270. 9:25And the clock signal keeps that whole chugging
271. 9:27through in that way.
272. 9:28I love it.
273. 9:31In a big picture, this is what we're
274. 9:33trying to teach you in this series of lectures.
275. 9:35We're trying to build a system.
276. 9:36In that system, we're going to have data path and control.
277. 9:39We're going to see that in later lectures
278. 9:41that are dedicated to data path and control.
279. 9:43Here, we're just kind of talking about what
280. 9:45happens in the control world.
281. 9:47We've talked about state registers.
282. 9:49We've done that already.
283. 9:50Combinational logic is the next lecture.
284. 9:53State registers, you have the register.
285. 9:55We haven't really talked about how
286. 9:56to build the logic in detail.
287. 9:58That's also the next lecture.
288. 9:59And how to put that as part of switching networks
289. 10:01is all part of that next lecture.
290. 10:02So we've kind of done in this series of lectures,
291. 10:04this in the next one.
292. 10:07We're going to probably do a little bit of this,
293. 10:09a little bit of this in the fourth lecture.
294. 10:11And then put these together in the series of lectures
295. 10:13after that to be able to build a working RISC V system that
296. 10:17can interpret all the RISC V machine code
297. 10:19we've been producing from our compiler, assembler,
298. 10:21and linker.
299. 10:23In summary, we're at the end of this series.
300. 10:27State elements are used to build memories.
301. 10:29We saw that.
302. 10:29You can build a register from a flip-flop.
303. 10:32From a little teeny baby flip-flop,
304. 10:33you can build a register.
305. 10:34From that register, you can think
306. 10:36of that as building memory.
307. 10:37We haven't talked about that.
308. 10:38But we can talk about that a little bit later
309. 10:39when we talk about how to build some of these elements.
310. 10:41But the same idea, same idea.
311. 10:43All you have to do is be able to say,
312. 10:44rather than one register, which of these kind
313. 10:46of small registers am I going to write to.
314. 10:48That's, in a way, all that memory is, is telling
315. 10:50which of these registers am I writing to?
316. 10:52Think of each memory as just a log.
317. 10:53A lot of these registers that each have an address.
318. 10:56I want to change that one.
319. 10:57Each one of these is just a register at the lowest level.
320. 11:01State elements also help control the flow of information.
321. 11:04Otherwise the combinational logic circuit
322. 11:06would just have infinite feedback if it's too fast.
323. 11:08You have to kind of slow down so it's part
324. 11:09of the heartbeat of the system.
325. 11:11You know that we use D flip-flops to build registers.
326. 11:14Clocks tell us if we clock these flip-flops, the they're
327. 11:16going to grow at a kind of cha-chunk,
328. 11:18cha-chunk, cha-chunk in my pipeline system,
329. 11:21would love that.
330. 11:22And I've mentioned even pipeline for a faster
331. 11:25pipeline, a long delay combinational logic.
332. 11:27Break them into pieces, pipeline it to have a faster clock.
333. 11:29We can do that, smaller clock period, we love that.
334. 11:32And they're extremely useful.
335. 11:33You're going to see them a lot of classes.
336. 11:35Finite state machines are really powerful ideas.
337. 11:38You'll see them in 151A, 152, 164, 172, lots.
338. 11:41You remember I was talking about the language as parsing
339. 11:43languages?
340. 11:44I'm using 164 speak.
341. 11:46If we think about 164, the compiler
342. 11:49class in some sense in programming systems,
343. 11:53we'll teach you how to use a flip-flop
344. 11:55to be able to parse a language and a finite state
345. 11:57machine-- not a flip-flop, but a finite state machine,
346. 11:59to be able to parse a language.
347. 12:00This finite state machine parses it
348. 12:01and is able to receive, and navigate, and decode
349. 12:06this particular language.
350. 12:07So we can use finite state machines
351. 12:08in many different ways.
352. 12:10We're all done.
353. 12:11See you at the next lecture.