Create a Free IGI Global Library Account to Receive a 25% Discount on All Purchases

Exclusive benefits include one-click shopping, flexible payment options, free COUNTER 4 and MARC records, and a 25% discount on all titles as well as the award-winning InfoSci^{®}-Databases.

InfoSci^{®}-Journals Annual Subscription Price for New Customers: As Low As US$ 4,950

This collection of over 175 e-journals offers unlimited access to highly-cited, forward-thinking content in full-text PDF and XML with no DRM. There are no platform or maintenance fees and a guarantee of no more than 5% increase annually.

Encyclopedia of Information Science and Technology, Fourth Edition (10 Volumes) Extended Offer

Receive the complimentary e-books for the first, second, and third editions with the purchase of the Encyclopedia of Information Science and Technology, Fourth Edition e-book. Plus, take 20% off when purchasing directly through IGI Global's Online Bookstore.

Ghai, Deepika and Neelu Jain. "Signal Processing: Iteration Bound and Loop Bound." Research Advances in the Integration of Big Data and Smart Computing. IGI Global, 2016. 153-177. Web. 18 Mar. 2018. doi:10.4018/978-1-4666-8737-0.ch009

APA

Ghai, D., & Jain, N. (2016). Signal Processing: Iteration Bound and Loop Bound. In P. Mallick (Ed.), Research Advances in the Integration of Big Data and Smart Computing (pp. 153-177). Hershey, PA: IGI Global. doi:10.4018/978-1-4666-8737-0.ch009

Chicago

Ghai, Deepika and Neelu Jain. "Signal Processing: Iteration Bound and Loop Bound." In Research Advances in the Integration of Big Data and Smart Computing, ed. Pradeep Kumar Mallick, 153-177 (2016), accessed March 18, 2018. doi:10.4018/978-1-4666-8737-0.ch009

Digital signal processing algorithms are recursive in nature. These algorithms are explained by iterative data-flow graphs where nodes represent computations and edges represent communications. For all data-flow graphs, time taken to achieve output from the applied input is referred as iteration bound. In this chapter, two algorithms are used for computing the iteration bound i.e. Longest Path Matrix (LPM) and Minimum Cycle Mean (MCM). The iteration bound of single-rate data-flow graph (SRDFG) can be determined by considering the Multi-rate data-flow graph (MRDFG) equivalent of the SRDFG. SRDFG contain more nodes and edges as compared to MRDFG. Reduction of nodes and edges in MRDFG is used for faster determination of the iteration bound.

Iteration bound means time taken to achieve output from the applied input (Parhi & Messerschmitt, 1987). Many Digital Signal Processing (DSP) algorithms like recursive and adaptive digital filters contain feedback loops which induce an inherent lower bound on iteration period (Gerez, Heemstra & Herrmann, 1992). This bound is called iteration bound. It is a fundamental limit of recursive Data Flow Graph (DFG) which tells how fast DSP program can be executed in hardware (Lee, Chan & Verbauwhede, 2007). It is used as a characteristic in representation of algorithm in the form of DFG (Ito & Parhi, 1995).

A graphical representation of a DSP based system y(n) = ay(n – 1) + x(n) is shown in Figure 1(a). DFG representation of this equation is shown in Figure 1(b). It consists of a set of nodes and edges. The nodes represent computations and has an execution time associated with it (Lee & Messerschmitt, 1987). Node A represents addition and node B corresponds to multiplication. The node A and node B have an execution time of 4 u.t. (unit time) and 8 u.t. respectively. The edges represent communication between the nodes given by distinct direction. The edge A→B has zero delay and the edge B→A has one delay.

Figure 1.

(a) Graphical representation; (b) DFG of y(n)=ay(n-1)+x(n)

This chapter throws light on the following points:

1.

Defines critical path, loop bound and iteration bound.

2.

Algorithms such as Longest Path Matrix (LPM) and Minimum Cycle Mean (MCM) are defined to compute iteration bound.

3.

The iteration bound of Single-rate DFG (SRDFG) from Multi-rate DFG (MRDFG) is addressed.

1.1 Critical Path

It is the path of DFG with longest computation time but should not contain any delay. The speed of DSP system depends on the critical path computation time and it decreases with increase in computation time. Figure 2 shows DFG of a DSP system consisting: (1) loop, (2) path - with delay, and (3) path - without delay.

Figure 2.

Critical path

1. Loop

1→4→2→1

1→5→3→2→1

1→6→3→2→1

2.

Path - With Delay

1→4→2

1→5→3→2

1→6→3→2

3. Path - Without Delay

4→2→1

5→3→2→1

6→3→2→1

The maximum computation time (6 u.t.) with zero delay among these paths is 6→3→2→1. This path is known as critical path.