VLSI Digital Signal Processing Systems: Design and Implementation

2.6    CONCLUSIONS

DSP programs have the property that they are executed from n = 0 to n = ∞. These programs are often represented using DFGs, which can be recursive or nonrecursive. When the DFG is recursive, the iteration bound is the fundamental limit on the minimum sample period of a hardware implementation of the DSP program. Two algorithms for computing the iteration bound were discussed. The LPM algorithm finds the iteration bound with time complexity and the MCM algorithm finds the iteration bound with time complexity . The MCM algorithm is usually faster than the LPM algorithm because e_d ≤ d² holds for most cases.

Fig. 2.12    The DFG used in Problem 1.

Fig. 2.13    A 4-level pipelined all-pass 8th-order IIR digital filter.

The iteration bound of a multirate DFG can be determined by first constructing an equivalent single-rate DFG and then computing the iteration bound of the single-rate DFG using 1 of the 2 algorithms described in this chapter. The algorithm in Fig. 2.10 can be used to construct an equivalent single-rate DFG from the multirate DFG.