CSE 140L LAB3 Design of Finite State Machines

Fall 2010, Professor C K Cheng. Revised by Vikram Murali.

Due Time : 19th November 2010.


- Learn how to use VHDL to design a finite state machine. 
- Learn how to use schematic capture to design a finite state machine. 
- Understand that a FSM can be implemented with digital logic, and also withVHDL. 
- Learn how to use the FPGA to demonstrate your FSMs through the outputs and through the monitor connection. 
- Learn the difference between Mealy and Moore machines and compare their results with different state assignments. 

Part 1. FSM Design.

In this part you need to build a simple traffic controller. The output is two traffic lights, one for north-south and one for east-west, intersections. The traffic lights should be implemented using the two LED outputs (7 segment displays) on your board as shown in the following figure. 

Two push buttons on your board should be used as the two input "Walk" signals, one for each direction. By default the NS direction is given a higher priority. This means that the green light on the NS direction and the red light on the EW direction should be your default state. The FSM will keep in this default state unless WalkNS = off and WalkEW = on. This input combination will cause the FSM to advance to the next two states where the NS light appears yellow for one clock cycle and then orange for another cycle (while EW continues to be red). Afterward, NS light becomes red and the EW light becomes green. The green light on EW holds for two cycles no matter what the input signals are. After that, if the input signals are still "WalkNS = off and WalkEW = on", the state of the FSM will not change. Otherwise, the yellow light on EW will be on, and after one cycle the orange and then the red light on EW and the green light on NS will also turn on at that time. At that time, the traffic controller is back to the default state. 

As was explained in the discussion session, you will need just 3 Flip Flops to implement this design. It is sufficient to implement only the Moore model for this problem. Go in a step wise manner starting with the state diagram. Remember: the output of the DFFs is the present state bits, and the input will be the next state bits. You also need to incorporate two input pins for the two buttons, and output pins that connect to the segment displays. Turn off all other segments. Your goal will be to figure out the combinational logic for each of the output pins and next state bits. 

Here are the Discussion slides from 11/03/2010.:  Discussion slides  You might find it useful. 

- Draw the FSM of your traffic light controller (Moore).
- Include the state/output table of your traffic light controller 
- Include schematic diagrams of your circuit 
- No need to include functional and timing diagrams. 
- Pretend your system is currently NS = green and EW = red. Someone comes along and presses the EW button. Then someone presses the NS button one second later. Describe what you see and explain why. Can you make the green light on EW hold forever? Explain.


Part 2. The Train! 

You will design the FSM for a train controller, and you will demonstrate your train on the monitor. We will provide the foundation of the code, including the VHDL file that connects to the monitor, as well as other files that you will need. All you need to do is edit the tcontrol.vhdl file to introduce proper state transitions as per your state machine to implement your control circuitry. 

The basic description of your train is as follows: You have two trains going clockwise on two separate tracks, except for a shared track at the bottom. When train A occupies the shared track, then B obviously cannot go, and vice versa. 

Therefore, you will be designing the control system for the trains. You will have four inputs - sensors 1, 2, 3, and 4. Each of these sensors returns a 0 if the train is far away or a 1 if the train is close. You will also have four outputs - SW1 and SW2, and DirA and DirB. SW1 and SW2 are the switch controls that determine which track the shared track is connected to. A value of 0 sets the track for Train A, the outer track and a value of 1 sets the track for Train B, the inner track. In addition, DirA and DirB control whether or not the train goes. For example, when DirA = (00), Train A will stop, and when DirA = (10), Train A will go. Likewise, DirB controls the motion of Train B with the same code. A value of (01) causes the train to reverse.                                                     

From these 4 inputs and 4 outputs, we design the control system ensuring that the two trains never collide. Thus, the way this works is that when both trains are choo-chooing on the outside of the tracks, all four sensors will be 0. One train will eventually hit their respective sensor however (sensor 4 for A, 3 for B). When this happens, this means that that train now is in the shared track. The switches need to be changed so that the switches are connected to that train's track. Eventually the other train will try to get in on the shared track. The sensor will see this and should stop the train from moving. When the first train goes past the 2nd sensor (S1 or S2), that means that the train is now past the shared track. The stopped train can now proceed. Train A has priority over Train B, so if both trains hit S4 and S3 at the same time, Train A would get to go. 

You will be designing this control system in a step-by-step manner. The first thing you will draw out is the Finite State Diagram (Moore). Be sure to consider all possible input combinations that can occur from each state you are in, while drawing the diagram. This will be a good thinking exercise. To reiterate, your aim is to guard the shared portion of the track and prevent multiple entries into it. Then you will implement this in VHDL. We will give you the framework, so all you need to do is fill in the state transition and the output logic. You will need to demonstrate this lab as usual to us during OH. 

The zip file is here: Train Files for DE1 board and Train Files for DE2 board. Unzip it and you will see the vhdl files that we have given you. You will want to open up tcontrol.vhdl, as that is what you need to edit. Follow along with the comments we added in tcontrol so that you can see what you need to do. Though there are some state names in the tcontrol.vhdl file, feel free to change them. You may also choose to use all four sensor inputs to do all your transitions to be systematic. But there is no hard and fast rule. The VHDL file only gives you a sample of how to do things. 

There are two parts that you will modify: the state transitions part, and the output part. Once you are done with that, proceed to compile and program, like any other project. After that, connect your board to the monitor and verify that the output looks good. We have included a video file of what the mirror image of the output should look like here . 

VHDL Tutorial - this tutorial is pretty good for VHDL. While you probably do not really need to go through it, some of you might be more interested. The edits you have to make will be pretty easy, assuming you have some programming experience. There are many tutorials out there that you can search for. This class is not a VHDL design class, but at the least you should be able to look at a fairly simple VHDL file and have a good idea of what it is doing. For kicks, you can take a look at the VHDL for train.vhd. It controls the monitor outputs. You can see how much more complicated it is for the FPGA to display even simple images on the screen.

You must also control the speed of your train with the switches. Demonstrate even this to us. Switch SW0 and SW1 control the speed of one train, SW2 and SW3 control the speed of the other train! (Here SW 0 to SW 3 mean the switches on your board). 

- Draw the FSM of your train controller 
- Include the VHDL code of your train 
- Write a 1/2 page (more if you want) description of what your VHDL code is doing for tcontrol. Start from the top and go towards the end. Convince us that you know what each major segment of the VHDL is doing. As we already know, the major segments are the ENTITY part, the ARCHITECTURE PART, the "PROCESS (clock) part", and the "WITH state SELECT" part. (This must be easy as Each of these was already discussed in detail in the discussion class). Relate the FSM with the VHDL code by explaining how the VHDL implements the FSM you came up with. 
-Let's have some fun with our train. Switch 1 and 2 are set incorrectly so that the incoming trains will derail. Try it! Describe what happens. 

BONUS POINTS: for 5 bonus points, demonstrate for us some wacky or interesting train pattern. Vary the speeds or change the outputs, states, etc. See what you can do! Make the trains go in the reverse directions. Close calls are always fun... things to try including: reversing Train B onto A and seeing what happens, or doing head-on collisions, etc. You can get B onto A's track or vice versa, or you can do funny train patterns. Have fun and be creative!! Note, for this, the best advice I have is to try weird things, a lot of times your trains will halt, or get stuck, so try some other combination or vary the speeds to get interesting situations. (The reason this happens is that your states might no longer make sense, such as the case when both A and B are on the same track, and one of the trains hits a sensor. You can fix this by adding the correct states, or you can try varying the speeds so that one train goes way faster than the other, ends up on the same track, and then rams the other train (before your train controller realizing something is wrong and freezing your trains). This one is for you guys to have fun and try various things, so don't worry about making a system that actually is correct!. It is fine if the trains are still no longer running on the tracks. But try to explain to us what is happening. 

Part3 : Sequence Detector :

Design a simple sequence detector to output a 1 whenever a combination of 0110 is encountered in the input sequence. Give your inputs using push button switches and implement this problem statement as both Mealy and Moore machines in VHDL. Since you already know the framework, we are not going to give you any files here. So again : You need to make your state machines for both Mealy and Moore models for this detector, implement them in VHDL (Verilog also very much acceptable) and run it on Quartus, program it on your board and show us that and how it works. Please make sure your report contains :

- Your Mealy and Moore state machines.
- Include your State transition tables. 
- VHDL/Verilog code for the sequence detector (both Mealy and Moore).
- Mention the differences observed between the two models. Which do you think is better and why ? Explain.
- Design the circuit using logic mininisation method. Get the final implementation on paper (like problem 1). No need to use the board! Now compare both methods. Do you see how much more comfortable using HDL is ?


You will need to demonstrate your project to a lab TA. Please look at the office hours for when we are available. We will be using sign up sheets again. But we will let you know time frames and other stuff in due course of time. For your demonstration, you will need to demonstrate all three parts. You can bring your laptop with your FPGA board to us and program the FPGA board in between demonstrations. If something doesn't work correctly, then please go back and fix it. 

Report Instructions

Your lab report should include: 

- Title page, which contains Names and PID of students, due date, title of lab, and brief description of each person's contribution. 
- Part 1 - everything that was listed 
- Part 2 - everything that was listed 
- Part 3 - everything that was listed 

Here are the Discussion slides from 11/10/2010. This will give you a summary of the assignment :  Discussion2 slides  . Just Keep in mind whatever we discussed.


30% of your grade will be from the demonstration. The other 70% will be in your report and the answers you gave to our questions and how complete you sounded in them. All the best!!