Lab 2 - Finite State Machine Pattern Detection
CS3410 Spring 2015
Due in class
Please submit required documents to CMS
Overviews
Last week we completed the ALU which had no state. This week we will be introducing state into our circuit using Registers.
Your task
Your task is to implement a finite state machine which detects the first occurrence of the string "101" in any given binary input string. It must stop at the last state. For example, a given input would be 111010010001.
Part 1a: Finite State Machine
Draw out a Mealy machine FSM that detects the first occurrence of "101" in any binary string on paper. Additionally, draw the truth table for your FSM. The inputs are a character in your binary string and your current state. You should output a 1 if you are in the final state, 0 otherwise.
| Show your Mealy Machine and your Truth Table to your TA. |
Part 1b: Implement the circuit!
Implement your finite state machine in Logisim. You should use registers to keep track of state (Hint: The value in the register is the state you are currently in.) The value in the register should not change after you have reached the final state. Use the truth table you created to implement your circuit (You can use the Analyze Circuit feature under the Project tab in Logisim to simplify your circuit.) The input to your circuit should be a 1-bit input. You can test your circuit by changing the input from 0 to 1 and vice versa.
Input: 1-bit character, 0 or 1
Output: 1 if in final state, 0 otherwise.
| Show your circuit to your TA. |
Part 2a: Adding Complexity
Now that you've correctly implemented the FSM, draw out a new finite state machine that detects the string "101" twice in a binary string and then stops. This FSM should be similar to the previous one. Also, draw the corresponding truth table for this circuit.
Part 2b: Implement the circuit!
Implement the circuit in Logisim. Make sure to use the correct number of bits for your registers to reflect the new FSM.
The Register & Clock
Register: Since we will need to keep track of several different states, a register should be used to hold the value corresponding to the current state.
Clock: In order to maintain or change the register's state, you can put a Logisim "Clock" into your circuit and set Logisim to toggle the clock one step at a time, or automatically at a set frequency. You should use a single clock for your entire circuit.
What to Submit
Submit a single Logisim project file containing all of your circuits. There should be one top-level circuit named "FSM 1". If you did the optional part 2, there should be two top-level circuits "FSM 1" and "FSM 2".