VLSI Digital Signal Processing Systems: Design and Implementation

2.2    DATA-FLOW GRAPH REPRESENTATIONS

DSP programs are considered to be nonterminating programs that run from time index n = 0 to time n = ∞. For example, a DSP program that computes y(n) = ay(n − 1) + x(n) represents the following program:

for n = 0 to ∞

    y(n) = ay(n − 1) + x(n)

The input to this DSP program is the sequence x(n) for n = 0,1,2,…, and the initial condition y(− 1). The output is the sequence y(n) for n = 0,1,2,….

Fig. 2.1    (a) A graphical representation of y(n) = ay(n − 1) + x(n). (b) A DFG for this program. The numbers in parentheses are the execution times for the nodes.

A DSP program is often represented using a DFG, which is a directed graph (i.e., each edge has a distinct direction) that describes the program (see also Section 1.4.3). For example, the program y(n) = ay(n − 1) + x(n) is graphically represented in Fig. 2.1(a). A simplified version of this program is shown in Fig. 2.1(b). The structure in Fig. 2.1(b) is a DFG, which consists of a set of nodes and edges. The nodes represent tasks or computations (the node A represents addition and the node B represents multiplication), and each node has an execution time associated with it. The edges represent communication between the nodes, and each edge has a nonnegative number of delays associated with it. In our example, the edge A → B has zero delays and the edge B → A has one delay. An iteration of a ...