Fast CORDIC algorithm with sine governed termination

Details Fast CORDIC algorithm with sine governed termination Fast CORDIC algorithm with sine governed termination

1999-06-18

2002-05-07

Malzahn, David H. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S276000, C712S007000

Reexamination Certificate

active

06385632

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method for evaluating one or more functions of one or more variables.
2. Description of the Related Art
In an article entitled “The CORDIC Trigonometric Computing Technique”, authored by Jack E. Volder, and published in IRE Trans. Electron. Comput. EC-8:330-334 (1959), Volder describes the Coordinate Rotation Digital Computer (CORDIC). In this article, which is incorporated by reference in its entirety, Volder discloses a computational algorithm based on a convergent series of elementary rotations. This algorithm will be referred to herein as the CORDIC algorithm. The CORDIC algorithm in its various realizations may be used to compute a variety of elementary functions such as, e.g., sine, cosine, tangent, arctangent, exponential, logarithm, hyperbolic sine, hyperbolic cosine, hyperbolic tangent, etc. In addition, the CORDIC algorithm may also be used to compute two-dimensional rotations, multiplications, divisions and square roots.
The CORDIC algorithm receives an input point (X
0
, Y
0
) and an input angle &lgr;
0
, and applies a series of iterations to these input operands. Each iteration of the series operates on a current intermediate point (X
i
, Y
i
) and a current residual angle &lgr;
i
, and generates an updated intermediate point (X
i+1
, Y
i+1
) and an updated residual angle &lgr;
i+1
. In the first iteration, the current intermediate point is taken to be the input point (X
0
, Y
0
) and the current residual angle is taken to be the input angle &lgr;
0
. A mathematical analysis of the CORDIC algorithm reveals that the intermediate point (X
i
, Y
i
) converges as the iteration index increases. The limiting resultant point is given by the equations
X
R
=
K
⁢
 
⁢
R
0
⁢
cos
⁡
(
θ
0
+
λ
0
)
=
lim
i
→
∞
⁢
X
i
(
1
)
Y
R
=
K
⁢
 
⁢
R
0
⁢
sin
⁡
(
θ
0
+
λ
0
)
=
lim
i
→
∞
⁢
Y
i
,
(
2
)
where K is a known constant, R
0
is the radius of the point (X
0
, Y
0
) with respect to the origin, and &thgr;
0
is the counter-clockwise angle of the input point (X
0
, Y
0
) with respect to the positive x axis. Geometrically, the resultant point (X
R
, Y
R
) is a rotated and scaled image of the input point (X
0
, Y
0
). In other words, the resultant point (X
R
, Y
R
) is that point which arises from rotating the input point (X
0
, Y
0
) by input angle &lgr;
0
and then radially extending the interim rotated point by factor K. One advantage of the CORDIC algorithm lies in the fact that it implements this scaled rotation more efficiently than a direct computation of equations (1) and (2) which would generally require a pair of hardware multiplies and trigonometric evaluations.
Suppose that the input point (X
0
, Y
0
) is chosen to be (1/K,0). In this case, the initial radius R
0
equals 1/K and the angle &thgr;
0
of the input point with respect to the positive x axis equals zero. According to equations (1) and (2), after N iterations of the CORDIC algorithm, the x-coordinate X
N
approximates the value cos(&lgr;
0
), and the y-coordinate Y
N
approximates the value sin(&lgr;
0
). By various arrangements of the initial conditions and the structure of the CORDIC algorithm, a great variety of elementary functions may be evaluated.
The CORDIC algorithm operates on the input point (X
0
, Y
0
) and the input angle &lgr;
0
by applying an iterative series of pseudo-rotations governed by the following system of equations:
Y
i+1
=Y
i
+&xgr;
i
2
−i
X
i
  (3)
X
i+1
=X
i
−&xgr;
i
2
−i
Y
i
  (4)
 &lgr;
i+1
=&lgr;
i
−&xgr;
i
·&agr;
i
,  (5)
&agr;
i
=arctan(2
−i
),  (6)
where the iteration index i is greater than or equal to zero, and where the scalar factor &xgr;
i
takes the value ±1 depending on the sign of the residual angle &lgr;
i
. In particular, if the residual angle &lgr;
i
is positive, the factor &xgr;
i
takes the value +1, and thus, equations (6) and (7) implement a pseudo-rotation of the intermediate point (X
i
, Y
i
) by the angle &agr;
i
, and equation (8) computes an updated residual angle &lgr;
i+1
by subtracting the angle &agr;
i
from the current residual &lgr;
i
. Conversely, if the residual angle &lgr;
i
is negative, the factor &xgr;
i
takes the value −1, and thus, equations (6) and (7) implement a pseudo-rotation of the intermediate point (X
i
, Y
i
) by the angle −&agr;
i
, and equation (8) computes the updated residual by adding the angle &agr;
i
to the current residual.
It is noted that equations (6) and (7) implement a pseudo-rotation of the point (X
i
, Y
i
) by the rotation angle &agr;
i
. The direction of the pseudo-rotation (clockwise or counter-clockwise) depends on the value of factor &xgr;
i
. The resultant point (X
i+1
, Y
i+1
) may be equivalently expressed by the relations
Y
i+1
={square root over (1+2
−2i
)}
R
i
sin(&thgr;
i
+&xgr;
i
&agr;
i
),  (7)
X
i+1
={square root over (1+2
−2i
)}
R
i
cos(&thgr;
i
+&xgr;
i
&agr;
i
),  (8)
where R
i
is the radius of the point (X
i
, Y
i
), and &thgr;
i
is the angle of the point (X
i
, Y
i
) with respect to the positive x axis, i.e.
Y
i
=R
i
sin(&thgr;
i
),  (9)
X
i
=R
i
cos(&thgr;
i
).  (10)
The resultant point (X
i+1
, Y
i+1
) is slightly farther from the origin than the source point (X
i
, Y
i
), i.e. by a factor of
{square root over (1+2
−2i
)}, and for this reason the resultant point cannot be said to be a pure rotation of the source point.
As the iteration index i increases, the intermediate point (X
i
, Y
i
) converges to the limiting resultant point given by equations (1) and (2). Furthermore, the residual angle &lgr;
i
converges to zero. It can be shown that the CORDIC algorithm exhibits an exponential rate of convergence, i.e. after N iterations of the CORDIC algorithm the residual angle &lgr;
N
has an absolute value smaller than 2
−(N−1)
. In addition, the coordinates of the intermediate point (X
N
, Y
N
) approximate the corresponding coordinates of the limiting resultant (X
R
, Y
R
) to within a tolerance of KR
0
2
−(N−1)
. In other words, each iteration of the CORDIC algorithm yields an additional bit of precision in the binary representations of X
N
and Y
N
.
Iteration equations (6), (7) and (8) may be efficiently implemented with (a) shifters configured to perform the indicated multiplications by powers of two, (b) adders configured to perform the addition and subtraction operations, and (c) a comparator to test the residual value for controlling the conditional additions and subtractions. In particular, it is noted that the iteration equations (6), (7) and (8) may be evaluated without performing hardware multiplies or trigonometric evaluations. The angular constants &agr;
i
may be stored in a lookup table. These features allow the CORDIC algorithm to compute approximations to X
R
and Y
R
in significantly less time than direct implementations of equations (1) and (2) which achieve a comparable precision.
It is noted that multiplication of a binary number by ½ corresponds to shifting the bits of the binary number to the right one position with respect the binary point. In general, multiplication of a binary number by the factor 2
−L
corresponds to shifting the bits of the binary number to the right L bit positions.
Various ways to improve the CORDIC algorithm have been sought. One prior art method for improving the CORDIC algorithm has been advanced by Timmermann et al. in a paper entitled “Modified CORDIC Algorithm with Reduced Iterations”, Electronic Letters, vol. 25, no.15, pages 950-951, copyright 1989, which is hereby incorporated by reference in its entirety. Timmermann et al. make the observation that the first iterations of the CORDIC algorithm make the most

Affiliated with

Also associated with

Rating

Fast CORDIC algorithm with sine governed termination does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast CORDIC algorithm with sine governed termination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast CORDIC algorithm with sine governed termination will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2912815