Lab 2 - Finite State Machine Pattern Detection

CS3410 Spring 2014

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. Get both of these checked off from a TA before you proceed to the next part.  The inputs are your a character in your binary string and your current state. You should output a 1 if you are in the final state, 0 otherwise.  

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. (hint: you can use the Combinational Analysis feature 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 string

Output: should output 1 if we are in our final state, 0 otherwise. 

Get this checked off from a 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. 

FSM

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. Get this checked off.

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 two top-level circuits named "FSM A" and "FSM B".