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⩾B, B being the radix. This paper presents new techniques for the direct computation of division, that use an over-redundant digit set for representing the quotient, instead of simply redundant ones used previously. In particular, general criteria for synthesizing the digit selection rules and remainder updating are given for any radix and index of redundancy. A methodology combining the use of over-redundant digit sets with the prescaling of the divisor is 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 unit by M.D. Ercegovac and T. Lang (1990) possible to avoid the digit selection table. The paper also presents a modified algorithm for on-the-fly conversion of the result into the irredundant form. The proposed methodology can be considered as an alternative to existing division techniques