DIGIT-SET CONVERSIONS - GENERALIZATIONS AND APPLICATIONS

The problem of digit set conversion for fixed radix is investigated fo r the case of converting into a non redundant, as well as into a redun dant, digit set. Conversion may he from very general digit sets, and c overs as special cases multiplier recodings, additions, and certain mu ltiplications. We generalize known algorithms for conversions into non redundant digit sets, as well as apply conversion to generalize the O (log) time algorithm for conditional sum addition using parallel prefi x computation, and a comparison is made with standard carry-lookahead techniques. Examples on multi-operand addition are used to illustrate the generality of this approach. O(1) time algorithms for converting i nto redundant digit sets are generalized based on a very simple lemma, which provides a framework for all conversions into redundant digit s ets. Applications in multiplier recoding and partial product accumulat ion are used here as exemplifications.