Acquire a Source of Open Access (OA) APC Funding for Your Institution Through IGI Global's OA Fee Waiver (Offset Model) Initiative

For any library that invests in IGI Global's InfoSci-Books and/or InfoSci-Journals databases, IGI Global will match the library’s investment with a fund of equal value to go toward subsidizing the OA APCs for their faculty patrons when their work is submitted/accepted under OA into an IGI Global journal.

Subscribe to the Latest Research Through IGI Global's InfoSci-OnDemand Plus

InfoSci®-OnDemand Plus, a subscription-based service, provides researchers the ability to access full-text content from over 100,000+ peer-reviewed book chapters and 25,000+ scholarly journal articles that spans across 350+ topics in 11 core subjects. Users can select articles or chapters that meet their interests and gain access to the full content permanently in their personal online InfoSci-OnDemand Plus library.

Purchase the Encyclopedia of Information Science and Technology, Fourth Edition

and Receive Complimentary E-Books of Previous Editions

When ordering directly through IGI Global's Online Bookstore, 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.

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 5 reports and MARC records, and a 25% discount on single all titles, as well as the award-winning InfoSci^{®}-Databases.

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. 26 May. 2019. 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 May 26, 2019. 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.