Page 248 - DSP Integrated Circuits

6.3 Precedence Graphs 233

Figure 6.11 Latency models for a serial/parallel multiplier

6.3.3 Sequentially Computable Algorithms

A precedence graph may be contradictory in the sense that it describes an impossi-
ble ordering of events [6 — 7, 9]. An example of such a precedence graph is shown
in Figure 6.12. Event A can occur only after event C has occurred. However, event
C can only occur when event B has occurred, but event B can not occur until event
A has occurred. Hence, this sequence of events is impossible since the sequence
cannot begin.
In a digital signal processing algorithm, events
correspond to arithmetic operations. In a proper
algorithm, at least one of the operations in each
recursive loop in the signal-flow graph must have
all its input values available so that it can be exe-
cuted. This is satisfied only if the loops contain at
least one delay element, since the delay element
contains a value from the preceding sample interval
that can be used as a starting point for the compu-
tations in the current sample interval. Thus, there Figure 6.12 Directed, cyclic
must not be any delay-free loops in the signal-flow precedence
graph
graph. For a sequentially computable algorithm the
corresponding precedence graph is called a directed
acyclic graph (DAG).

Theorem 6.1
A necessary and sufficient condition for a recursive algorithm to be
sequentially computable is that every directed loop in the signal-flow
graph contains at least one delay element.