VLSI Digital Signal Processing Systems: Design and Implementation

A.1    INTRODUCTION

In this appendix, the Bellman-Ford algorithm and the Floyd-Warshall algorithm shortest path algorithms are described. These algorithms can be used to solve several problems in VLSI signal processing such as computing the iteration bound of recursive DFGs (see Chapter 2), retiming (see Chapter 4), and retiming for folding (see Chapter 6).

The level of detail included here is intended to be enough so that the reader can use these algorithms to solve the problems mentioned above. The theory behind these algorithms has been omitted; however, for the interested reader, there is a reference that discusses the theory behind these algorithms (e.g., [1], [2]).

The concepts of shortest paths and negative cycles are demonstrated using the DFG in Figure A.1. The length of a path is the sum of the weights on the edges of the path. The path 2 → 3 → 4 has length 1 + 2 = 3. There are 2 paths from node 2 to node 4, namely the path 2 → 4 with length 1 and the path 2 → 3 → 4 with length 3. The shortest path from node 2 to node 4 is min{1,3} = 1. A negative cycle in a directed graph is a directed cycle such that the sum of the lengths on the edges of the cycle is negative. Figure A.1 contains the 2 cycles 2 → 4 → 1 → 2 and 2 → 3 → 4 → 1 → 2. The cycle 2 → 4 → 1 → 2 is a negative cycle because the sum of the edge weights is 1 + 1 + (−3) = −1. The other cycle, 2 → 3 → 4 → 1 → 2, is not a negative cycle because the sum of the edge weights is 1 + 2 + 1 + (−3) = 1. With this in mind, ...