OVER-REDUNDANT DIGIT SETS AND THE DESIGN OF DIGIT-BY-DIGIT DIVISION UNITS

Over-redundant digit sets are defined as those ranging from -s to +s, with s greater-than-or-equal-to B, B being the radix. This paper prese nts new techniques for the direct computation of division, that use an over-redudant digit set for representing the quotient, instead of sim ply redundant ones used previously. In particular, general criteria fo r synthesizing the digit selection rules and remainder updating are gi ven for any radix and index of redundancy. A methodology combining the use of over-redundant digit sets with the prescaling of the divisor i s also studied in order to achieve radix-B division units with trivial digit selection functions. It is also shown, for the specific case of radix-4, that using a prescaling slightly wider than in a radix-4 uni t by Ercegovac and Lang, it is possible to avoid the digit selection t able. The paper presents also a modified algorithm for on-the-fly conv ersion of the result into the irredundant form. The proposed methodolo gy can be considered as an alternative to existing division techniques .