Browse Prior Art Database

High Radix Division Quotient Selection by 2 Level Control Memories

IP.com Disclosure Number: IPCOM000083938D
Original Publication Date: 1975-Aug-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 4 page(s) / 75K

Publishing Venue

IBM

Related People

Tan, KG: AUTHOR

Abstract

There is described apparatus in which high-radix division (r = 4,8,10, .... etc.) quotient selection is performed by 2-level control memory, rather than the conventional combinational logic.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 4

High Radix Division Quotient Selection by 2 Level Control Memories

There is described apparatus in which high-radix division (r = 4,8,10, .... etc.) quotient selection is performed by 2-level control memory, rather than the conventional combinational logic.

In high-radix division, each iteration is defined by:

p(i+1)=rp(i) - q(i+1)d (1) where

p(i) = The partial remainder produced in the ith iteration.

d = The divisor.

r = The radix. q(i+l) = The quotient generated for (i+1)th iteration. Let; d be the truncated divisor, rp be the truncated shifted partial remainder,

k be the redundancy constant k=/n//r-1, where n is the

largest positive quotient allowed in each iteration,

x be the number of bits in d, and

y be the number of fractional bits in rp(i).

Equation (1) can be rearranged in the following form:

rp(i) = p(i+1)+q(i+1)d (2) which can be plotted as a function of d with q(i+1) as the parameter ranging from -n to n in steps of 1. This graphical representation of division iteration is referred to as the P-D plot.

It can be shown from the P-D plot that.

x >/- 2 log(2) k(r-2) ) over (2K-1) )

) for 1 >/- k > 1/2

y >/- 2 - log(2) (2k-1) )

The P-D plot of a given radix will completely specify the division iteration steps. A given divisor d and the shifted partial remainder rp(i) will specify a point in the P-D plot. The value of this point will be the new quotient digit q(i+1). The redundancy is manifested by the overlapping regions Q(j), in which either q(i+1) = j or j-1 can be the correct choice for the quotient (j range from 1 to n).

Ordinarily, a set of boolean equations and a group of combinational circuits are used to implement the quotient selection mechanism from the P-D plot. Since the divisor is assumed to be normalized, (1/2 </- d < 1) and the absolute value of p(i) </- k x d, the P-D plot is symmetrical about the d-axis. The quotient selection in the negative region (rp < o) can be made to be the mirror image of the positive region.

Assume the quotients are binary coded numbers, the total number of bits required (B) for the positive region of the P-D plot can be shown to be: B = log(2) r (kr x (2/x/-1) 2/y-1/+2/x-1/) (3). A detailed assignment of the P-D plot for r=4, k=2/3 is given in Fig. 1. The overall high-radix division with 2-level control memory scheme is shown in Fig. 2.

1

Page 2 of 4

In this organization, the P-D plot is implemented in the 2nd-level control memory (can be read-only). (In some cases, for the sake of speed, both positive and neg...