Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
And welcome back. Now let's actually talk about finite state machines and what we can use them for. You might have seen finite state machines before in other classes.
The idea is you have these series of states and transitions, and in this particular picture we have the output is a function of the transition. So the arrows are the transition.
This says, well when should you make that transition? I was in state 1. When should you make that transition? Well when you get this input, this particular sequence.
And here is my output here. You can also, by the way, have outputs attached only to the states. So I say when I'm in that state, that's my output.
Two ways of doing that — you either transition on the arrows or on the states themselves.
And we can see how to use combinational logic and registers to convert any finite state machine into a circuit that we can actually build. Pretty cool. Let's actually take an example.
So we're going to play with this on a finite state machine to detect three 1's. So detectors are really easy to do. We've used this in exams before.
It's a nice example. So what it says is when I have three 1's, I want to output a 1. And then should I continue to output a 1 when I get the fourth 1?
No. In this particular state, this particular idea — this has to be part of the spec, by the way — you need to tell me what happens on the fourth 1.
And then usually in this input-output example tells you what to do on the fourth 1. The idea is the third 1 — one 1, nothing. Two 1's, nothing.
Three consecutive 1's — there's my 1 — four consecutive 1's, you don't want to have that be high. You want to reset it and be looking for the next three 1's.
So only if you have six, so there's six will it bleep here for the first three and there for the second three. Okay, so let's see if we can actually think about this.
What will the FSM look like for that? Well we're going to have only three states for this particular one. You can have more.
I can have a lot of redundant situations, but this is the tightest, smallest FSM that will do this for us.
By the way, every state — this is an FYI — every state has to have every possible combination of inputs exiting from that state.
Which means I mean that state, I have all the possible range of my inputs, I have to have an exit arrow for all of these options. So here I only have one bit.
My one bit is my input, so that bit can have a 0 or 1. So every one of these states has a 0 exit arrow or 1 exit arrow.
Here's state 1. I don't even know what this is yet, but state 1 has a 1 exit arrow. There's my 0, and here state 2 has my 1 and my 0.
So every state has one of these possibilities, otherwise it's not valid. The second thing — I didn't do this. I wanted to show you what it is.
Every finite state machine should have an arrow indicating the initial state. You just can't have this set of arrows and transitions to not know where to start. You got to know where to start.
And usually there's an arrow in, or what they'll often do — I'll just show you this — they'll do a double circle.
That's a double circle around that and that says, okay, that's the initial state. One of those two ways is fine. Let's go with the arrow.
So it means we're going to start at state 0. And in fact, there's a semantic meaning behind this particular example, the labels of the states.
We're going to actually call state 0, state 1, state 2 the number of 1's I've seen so far. So I'm initialized to have seen no 1 so far.
You could also initialize to say I see one. But in this particular case, I'm going to initialize to seeing zero 1's so far.
And then every time I see a 1, notice this, I'm going to transition to say now I've seen one 1 so far. Now I've seen two 1's so far.
And when I get the third 1, that's my third 1 in a row — I'm going to output 1 — that's why this is right here — and then reset to my initial seeing zero 1's so far.
So I'm not going to say, well I stay there. So let's play with this. Here we go. I'm at 0.
Okay, here we go. I'm at 0. And I stay at 0 as long as I keep seeing 0's. I see my first 1.
Yay, I've seen a 1. Now I'm at state 1. And now, oh no, I see a 0. I'm going to go back to there.
So I reset the number of 1's I've seen so far. Same idea here. I've seen one 1. I've seen two 1's.
Oh, I go back here. The third was not a 1, it's a 0. I reset. I do not output anything.
See how this all makes sense? Let's do this. Now I've seen three 1's. Here we go.
One 1, two 1's, on that third 1 I output 1. There's my output 1. Love it. And I reset having seen zero 1's so far.
So I go here. See one, after here I'm state 1. State 2, go back to state 0 seeing one, and there's my 1. Seen one, seen two, now go back to 0.
There's my second blip. So all that makes sense. Ask yourself, how would you modify this diagram if you want to stay 1 all along?
So if I see four 1's I should output two of these guys. If here I want to output one solid set. So I basically keep outputting 1 if I continue to see 1's.
How would you modify this diagram — think to yourself of how to do that, how to modify the diagram to make that happen. And 3, 2, 1, all right, welcome back.
So here's how to do that. If I wanted to have this continuous, that basically says rather than reset to state 0, I should reset to, drum roll, state 2.
So I stay in state 2. So if I were to change this arrow and say this now goes this way. Now I've got the third one.
I output one and I stay in state 2, because I've seen two in a row. And the more ones I see, if I see another one, I'll stay there.
And only when I see a 0 do I reset to 0. So if all I do is change this one arrow back to there, that's a great exam question.
What happens when I change just one arrow? What different language am I interpreting?
Well, it means that rather than three 1's and reset, three 1's and reset, it's three 1's and then stay high until I see a 0. And that's exactly what would happen.
So this arrow would just change back to land in S2. That's all.
Small change, and you can make a different language that you're parsing in some sense, in terms of the number of 1's I'm outputting. How do we build this?
We've kind of already seen the main structure. I've got the pieces already. I've got some combinational logic that can handle inputs and previous state.
I've got a next state, which tells me where I'm going to be in the future. And I've got my output. I take a register. This is standard.
I just go off the shelf, grab my register, and how to handle that. And that's going to handle my previous state. And I wire it like this. This is really cool.
That register remembers what state I'm in. And all it is is, you've reset it to the 0 state. It's a nice thing to do, reset to 0.
That's nice to have 0 be the initial state always, because then you reset it, it's fine. You don't have to load in whatever the initial state is at 75.
But make it 0. That way you load to 0, you reset to 0.
And the combinational logic is used to store and figure out what the mapping is, what my next stage should be, and also what my output should be.
So there's a 1 to 1 connection between what this combinational logic looks like and my state diagram we saw before.
So here it is, this is the truth table for the combinational logic to do that three inputs. Let's see what happens. Here we go. Remember the picture, just to remember the picture before.
My previous state was 0. If I get 0, I stay in 0, I output 0. In fact, I only output one in the last case.
Watch, for my state of 0, I get a 1. Now I've seen 1. Remember that semantic meaning of the state numbers is how many 1's I've seen. I've seen 1.
I still output 0. And remember, all these are output 0. If I'm at 1, I want to get a 0. Oh, I got to reset.
So already you can read this and say, oh, yeah, look, I reset when I get a 0. If I happen to be at 2 and I reset, I go back to 0.
But if I get a 1 and another 1, I go to state 2. So all this is consistent.
And then, when I get a 1, so if I'm in state 2, and I get a 1, I reset to state 0, and I output a 1, exactly.
So how would I make that change we did? How would I make the change in this truth table to the idea that if I get the fourth 1, I want to stay high?
So I figure the one, stay high, and keep out putting a 1 as long as I continue to see 1's. Ready? Pause the video and come back.
And I'll give you the answer in 3, 2, 1. It was only that last state before I was at state 2. I had a 1 and I went to 0.
The only change we made is, I crossed this off and I say, bloop, 1. Now I stay in state 2 and I continue to output 1 as long as I keep getting 1's.
That very simple change makes the change semantically and what that circuit is going to be doing for me. Pretty cool, right? Good stuff, easy. So here's the general model for a synchronous system.
I've got this loop. That same picture you saw before is here. It's right here. That's the same picture you saw before.
It's clocked, I've got some stuff. And the feedback is only within that system. But you can imagine that following up with another series of what it's calculating, what it's doing.
And here's the fun thing. You could have optional feedback from this state back in there, which means this combinational logic is not only knowing the next state but the state after that too.
That's fine. You can have that feedback as well. And you can imagine many, many more of these with a lot more lines feeding back to this very powerful system, doing something very complex.
That's it, synchronous digital systems. This is what we're trying to say and this is the general structure for that. Collections of CL blocks, separated by registers, I said that.
They may be back to back or the CL might be back to back as well. Feedback is optional. You don't have to have the feedback at all.
And the clock signal keeps that whole chugging through in that way. I love it. In a big picture, this is what we're trying to teach you in this series of lectures.
We're trying to build a system. In that system, we're going to have data path and control. We're going to see that in later lectures that are dedicated to data path and control.
Here, we're just kind of talking about what happens in the control world. We've talked about state registers. We've done that already. Combinational logic is the next lecture.
State registers, you have the register. We haven't really talked about how to build the logic in detail. That's also the next lecture.
And how to put that as part of switching networks is all part of that next lecture. So we've kind of done in this series of lectures, this in the next one.
We're going to probably do a little bit of this, a little bit of this in the fourth lecture.
And then put these together in the series of lectures after that to be able to build a working RISC V system that can interpret all the RISC V machine code we've been producing from our compiler, assembler, and linker.
In summary, we're at the end of this series. State elements are used to build memories. We saw that. You can build a register from a flip-flop.
From a little teeny baby flip-flop, you can build a register. From that register, you can think of that as building memory. We haven't talked about that.
But we can talk about that a little bit later when we talk about how to build some of these elements. But the same idea, same idea.
All you have to do is be able to say, rather than one register, which of these kind of small registers am I going to write to.
That's, in a way, all that memory is, is telling which of these registers am I writing to? Think of each memory as just a log.
A lot of these registers that each have an address. I want to change that one. Each one of these is just a register at the lowest level.
State elements also help control the flow of information. Otherwise the combinational logic circuit would just have infinite feedback if it's too fast.
You have to kind of slow down so it's part of the heartbeat of the system. You know that we use D flip-flops to build registers.
Clocks tell us if we clock these flip-flops, the they're going to grow at a kind of cha-chunk, cha-chunk, cha-chunk in my pipeline system, would love that.
And I've mentioned even pipeline for a faster pipeline, a long delay combinational logic. Break them into pieces, pipeline it to have a faster clock. We can do that, smaller clock period, we love that.
And they're extremely useful. You're going to see them a lot of classes. Finite state machines are really powerful ideas. You'll see them in 151A, 152, 164, 172, lots.
You remember I was talking about the language as parsing languages? I'm using 164 speak.
If we think about 164, the compiler class in some sense in programming systems, we'll teach you how to use a flip-flop to be able to parse a language and a finite state machine — not a flip-flop, but a finite state machine, to be able to parse a language.
This finite state machine parses it and is able to receive, and navigate, and decode this particular language. So we can use finite state machines in many different ways.
We're all done. See you at the next lecture.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.