Cordic method and architecture applied in vector rotation

• US 20030097388A1
• Filed: 05/06/2002
• Published: 05/22/2003
• Est. Priority Date: 10/31/2001
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Wu, Cheng-Shing, Pan, Chia-Ho, Wu, An-Yeu
• Granted Patent: US 7,047,269 B2
• Time in Patent Office: Days
• US Class Current: 708/441
• CPC Class Codes: G06F 7/5446 using crossaddition algorithms, e.g. CORDIC

Abstract

A CORDIC method and a CORDIC architecture applied in vector rotation are disclosed. An elementary angles set is extended by representing the elementary angles as the arctangent of the sum of two single signed-power-of-two terms to an extended elementary angles set. A combination of elementary angles is found from the extended elementary angles set such that the residue angle error can be minimized. A quantized scaling factor is used to scale the combination of elementary angles after being micro-rotated.

Claims

1. A CORDIC method applied in vector rotation comprising the steps of:

(A) extending an elementary angles set;

S₁={tan<sup>−

1</sup>(a′

*2<sup>−

s′</sup>

);

a′

∈

{−

1,0,1{,s′

∈

{0,1, . . . ,N−

1}},

by representing the elementary angles as the arctangent of the sum of two single signed-power-of-two (SPT) terms (a′

*2<sup>−

s′</sup>

) to an extended elementary angles set;

s₂={tan<sup>−

1</sup>(a′

₀*2<sup>−

s′

₀</sup>+a′

₁*2<sup>−

s′

₁</sup>);

a′

₀,a′

₁∈

{−

1,0,1},s′

₀,s′

₁∈

{0,1, . . . ,N−

1}},

where N is the number of elementary angles;

(B) finding a combination of elementary angles from the extended elementary angles set such that the residue angle error;

${\mathrm{\varepsilon <br><br>}}_m=|\mathrm{\theta <br><br>}-\underset{j=0}{\overset{R_m-1}{\sum <br><br>}}<br><br>{\tan }^{-1}[a_0<br><br>\left(j\right)*2^{-S_0<br><br>\left(j\right)}<br><br>a_1<br><br>\left(j\right)*2^{-S_1<br><br>\left(j\right)}|,$

can be minimized, where θ

is a target angle;

R_m is the maximum iteration number;

j denotes the iteration index;

s₀(j),s₁(j),∈

{0,1, . . . , N−

1} are the rotational sequences;

a₀(j), a₁(j), control direction of j-th micro-rotation of 2<sup>−

S₀(j)</sup>, 2<sup>−

S₁(j)</sup>; and

(C) using a quantized scaling factor to scale the combination of elementary angles determined in step (B) after being micro-rotated.

2. The method as claimed in claim 1, wherein, based on the extended elementary angles set of step (A), the CORDIC method is performed by the recurrence equations:

3. The method as claimed in claim 1, wherein, in step (B), a Trellis-based Searching (TBS) method is employed to find the combination of elementary angles, and the TBS method uses a cumulative angle Φ

(i,k) to denote the best approximation of angle θ

in a k-th state up to an i-th step;

the TBS method comprises the steps of;

(B1) setting all Φ

(i,k) as the corresponding elementary angles r(k);

(B2) for a path which leaves the k-th state at the i-th step and enters the k-th state at the (i+1)-th step, corresponding to an operation of Φ

(i,k)+r(k′

), and for all paths, taking Φ

(i,k)+r(k′

) as the candidate for Φ

(i+1,k′

)

(B3) comparing all candidates for Φ

(i+1,k) at each search step, so as to select a candidate closest to the target angle θ

as Φ

(i+1,k) and record the corresponding path as a surviving path; and

(B4) after calculating the cumulative angles for all states at the last search step, selecting a cumulative angle closest to the target angle θ

for use as a global result θ

_TBS, and tracing along its surviving path backward to determine all micro-rotations.

4. The method as claimed in claim 3, wherein, in step (B3), Φ

(i+1,k) is determined by;

Φ

(i+1,k)=min {|Φ

(i,k*)+r(k)−

θ

|;

1≦

k*≦

Z(S₂)},

where Z(S₂) denotes the number of elementary angles in an extended set S₂.

5. The method as claimed in claim 4, wherein, in step (B4), θ

_TBS is decided by;

θ

_TBS=min {|Φ

(R_m,k′

)−

θ

|;

1≦

k′

≦

Z(S₂)}.

6. The method as claimed in claim 1, wherein, in step (C), the quantized scaling factor is:

7. The method as claimed in claim 6, wherein step (C) accomplishes scaling operations within R, iterations by using recurrence equations:

8. The method as claimed in claim 6, wherein the scaling operation is initialized as ^{{tilde over (x)}(0)=x(R_m)} and ^{{tilde over (y)}(0)=y(R_m)}.

9. A CORDIC processor applied in vector rotation for performing micro-rotational phase operations:

10. The processor as claimed in claim 9, wherein, in the micro-rotational phase, the first and second barrel shifters are shifted by s₁(i) and s₀(i) bits, respectively;

the third and fourth barrel shifters are shifted by s₀(i) and s₁(i) bits, respectively;

the second input terminals of the first and second multiplexers are switched to connect to their output terminals, respectively;

the first input terminals of the third and fourth multiplexers are switched to connect to their output terminals, respectively;

the first to fourth adders/subtracters perform addition and subtraction under the control of a₀(i) and a₁(i).

11. The processor as claimed in claim 9, wherein, in the scaling phase, the first and second barrel shifters are shifted by q₁(m) and q₀(m) bits, respectively;

the third and fourth barrel shifters are shifted by q₀(m) and q₁(m) bits, respectively;

the first input terminals of the first and second multiplexers are switched to connect to their output terminals, respectively;

the second input terminals of the third and fourth multiplexers are switched to connect to their output terminals, respectively;

the first to fourth adders/subtracters perform addition and subtraction under the control of k₀(m) and k₁(m).

12. A CORDIC architecture applied in vector rotation comprising (R_m+R_s) CORDIC processors as claimed in claim 9 connected in cascade form, in which the R_m leading processors are used in the micro-rotational phase and the following R_s processors are used in the scaling phase.