CS 245 Finite State Machine Design
Purpose:
1. Solve some "real-life" problems with state machines.
2. Be able to implement a finite state machine with D FFs and JK FFs.
3. Use CircuitMaker or Digital Works to design and simulate a finite state machine.
Procedure (Part 1):
Refer to the state transition diagram for a subway turnstile:
WALK_THRU
+--------------------------------+
|
|
v
|
+--------+ COIN +--------+ |
| LOCKED |---------> | OPEN |---+
| |
|--------|
| |---+
|CT_PULSE|---+
+--------+ | +--------+
|
^ |
^
|
| |
|
|
+----------+
+----------+
!COIN
!WALK_THRU
This is a Moore machine. The sequence always begins in the "LOCKED" state. If no coin is inserted (!COIN Input), the turnstile remains locked. After a coin is inserted (COIN Input), the turnstile unlocks by going to the "OPEN" state. The "OPEN" state also has an output (CT_PULSE) that sends a "1" to a counter to keep track of how many people have used the subway. If nobody walks through the turnstile (!WALK_THRU Input), it remains open. After someone walks through it (WALK_THRU Input), it goes back to the "LOCKED" state and accepts another coin.
1. Design the state machine using D flip flops.
2. Design the state machine using JK flip flops.
3. Use CircuitMaker or Digital Works to create and simulate the "best" of the two circuits. Verify that your circuit's actual state transition diagram matches the one shown above.
NOTE: Do not design the counter that tracks the number of subway users. Your circuit should only generate the pulse that triggers the counter.
HINTS:
1. Assign a state number to each of the state names, e.g. LOCKED = 0 & OPEN = 1.
2. CT_PULSE is only generated when in state OPEN. It is a "0" when in state LOCKED.
3. There are two inputs: COIN and WALK_THRU. There are four possible combinations of these two inputs, but not all of them make sense. For example, it is not possible to "walk thru" when in state LOCKED. Use "don't cares" for these situations.
Procedure (Part 2):
Refer to the state transition diagram for a simple CPU:
+-------+
| 000 |
+---->|-------|
| |1000000|
| +-------+
| |
| | X=0, X=1
| |
| V
| +-------+
| | 001 |
| |-------|
| |0100000|
| +-------+
| |
| | X=0, X=1
| |
| V
| +-------+
| | 010 |
| |-------|------------------------+
|
|0010000|
|
|
+-------+
|
|
|
|
| | X=0
(ADD)
| X=1 (SUB)
|
|
|
|
V
V
|
+-------+
+-------+
| | 011
|
| 101 |
|
|-------|
|-------|
|
|0001010|
|0000110|
|
+-------+
+-------+
|
|
|
| | X=0,
X=1
| X=0, X=1
|
|
|
|
V
V
|
+-------+
+-------+
| | 100
|
| 110 |
|
|-------|
|-------|
|
|0100001|
|0000001|
|
+-------+
+-------+
|
|
|
| | X=0,
X=1
| X=0, X=1
|
|
|
|
V
V
+---------------------------------------
This is also a Moore machine. It controls a simple CPU that reads data from memory and then either adds it to or subtracts it from some data already in the CPU. If addition is specified, X = 0. If subtraction should be performed, X = 1. Each state shows the state number in the top half of the box, and the outputs in the bottom half of the box.
The procedure always starts at state 000. The outputs in state 000 send an address to memory.
State 001 is always the next state. It brings the data from the specified memory address into an input buffer (temporary holding register).
State 010 always comes after state 001. It moves the data from the input buffer into a data register connected to the add/subtract circuit.
The count sequence from here depends on the value of X. If ADD is specified (X=0), the circuit goes next to state 011. Here the circuit is set up for addition, and the two numbers to be added are put on the adder's inputs. State 100 is next. It puts the result in the output register and then returns to state 000. If SUBTRACT is to be done instead (X=1), the circuit goes from state 010 to state 101. The subtract function is selected, and the two numbers to be subtracted are sent to the subtractor's inputs. Then, state 110 puts the results in the output register and returns to state 000.
1. Design the state machine using D flip flops.
2. Design the state machine using JK flip flops.
3. Use CircuitMaker or Digital Works to create and simulate the "best" of the two circuits. Verify that your circuit's actual state transition diagram matches the one shown above.
NOTE: Do not design the adder, subtractor, or other registers controlled by the state machine. Your circuit must simply generate the seven output bits for each state.
Questions:
What are state machines? How are they different than counters? Where are they used?
What conclusions can you make about the design, and implementation of state machines?
Could either of these circuits been designed as a Mealy machine instead? How would they have been different? Which design would be the "best?"