## 5.2 AN ALGORITHM FOR UNFOLDING

In this section, an algorithm for unfolding a DFG by an unfolding factor *J* is described. Before this algorithm is presented, some notations are introduced and some basic properties of unfolded DFGs are described.

The operation is the floor of *x*, which is the largest integer less than or equal to *x.* For example, The operation *a*%*b* is the remainder after dividing *a* by *b,* where *a* and *b* are integers. For example, 11%4 = 3 and 25%3 = 1.

For each node *U* in the original DFG, there are *J* nodes with the same function as *U* in the *J*-unfolded DFG. For example, for the adder in Fig. 5.1(a), there are 2 adders in the 2-unfolded DFG in Fig. 5.1(b). Similarly, there are 2 multipliers in Fig. 5.1(b) corresponding to the multiplier in Fig. 5.1(a).

For each edge in the original DFG, there are *J* edges in the *J*-unfolded DFG. This can be observed in Fig. 5.1, where the edge from the adder to the multiplier in the original DFG results in 2 edges from an adder to a multiplier in the unfolded DFG.

Keeping in mind that the DFG of the *J*-unfolded program contains *J* times as many nodes and edges as the DFG of the original DFG, the following unfolding algorithm can be used to construct a *J*-unfolded DFG.

**Unfolding Algorithm**

- For each node
*U*in the original DFG, draw the*J*nodes ...

Get *VLSI Digital Signal Processing Systems: Design and Implementation* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.