Editing CORDIC (section)

== Modes of operation ==

=== {{anchor|rotation mode}} Rotation mode ===
CORDIC can be used to calculate a number of different functions. This explanation shows how to use CORDIC in ''rotation mode'' to calculate the sine and cosine of an angle, assuming that the desired angle is given in [[radian]]s and represented in a fixed-point format. To determine the sine or cosine for an angle {{nowrap|<math>\beta</math>,}} the ''y'' or ''x'' coordinate of a point on the [[unit circle]] corresponding to the desired angle must be found. Using CORDIC, one would start with the vector <math>v_0</math>:

: <math>v_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}.</math>

[[Image:CORDIC-illustration.svg|thumb|300px|An illustration of the CORDIC algorithm in progress]]
In the first iteration, this vector is rotated 45° counterclockwise to get the vector <math>v_1</math>. Successive iterations rotate the vector in one or the other direction by size-decreasing steps, until the desired angle has been achieved. Each step angle is <math>\gamma_i = \arctan{(2^{-i})}</math> for <math>i = 0, 1, 2, \dots</math>.

More formally, every iteration calculates a rotation, which is performed by multiplying the vector <math>v_i</math> with the [[rotation matrix]] <math>R_{i}</math>:

: <math>v_{i+1} = R_i v_i.</math>

The rotation matrix is given by

: <math>R_i = \begin{bmatrix}
 \cos(\gamma_i) & -\sin(\gamma_i) \\
 \sin(\gamma_i) & \cos(\gamma_i)
\end{bmatrix}.</math>

Using the [[List of trigonometric identities|trigonometric identity]]:

: <math>\begin{align} 
 \tan(\gamma_i) &\equiv \frac{\sin(\gamma_i)}{\cos(\gamma_i)},
\end{align}</math>

the cosine factor can be taken out to give:

: <math>R_i = \cos(\gamma_i) \begin{bmatrix}
 1 & -\tan(\gamma_i) \\
 \tan(\gamma_i) & 1
\end{bmatrix}.</math>

The expression for the rotated vector <math>v_{i+1} = R_i v_i</math> then becomes:

: <math>\begin{bmatrix}
 x_{i+1} \\
 y_{i+1}
\end{bmatrix} = \cos(\gamma_i) \begin{bmatrix}
 1 & -\tan(\gamma_i) \\
 \tan(\gamma_i) & 1
\end{bmatrix} \begin{bmatrix}
 x_i \\
 y_i
\end{bmatrix},</math>

where <math>x_i</math> and <math>y_i</math> are the components of <math>v_i</math>. Setting the angle <math>\gamma_i</math> for each iteration such that <math>\tan(\gamma_i) = \pm 2^{-i}</math> still yields a series that converges to every possible output value. The multiplication with the tangent can therefore be replaced by a division by a power of two, which is efficiently done in digital computer hardware using a [[bit shift]]. The expression then becomes:

: <math>\begin{bmatrix}
 x_{i+1} \\
 y_{i+1}
\end{bmatrix} = \cos(\arctan(2^{-i})) \begin{bmatrix}
 1 & -\sigma_i 2^{-i} \\
 \sigma_i 2^{-i} & 1
\end{bmatrix} \begin{bmatrix}
 x_i \\
 y_i
\end{bmatrix},</math>

and <math>\sigma_i</math> is used to determine the direction of the rotation: if the angle <math>\gamma_i</math> is positive, then <math>\sigma_i</math> is +1, otherwise it is −1.

The following trigonometric identity can be used to replace the cosine:

: <math>\cos(\gamma_i) \equiv \frac{1}{\sqrt{1 + \tan^2{\gamma_i}}}</math>,

giving this multiplier for each iteration:

: <math>K_i = \cos(\arctan(2^{-i})) = \frac{1}{\sqrt{1 + 2^{-2i}}}.</math>

The <math>K_i</math> factors can then be taken out of the iterative process and applied all at once afterwards with a scaling factor <math>K(n)</math>:

: <math>K(n) = \prod_{i=0}^{n-1} K_i = \prod_{i=0}^{n-1} \frac{1}{\sqrt{1 + 2^{-2i}}},</math>

which is calculated in advance and stored in a table or as a single constant, if the number of iterations is fixed. This correction could also be made in advance, by scaling <math>v_0</math> and hence saving a multiplication. Additionally, it can be noted that<ref name="Muller_2006"/>

: <math>K = \lim_{n \to \infty} K(n) \approx 0.6072529350088812561694</math>

to allow further reduction of the algorithm's complexity. Some applications may avoid correcting for <math>K</math> altogether, resulting in a processing gain <math>A</math>:<ref name="Andraka_1998"/>

: <math>A = \frac{1}{K} = \lim_{n \to \infty} \prod_{i=0}^{n-1} \sqrt{1 + 2^{-2i}} \approx 1.64676025812107.</math>

After a sufficient number of iterations, the vector's angle will be close to the wanted angle <math>\beta</math>. For most ordinary purposes, 40 iterations (''n''&nbsp;=&nbsp;40) are sufficient to obtain the correct result to the 10th decimal place.

The only task left is to determine whether the rotation should be clockwise or counterclockwise at each iteration (choosing the value of <math>\sigma</math>). This is done by keeping track of how much the angle was rotated at each iteration and subtracting that from the wanted angle; then in order to get closer to the wanted angle <math>\beta</math>, if <math>\beta_{n+1}</math> is positive, the rotation is clockwise, otherwise it is negative and the rotation is counterclockwise:

: <math>\beta_0 = \beta </math>

: <math>\beta_{i+1} = \beta_i - \sigma_i \gamma_i, \quad \gamma_i = \arctan(2^{-i}).</math>

The values of <math>\gamma_n</math> must also be precomputed and stored. For small angles it can be approximated with <math>\arctan(\gamma_n) \approx \gamma_n</math> to reduce the table size.

As can be seen in the illustration above, the sine of the angle <math>\beta</math> is the ''y'' coordinate of the final vector <math>v_n,</math> while the ''x'' coordinate is the cosine value.

=== {{anchor|vectoring mode}} Vectoring mode ===
The rotation-mode algorithm described above can rotate any vector (not only a unit vector aligned along the ''x'' axis) by an angle between −90° and +90°. Decisions on the direction of the rotation depend on <math>\beta_i</math> being positive or negative.

The vectoring-mode of operation requires a slight modification of the algorithm. It starts with a vector whose ''x'' coordinate is positive whereas the ''y'' coordinate is arbitrary. Successive rotations have the goal of rotating the vector to the ''x'' axis (and therefore reducing the ''y'' coordinate to zero). At each step, the value of ''y'' determines the direction of the rotation. The final value of <math>\beta_i</math> contains the total angle of rotation. The final value of ''x'' will be the magnitude of the original vector scaled by ''K''. So, an obvious use of the vectoring mode is the transformation from rectangular to polar coordinates.