# Lab 4: Finite State Machine Pattern Detection

CS 3410 Spring 2017

**Due:** Show your completed FSM to your TA before the end of Lab Section.

## Overview

Last week we completed the ALU which had no
state. This week we will be introducing state into our circuit using
Registers.

Remember, you should work in pairs for this lab.

## The Main Event

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.

#### Part A: Finite State Machine

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).

#### Checkoff #1

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.

#### Part B: 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).

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.

#### Checkoff #2

Show your circuit to your TA.