Redundant arithmetic, algorithms and implementations

Performance in many very-large-scale-integrated (VLSI) systems such as digi tal signal processing (DSP) chips, is predominantly determined by the speed of arithmetic modules like adders and multipliers. Even though redundant a rithmetic algorithms produce significant improvements in performance throug h the elimination of carry propagation, efficient circuit implementations o f these algorithms have been traditionally difficult to obtain. This work p resents a survey of circuit implementations of redundant arithmetic algorit hms. The described implementations are divided into three main groups: (1) conventional binary logic circuits, which encode the multivalued digits of redundant arithmetic into two or more binary digital signals; (2) current-m ode multiple-valued logic circuits, which directly represent multivalued re dundant digits using non-binary digital current signals; and (3) heterostru cture and quantum electronic circuits. intended for very compact designs ca pable of operating at extremely high speeds. For each of the circuits, the operating principle is described and the main advantages and disadvantages of the approach are discussed and compared. (C) 2000 Published by Elsevier Science B.V.