Method and apparatus for accumulating partial quotients in a digital processor

Abstract

In a digital processor performing division, quotient accumulation apparatus is formed of a set of muxes and a single carry save adder. Partial quotients are accumulated in carry-save form with proper sign extension. Delay of partial quotient bit fragments from one iteration to a following iteration enables the apparatus to limit use to one carry save adder. By enlarging minimal logic, the quotient accumulation apparatus operates at a rate fast enough to support the rate of fast dividers.

What is claimed is:  
     
         1 . A digital processor logical division method, comprising the steps of: 
 producing partial quotients and partial remainders in a processing loop, the processing loop operating at a working rate; and    accumulating the partial quotient at a rate faster than the working rate such that the step of accumulating is fast enough to support the processing loop, said accumulating using a same format for the partial quotients as format of the partial quotients produced by the processing loop.    
     
     
         2 . The method of  claim 1  wherein the step of accumulating includes providing proper sign extension of the partial quotients by using a single constant value for sign extensions of all the partial quotients and by using switch bits to switch sign extension bits as needed.  
     
     
         3 . The method of  claim 2  wherein the step of using a single constant value includes fragmenting the value into different bits used in different iterations of the accumulating.  
     
     
         4 . The method of  claim 3  wherein the step of accumulating includes delaying bit portions of partial quotients for input into a carry save adder at different iterations.  
     
     
         5 . The method of  claim 1  wherein the step of accumulating includes limiting logic to a single carry save adder and a set of multiplexes providing input to the carry save adder, in a number less than or equal to maximum number of inputs of the carry-save adder.  
     
     
         6 . The method of  claim 5  wherein the step of accumulating includes delaying bit portions of partial quotients for input into the carry save adder at different iterations.  
     
     
         7 . The method as claimed in  claim 1  wherein the format of the partial quotients is carry save format.  
     
     
         8 . A digital processor logical division system comprising: 
 a processing loop producing partial quotients and remainders in a certain format, the processing loop operating at a working rate; and    a quotient accumulator responsive to the processing loop and efficiently accumulating the partial quotients in the certain format at a rate faster than the working rate, such that the quotient accumulator is sufficiently fast to support the processing loop.    
     
     
         9 . A digital processor logical division system as claimed in  claim 8  wherein said certain format is carry save format.  
     
     
         10 . A digital processor logical division system as claimed in  claim 8  wherein the quotient accumulator provides proper sign extension of the partial quotients by using a single constant value for sign extensions of all the partial quotients and by using switch bits to switch sign extension bits as needed.  
     
     
         11 . A digital processor logical division system as claimed in  claim 10  wherein the quotient accumulator further fragments the single constant value into different bits used in different iterations of accumulating.  
     
     
         12 . A digital processor logical division system as claimed in claim  111  wherein the quotient accumulator further delays bit portions of partial quotients for input into a carry save adder at different iterations.  
     
     
         13 . A digital processor logical division system as claimed in  claim 8  wherein the quotient accumulator includes limited logic of a single carry save adder and a set of multiplexers providing input to the carry save adder, in a number less than or equal to maximum number of inputs of the carry save adder.  
     
     
         14 . A digital processor logical division system as claimed in  claim 13  wherein the quotient accumulator further delays bit portions of partial quotients per input into the carry save adder at different iterations.