Finite-State Machines
A Finite State Machine is a machine with a finite number of states 💀. FSMs are a way of thinking about a process where:
- There is a series of inputs.
- We need to produce a series of outputs.
- The state store some information.
- The inputs can change the state and the outputs.
FSMs. come up all the time in programming and hardware design. They're great for controlling single multiple-step procedures.
Take for example, a ceiling fan. Its' states can be off, high, medium, and low. The input is the chain and the output is the motor. When you pull the chain, it changes state.
At any point in time, the input (chain) can be either pulled or not-pulled.
This is the state transition diagram.
We can represent this with... A TRUTH TABLE!!! (and store the states in a latch)
But... we need bits. so let off mean 00, high mean 01, med mean 10, low mean 11, 0 mean not pulling, and 1 means pulling.
Now, we can do two K-maps to find an optimal circuit because we need to split each bit up.
We will store the previous state in registers or in programming, use if's and switches.
For the outputs, our fan controller has to control the motor. We can make a table showing the output(s) for each state.
We can now represent our outputs in the state machine, make a table, get k-maps, and make circuits.
This is a sequential circuit since the state changes over time. But the state transition and output tables are just combinational. Here is a general organization of any Moore FSM circuit:
Creating a State Machine
- Understand the problem.
- Represent all possible states and transitions.
- Encode the states.
- Implement the machine.
Let's do another example. Let's take an espresso machine where each espresso costs 15¢ 💀. The machine takes 5¢ and 10¢. It also gives no change back.
Let's make a FSM and table.
Encode the states.
And do some K-map magic! Also, make the circuit.
Combine everything together.
