Optimal purely systolic addition

The author introduces a purely systolic hardware algorithm for addition which is based on a mesh-connected arrangement of cells. The proposed FASTA algorithm is well suited for realization in integrated technologies. Its area, computation time, and period satisfy A( n)=O(n), T(n)=O(√n), and P(n)=O(√n), respectively, where n denotes the operand length. Therefore, this adder is T-, APT-, and AT²-optimal in the linear model for signal propagation delays. In the class of Θ(√n) time adders it is optimal with respect to A, P, T, AT, APT, AP ², and AT². The suggested algorithm essentially is a solution to the general problem of parallel prefix computation. Therefore, it can serve as a paradigm for the design of optimal purely systolic hardware algorithms in a wide range of application domains