Generalized earliest-first fast addition algorithm

Abstract

This paper presents a generalized earliest-first (GEF) addition algorithm to accelerate carry propagation addition (CPA). A set of operators and notations have been developed to describe and analyze traditional carry-lookahead or conditional-sum-based algorithms. The proposed GEF algorithm schedules bit-level operations of CPA in an earliest-first manner to reduce the overall latency. With the aid of the developed operators and notations, the algorithm can be generalized to any algorithm based on carry-lookahead or conditional-sum rule. An adder generated by using the GEF algorithm outperforms traditional algorithms when inputs do not arrive simultaneously.