Radix 2 division with over-redundant quotient selection

Hosahalli R. Srinivas, Keshab K Parhi, Luis A. Montalvo

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

In this paper we present a new radix 2 division algorithm that uses a recurrence employing simple 3-to-2 digit carry-free adders to perform carry-free addition/subtraction for computing the partial remainders in radix 2 signed-digit form. The quotient digit, during any iteration of the division recursion, is generated from the two most-significant radix 2 digits of the partial remainder and independent of the divisor in over-redundant radix 2 digit form (i.e., with digits which belong to the digit set {•2, •1, 0, +1, +2}). The over-redundant quotient digits are then converted to the conventional radix 2 digits (belonging to the set {•1,0, +1}) by using a reduction technique. This division algorithm is well suited for IEEE 754 standard operands belonging to the range [1, 2) and is slightly faster than previously proposed radix 2 designs (such as the radix 2 SRT), which do not employ input scaling, since the quotient selection for such algorithms is a function of more than two most-significant radix 2 digits of the partial remainder. In comparison with the designs that employ input scaling, the proposed design although slightly slower saves hardware required for scaling purposes.

Original languageEnglish (US)
Pages (from-to)85-92
Number of pages8
JournalIEEE Transactions on Computers
Volume46
Issue number1
DOIs
StatePublished - Dec 1 1997

Fingerprint

Digit
Division
Quotient
Adders
Remainder
Hardware
Scaling
Partial
Subtraction
Signed
Recursion
Recurrence
Divisor
Iteration
Computing

Keywords

  • Division
  • Division without prescaling
  • Over-redundant representation
  • Radix 2 redundant arithmetic
  • Signed digit arithmetic
  • Two-digit quotient selection

Cite this

Radix 2 division with over-redundant quotient selection. / Srinivas, Hosahalli R.; Parhi, Keshab K; Montalvo, Luis A.

In: IEEE Transactions on Computers, Vol. 46, No. 1, 01.12.1997, p. 85-92.

Research output: Contribution to journalArticle

Srinivas, Hosahalli R. ; Parhi, Keshab K ; Montalvo, Luis A. / Radix 2 division with over-redundant quotient selection. In: IEEE Transactions on Computers. 1997 ; Vol. 46, No. 1. pp. 85-92.
@article{33c49337a1534e27b8b887a37f2cd510,
title = "Radix 2 division with over-redundant quotient selection",
abstract = "In this paper we present a new radix 2 division algorithm that uses a recurrence employing simple 3-to-2 digit carry-free adders to perform carry-free addition/subtraction for computing the partial remainders in radix 2 signed-digit form. The quotient digit, during any iteration of the division recursion, is generated from the two most-significant radix 2 digits of the partial remainder and independent of the divisor in over-redundant radix 2 digit form (i.e., with digits which belong to the digit set {•2, •1, 0, +1, +2}). The over-redundant quotient digits are then converted to the conventional radix 2 digits (belonging to the set {•1,0, +1}) by using a reduction technique. This division algorithm is well suited for IEEE 754 standard operands belonging to the range [1, 2) and is slightly faster than previously proposed radix 2 designs (such as the radix 2 SRT), which do not employ input scaling, since the quotient selection for such algorithms is a function of more than two most-significant radix 2 digits of the partial remainder. In comparison with the designs that employ input scaling, the proposed design although slightly slower saves hardware required for scaling purposes.",
keywords = "Division, Division without prescaling, Over-redundant representation, Radix 2 redundant arithmetic, Signed digit arithmetic, Two-digit quotient selection",
author = "Srinivas, {Hosahalli R.} and Parhi, {Keshab K} and Montalvo, {Luis A.}",
year = "1997",
month = "12",
day = "1",
doi = "10.1109/12.559806",
language = "English (US)",
volume = "46",
pages = "85--92",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "1",

}

TY - JOUR

T1 - Radix 2 division with over-redundant quotient selection

AU - Srinivas, Hosahalli R.

AU - Parhi, Keshab K

AU - Montalvo, Luis A.

PY - 1997/12/1

Y1 - 1997/12/1

N2 - In this paper we present a new radix 2 division algorithm that uses a recurrence employing simple 3-to-2 digit carry-free adders to perform carry-free addition/subtraction for computing the partial remainders in radix 2 signed-digit form. The quotient digit, during any iteration of the division recursion, is generated from the two most-significant radix 2 digits of the partial remainder and independent of the divisor in over-redundant radix 2 digit form (i.e., with digits which belong to the digit set {•2, •1, 0, +1, +2}). The over-redundant quotient digits are then converted to the conventional radix 2 digits (belonging to the set {•1,0, +1}) by using a reduction technique. This division algorithm is well suited for IEEE 754 standard operands belonging to the range [1, 2) and is slightly faster than previously proposed radix 2 designs (such as the radix 2 SRT), which do not employ input scaling, since the quotient selection for such algorithms is a function of more than two most-significant radix 2 digits of the partial remainder. In comparison with the designs that employ input scaling, the proposed design although slightly slower saves hardware required for scaling purposes.

AB - In this paper we present a new radix 2 division algorithm that uses a recurrence employing simple 3-to-2 digit carry-free adders to perform carry-free addition/subtraction for computing the partial remainders in radix 2 signed-digit form. The quotient digit, during any iteration of the division recursion, is generated from the two most-significant radix 2 digits of the partial remainder and independent of the divisor in over-redundant radix 2 digit form (i.e., with digits which belong to the digit set {•2, •1, 0, +1, +2}). The over-redundant quotient digits are then converted to the conventional radix 2 digits (belonging to the set {•1,0, +1}) by using a reduction technique. This division algorithm is well suited for IEEE 754 standard operands belonging to the range [1, 2) and is slightly faster than previously proposed radix 2 designs (such as the radix 2 SRT), which do not employ input scaling, since the quotient selection for such algorithms is a function of more than two most-significant radix 2 digits of the partial remainder. In comparison with the designs that employ input scaling, the proposed design although slightly slower saves hardware required for scaling purposes.

KW - Division

KW - Division without prescaling

KW - Over-redundant representation

KW - Radix 2 redundant arithmetic

KW - Signed digit arithmetic

KW - Two-digit quotient selection

UR - http://www.scopus.com/inward/record.url?scp=0031348556&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031348556&partnerID=8YFLogxK

U2 - 10.1109/12.559806

DO - 10.1109/12.559806

M3 - Article

VL - 46

SP - 85

EP - 92

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 1

ER -