Page 249 - DSP Integrated Circuits
P. 249
234 ChapterG DSP Algorithms
An algorithm that has a delay-free loop is non-sequentially computable [9].
Such an algorithm can be implemented neither as a computer program nor in
digital hardware. These algorithms are therefore of no practical use. Algorithms
must therefore be checked for delay-free loops since such loops may occur in
certain synthesis procedures.
6.3.4 Fully Specified Signal-Flow Graphs
Usually, a signal-flow graph is not fully speci-
fied from a computational point of view. For
example, the order in which three or more val-
ues are added is usually not specified in signal-
flow graphs. The ordering of the additions is,
under certain conditions, not important if
two's-complement representation is used.
These conditions will be further discussed in
Chapter 11. However, the ordering of the addi-
tions may affect the computational properties
of the algorithm. For example, the maximum
sample rate may change. In a fully specified
signal-flow graph, the ordering of all opera-
tions is uniquely specified as illustrated in Fig-
ure 6.13. Generally the signal-flow graph
Figure 6.13 Signal-flow graph
should be described in terms of the operations
and the
that can be executed by the processing ele- corresponding fully
ments that are going to be used in the imple- specified signal-
mentation. flow graph
6.4 SFGs IN PRECEDENCE FORM
In this section we will present a method of redrawing the signal-flow graph into a
precedence form that yields the order in which the node values must be computed
[6, 7]. A procedure for deriving the expressions for the node values in a sequen-
tially computable order is shown in Box 6.1.
In the next section we will use the prece-
dence form to derive the corresponding set of
difference equations in a form that can easily
be mapped to code for a general-purpose signal
processor. Note, however, that the precedence
form represents a simplified view of an algo-
rithm and does not provide full insight into the
computational properties of the signal-flow Figure 6.14 Sets of nodes that are
graph. We will develop a better insight into the sequentially
true properties later in this chapter and in the computable
next chapter.
If the procedure shown in Box 6.1 is termi-
nated prematurely due to lack of initial nodes, then the remaining part of the pre-
cedence graph contains a cycle that corresponds to a delay-free loop in the signal-