Carry-Free Radix-2 Subtractive Division Algorithm and Implementation of the Divider

Jen-Shiun Chiang; Hung-Da Chung; Min-Show Min-Show

doi:10.6180/jase.2000.3.4.03

Carry-Free Radix-2 Subtractive Division Algorithm and Implementation of the Divider

Electrical Engineering

Jen-Shiun Chiang ¹, Hung-Da Chung¹ and Min-Show¹

¹Tsai Department of Electrical Engineering Tamkang University Tamsui, Taipei, Taiwan

Received: November 18, 1999
Accepted: November 4, 2000
Publication Date: December 1, 2000

Download Citation: ||https://doi.org/10.6180/jase.2000.3.4.03

ABSTRACT

A carry-free subtractive division algorithm is proposed in this paper. In the conventional subtractive divider, adders are used to find both quotient bit and partial remainder. Carries are usually generated in the addition operation, and it may take time to finish the operation, therefore, the carry propagation delay usually is a bottleneck of the conventional subtractive divider. In this paper, a carry-free scheme is proposed by using signed bit representation to represent both quotient and partial remainder. During the arithmetic operation, a special technique is used to decide the quotient bit, and the new partial remainder can be found further by a table lookup-like method. The signed bit format of the quotient can be converted by on-the-fly conversion to the binary representation. Based on this algorithm a 32-b/32-b divider is designed and implemented, and the simulation shows that the divider works well.

Keywords: Divider, radix-2, quotient bit, partial remainder, carry propagation delay, high speed, Svobota-Tung division algorithm, signed digit, prescaling, table look-up, on-the-fly conversion

REFERENCES

[1] Atkins, D. E., “Higher-Radix Division Using Estimates of the Divisor and Partial Remainders”, IEEE Trans. on Comp., vol. C-17, no. 10, Oct., pp. 925-934 (1968).
[2] Bashagha, A. E. and Ibrahim, M. K., “A New Digit-Serial Divider Architecture”, Int. J. of Electronics, vol.75, no. 7, July, pp. 133-140 (1993).
[3] Burgess, N., “A Fast Division Algorithm for VLSI”, IEEE Int. Conf. On Computer Design, pp. 560-563 (1991).
[4] Cortadella, J. and Lang, T., “High-Radix Division and Square-Root with Speculation”, IEEE Trans. on Comp., vol. 43, no. 8, pp. 919-931, Aug. (1994).
[5] Ercegovac, M. D., Lang, T., “ON-the-Fly Conversion of Redundant into Conversion Representations”, IEEE Trans. on Comp., vol. C-36, no. 7, July, pp. 895-897 (1987).
[6] Ercegovac, D. and Lang, T., “Simple Raduix-4 with Scaling”, IEEE Trans. on Comp., vol. 39, no. 9, Aug., pp. 1204-1208 (1990).
[7] Ercegovac, M. D. and Lang, T., “Simple Radix-4 Division Unit with Operands Scaling”, IEEE Trans. on Comp., vol. 49, no. 9, Sept., pp. 1204-1208 (1990).
[8] Ercegovac, M. D. and Lang, T., Division and Square Root: Digit-recurrence Algorithms and Implementations, The Netherlands: Kluwer Academic Publishers (1994).
[9] Hwang, K., Computer Arithmetic Principles, Architecture, and Design, John Wiley and Sons (1979).
[10] Montuschj, P. and Cimiera, L., “Over-Redundant Digit Sets and the Design of Digit-by-Digit Division Units,” IEEE Trans. on Comp., vol. 43, no. 3, pp. 269-279, March (1994).
[11] Svoboda, A., “An Algorithm for Division”, Information Processing Machines, no. 9, pp. 25-32, Sept. (1963).
[12] Swartzlander, E. E., Computer Arithmetic, vol. 1, Los Alamitos-California, IEEE Computer Society Press, pp. 156-157 (1990)
[13] Tung, C., “A Division Algorithm for Signed-Digit Arithmetic”, IEEE Trans. on Comp., vol. C-17, no. 9, pp. 887-889, Sept. (1968).
[14] Tung, C., “Signed-Digit Division Using Combinational Arithmetic”, IEEE Trans. on Comp., vol. C-19, no. 8, pp. 746-748, Aug. (1970).
[15] Williams, T. E. and Horowitz, M. A., “A 160ns 54-bit CMOS Division Implementation Using Self-Timing and Symmetrically Overlapped SRT Stages”, 10th IEEE Symp. Computer Arithmetic, Grenoble, France, pp. 210-217, June (1991).