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
   250   251   252   253   254   255   256   257   258   259   260