How do I write a VHDL code

How do I write the VHDL description of a simple algorithm: the data path

How do I write the VHDL description of a simple algorithm: the data path

This article will show you how to write the VHDL code for a simple algorithm.

This article describes the conversion of a simple algorithm, e.g. B. an LCM algorithm (Least Common Multiple), described in a VHDL description. The data path of the algorithm is discussed in this article. In the next article we will discuss the control path of the algorithm.

Separate the data path from the control path

Conventional digital design divides a given problem into two sections: a data path and a control path (or controller). As a well-known example, consider a microprocessor that consists of an arithmetic and logic unit (ALU) and a control path. The ALU can have several arithmetic units, for example adders and multipliers. The data processing is performed by the ALU and therefore the ALU is considered to be the data path of this system. The control path determines which operation is performed by the ALU. By specifying a particular sequence of operations, the control unit can implement a given algorithm.

The following block diagram shows the idea of ​​dividing a system into a data path and a control path.

Illustration 1. A controller and a data path work together to implement an algorithm. Image courtesy of Digital Systems Design using VHDL.

As you can see in the diagram, some of the system inputs go to the controller and some go into the data path. For example, there may be a "start" input that triggers a system implemented multiplication algorithm.

In this case, "start" corresponds to one of the "control inputs" shown in the diagram, and the multiplication operands correspond to the "data input". The controller also receives some inputs as "status signals" from the data path. A multiplication overflow flag is an example of a "status signal". Based on the control inputs and the status signals, the controller determines the upcoming operations for the data path.

By separating the data path from the controller, we can find the errors in the design process more easily. In addition, this design methodology facilitates future modifications to the system.

To explore this design method further, let's use the example of a Least Common Multiple (LCM) algorithm implemented as a VHDL description.

The pseudocode of an LCM algorithm

Listing 1 shows the pseudocode to find the LCM of m and n. Let us assume that $ 1 \ leq m \ leq 7 $$ and $$ 1 \ leq n \ leq 7 $$.

Listing 1

This algorithm uses repeated addition operations to find the multiples of m and n. These multiples are stored in a and b, respectively. After each iteration of the algorithm, we check a and b; If they are equal, we have found a common multiple and the algorithm ends. Since the smaller multiples are checked first, the algorithm gives the LCM of m and n.

Find the building blocks of the data path

Let's take a look at which building blocks are needed to implement the data path of the above algorithm in hardware. Computer programming language uses a "variable" to store information that is later referenced or used. We can use some flip-flops as storage elements to store the value of variables a and b. These two registers must be wide enough to hold the LCM of m and n. Since $$ 1 \ leq m \ leq 7 $$ and $$ 1 \ leq n \ leq 7 $$, the LCM will be less than $$ 7 \ times 6 = 42 $$. (Note that the LCM of 7 and 7 is 7.) So we need two six-bit registers to implement a and b.

Also, taking into account lines 7 and 11 of the code, we need two adders to calculate a + m and b + n. Since the maximum value of this addition result is 42, 6-bit adders are wide enough to avoid an additional overflow.

The code suggests that we will need some multiplexers as well. Why "text-align: center;"> Listing 2

As you can see, sometimes we just keep the current value of a and b (lines 12 and 8). Since there are three different values ​​that can be assigned to each of registers a and b, we need two three-to-one multiplexers. The required blocks are shown in Figure 2.

Figure 2

Connect the components

The following figure shows a possible connection of these components to implement the above algorithm. In this figure, the set of D Flip-Flops (DFFs) used to store the values ​​of a and b are represented by a single DFF.

Figure 3

As you can see, the control input goes to the select input of the two multiplexers. By choosing different values ​​for sel, we can do the three assignments of the algorithm. For example, if the two multiplexers select the input labeled "0", the inputs m and n are passed to a_next and b_next, respectively. With the next clock edge, the a and b registers are updated with the value of the inputs m and n. This corresponds to lines 1 and 2 of Listing 2. Notice that we assign m and n, which are three-bit numbers, to a and b, which are 6-bit registers. Therefore, in Figure 3, the concatenation operator is used to append three zeros to the left of m and n (and this in turn is the reason why the adders in Figure 3 have two six-bit inputs, as opposed to the adders in Figure 2), which have a three-bit input and a six-bit input).

If the two multiplexers of Figure 3 select the input labeled "1", the next value of a will be equal to m plus the current value of the a register. In this case, the b register retains its current value. This corresponds to lines 7 and 8 of Listing 2. The multiplexers can also choose the red paths that correspond to lines 12 and 13 of Listing 2.

The scheme of Figure 3 can perform the required operations on inputs m and n; however, a corresponding signal must be generated for the selection input of the multiplexer. At the beginning of the algorithm, sel chooses the path in dark blue to update the registers with the value of the inputs. For the rest of the algorithm, either the light blue paths or the red paths are chosen. This choice is made based on the result of the comparison of a and b (see lines 5 and 10 of Listing 2). Hence, two more circuits must be added to the scheme of Figure 3: one circuit to compare a with b and one to generate an appropriate signal for the sel input. Comparing two binary numbers is a trivial task, but what about generating the SEL signal? By determining which operations are being performed, the sel signal actually specifies the state of the system and so it is not surprising that we can use a finite state machine (FSM) to generate sel. An FSM is in exactly a finite number of states at any given time and can be designed to go from one state to another in response to certain conditions. In the case of the LCM example, a state transition may occur in response to the result of the comparison between a and b.

We will discuss the control path of the LCM algorithm in the next article and then use our results to write the VHDL code for the algorithm.

Summary

  • Conventional digital design divides a given problem into two sections: a data path and a control path (or controller).
  • The data path does the actual processing of the input data, and the control path determines what operation should be performed by the data path.
  • By disconnecting the data path from the controller, you can find design flaws and implement changes more easily.
  • An FSM can be used to generate the signal for the select input of the routing multiplexers in the data path.

To see a full list of my items, please visit this page.