UPC EETAC Bachelor's Degree in Telecommunications Systems and in Network Engineering EEL

L5.4

Lecture 1

L6.1: Finite State Machine (FSM)

 [P6] Example application: designing toggle flip-flop (T_FF) as FSM

AR1

[22/10]

2.5. Finite State Machine (FSM) architecture.

Most of real-world applications are based on FSM
- Motion control and robotics
- User interfaces
- Traffic control system
- Self-driving cars
- Media players and entertainment devices
- Elevator control systems, washing machines, dishwashers, home appliances
- Vending machines, ATM's, payment processing, etc.
- HVAC (heating, ventilation and air conditioning) and climate control systems
- Transmitters and receivers
- and many more...

2.5.1.Specifications

2.5.1.1. Function table, symbol, state diagram

2.5.1.2. CLK and CD circuits

2.5.1.3. Example of timing diagram

2.5.1.4. Systematic design procedure (pdf). The sequence for designing FSM in our CSD course: 

CSD - P6: FSM design procedure

1. Specifications

a) Draw the project symbol and explain how the circuit works using function tables or similar descriptions.

b) Draw a sketch of timing diagram because in this Chapter 2 representing the system evolving in time is a fundamental idea. Besides, it will be translated as an example stimulus process for testbenching.

2. Planning

c) Infer a state diagram (sometimes it is discussed in specifications because it is a tool of great help to comprehend the project). Do it always in the same way: cycles, states; arrows, state transitions and loops; parenthesis in a different colour indicating outputs for each state.

d) Draw the FSM general architecture.

FSM

Fig. 1. FSM architecture in a single file (plan C1) using up to three processes. Signals future_state and present _state are also named next_state and current_state respectively.

D_FF is the building block acting as state register (r-bit memory cell) to be used with combinational circuits form Chapter 1 to implement finite state machines (FSM). The present_state is updated after the CLK's rising edge. CD = '1' resets the FSM.

e) Adapt the general FSM architecture to your problem and draw the state register based on D_FF. Deduce how many D_FF are required if you are coding states in binary sequential, one-hot or Gray.

f) Write the truth table of CC2 and its equivalent behavioural (plan B) interpretation as a flowchart. CC2 is for calculating outputs, thus, this combinational circuit implements all the signals drawn in parenthesis in the state diagram. 

g) Write the truth table of CC1 and its equivalent behavioural (plan B) interpretation as a flowchart. CC1 is for calculating the next state to go, thus, this combinational circuit is in charge of all the circuit state transitions (arrows).

3. Development

h) Write the VHDL file (plan C1, a single file containing three processes representing the translation of the FSM. State-type signals: state enumeration.

i) Run a project using an EDA synthesis tool for a CPLD or FPGA target chip.

j) Discuss RTL and technology schematics. Check the number of registers D_FF used.

4. Test (functional)

k) Generate the skeleton of the testbench fixture. Translate your initial timing diagram sketch into VHDL stimulus processes. Consider the CLK_period constant and how long the simulation has to run.

l) Simulate the circuit using your VHDL test bench and discuss the results. Represent the waveforms of current_state and next_state signal as well in wave diagrams.

5. Test (gate-level)

m) Simulate the technology circuit (flat vho, sdo or sdf) using your VHDL testbench and discuss results.

n) Using the timing analyser tool, measure tCO and deduce the maximum CLK frequency that can be applied to your design considering a target chip.

6. Prototyping

It is always possible to use any of our lab training boards for CPLD or FPGA to synthesise the circuit and experimenting in the lab using real instrumentations for measurements and characterisation.

7. Report (handwritten) and presentation

Follow usual indications on reporting. It is easy for most circuits to generate more that twelve pictures, sketches, diagrams, computer results, etc. to report perfectly well how the circuit that you have invented is conceived and how does it perform.

Report pictures may be used later as slides for oral presentations and recordings.

Ref. General ideas on designing FSM (Advanced Micro Devices AMD, 1993).

 

2.5.2.Planning

2.5.2.1. Architecture: canonical, synchronous, plan C1: hierarchical, structural in a single VHDL file

Let us introduce the key concept and architecture of finite state machine (FSM) as the standard canonical synchronous sequential system to solve most of applications. In CSD we represent the FSM as hierarchical, three blocks (or processes), hierarchical structure in a single VHDL file: plan C1 (the only circuit in CSD where plan C1 is used for practical reasons).

2.5.2.2. State diagram, and FSM adaptation

2.5.2.3. State register: r-bit memory (D_FF), state encoding (binary sequential, Gray, one-hot, etc.)

2.5.2.4. Output logic (CC2): truth table, behavioural interpretation: flowchart

2.5.2.5. Next state logic (CC1): truth table, behavioural interpretation: flowchart

 

2.5.3. Developing

2.5.3.1. VHDL translation, state enumeration, project location.

2.5.3.2. Synthesis project for a target chip. FSM encoding options

2.5.3.3. Target chip resource usage (D_FF registers)

2.5.3.4. RTL and technology view discussion

2.5.3.5. FSM state diagram discussion

 

2.5.4. Testing (functional)

2.5.4.1. Test-bench fixture schematic and test-bench VHDL file

2.5.4.2. CLK and other signals stimulus processes

2.5.4.3. Functional simulation and wave results discussion

2.5.4.3. Internal signals representation (current_state, next_state)

 

2.5.5. Testing (technology)

2.5.5.1. Gate-level (timing) simulation and results discussion

2.5.5.2. Propagation time CLK to output measurements (tCO). How does a cricuit behave in a given active CLK transition?

2.5.5.3. Timing analyser spreadsheet and measurement of the maximum frequency of operation. What is the worst longuest propagation delay in a given synchronous circuit?

 

2.5.6. Prototyping

Our applications can be put into practice using FPGA traning boards. Example of prototyping are given in LAB6 and LAB7 tutorials.

2.6. Examples of FSM in VHDL: single-file (plan C1) projects

2.6.1. Designing flip-flops as FSM (two-state machines)

We have developed full tutorials on designing basic flip-flops as FSM in VHDL. You ca use these materials for both, comprehending how flip-flops work, and also as introductory examples to FSM design becasue they contain only two states.

2.6.1.1. RS flip-flop (RS_FF is JK_FF never using J = 1; K = 1}

2.6.1.2. D-type (data) flip-flop {D_FF}

2.6.1.3. JK flip-flop {JK_FF}

2.6.1.4. T-type (toggle) flip-flop {T_FF}

 

And now, once considered these simple two-state systems, we can continue examining any other example of FSM application. For instance, before attempting the next class on a 16-key matrix keypad, we can get an idea on a bicycle flashing lamp with a single push-button or LAB6 on classroom luminaries.

 

Exercise: Solve this sequence detector that works sampling continuously a bit stream of data. 

Question

Imagine states labels such: "No_symbols", "One_symbol", etc. No_symbols is the initial state of the FSM where none of three symbols of the right combination has been sampled yet. 

Design and test the full circuit following our FSM procedure.

Additional question: How to modify the state diagram if we impose that Q has to be a pulse of 2·TCLK duration?