Arithmetic - Signal Processing Systems - page 610

where r 0 = X . Therefore, if 2 r i − 1 − D is positive, we set z i = 1, otherwise z i = 0

and r i = 2 r i − 1 . r i is the remainder after iteration i and considering ( 33 ) wehave

r i 2 − 1 . To compute a quotient with W f fractional bits obviously W f iterations of
( 34 ) are required.
Instead of restoring the remainder by adding the divisor, we can assign a negative
quotient digit. This gives the nonrestoring division selection rule of the quotient
digits, z i ,in( 34 ) as

R =

1

, ≥ . .

r i − 1 D 0i e same sign

z i = (35)

− , < . . .

1 r i − 1 D 0i e different signs

Note that with this definition of the selection rules the remainder will sometimes
be positive, sometimes negative. Hence, division with a signed dividend and/or
divisor is well covered within this approach. This also gives that the final remainder
does not always have the same sign as the dividend. Hence, in that case we must
compensate by adding or subtracting D to R and consequently subtracting or adding
one LSB to Z .
The result from the nonrestoring division will be represented using a representa-
tion with q i ∈{− . This representation is sometimes called nega-binary and is

in fact not a redundant representation. The result should in most cases be converted
into a two's complement representation. Naturally, one can convert this by forming a
word with positive bits and one with negative bits and subtract the negative bits from
the positive bits. However, for this all bits must be computed before the conversion
can be done. Instead, it is possible to use the on-the-fly conversion technique in [ 9 ]
to convert the digits into bits once they are computed.
Another consequence of the nega-binary representation is that if a zero remainder
is obtained, this will not remain zero in the succeeding stages. Hence, a zero
remainder should be detected and either the iterations stopped or corrected for at
the end.

1 , 1 }

4.2 SRT Division

The SRT division scheme extends the nonrestoring scheme by allowing 0 as a
quotient digit. Furthermore, by restricting the dividend to be in the range 1

/ 2 ≤

D 1, which can be obtained by shifting, the selection rule for the quotient digit in

( 34 ) can be defined as

<

⎧
⎨

− 1 , 2 r i − 1 < − 1 / 2

z i = (36)

0 , − 1 / 2 ≤ 2 r i − 1 < 1 / 2

⎩

1 , 1 / 2 ≤ 2 r i − 1