Determining the Iteration Bounds of Single-Rate and Multi-Rate Data-Flow Graphs

Digital signal processing algorithms are described by iterative data-flow graphs where nodes represent computations and edges represent communications. In this paper we propose a novel method to determine the iteration bound, which is the fundamental lower bound of the iteration period of a processing algorithm, by using the minimum cycle mean algorithm to achieve a lower polynomial time complexity than existing methods. It is convenient to represent many multi-rate signal processing algorithms by multi-rate data-flow graphs. The iteration bound of a multi-rate dataflow graph (MRDFG) can be determined as the iteration bound of the single-rate data-flow graph (SRDFG) equivalent of the MRDFG. We present an approach to eliminate node redundancy in the equivalent SRDFG for faster determination of the iteration bound of an MRDFG. 1 Introduction Digital signal processing algorithms are repetitive in nature. These algorithms are described by iterative data-flow graphs (DFGs) where nodes re..