Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Fast Divide Algorithm with minimum Expression of the redundant Partial Remainder

IP.com Disclosure Number: IPCOM000010389D
Original Publication Date: 2002-Nov-22
Included in the Prior Art Database: 2002-Nov-22
Document File: 3 page(s) / 14K

Publishing Venue

IBM

Abstract

A fast SRT Divide Algorithm with minimum expression of redundant partial remainder is shown. State of the art designs use the carry part in the same width as the sum part for the redundant expression of the partial remainder. The carry part can be reduced without having disadvantages for performance and cycle time. The advantage is a reduced area and power consumption. The implemented example saves 82 latches with a total width of 116 bits for the SRT divide 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 60% of the total text.

Page 1 of 3

  Fast Divide Algorithm with minimum Expression of the redundant Partial Remainder

A state of the art Divide Algorithm (any subtraction method with redundant remainder expression i.e. SRT with radix 4) can look as Figure 1 shows. The Partial Remainder for the next iteration is calculated as follows:

Pi+1 = (r. Pi) - qi+1 . divisor

    Where r is the radix of the algorithm (i.e. 4) and q are the quotient bits. In the state of the art algorithm, the partial remainder is expressed with a sum part and a carry part with about the same width (i.e. 116 bits each

Partial Remainder

carry bits

Divisor

sum bits

Select/Multiply

Subtractor

Figure 1 State of the art Divide Algorithm

Partial Remainder

carry bits

..

Divisor

sum bits

Select/Multiply

Subtractor

[This page contains 4 pictures or other non-text objects]

Page 2 of 3

Figure 2 Divide Algorithm with minimum Partial Remainder

    A redundant expression is state of the art, since an explicit expression of the partial remainder would require an 'carry-propagate-adder', which is not favorable because of the long timing delay. With the redundant expression, a 'Carry-Save-Adder' can be used, which is much faster.

    The invention is to use only every fourth (in the implemented version) carry bit for the expression of the partial remainder.

    This saves in the implemented hardware 82 latches. With the additional saving of clock buffers, area and wiring length, an additional advantage of a faster cycletime is possible.

ci

Input to Subtractor

...