Square root extraction circuit and floating-point square...

Details Square root extraction circuit and floating-point square... Square root extraction circuit and floating-point square...

2000-09-22

2004-11-16

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S500000

Reexamination Certificate

active

06820107

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a square root extraction algorithm and a square root extraction circuit used for three-dimensional graphics processing which requires numerical calculations, particularly vector normalization.
2. Description of the Background Art
Graphics processing employing vector normalization, principally light source calculations, uses the result of vector normalization (X/SQRT(X) where X is a vector and SQRT(X) is the square root of X) for processing Thus, the increase in operation speed of the normalization is significant to increase the light source calculating speed. Attempts have been made to implement a square root extraction operation via software or special-purpose hardware- The software for the square root extraction operation requires no special hardware structure and hence necessitates no consideration for a circuit size (costs) when the LSI technique is applied thereto, but requires a large number of repetitive operations using an approximation algorithm. For this reason, the special-purpose hardware is used when a higher priority is given to a processing speed.
However, a conventional square root extraction circuit employing the square root extraction algorithm which determines conventional non-recovery type square roots has a hardware structure as disclosed in “Computer High-speed Operation System,” Kindai Kagaku Sha Co., Ltd. Thus, to determine an N-digit square root, the conventional square root extraction circuit is subject to the following restrictions:
(1) N·(N+1)/2 adders are required.
(2) CAS cells (controllable add/subtract cells) must be used which have a more complicated internal structure as one-unit adders than do full adders.
(3) The operation of a digit of a given significance is not permitted to start until a carry output from the highest-order adder for the digit of the next higher significance (an extracted square root output for that digit) is determined. This decreases the operation speed.
The drawback (2) is described in detail hereinafter.
The CAS cell is a 4-input 4-output controllable add/subtract cell which receives data inputs A, B, a carry input CI, and a control input P to provide an addition (subtraction) output S and a carry output CO which satisfy the conditions described below, a data output B (equal to the data input B), and a control output P (equal to the control input P).
S=A{circumflex over ( )}(B{circumflex over ( )}P){circumflex over ( )}CI
CO=(A+C)·(B{circumflex over ( )}P)+A·C
The symbol “{circumflex over ( )}” means an exclusive-OR operation. The control input (output) P indicates an addition when it is “0”, and indicates a subtraction when it is “1”. In this manner, the CAS cell is a circuit which functions to perform a 1-bit addition/subtraction.
To determine the binary square root Q={
0
.q
1
q
2
q
3
q
4
}
2
of a binary number A={
0
.a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
}
2
, the conventional square root extraction algorithm determines whether the calculation for a digit of a given significance q(i+1) employs an addition or a subtraction, depending upon whether the value of the output digit of the next higher significance q(i) is “1” or “0”. Thus, the conventional square root extraction circuit constructed such that the value of the square root extraction output digit of a given significance q(i) selectively determines the operation contents (addition or subtraction) in the CAS cells for the digit of the next lower significance q(i+1) is slow in operation speed and requires the CAS cells having the 1-bit addition/subtraction function
FIG. 22
is a diagram of a square root extraction circuit employing the conventional algorithm.
As illustrated, two CAS cells are used for the output q
1
, four CAS cells for the output q
2
, six CAS cells for the output q
3
, and eight CAS cells for the output q
4
. In
FIG. 22
, an input shown as given to the middle of the top side of the block of each CAS cell corresponds to the data input A, an input shown as given obliquely to the upper-left corner of the block corresponds to the data input B, an input shown as given across the block corresponds to the control input P, an input shown as given to the right side of the block corresponds to the carry input CI, an output shown as provided from the left side of the block corresponds to the carry output CO, and an output shown as provided from the middle of the bottom side of the block corresponds to the addition (subtraction) output S. The CAS cell has a greater circuit size than that of a full adder and a half adder which are simple in construction, resulting in a complicated circuit structure of the conventional square root extraction circuit.
SUMMARY OF THE INVENTION
A first aspect of the present invention is intended for a square root extraction circuit for calculating binary input data (
0
.a(
1
) a(
2
) a(
3
) . . . a(n)) using a square root extraction algorithm to output binary square root data (
0
.q(
1
) q(
2
) q(
3
) . . . q(m)), the square root extraction algorithm including an algorithm for determining the square root data on the basis of the input data by only additions of square root partial data q(
1
) to q(m) in q(
1
) to q(m) order. According to the present invention, the square root extraction circuit comprises: first to mth digit calculating portions each including a plurality of adders connected in series so that carries are propagated therethrough, wherein respective ones of the adders which are connected in the last position in the first to mth digit calculating portions provide carry outputs serving as the square root partial data q(
1
) to q(m), respectively, in accordance with the square root extraction algorithm.
A second aspect of the present invention is intended for a square root extraction circuit for calculating binary input data (
0
).a(
1
) a(
2
) a(
3
) . . . a(n)) using a square root extraction algorithm to output binary square root data (
0
.q(
1
) q(
2
) q(
3
) . . . q(m)), the square root extraction algorithm including an algorithm for determining the square root data on the basis of the input data by only additions of square root partial data q(
1
) to q(m) in q(
1
) to q(m) order, the algorithm having preceding digit based operation portions for performing operations to output the square root partial data q(
2
) to q(m) by using the square root partial data q(
1
) to q(m−1) provided in their preceding digit positions as operation parameters. According to the present invention, the square root extraction circuit comprises: first to mth digit calculating portions including at least first to mth adder groups, respectively, each of the first to inth adder groups including a plurality of adders connected in series so that carries are propagated therethrough, wherein respective ones of the adders which are connected in the last position in the first to (p−1)th digit calculating portions (2≦p≦m) provide carry outputs serving as the square root partial data q(
1
) to q(p−1), respectively, in accordance with the square root extraction algorithm, and wherein the preceding digit based operation portions of the pth to mth digit calculating portions include carry output prediction circuits for performing logic operations based on the carry outputs from respective ones of the adders which are connected in the last position in the adder groups thereof and the square root partial data q(p−1) to q(m−1) provided in their preceding digit positions to output the square root partial data q(p) to q(m), respectively.
Preferably, according to a third aspect of the present invention, the square root extraction circuit of the second aspect further comprises: a rounding circuit for rounding square root data (
0
.q(
1
) q(
2
) q(
3
) . . . q(k−1)) (p≦k≦m) based on the square root partial data q(k) to q(m) outputted from the carry output prediction circuits of the kth to mth digit calculating portions to output rounded square root

Affiliated with

Also associated with

Rating

Square root extraction circuit and floating-point square... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Square root extraction circuit and floating-point square..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Square root extraction circuit and floating-point square... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3298631