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-
   244   245   246   247   248   249   250   251   252   253   254