A 32-bit Integer Division Algorithm Based on Priority Encoder
Firas Hassan, Ahmed M. Abuseta Ammar, Hayden Drennen · 2020
In this paper, an algorithm for 32-bit integer division is proposed. The algorithm calculates the integer division of positive and negative dividends and divisors represented in sign and magnitude. It calculates the magnitudes and signs of the quotient and remainder separately based on the magnitudes and signs of the divided and divisor. In the algorithm, the magnitude of the remainder is initially set to be the dividend and is iteratively reduced until it becomes smaller than the magnitude of the divisor; afterwards the algorithm converges. A priority encoder is used to improve the convergence rate by skipping the zeros between the high bits while shifting the divisor in each iteration to be aligned with the partial remainder. The magnitude of the quotient is initially set to zero and updated based on the amount of shift in each iteration. A hardware architecture is proposed to implement the algorithm. The hardware is synthesized on an FPGA device, and its functionality was verified by ModelSim simulations. The results show that the hardware achieves a maximum operating frequency of 90.9MHz, and achieves an improvement of 31.43%, 59.12%, and 18.1%, in terms of delay, LUTs, and slices, respectively, over the most recent existing approach. MATLAB simulations were also conducted to measure the convergence rate. The MATLAB simulation results show that on average the convergences rate is less than or equal to the half of the difference between the number of bits in the dividend and the number of bits in the divisor.