Implementation of very high radix division in FPGAs

Headnote

A new approach in multiplication-based dividers for FPGAs is proposed. It relies on very high radix algorithms with prescaling of divisor and dividend. The required multiplications ( prescale factor computations, divisor prescaling, dividend prescaling, and the division main iteration) are performed using a simplified version of a multiply - add fused unit, which integrates well into the FPGA specific structure. It is shown that the proposed implementation uses a small number of DSP blocks (three for IEEE simple precision, five for IEEE double precision and eight for IEEE quad precision for Spartan 6 devices), in order to perform the division.

(ProQuest: ... denotes formulae omitted.)

Introduction: Very high radix division represents a trade-off between the fast, but expensive, iterative dividers and the cheaper, but with less performance, digit recurrence dividers [1, 2]. As in the case of the digit recurrence division, these algorithms rely on the following iteration:

... (1)

where W(i) is partial remainder at step i (W (0)=Y dividend), r = 2b is radix, q(i ) is quotient digits, D is divisor. To simplify the quotient selection, a prescale factor M is computed [1], in order to:

... (2)

The main iteration becomes:

... (3)

where W(i) is partial remainder at step i (W (0)=M *Y dividend)

At each iteration, a number b of quotient bits are obtained. Because of prescaling, the quotient selection is performed as follows:

... (4)

In very high radix division, b ≥ 8 and thus a full-scale multiplication is required in order to obtain q(i)* D. Usually the main iteration in (1) is performed using a fused multiply accumulate unit [1, 2]. A very high radix algorithm with prescaling requires the following steps: 1. Compute the prescale factor; 2. Prescale the divisor; 3. Prescale the dividend; 4. Perform the main iteration in order to obtain the required number of quotient bits. Several methods for computing the prescale factor have been devised, such as the L-approach, Newton-Raphson iteration or T-method [1].

Very high radix algorithms have been implemented, especially for VLSI technology [1, 2]....