At the heart of digital design is the Finite State Machine (FSM). In our logic designs, we use them to control data flow and algorithms along with implementing communication protocols.
One of the great things about the PYNQ logictools overlay, which we began to explore in the last PYNQ editon, is that it allows Python developers to access lower level hardware functions including FSM creation.
Just as we can use the logictools overlay for pattern generation and logic analysis, we can also use the logictools overlay to define finite state machines. These FSMs are implemented in the programmable logic, again using Python and WaveDrom.
How the actual finite state machines are implemented in the PL is very interesting. This is done using block RAMs, based from an approach outlined in Xilinx white paper (WP335) written by the legendary Peter Alfke. Using BRAM in this way provides a efficient, high performance and easily modifiable solution. When the block RAM is connected to the Zynq or Zynq MPSoC processing system it means the actual FSM design can be implemented and changed at run time.
To support this run time definition and update the PYNQ framework that provides Python scripts and APIs, configure the BRAM contents to implement the FSM.
All we need to do in our Jupyter notebook is define the FSM using a derivation of the WaveDrom format. We can then use the nine FSM API calls which support creation, loading, execution, and visualization of FSMs.
The hardware implementation is fairly straightforward and all the IP is available in either the standard Vivado IP Library or the PYNQ IP directory provided on GitHub. The current implementation of the FSM provides Moore outputs — that is outputs are a function of the present state.
This means if you want to implement FSM generation in your custom overlay, it can be easily implemented. You can even create a reusable hierarchical block to ease the implementation in your own overlay project.
In our Jupyter notebook, creating and running a FSM is very simple, again we use a modified WaveDrom JSON format.
In this format, we define the input signal and which corresponding bit is used for that input. We define the output signal and there corresponding output bits as well. To implement the state machine, we need to define the states and the transitions between the states.
Of course, to create the state machine transition table we need to draw a state diagram which shows the each state and the transitions between the them. If you are not familiar with creating state diagrams, you might want to quickly review the Element14 programmable logic short course.
From the state diagram, we are then able to create the transition table. The example below comes with the PYNQ logictools notebook and shows how a grey code counter is implemented.
Once we have described our transition table we can double-check it’s correctness against our original state diagram by asking the Jupyter notebook to draw the state diagram.
In the remainder of this blog, we are going to examine how we can create our own state machine which implements a sequence detector.
Let’s assume we wish to detect the sequence 1101 on a input and allow for overlapping detection.
The state diagram for the detector can be seen below.
To implement this in the PYNQ Z2, we create the following transition table, where the – symbol means we do not care.
The very last line is the reset input, which takes us back to S0.
Using the show_state_diagram, we can see the double check the state diagram is correct against the original design intent.
We can then run the FSM using the FSM API commands.
As you can see, we can quickly and easily implement FSMs using the logictools overlay with python.
This is overlay is a great tool for developing and testing FSMs; of course the real benefit comes from including them within custom overlays. In custom overlays, if we want the determinism and granularity of a state machine and the flexibility offered by using high level languages like Python to determine the behavior at run time, we should be using the FSM generator.