Lab3Tutorial

Lab3 Tutorial : a simple pattern recognizer design

Design Specification

    The pattern recognizer in the tutorial is a state machine with one-bit input, X, and one-bit output, Z.
    Whenever the input sequence X(t-2,t-1, t) matches 110 or 101, the output Z is 1.
    Otherwise, the output is 0.

Step by Step Tutorial ( A Mealy Machine Implementation )

1. Design the state diagram

2. Input the state diagram into StateCAD

3. Generate the VHDL program

4. Add the VHDL program to Xilinx ISE Project

5. Generate the layout of the design by FPGA floorplanner

6. Timing simulation

7. Manually assign state encodings

1. Design the state diagram

The state diagram of the machine is as follows.

There are four states, S0, S1, S2, and S3, in the diagram. In order to detect a pattern of 110 and 101, the machine needs to memorize the sequence 11 and 10 in the input, which derives the states S2 and S3 in the diagram. Then in order to find the input sequence 11 and 10, the machine needs to memorize the input 1, which gives the state S1. State S0 means the machine does not find any (partial) match with the two patterns. S0 is also the initial state.

We then figure out what are the transitions between the states. For each state, the machine decides what the next state is based on the current input X. For example, if the current state is S3 and the current input is 1, the next state is S1. The transition from S3 to S1 also means the machine detects a pattern 101, which should give the output 1. Note that when input is 1, the next state for S2 is S2, not S1. ( What happens if the next state of S2 is S1 when input is 1? Would it be able to identify a match in 1110?)

2. Input the state diagram into StateCAD

2.1 Create a new design:

In Xilinx Project Navigator, click on File->New Project.
Make sure to select HDL in the Top Level Module Type drop-down list.

2.2 Create new state diagram source:

In Xilinx Project Navigator, click on Project-> New source. In the pop-up New Source window, select State Diagram from the list on the left, and put in the name of the diagram, e.g. mealy.dia, in the file name box. Click next and then finish in the next dialog.
Then the StateCAD with an empty design will be opened as follows:

2.3 Build the state diagram:

2.3.1 We use the state machine wizard to build the state diagram.
Click the state machine wizard button , the following window appears:

Change the number of states to 4. Click on next.

2.3.2 The reset setting window should pop up.
Make sure you check the Asynchronous reset mode, which will make the design simple. Click Next and then Finish.

2.3.3 A green line box will appear in the StateCAD window. Click to get the following state diagram.

2.4 Edit the state diagram according to our design:

2.4.1 To change the state information, double click on the state circle.
For example, double click the STATE1 circle, and the following window pops up.

We can change the name of the state in the State Name box. Output of the state can be described in the output window (for Moore machines). For the Mealy machine, there is no output at the states. Click OK when we finish modifying the state information.

2.4.2 Click the Add Transition button on the left side to add transitions.
When adding a transition, double click on the edge of the starting state, then double click on the ending
state.

2.4.3 To change the transition information, double click the transition edge.
The following window should appear.

We can input the condition for the transition in the Condition window (xin = '0' is shown, in which xin is the input signal X. X is a reserved word. So we use xin here). Output on the transition can be specified in the Outputs window. (Z = '1' is shown). Click OK when done.

2.5 The final Mealy machine state diagram will look like the following:

3. Generate the VHDL program

3.1 Configure the VHDL Compiler:
Click on Options->Configuration. The following window appears.

Make sure to
1) check Enumerated in the State Assignment;
2) highlight VHDL in the Language list;
3) highlight IEEE 1076 in Language Vendor.
Click OK to close the window and then save the state diagram.

3.2 Generate the VHDL codes:

Click the compile button . If the compile is successful, the following dialog appears.

Click Close and the following window with the VHDL code will appear.
The VHDL code is stored in a file MEALY.vhd in the current project directory.

4. Add the VHDL program to Xilinx ISE Project

Add the VHDL source file generated by StateCAD (MEALY.vhd) into your project.
In Xilinx ISE, click Project->Add source. Highlight the MEALY.vhd file, then click open.
The following window appears.

Highlight VHDL Design File and click OK.

Now the VHDL design of the state machine should be include in the project as follows:

5. Generate the layout of the design by FPGA floorplanner

5.1 Highlight MEALY.vhd in the source window. In the Process View window,
double click View/Edit Placed Design (Floorplanner) under Implement Design->Place & Route.

The Xilinx tool will go through synthesis, translate, map, and place & route. When the implementation is done, the floorplanner window shows up with the placed design as follows:

Zoom in to check the design. Note that the implementation consists of 2 flip-flops (green rectangles), and 1 combinatorial logic units (green trapezoids).

5.2 Check the state encoding and logic block usage in the synthesis report:

Inn the Process View window, double click View Synthesis Report under Synthesize-XST. The report
should be shown. Scroll down to "State Encoding" and "Device utilization summary" and check how many of each elements are used. Note that the numbers should be consistent with that in the floorplanner view.

6. Timing simulation

This step is similar to what we have done in Lab 1 and 2. Create a test bench, then simulate it in the ModelSim. Make sure to set the RESET signal as 1 for 1 or two clock cycles in the begin of the simulation to initialize the state machine.

7. Manually assign state encodings

7.1 Modify the VHDL code to assign different state encodings:
Double click the VHDL source file, MEALY.vhd, in the Sources in Project window.

Insert two lines of codes into the VHDL source file, right after the state definition line.

The VHDL codes looks like the following:

ARCHITECTURE BEHAVIOR OF MEALY IS
TYPE type_sreg IS (s0,s1,s2,s3);
attribute enum_encoding : string;
attribute enum_encoding of type_sreg : type is "0001 0010 0100 1000";
SIGNAL sreg, next_sreg : type_sreg;
BEGIN
...

The two red lines are inserted. The green lines are original.
In this modified encoding, state s0 is encoded as 0001; s1 is 0010; s2 is 0100; s3 is 1000.
Remember to save as another name after modification.

7.2 Modify the XST synthesis properties:

In the Process View window, right click on the Synthesis-XST, click on the Properties (last item in the right-click menu). A window pops up as follows

In the Synthesis Options, change the Optimization Goal to Area (default is Speed).

In the HDL Options, change the FSM Encoding Algorithm to User (default is Auto).

Click OK to close the window.

7.3 Implement the state machine with different state encodings.
Check the synthesis report to compare the device utilizations.