Signal Processing: Iteration Bound and Loop Bound

1. Introduction

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.