Page 255 - DSP Integrated Circuits
P. 255
240 Chapter 6 DSP Algorithms
output nodes belonging to node set N2 have the necessary inputs and can therefore
be executed immediately. Once this is done, those operations having output nodes
belonging to node set N% have all their inputs available and can be executed. This
process can be repeated until the last set of nodes has been computed. Finally, the
signal values corresponding to node set NI can be updated via the delay elements.
This completes the operations during one sample interval.
A method for ordering the updating of the node values that correspond to
delay elements is shown in Box 6.2. Delay elements connected in series are
updated sequentially starting with the last delay element, so that auxiliary mem-
ory cells are not required for intermediate values.
Operations with outputs belonging to the different node sets must be executed
sequentially while operations with outputs belonging to the same node set can be
executed in parallel. Similarly, updating of node values that correspond to delay
elements must be done sequentially if they belong to different subsets of Nik- The
updating is done here at the end of the sample interval, but it can be done as soon
as a particular node value is no longer needed. We will illustrate the method with
an example.
1. Extract the delay branches in the original signal-flow graph. Note that
all delay branches terminate on node set NI. Let k = 1.
2. Find the set of terminal nodes in the delay element graph and denote
this subset N\^. Update these node values and delete all incident delay
branches.
3. If there are any branches left, let k <— k + 1 and repeat from step 2.
Box 6.2 Procedure for deriving the order for updating the delay elements
EXAMPLE 6.2
Determine the system of difference equations in computable order for the second-
order digital filter in Example 6.1.
The system of difference equations can be obtained directly from Figure 6.25.
All nodes belonging to node set NI are initial values. Hence, all nodes in set N2 can
be computed immediately. In the next step, the nodes belonging to set NS can be
computed using the values from node sets NI and N2 as inputs to those operations
with output values that belong to node set N^. In the same way, the remaining
node sets can be computed successively.
Lastly, we update the two cascaded delay elements. According to the proce-
dure shown in Box 6.2, the updating must begin with node v%, i.e., copy the value
v\(n) into the storage cell for V2, in order to release the storage cell used for v\ so
that it can be overwritten. Auxiliary memory cells are therefore not needed. The
result is summarized in Table 6.1.
The operations are here assumed to be executed as soon as their input values
are available. However, the execution of an operation can be postponed until the
result is needed as input to a subsequent operation. For example, UIQ need only be
computed prior to y(n). In Chapter 7 we will discuss scheduling techniques that