A systolic ON-LINE non-restoring division scheme

A new improved version of the classic binary non-restoring division algorithm is presented. It is implemented on a systolic ON-LINE architecture, targeted at use in digital signal processing applications. The overall goal is to implement DSP algorithms using redundant data representations throughout the algorithm, and to obtain a balanced architecture according to the specifications of the application. The improved algorithm is based on calculating the absolute valve rather than obtaining the sign of the remainders. The use of absolute value is based on a paper introducing absolute value in the operations of a CORDIC unit by H. Dawid and H. Meyr (1992). Compared to the original work, the algorithmic contributions of this paper is a mathematical deduction of the algorithm applied to division. The new algorithm maintains the advantages of the non-restoring division compared to SRT: No normalization or scaling of the divisor is required, and the output quotient is produced in a non-redundant number representation. The algorithm is mapped onto a pure systolic ONLINE architecture, and an implementation presented. The architecture contains no global communication, and it can be pipelined all the way down to gate level, as opposed to traditional architectures. The architecture is both modular and regular, enabling further multiplexing for a better match to the specifications of an application. The presented implementation is shown to be area/spl times/time optimal for applications containing a mixture of both division and multiplication.<>