Algorithm (Method) and VLSI architecture for fast evaluation...

Details Algorithm (Method) and VLSI architecture for fast evaluation... Algorithm (Method) and VLSI architecture for fast evaluation...

1999-04-07

2002-11-12

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S276000

Reexamination Certificate

active

06480871

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to transcendental function evaluation, and, more particularly, to a method and apparatus for ultrafast evaluation of trigonometric functions using CORDIC rotations.
BACKGROUND OF THE INVENTION
The CORDIC algorithm was introduced by Volder [1] for computations of trigonometric functions and their inverses. In the classic reference [1], he also showed that the CORDIC method can be used for multiplication/division, as well as for conversion between binary and mixed radix number systems. Walther then demonstrated a “unified” CORDIC algorithm [2] that could be used to calculate trigonometric, exponential and square root functions along with their inverses; as well as to carry out multiply/divide operations. In essence, the CORDIC method evaluates elementary functions merely by table look-up, shift and addition operations (Following the literature and standard design practice in this area, the term “addition” is also assumed to include subtraction).
To evaluate an elementary function accurate to n bits, n pre-calculated fixed constants are all that are required to be stored in the look-up table. In some methods the number of constants to be stored can be n+1 or n+2. Each value stored in the look-up table must be accurate up to n+1 bits where the target output precision is n bits. This is a very small storage requirement and the look-up table can be realized easily in hardware.
The CORDIC algorithm has nice geometrical interpretations [1, 2]: trigonometric, exponential and multiply functions are evaluated via rotations in the circular, hyperbolic and linear coordinate systems, respectively. Their inverses (i.e., inverse trigonometric functions, logarithm and division) can be implemented in a “vectoring” mode in the appropriate coordinate system. Since its inception, CORDIC methods have been investigated by many researchers and have been employed in software and/or hardware for a variety of applications as summarized by the inventor hereof [3].
In this invention, I demonstrate an ultrafast double-stepping method applicable in the CIRCULAR ROTATION mode (used to evaluate sine/cosine/tangent) functions. I begin with an explanation of the circular rotations which are based on the iteration [5]
X
i+1
=X
i
−s
i
Y
i
2
−i
  (1)
Y
i+1
=Y
i
+s
i
X
i
2
−i
  (2)
Z
i+1
=Z
i
−s
i
arctan 2
−i
where
s
i
&egr;{−1, 0, +1}  (3)
and the angles arctan 2
−i
, i=0, 1, 2, . . . are known as “elementary angles” which are pre-computed and stored in a look-up table in typical CORDIC implementations. Using complex numbers, equations (1) and (2) can be rewritten as [6]
W
i+1
=W
i
·(1+js
i
2
−i
)  (4)
where complex variable
W
i
=(
X
i
+j·Y
i
) and
j
={square root over (−1 )}  (5)
Using the polar form of complex numbers,
W
+1
=
W
i
{square root over (1+(
s
i
2
−i
)
2
)}·e
j&thgr;i
=W
i
·K
i
·e
j&thgr;i
where  (6)
&thgr;
i
=
arctan
(
s
i
2
−i
) and
K
i
={square root over (1 +(
s
i
2
−i
)
2
)}
  (7)
Starting with W
0
, if m iterations are carried out, then
W
m
=W
0
·K·e
j&thgr;
where  (8)
K
=
∏
i
=
0
m
-
1
⁢
 
⁢
K
i
=
∏
i
=
0
m
-
1
⁢
 
⁢
1
+
(
s
i
⁢
2
-
i
)
2
⁢
 
⁢
and
(
9
)
θ
=
∑
i
=
0
m
-
1
⁢
 
⁢
θ
i
=
∑
i
=
0
m
-
1
⁢
arctan
⁡
(
s
i
⁢
2
-
i
)
(
10
)
If S
i
, i=0, . . . , m−1, are selected so that
∑
i
=
0
m
-
1
⁢
arctan
⁡
(
s
i
⁢
2
-
i
)
→
θ
0
⁢
 
⁢
then
(
11
)
 
W
m
→W
0
·K
(cos &thgr;
0
+j
sin &thgr;
0
)=(
X
0
+jY
0
)·
K(cos &thgr;
0
+j
sin &thgr;
0
) or  (12)
X
m
→K
(
X
0
cos &thgr;
0
−Y
0
sin &thgr;
0
) and  (13)
Y
m
→K
(X
0
sin &thgr;
0
+Y
0
cos &thgr;
0
)  (14)
If the initial values X
0
and Y
0
are set to 1 and 0, respectively, then
X
m
→K
cos &thgr;
0
and
Y
m
→K
sin &thgr;
0
  (15)
In general, the coefficients s
i
at each step of the CORDIC iteration can take any of the three values {−1, 0, +1}. If s
i
=0 is allowed, then the scaling factor K is not a constant, but depends on the actual sequence of s
i
values. On the other hand, if s
i
can be restricted to ±1, then K is a constant (since the number of iterations m that are to be executed for a given precision are known ahead of time).
In this case, selecting
X
0
={fraction (1
/K
)} and
Y
0
=0 yields  (16)
X
m
→cos &thgr;
0
and
Y
m
→sin &thgr;
0
  (17)
To evaluate the sine and cosine of an argument &thgr;
0
up to n bits of precision, the constant-scale-factor CORDIC method therefore sets Z
0
=&thgr;
0
, X
0
={fraction (1/K)} and Y
0
=0. It then executes n iterations of equation (3), where the s
i
values at each step i=1, . . . , n are selected so as to take the Z
i+1
value as close to zero as possible. In other words, initial angle &thgr;
0
gets “zeroed-out”. For every iteration of equation (3), once the s
i
value for that iteration i is determined, one iteration of equations (1) and (2) is carried out in tandem. At the end of n iterations, the X and Y variables contain the cosine and sine of argument &thgr;
0
, accurate up to n bits.
This method falls under the category of “additive normalization” since the initial angle Z
0
=&thgr;
0
is zeroed out (i.e., it has at least m−2 leading zeroes in a non-redundant representation, if m iterations are executed) by adding ±arctan 2
−i
, i=0, . . . , (m−1). In other words, in CORDIC, n+1 angles (arctan 2
0
, . . . , arctan 2
−n
) must be utilized for n bits of precision. This can be deduced using the following identities
arctan
⁢
 
⁢
2
-
n
<
∑
k
=
n
+
1
∞
⁢
arctan
⁢
 
⁢
2
-
k
<
2
-
n
(
18
)
arctan
⁢
 
⁢
2
-
n
-
∑
k
=
n
+
1
n
+
p
⁢
arctan
⁢
 
⁢
2
-
k
≤
∑
k
=
n
+
p
+
1
∞
⁢
arctan
⁢
 
⁢
2
-
k
<
∑
k
=
n
+
p
+
1
∞
⁢
2
-
k
=
2
-
(
n
+
p
)
(
19
)
At step i if the residual angle Z
i
>0 then the algorithm selects s
i
=+1 and if Z
i
<0 then s
i
=−1 so that the magnitude of the residual angle is constantly being reduced toward zero. For this method to work, the initial angle must satisfy
&LeftBracketingBar;
Z
0
&RightBracketingBar;
≤
∑
k
=
0
∞
⁢
arctan
⁢
 
⁢
2
-
k
=
1.74328662
(
20
)
This range covers all angles of practical interest since {fraction (&pgr;/2)}≈1.5708<&Sgr;
k=0
∞
arctan 2
−k
.
With the introduction of (redundant) signed-digit representations [3] the addition becomes carry-free. That is, the addition takes a small fixed amount of time, irrespective of the wordlength, thus offering a potential for significant speedup. To fully exploit the speed advantage gained by using signed digits, the sign detection of the residual angle also must be performed in a constant (and small) time delay independent of the precision/wordlength. The next action depends on whether the current residual angle is positive or negative. This in turn implies that only a fixed number of leading digits can be processed to determine the sign of the residual angle.
In most methods [4, 5] a window of three (leading) digits turns out to be sufficient to determine the sign. At each iteration, the window shifts right by one digit position. If at least one of the digits in the window of interest is non-zero, the sign of the residual angle can be determined to be ±1. If the sign is ±1, the next elementary angle (arctan 2
−i
at step i) should be subtract

Affiliated with

Also associated with

Rating

Algorithm (Method) and VLSI architecture for fast evaluation... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Algorithm (Method) and VLSI architecture for fast evaluation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithm (Method) and VLSI architecture for fast evaluation... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2963456