Lab #12: Finite State Machines (Sequence Detector)Revised 4/14/2009OverviewA finite state machine is a digital system that can be characterized by a finite number of states, with transitions between states controlled by the present state and current input values. The output of the FSM will be a function of the current inputs and present state.In this lab you will design a finite state machine whose output will only be based on the present state. A sequence of data (one bit) will be the input into the machine. If the sequence “1101” occurs, the output will be a 1. Otherwise the output will be a 0. Sequences can overlap – the 1 indicating the last bit of 1101 can also be the first bit of a trailing sequence. The FSM will be designed using the standard process of designing synchronous sequential digital systems. The finite state machine should be designed as follows:Registers are a storage device for data. Registers are used to hold the values of the states of the machine.When writing new code, it is easy to use versions from previous projects, by adding a copy of a source to a project. Make certain to add a copy and not just add a previous source to anew project – this will protect the original source from getting changed.Before beginning this lab, you should:• Be well practiced in the design ofvarious flipflop circuits.• Be familiar with the Xilinx WebPackdesign tool suite.After completing this lab, you should:• Understand the design and function ofsequential building blocks.This lab exercise requires:• A Digilab BaSYS board• A PC running the Xilinx ISE CAD toolsLab #12 FSM Sequence DetectorBackgroundThe canonical model for a synchronous sequential system is shown below. The present input, w, is fed into a combinational network, C1, which is the input into a series of FFs. The FFs are fed back through the combinational network as inputs, along with the input, w, as inputs to determinethe next state of the registers. The system has two sets of outputs, the states and the output, z.Notice in the diagram above the blue line, from the input w, feeding into the second set of combinational logic, C2. Two different types of synchronous sequential machines exist. Moore machines have outputs that are only dependent on the present state (the blue line is not necessaryfor this type of system). Alternatively, systems can be designed with the outputs dependent on the present state as well as the present input, Mealy machines. Here the blue line would be used. In this week’s lab, we are designing the Moore type of FSM. Mealy machines typically allow forless states than Moore machines.We want to design a sequence detector that will output a 1 if the sequence “1101” is detected in the data coming in.))In the system shown above, a 1 would be output during the next clock cycle.Lab #12 FSM Sequence DetectorDesignTo design the system, we must decide what needs to be remembered using a bubble diagram. States will be used to indicate what needs to be remembered.S0 will represent the first state – the initial state. The output, z will be 0 in S0.From S0, if w = 0, no need to remember it since we are looking for the sequence 1101. The first bit needs to be a 1. We will stay in state S0 until a 1 is received. If w=1, we need to remember that so we will go to a new state, S1.S1 will represent that a “1” has been received. The output, z, will be 0 in state S1.From S1, if w=0, go back to state S0. We were looking for 11 as the first two bits, so 10 is not that. From S1, if w=1, we have the first two bits, so we need a new state, S2.S2 represents that “11” has been received. The output, z will be = 0 in state S2.From S2, if w=0, we need a new state, S3. If w=1, go back to state S2, as we have two 11’s in a row.S3 represents that “110” has been received. The output,z, will be 0 in state S3.From state S3, if w=0, go back to state S0. We have 1100 which is not what was desired. If w=1,we have “1101”, the pattern was detected, and we need a new state, S4.S4 represents that “1101” has been detected. The output, z, should equal 1 in state S4.From S4, if w=1, return to S2, as “11” has been detected. If w=0 in state S4, retrun to S0.Below are the diagrams indicating the finite state machine.Lab #12 FSM Sequence DetectorLab #12 FSM Sequence DetectorNext Step in process – Creation of a state table and encodingUsing the Bubble diagram, a state table must be created. Fill in the state table below with the correct data, based on the bubble diagram.InputwPresentstateNextStateOutput0 S00 S10 S20 S30 S41 S01 S11 S21 S31 S4# of FFs needed – If we assume binary encoding, how many FFs are needed to implement the FSM. # of states = _______________________#FF = Log2(#of states) = __________________Write the encodings in the box below for the present state and next state based on binary encoding.InputWPresentstateNextStateOutput0 S00 S10 S20 S30 S41 S01 S11 S21 S31 S4Lab #12 FSM Sequence DetectorNext State and Output EquationsWrite the equations for the inputs of each of the FFs. Make Kmaps, enter the data and determinethe minimum SOP equation. This would be the C1 combinational logic in the canonical model.What is the equation for the output? This would be the C2 combinational logic in the canonical model.Designing the FSMThe files for the lab are being emailed as a zip file. Look at the code for the sequence_detector and note how a case statement was used for the C1 modules.Run the project and show the TA how the states are being implemented using LED[3:1] and the output is on LED[0]. The inputs are btn[1] for a 1 input and btn[0] for a 0 input. Test the FSM to make certain it works.Lab #12 FSM Sequence