Pipelining, Retiming, Look-ahead Transformation and Polyphase Decomposition - Digital Design of Signal Processing Systems: A Practical Approach - page 317

1

x[n] ay[n-1] + x[n] = y[n]

+

2

y[n]

ay[n-1] 3

x

a

y[n-1]

Figure 7.19

Iteration period of first-order IIR system is equal to T m þ T a

Example: Figure 7.19 shows an IIR system implementing the difference equation:

y½¼ay n ½ 1 þx½n ð 7 3 Þ

:

The algorithm needs to perform one multiplication and one addition to compute an output sample in
one iteration. Assume the execution times of multiplier and adder are T m and T a , respectively. Then
the iteration period for this example is T m þ

T a . With respect to the sample period T s of input data,

these timings must satisfy the constraint:

T m þT a T s ð 7 : 4 Þ

7.3.1.2 Loop and Loop Bound

A loop is defined as a directed path that begins and ends at the same node. In Figure 7.19 the directed
path consisting of nodes 1 ! 2 ! 3 ! 1 is a loop. The loop bound of the ith loop is defined as
T i /D i , where T i is the loop computation time and D i is the number of delays in the loop. For the loop
in Figure 7.19 the loop bound is (T m þ T a )/1.

7.3.1.3 Critical Loop and Iteration Bound

A critical loop of a DFG is defined as the loop with maximum loop bound. The iteration period of
a critical loop is called the iteration period bound (IPB). Mathematically it is written as:

T i
D i

IPB ¼ max

all L i

where T i and D i are the cumulative computational time of all the nodes and the number of registers in
the loop L i , respectively.

7.3.1.4 Critical Path and Critical Path Delay

The critical path of a DFG is defined as the path with the longest computation time delay among all
the paths that contain zero registers. The computation time delay in the path is called the critical path
delay of the DFG.