Hybrid Signed–Digit Number Systems:A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains
Dhananjay S. Phatak Electrical Engr. Dept., State University of New York Binghamton, NY 1302–6000
phatak@ee.binghamton.edu Israel Koren, Fellow, IEEE Department of Electrical and Computer Engineering
University of Massachusetts, Amherst, MA 01003 (IEEE Transactions on Computers, vol. 43, No. 8, August 1994
pp 880-891)
ABSTRACTA novel hybrid number representation is proposed in this paper. It includes the two’s complement
representation and the signed-digit representation as special cases. The hybrid number representations
proposed are capable of bounding the maximum length of carry propagation chains during addition to
any desired value between 1 and the entire word length. The framework reveals a continuum of number
representations between the two extremes of two’s complement and signed-digit number systems and
allows a unified performance analysis of the entire spectrum of implementations of adders, multipliers
and alike.
We present several static CMOS implementations of a two–operand adder which employ the pro-
posed representations. We then derive quantitative estimates of area (in terms of the required number
of transistors) and the maximum carry propagation delay for such an adder. The analysis clearly illus-
trates the tradeoffs between area and execution time associated with each of the possible representations.
We also discuss adder trees for parallel multipliers and show that the proposed representations lead to
compact adder trees with fast execution times.
In practice, the area available to a designer is often limited. In such cases, the designer can select the
particular hybrid representation that yields the most suitable implementation (fastest, lowest power con-
sumption, etc.) while satisfying the area constraint. Similarly, if the worst case delay is predetermined,
the designer can select a hybrid representation that minimizes area or power under the delay constraint.
Index terms : Bounded Carry Propagation, Carry–free addition, Hybrid Signed–Digit Number
System, Redundant Number Representation, Signed–Digit Numbers, Static CMOS implementation.