Constructing zero-deficiency parallel prefix adder of minimum depth

Abstract

Parallel prefix adder is a general technique for speeding up binary addition. In unit delay model, we denote the size and depth of an n-bit prefix adder C(n) as SC(n) and dC(n) respectively. Snir proved that sC(n) + dC(n) ≥ 2n - 2 holds for arbitrary prefix adders. Hence, a prefix adder is said to be of zero-deficiency if sC(n) + dC(n) = 2n - 2. In this paper, we first propose a new architecture of zero-deficiency prefix adder dubbed Z(d), which provably has the minimal depth among all kinds of zero-deficiency prefix adders. We then design a 64-bit prefix adder Z64, which is derived from Z(d)|d=8, and compare it against several classical prefix adders of the same bit width in terms of area and delay using logical effort method. The result shows that the proposed Z(d) adder is also promising in practical VLSI design.