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


P6: finite state machines (FSM)


Resources in lectures and labs: L6.1, Lab6 on the design of the classroom Light control, L6.2.

Example project: 16-key matrix keypad encoder type MM74C922

1. Specifications

In the first stage of project designing, customers and company staff meet together to discuss which are the features of the product or project under design. We do it in class investing all the necessary time to fully understand how does the system work.


Fig 1. Symbol (Visio)of the Matrix_encoder_16key to be designed using a FSM architecture. This circuit can be compared to the standard Enc_16_4 studied as a combinational block in P2.

Some theory on how a matrix keyboard operates. In this Proteus simulation there is a 16-key matrix keyboard component. As recommended in the classic chip MM74C922 (see the Fig. 2), a CLK frequency 200 Hz may be a convenient for scanning keys (use a  COSC = 330 nF). 

keyboard freq
Fig 2. Study and adaptation of the MM74C922 and how the scanning frequency can be fixed for this chip when using its internal oscillator. This is another Proteus simulation of the complete MM74C922 chip running a a 16-key matrix encoder.

Therefore, the circuit to invent has to be similar to Fig. 3. A power-ON reset can be used to initialise the FSM.

Fig 3. Circuit to scan rows and read columns. From the chip example above, a convenient scanning frequency may be about 200 Hz.  

Propose a state diagram to figure out how the matrix scanner works on the basis of a FSM. Fig. 4 shows an example considering the signal Row Scanning Enabled (RSE) derived from Columns(3..0) which is '1' when no keys are pressed. In each state all the output values must be set, and for clarity reasons it is indicated as (*) to be represented in another sheet op paper. Discuss which may be the output values in each state.

State diagram

Fig 4. Architecture of the 16-key matrix keyboard encoder FSM and some other planning ideas (click to zoom).

Draw an example of a timing diagram as in Fig. 5 because precisely in this problem is not easy to comprehend which kind of signals are intervening in the system and when. Do it perhaps side by side with the state diagram for better understanding.

timing diagram
Fig 5. Discuss an example of a timing diagram imagining the Columns(3..0) vector values that will be read from the keypad. Which may be an initialisation? Watch the rec. because this time, a video sequence is much better than a final photograph.


Prior to attempting the design of the matrix encoder proposed here, run several of the following tutorials to get in touch with the concepts associated to the FSM architecture and the proposed CSD FSM design procedure.

Other similar FSM design projectsD_FF, JK_FF, T_FF, LED bicycle torch, low-pass filter and synchroniser (debouncing_filter, traffic light controller, 1-digit BCD synchronous up counter Counter_BCD_1digit for a few number of states (counters plan X: FSM strategy, state enumeration), LED sequencer (discussion).  


2. Planning

Devising a strategy to solve the problem. This is the engineer's job and the most difficult task. Generally, many teams intervene planning top-down strategies to conceive how modules and components can be assembled and interconnected. As you have seen in the many projects solved hitherto, our plan must be in the end a detailed "camera-ready" schematic for an immediate VHDL translation when starting development. We follow always this CSD FSM design procedure.

Let's implement the FSM capable of solving the state diagram above.



Fig 6. This is the adaptation of the general FSM architecture to the problem.

state register
Fig 7. Draw the state register for this application based on D_FF. For instance, when coding in binary sequenctial only 3 D_FF are required, but 8 D_FF wehn coding states in one-hot. In this way the system has a memory cell to "remember" its current internal state.
CC2 discussion and truth table

Fig 8. The CC2 truth table discussion. It is about determining which outputs are required in each state.

Continue with the translation of the CC2 truth table using a behavioural interpretation based on flowcharts or ASM (algorithmic state machine) diagrams. This plan B is referred as the number 8 in the list.

Flowchart 2
Fig 9. Discuss the translation of the CC2 truth table into a flowchart.
CC1 discussion

Fig 10. Example of CC1 discussion. All the state transitions must be considered in the table.

Continue with the translation of the CC1 truth table using a behavioural interpretation based on flowcharts or ASM (algorithmic state machine) diagrams.

CC1 flowchart
Fig 11. Discuss the translation of the CC1 truth table into a flowchart.


3. Development

Carrying out the plan usually is the job of an engineer or better a technician when planning phase is complete. In the same way that an architect is not required every day in the construction site.

Here we have to write the previous schematics, truth tables and flowcharts in a single VHDL source file like this Matrix_encoder_16key.vhd based on our CSD style. Start a new project using an EDA tool and synthesise a circuit for a specific target CPLD or FPGA target chip.

In our project, the RTL view must show the main details of the FSM. Print and comment the schematic indicating the main components CC1, CC2 and the state register.  Be aware that this schematic depends on the EDA tool where each one has its own style for representing the ideal circuits interpreted from VHDL files.

RTL view 

Fig 12. Example of an RTL schematic (using Quartus Prime).

Fig. 13 is an example of state diagram as drawn by Synplify Pro Lattice edition that can be inspected from the RTL view. Try other tools such as Intel Quartus Prime.

State diagram

Fig 13. Example of state diagram epresented automatically by the EDA tool.

And below in Fig. 14 there is the default encoding (onehot), which means that 8 D_FF are required.

state encoding

Fig 14. Encoding states in this application.

Below in Fig. 15 is the technology view of the circuit being synthesised, which give you an idea of the design complexity and resources (instances) used. Count and check that the number of registers D_FF is what is expected accordingly to the chosen state encoding (binary sequential, Gray, one-hot). 

tech view

Fig 15. Example of a technology view (click to zoom).

Check the resources used in the project summary: chip pins, LUT's, slices, registers D_FF, etc.


4. Testing  (functional)

Examining test results, engineers must look back to see whether the device comply with the specifications; and forward to see which modifications may achieve better performance. Engineers must be able to organise test procedures to verify that the system works as expected before the next prototyping stage in the laboratory. 

In Fig. 16 is represented the VHLD test bench fixture for testing this application.

Testbench fxture
  Fig 16. Testbench schematic. It is generated automatically as a template from the EDA tool project navigator and then the user can add the stimulus from the timing diagram in Fig. 4 and the CLK process.  

Perform a functional simulation using a VHDL project simulator to verify that the device operates like expected in the initial timing diagram sketch in Fig. 4. This is an example matrix_encoder_16key_tb.vhd testbench file that can be used to obtain the results in Fig. 17. Modify the stimulus process to include other inputs. The circuit must work correctly for the 16 keys.

  Fig 17. Functional simulation with annotations and discussion to determine whether the circuit works as expected. 


5. Testing  (gate-level)

Perform a gate level simulation to measure the propagation time from CLK to output (tCO) for a given technology. For instance, Lattice ispMACH4128V CPLD, Xilinx Spartan-3E XC3S500E-FG320 or Intel MAX II EPM2210F324C3. Select a convenient CLK rising edge transition and measure how long does it take to have stable outputs.

Gate level analysis
Fig 18. Example of gate level simulations at a given CLK transition.

Using the timer analyser tool, we can determine the worst-case scenario, thus, determine the maximum processing speed of this circuit. A question equivalent to asking how fast can be scanning and encoding the keypad (in case of not having parasitic effects and key bouncing problems)?

CLK to Output Fig 19. The timing analyser tool can be used to measure the maximum speed of the system CLK:

CLKmax = 1/tP
tP   = tCO (the D_FF of the state register) + tPCC (CC2)

In this example, using Cyclone IV, tCO = 8.9 ns; 
fCLK max = 112.35 MHz

Here, if we like to go further, we can take advantage of the easiness in using EDA tools. For instance, we can compare circuit realisations and answer questions such:

1) What circuit is faster, the one using onehot or the one using a sequential-binary encoding (CC2 combinational blocks are different)?

2) What circuit uses more chip resources? Such answer can be deduced inspecting project summaries.

3) What technology FPGA, CPLD is faster solving the project?


6. Report

By now, you know very well how document your project and what is assessed. Therefore, try to self-assess your project using the rubric discussed in class. It's interesting to look back and annotate remarkable questions that were raised while working on the projects (thanks to students deep engagement and discussion), that in the end can be used to generate a higher quality device (advanced project):

- Why the system gets stuck when the matrix CLK frequency is too high?
- What can be done to prevent the hanging of the system and how it can recover automatically to a known state?
- Which is the advantage of using debouncing filters in each column?
- What can be done to design a system with all the outputs fully synchronised?
- What can be done to read/sample the columns on the rising edge of the CLK, so that they are going to be kept saved until the next rising edge?


7. Prototyping

Use training boards and perform laboratory measurements to verify how the circuit works.

It is interesting in order to see how the circuit works, to use some extra LED to visualise signals and data, which implies building a top schematic containing for instance a HEX_7SEG_DECODER to represent the 16 hexadecimal symbols. This is the top schematic to be implemented in the HWDLC4128V board (schematic) populated with a ispMACH4128V CPLD from Lattice Semiconductor. And this is the RTL view interpreted by Synplify Pro synthesiser tool.

Symbol TOP

Fig 20. The top schematic symbol that includes some extra ports for debugging purposes generated by the ispLEVER Classic. This is the complete zipped project where you can examine the top VHDL file.

Once the development board has been chosen, we have to assign PLD pins to inputs and outputs. This task is conveniently done using the spreadsheet "Constrain Editor", as represented in Fig. 21.

pin assignments

Fig 21. Using the Constrain Editor for pin assignments available through the ispLEVER Classic project navigator.  

So that the final configuration file *.JED can be downloaded into the chip. This task is performed as shown in Fig. 22, by a chip programmer tool like the ispVM System from Lattice Semiconductor.


Fig 22. This is the ispVM System tool to be used for chip programing. The development board is connected to the computer using a simple USB interface and the tool scans the hardware to detect which is the chip populating the board. Clicking GO the PLD is programmed in a few seconds.

For sPLD or CPLD technologies, the programming of the macrocells is permanent and only can be erased reprogramming he chip another time with the same or a different configuration.

For FPGA technologies, the programming of the LUT (look-up tables) is volatile, and the RAM is erased once unplugged from the power supply. Thus, usually boards contain a supportive EEPROM memory to save the FPGA configuration rewriting the RAM every time the board is powered.  


Finally, we can experiment with the prototype represented in Fig. 23 in order to see whether all the specifications has been met, as shown in this recording. Many times the real circuit, as it was in the simulations, does not fully work, and so, a design loop (Visio) must be started again to modify schematics, rewrite VHDL code and synthesise and program again.


Fig 23. This is a picture of the scanning keyboard running on a Lattice ispMACH4128V CPLD target chip (click to zoom).


Other similar projects on sequential circuits

- This project is complemented using materials from P8 on the design of the CLK_Generator component so that the CLK frequency can be derived from a quartz crystal oscillator populating the training board.

- This is an example of product enhancement: 16-key matrix encoder with handshake signals.


Other materials of interest

- General ideas on FSM. (AMD, 1993).

- An application note on how to design safe FSM, the concept to prevent that a machine "hangs" being unable to get back to a valid state.

- At this stage it is recommended to read books in digital electronics to see how the stuff  in sequential systems is explained and which are the differences with respect the methodologies in CSD.

- Here you are a commercial chip from SILEGO, a company specialised in "asynchronous" state machines (ASM) architectures  which is very similar to the system we are dealing with.  Naturally, we can implement the functionality of the chip in our PIC or Atmel microcontroller in the project P12 as an example of microcontroller application. 


Fig 24. Block diagram of the SILEGO GreenPAK chip that performs the I2C interface between a keypad and a microcontroller.