Implementing an algorithm by modelling an FSM in an HDL
Required tools
We are going to use Verilog for this project. So, any verilog compiler and simulator should do. Xilinx and ModelSim are really good tools. But since I’m a *nix guy, I’m going to use Icarus Verilog to compile code and gtkwave to view the signal timing diagrams. They are free to use, easy to learn and much more light-weight than other full-fledged options.
Steps to install, setup and use these two tools (iverilog and gtkwave) are explained in another of my article.
Concepts
In a complex digital system, the hardware is typically partitioned into two parts:
a) Data Path, which consists of the functional units where all computations are carried out. Typically consists of registers, multiplexers, bus, adders, multipliers, counters and other functional blocks.
b) Control Path, which implements a finite-state machine and provides control signals to the data path in proper sequence. In response to the control signals, various operations are carried out by the data path. Also, it takes inputs from the data path regarding various status information.
The state transition is controlled by control path or control unit or controller. The control unit (CU) send all the signals necessary to trigger any operation in data path. The data path consists of elements that process data and addresses. Usually there’s also a clock signal and a data bus that go to both data path and control path. By specifying a particular sequence of operations, the control unit can implement a given algorithm.
The following block diagram shows the idea of separating a system into a data path and a control path:
The problem to model
Multiplication by repeated addition
Algorithm: Multiply (a, b)
Step 1. Get the values for a and b.
Step 2. If (either a = 0 or b = 0) then
Step 3. Set the value of the product to be 0
Step 4. Else
Step 5. Set the value of product to 0
Step 6. While (b > 0)
Step 7. Set the value of product to (product + a)
Step 8. Set the value of b to (b - 1)
Step 9. End while loop
Step 10. End if
Step 11. Print the value of product
Step 12. Stop
Flowchart
Data path and control path design
Our data path consists of three registers: A, B and P, one adder unit and one comparator unit. Moreover, these components are connected to data bus (through which input data comes) and different incoming signals (LdA, LdP, clrP, LdB, decB, clk) from control unit and clock frequency generator. Also, there is an outgoing status signal eqz. Moreover there are 3 wires: wire x connecting register A to adder, wire y connecting register P to adder and wire z that puts the sum of A and P back into P.
If we see the overall system, 1 data line (data_in) and 2 signals (start and clk) are going in and one status signal (done) is coming out. These 4 parameters are what we we will use in test bench also to test our design. Other than that, 5 control signals are going to data path unit from control unit apart from a clock signal. And data path is returning eqz (equal to zero) status signal from comparator to CU.
The control unit and its signals help specify the transitions to different states for different operations and conditions. The following diagram shows how the algorithm flow chart is mapped to finite state diagram:
Implementation in Verilog
Module for parallel in parallel out register A
This PIPO register saves 16-bit data till load signal (ld) is not set again. Once ld is set, new data is loaded on the next positive clock edge.
Module for parallel in parallel out register P
This PIPO register saves 16 bit data till load (ld) or clear (clr) signal is not set again. Once ld is set, new data is loaded on the next positive clock edge. When clr signal is set, then all data is erased to 0.
Module for adder unit
Takes two 16 bit data and adds and returns back 16 bit sum. Doesn’t care for overflow.
Module for comparator unit
Checks if the data is equal to 0 or not.
Module for PIPO register B and counter (to decrement register B value)
PIPO register B loads new data if ld signal is on. It decrements the content of B by 1 if dec signal is on.
Module for data path
It implements the data path design.
Module for controller
Implements the control path design as shown in figure 6. The data path performs the actual processing on the input data, and the control path determines which operation should be performed by the data path using the signals LdA, LdB, LdP, clrP, decB and done. The CU also implements the FSM.
Test Bench
Implements test bench to test the modules by multiplying 5 with 6 using repetitive addition. The waveform dump file is saved in mul.vcd which can be used to visualize the signal waveforms for each time instant. It will also print each product value and done status signal value with their time instant value.
Output
