CS 3410 Fall 2018
Due: Sunday, September 30th before 11:59pm. Show your completed FSM to your TA before the end of Lab Section.
Your task is to implement a finite state machine which detects each occurrence of the string "101" in any given binary input string. For example, a given input would be 1110101001, to which the FSM should output 0000101000.
Draw out a Mealy machine FSM that detects each occurrence of "101" in any binary string on paper; that is, your FSM should output "1" if and only if the last three symbols read are equal to "101". Next draw the truth table for your FSM: The inputs are a single input character and your current state, and the outputs are the single character output of the FSM and the next state.
Finally, write out the Output and Next State boolean equations (derived from your truth table).
Show the state transition diagram of your Mealy Machine, your Truth Table, and the boolean equations for both the outputs and the next states to your TA.
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).
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. On each clock cycle, you will use this input along with the current state of the register to determine the 1-bit output and the next state of the register.
You can test your circuit by changing the input from 0 to 1 and vice versa.
Show your circuit to your TA.