EÆcient Arithmetic Implementations Based on Carry-Save Representations

This paper presents arithmetic implementations which use binary redundant numbers based on carry-save representations. It is well-known that constant-time addition, in which the execution delay is independent of operand length, is feasible only if the result is expressed in a redundant representation. Carry-save based formats are one type of a redundant representation which can lead to highly efficient implementations of arithmetic operations. In this paper, we discuss two specific carry-save formats that lead to particularly efficient realizations. We illustrate these formats, and the “equal-weight grouping ” (EWG) mechanism wherein bits having the same weight are grouped together during an arithmetic operation. This mechanism can reduce the area and delay complexity of an implementation. We present a detailed comparison of implementations based on these two carry-save formats including measurements from VLSI cell layouts. We then illustrate the application of these VLSI cells for multi-operand additions in fast parallel multipliers. Finally, we also indicate the relationship with previous results.