|
Published Articles >> Table of Contents >> Abstract
November 2003 (Vol. 52, No. 11)
pp. 1509-1514
Tight Upper Bounds on the Minimum Precision Required of the Divisor and the Partial Remainder in High-Radix Division
Behrooz Parhami, IEEE
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TC.2003.1244949
Send link to a friend
| Abstract |
|
Digit-recurrence binary dividers are sped up via two complementary methods: keeping the partial remainder in redundant form and selecting the quotient digits in a radix higher than 2. Use of a redundant partial remainder replaces the standard addition in each cycle by a carry-free addition, thus making the cycles shorter. Deriving the quotient in high radix reduces the number of cycles (by a factor of about h for radix 2^h). To make the redundant partial remainder scheme work, quotient digits must be chosen from a redundant set, such as [-2, 2] in radix 4. The redundancy provides some tolerance to imprecision so that the quotient digits can be selected based on examining truncated versions of the partial remainder and divisor. No closed form formula for the required precision in the partial remainder and divisor, as a function of the quotient digit set and the range of the partial remainder, is known. In this paper, we establish tight upper bounds on the required precision for the partial remainder and divisor. The bounds are tight in the sense that each is only one bit over a well-known simple lower bound. We also discuss the implications of these bounds for the quotient digit selection process.
|
 References
|
[1] D.E. Atkins, Higher Radix Division Using Estimates of the Divisor and Partial Remainders IEEE Trans. Computers, vol. 17, no. 10, pp. 925-934, Oct. 1968.
[2] N. Burgess and T. Williams, "Choices of Operand Truncation in the SRT Division Algorithm," IEEE Trans. Computers, vol. 44, no. 7, pp. 933-937, July 1995.
[3] M.D. Ercegovac and T. Lang, Division and Square Root—Digit-Recurrence Algorithms and Implementations. Kluwer Academic, 1994.
[4] H.A.H. Fahmy, A.A. Liddicoat, and M.J. Flynn, Improving the Effectiveness of Floating-Point Arithmetic Proc. 35th Asilomar Conf. Signals, Systems, and Computers, pp. 875-879, Nov. 2001.
[5] D. Harris, S. Oberman, and M. Horowitz, “SRT Division Architectures and Implementations,” Proc. IEEE 13th Int'l Symp. Computer Arithmetic (ARITH13), pp. 18-25, 1997.
[6] G. Jaberipur, B. Parhami, and M. Ghodsi, Weighted Bit-Set Encodings for Redundant Digit Sets Proc. 36th Asilomar Conf. Signals, Systems, and Computers, pp. 1629-1633, Nov. 2002.
[7] S.F. Oberman and M.J. Flynn, “Division Algorithms and Implementations,” IEEE Trans. Computers, vol. 46, no. 8, pp. 833-854, Aug. 1997.
[8] S.F. Oberman and M.J. Flynn, Minimizing the Complexity of SRT Tables IEEE Trans. VLSI Systems, vol. 6, no. 1, pp. 141-149, Mar. 1998.
[9] B. Parhami, Computer Arithmetic—Algorithms and Hardware Designs. New York: Oxford Univ. Press, 2000.
[10] B. Parhami, Precision Requirements for Quotient Digit Selection in High-Radix Division Proc. 35th Asilomar Conf. Signals, Systems, and Computers, pp. 1670-1673, Nov. 2001.
[11] D.S. Phatak and I. Koren, "Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains," IEEE Trans. Computers, special issue on computer arithmetic, vol. 43, no. 8, pp. 880-891, Aug. 1994. (An unabridged version is available on the web at.)
[12] J.E. Robertson, A New Class of Digital Division Methods IRE Trans. Electronic Computers, vol. 7, pp. 218-222, Sept. 1958.
[13] J.H.P. Zurawski and J.B. Gosling, “Design of a High-Speed Square Root Multiply and Divide Unit,” IEEE Trans. Computers, vol. 36, no. 1, pp. 13-23, Jan. 1987
|
 Additional Information
|
Index Terms- Digit-recurrence division, digit-selector PLA, high-radix division, p-d plot, quotient digit selection, SRT division.
Citation:
Behrooz Parhami,
"Tight Upper Bounds on the Minimum Precision Required of the Divisor and the Partial Remainder in High-Radix Division,"
IEEE Transactions on Computers,
vol. 52,
no. 11,
pp. 1509-1514,
Nov.,
2003
|
|
RSS Feed