**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".