Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-03-13
2002-02-19
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S622000
Reexamination Certificate
active
06349317
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to vector rotators and computers of sine and cosine, especially to high-radix CORDIC vector rotators.
BACKGROUND OF THE INVENTION
Vector rotation and the computation of sine and cosine (which are reducible to vector rotation) have applications in many areas that are critical to modern technology, such as telecommunications, image processing, radar, and digital signal processing. More specifically, vector rotation is used in such diverse applications as image rotation, Fourier and other Transform computations, modulation and demodulation. For example, in the computation of Discrete Fourier Transforms (including when using the Fast Fourier Transform algorithm), many multiplications of complex numbers are called for. However, each such multiplication is actually a vector rotation, and could be done using less circuit space by using a CORDIC rotator rather than 4 real-number multipliers.
The original CORDIC family of algorithms was discovered by Volder in 1956 and published three years later in the following paper: J. E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computing, EC-8, pp. 330-334, 1959. The CORDIC computer that Voider built computed in radix-2, that is, the convergence rate was 1 bit per iteration, and was used for aircraft navigation. Volder developed algorithms using essentially the same principle for computing many different functions, with vector rotation included.
A particularly simple explanation of the basic, radix-2 CORDIC algorithm, found in Ray Andraka's paper, “A Survey of CORDIC Algorithms for FPGAs,” Sixth International ACM/SIGDA Symposium on FPGA, Feb. 1998, pp. 191-200, runs as follows:
The well-known formulae for vector rotation can be rewritten as:
x
′=cos &thgr;[
x−y
tan&thgr;] (1)
y
′=cos &thgr;[
y+x
tan&thgr;] (2)
where (x, y) and (x′, y′) are the original and the rotated vectors, respectively, and &thgr; is the angle of rotation.
If we restrict the rotation angles &thgr; so that tan &thgr;=±2
−(i−1)
, for positive integer values of i, then the multiplication by the tangent in equations (1) and (2) is reduced to a shift operation when the numbers are represented in binary. (We assume that numbers are two's complement numbers.) It turns out that all angles within a certain useful range (that is, approximately [-1.743, 1.743]) can be expressed as a weighted sum of arctans of 2
−(i−1)
for some small set of contiguous positive integers i. In particular, if the weights are all ±1 then we can rotate a vector (x,y) by iteratively applying the following formula:
x
i
=K
i−1
[x
i−1
−y
i−1
d
i−1
2
−(i−1)
] (3)
y
i
=K
i−1
[y
i−1
+x
i−1
d
i−1
2
−(i−1)
] (4)
where
K
i
-
1
=
cos
(
tan
-
1
2
-
(
i
-
1
)
)
=
1
1
+
2
-
2
(
i
-
1
)
and d
i−1
=±1.
We will henceforth refer to the application of this formula as the i
th
iteration in radix-4 CORDIC. In radix-4 CORDIC, each iteration can be thought of as a simulation of two radix-2 iterations. Therefore we will call the first iteration “iteration number two,” the second iteration “iteration number four,” and, in general, the j
th
iteration “iteration number 2j.”
In practice, we would like to omit the multiplication with the K
i−1
factor, in which case we would not be merely rotating the vector, but also amplifying it by a factor of 1/K
i−1
in iteration i. The total gain for all iterations would be the product of all the K
i−1
's, and would be a constant for a fixed number of iterations n. As n approaches infinity, this constant gain approaches approximately 1.647. In many applications, this gain does no harm so long as it is constant. And it is a constant for a fixed n (number of iterations), so long as d
i−1
=±1.
To apply the above theory to an actual digital apparatus for rotating a vector by a given angle, we use what Volder, in his 1959 referred to earlier in this document, called “rotation-mode CORDIC,” which requires 3 input numbers—one for each of the two components x
0
, y
0
of the vector to be rotated, and a third number &thgr;
0
between -1.743 and +1.743 for the angle by which the given vector is to be rotated. The equations for the i
th
iterations for traditional, Volder-style radix-2 rotation-mode CORDIC is thus as follows:
x
−1
=x
i−1
−y
i−1
d
i−1
2
−(i−1)
(5)
y
−1
=y
i−1
+x
i−1
d
i−1
2
−(i−1)
(6)
&thgr;
−1
=&thgr;
i−1
−d
i−1
tan
−1
(2
−(i−1)
) (7)
where d
i−1
=−1 if &thgr;
i−1
<0 and +1 otherwise.
The choice of d
i−1
at each iteration is to bring the value in the angle accumulator (which was initialized to &thgr;
0
, the angle by which the vector is to be rotated) as close to 0 as possible. The idea is that after all the iterations have been performed, that angle would become 0 for the given precision at which the angle accumulator is kept. As a consequence of that angle becoming 0, the given vector will have been rotated by an amount equal to the input angle &thgr;
0.
Traditionally we will need as many iterations as there are fraction bits in the angle accumulator. But in practice it is possible to go through fewer iterations, if we accept the resulting imprecision in the total amount of vector rotation according to the 1998 paper by Andraka mentioned earlier in this document. According to that reference, the magnitude converges much faster than the phase, and so in applications in which phase accuracy is not critical (which is not uncommon in telecommunications, for example), only about half the usual number of iterations will be required.
Though simple, the method just explains suffers from 1-bit-at-a-time convergence. That is, for n bits of fractional precision, n iterations are needed (for full accuracy both in phase and magnitude), each involving 3 full-precision addition or subtraction. What seems to hinder Volder's circuit down is that it is unobvious how to select an d
i−1
without first computing &thgr;
i−1
. But improvements are possible, as we will discuss next.
Many researchers and inventors have improved on or extended Volder's method in various ways over the last few decades. Of these improvements or extensions, one of the most remarkable (and relevant to the result to be presented here) was by Baker, explained in the following paper: P. W. Baker, “Suggestion for a Fast Sine/Cosine Generator,” IEEE Transactions on Computers, pp. 1134-1136, Nov. 1976. Stated simply, Baker based his circuit on the observation that after a few initial radix-2 iterations, an entire sequence of d
i−1
's can be predicted at once, allowing the corresponding iterations to be done simultaneously using carry-save adders. However, Baker did not have a solution for the problem of speeding up the initial iterations. Thus improvements are still possible wherein the initial iterations would also be sped up.
In Vitit Kantabutra's article, “On Hardware for Computing Exponential and Trigonometric Functions,” IEEE Transactions on Computers, 45:3, March, 1996, as well as in Vitit Kantabutra's U.S. Patent No. 6,055,553, entitled, “Apparatus for Computing Exponential and Trigonometric Functions,” a new CORDIC variant was presented, wherein 8 iterations are lumped into a single iteration that does not take as long as 8 of the original iterations because of the fast, low-precision arithmetic used. This scheme therefore is able to speed up initial iterations (as well as the latter iterations). Due to the need for circuitry to handle 8 “logical” or original iterations in a single “physical” or new iterat
LandOfFree
Efficient radix-4 CORDIC vector rotators and computers of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient radix-4 CORDIC vector rotators and computers of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient radix-4 CORDIC vector rotators and computers of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980587