The paper presents a general theory for developing new Svoboda-Tung (or simply NST) division algorithms not suffering the drawbacks of the "classical" Svoboda-Tung (or simply ST) method. NST avoids the drawbacks of ST by proper recoding of the two most significant digits of the residual before selecting the most significant digit of this recoded residual as the quotient digit. NST relies on the divisor being in the range [1, 1+/spl delta/), where /spl delta/ is a positive fraction depending upon: 1) the radix, 2) the signed digit set used to represent the residual, and 3) the recoding conditions of the two most significant digits of the residual. If the operands belong to the IEEE Std range [1, 2), they have to be conveniently prescaled. In that case, NST produces the correct quotient but the final residual is scaled by the same factor as the operands, therefore, NST is not useful in applications where the unsealed residual is necessary. An analysis of NST shows that previously published algorithms can be derived from the general theory proposed in the paper. Moreover, NST reveals a spectrum of new possibilities for the design of alternative division units. For a given radix-b, the number of different algorithms of this kind is b/sup 2//4.

In this paper we present a new radix 2 division algorithm that uses a recurrence employing simple 3-to-2 digit carry-free adders to perform carry-free addition/subtraction for computing the partial remainders in radix 2 signed-digit form. The quotient digit, during any iteration of the division recursion, is generated from the two most-significant radix 2 digits of the partial remainder and independent of the divisor in over-redundant radix 2 digit form (i.e., with digits which belong to the digit set {-2, -1, 0, +1, +2}). The over-redundant quotient digits are then converted to the conventional radix 2 digits (belonging to the set {-1, 0, +1}) by using a reduction technique. This division algorithm is well suited for IEEE 754 standard operands belonging to the range (1, 2) and is slightly faster than previously proposed radix 2 designs (such as the radix 2 SRT), which do not employ input scaling, since the quotient selection for such algorithms is a function of more than two most-significant radix 2 digits of the partial remainder. In comparison with the designs that employ input scaling, the proposed design although slightly slower saves hardware required for scaling purposes.

Experience has shown that generator programs are quite often written by VLSI designers, as they hold the empirical knowledge better than anyone. However, their ability does not necessarily include programming and debugging skills: these designers have to focus on the problem at hand not on the tools or the language they use to solve it. GenOptim has been created to quickly design efficient IEEE 754 floating-point macro-cell generators that do not rely on particular target technologies. Whereas the design of fast and efficient adders, multipliers and shifters is well understood division and square root remain a serious design challenge. GenOptim was used to quickly evaluate new divider architectures.>

Two pure combinational radix-4 digit-set converters for use in hybrid arithmetic are presented. The conventional to minimally redundant balanced signed-digit set converter is very simple and has zero cost and delay in terms of gates. The balanced to conventional digit-set converter performs the conversion "on the fly" with the generation of the balanced signed-digits, from the most significant to the least significant one; it has an O(1) delay (i.e. constant and independent of the length n of the number), an O(n/sup 2/) cost and a regular structure suitable for VLSI implementation. A review of the principles of hybrid addition/subtraction was previously presented (N. Takagi et al., 1985).>