VLSI Digital Signal Processing Systems: Design and Implementation

4.2    DEFINITIONS AND PROPERTIES

4.2.1    Quantitative Description of Retiming

Retiming maps a circuit G to a retimed circuit G_r. In the context of retiming, the terms circuit and graph and DFG are often used interchangeably, as they are in this chapter. A retiming solution is characterized by a value r(V) for each node V in the graph. Let w(e) denote the weight of the edge e in the original graph G, and let w_r(e) denote the weight of the edge e in the retimed graph G_r . The weight of the edge U V in the retimed graph is computed from the weight of the edge in the original graph using

To demonstrate some formal retiming concepts, the filter in Fig. 4.1(a) is redrawn in Fig. 4.2(a), and the retimed filter in Fig. 4.1(b) is redrawn in Fig. 4.2(b). The retiming values r(1) = 0, r(2) = 1, r(3) = 0, and r(4) = 0 can be used to obtain the retimed DFG in Fig. 4.2(b) from the DFG in Fig. 4.2(a). For example, the edge 3 2 in the retimed DFG contains

delay, and the edge 2 1contains

delays. ...