Question

Explain the theory of designing a m-bit by n-bit binary divider.

Answer 1

COMBINATIONAL DIVISORS:

Let consider two unsigned binary numbers: D (m-bit dividend), and d (n-bit
divisor). In this case, the division consists on finding two unsigned binary numbers,
C (quotient) and r (remainder), r<d, such that:
D =C.d+r
The division is defined for d != 0. Therefore, in what follows it is assumed that
this condition is met, i.e., before dividing, it is checked if d != 0, and only in this
affirmative case, the division is performed.
With the condition r<d, C and r are unique, and to calculate them, an
immediate combinational solution might be thought obviously. To implement the
division it is sufficed, for example, a ROM of m+n address bits and m outputs
(2^m+n words of m bits), in which the quotient and the remainder corresponding to
every possible (D, d) are written. For real cases this is not a feasible combinational
solution since m+n will result almost always too large to directly synthesize the
corresponding functions (for example, to include all possible outputs in a ROM).
Another combinational solution is possible that attempts to mimic the division
algorithm as a series of subtractions and shifts. Before addressing this alternative,
more aspects about the operands have to be established. Specifically it is assumed
that, as usual, the relationship between the lengths of the dividend and the divisor
is m = 2n - 1, and that the most significant bit of the divisor, d, is 1. Neither of
these assumptions implies restriction, because on the one hand, the size of the
operand can always be adjusted by adding zeros, and, second, by shifting the
divisor it is possible to make 1 the most significant bit; after division, the shifts
made in the divisor must be properly transferred to the quotient and the remainder
to obtain correct results. With these assumptions, with n-bits for both the quotient
and to the remainder, all possible results may be represented, and the division is
made in n-steps, in each of which a bit of the quotient is obtained.
In what follows, an example will be used to reach a combinational divider
circuit: let n = 4, D = 0110101, d = 1011. The four stages of calculation for this
case are detailed in Fig a. In the first stage d is subtracted from the four most
significant bits of D (D6D5D4D3); if the result is positive (and therefore no output
borrow), the quotient bit is 1, and the difference D6D5D4D3 - d passes to the next
stage as the most significant bits of the modified dividend. If the result is negative
(i.e., there is output borrow), the quotient bit is 0, and the dividend unchanged
passes to the next stage. In other words, the quotient bit is the complement of the
borrow of the subtractor output, and if the quotient bit is 0, D without changing is
selected for the next stage, while if the quotient bit is 1, the most significant bits of
the dividend bit must be modified selecting D6D5D4D3 - d. Therefore, with a full
subtractor, FS, to take into account the possible borrow of the previous bit, plus one
2-to-1 multiplexer, the circuit necessary for processing each bit can be constructed,
as shown with cell CR of Fig. b. If for a given bit (as with the least significant
bit) no input borrows are to be considered, the full subtractor FS can be replaced by
a half subtractor, HS, resulting in the CS cell, simpler than the CR, Fig. c.
The second and subsequent iterations consist on repeating the same as the first
iteration, using in each case the unmodified or modified dividend which has
resulted in the previous iteration. Then, by subtracting, the divisor is shifted one
position to the right in each iteration. The remainder, r3… r0, is obtained in the
fourth iteration.
The circuit for dividing a number of seven bits by other of four bits is detailed
in Fig.d, in which 12 CR cells and 7 CS cells are used (or 19 CR cells, if only
one single type of cells want to be used). As it has been already indicated, the
divisor has to be adjusted to get that always the most significant bit is a 1, and after
division, these movements have to be translated to the results. It is straightforward
to extend these design divisors for any value of n.

SEQUENTIAL DIVISORS:

The most common divisors are the sequential. The ideas that led to the divisor of
Fig. d can be used to construct a divisor that divides D, of 2n - 1 bits, by d, of
n bits, using n clock pulses. As a particular case it is still assumed that n = 4.

Figure e shows a circuit using three CR cells, two CS cells, one 4-bit latch to
store the divisor, d (this register it is not shown in Fig. e), and an 8-bit register
for the dividend, D. This register D consists of two 4-bit register: the first register
(D7D6D5D4) must be simultaneous reading and writing (i.e., master-slave), the
second (D3D2D1D0) must be a shift register with serial input and output. The
registers d and D have to be loaded with the data to be processed before starting
operation. Obviously always D7 = 0 before starting to divide, and the divisor will
have been shifted so the most significant bit of d is 1. The shift register
(D3D2D1D0) is used to store the bits of the quotient. It is easily verified that this
circuit in Fig. e does the same as the one in Fig. d, unless using four clock
pulses. Therefore, after four iterations, the quotient is stored in D3D2D1D0 and the
remainder of the division is stored in D7D6D5D4. Again, this circuit can be
extended immediately to any value of n.