| 1 |
14 |
root |
<!--# set var="title" value="CORDIC Core" -->
|
| 2 |
|
|
<!--# include virtual="/ssi/ssi_start.shtml" -->
|
| 3 |
|
|
<BODY>
|
| 4 |
|
|
<B><FONT FACE="Helvetica,Arial" SIZE=+2 COLOR="#bf0000">Project Name: CORDIC core<BR>
|
| 5 |
|
|
(COordinate Rotation on a DIgital Computer)</B></FONT> </P>
|
| 6 |
|
|
<B><U><FONT SIZE=4><P>Description</B></U></FONT> </P>
|
| 7 |
|
|
<P>The CORDIC algorithm is an iterative algorithm to evaluate many mathematical functions, such as trigonometrically functions, hyperbolic functions and planar rotations.</P>
|
| 8 |
|
|
<B><U><FONT SIZE=4><P>Core Description</B></U></FONT> </P>
|
| 9 |
|
|
<P>As the name suggests the CORDIC algorithm was developed for rotating coordinates, a piece of hardware for doing real-time navigational computations in the 1950's. The CORDIC uses a sequence like successive approximation to reach its results. The nice part is it does this by adding/subtracting and shifting only.<BR>
|
| 10 |
|
|
<BR>
|
| 11 |
|
|
Suppose we want to rotate a point(X,Y) by an angle(Z). The coordinates for the new point(Xnew, Ynew) are:</P><DIR>
|
| 12 |
|
|
|
| 13 |
|
|
<P>Xnew = X * cos(Z) - Y * sin(Z)<BR>
|
| 14 |
|
|
Ynew = Y * cos(Z) + X * sin(Z)</P></DIR>
|
| 15 |
|
|
|
| 16 |
|
|
<P>Or rewritten:</P><DIR>
|
| 17 |
|
|
|
| 18 |
|
|
<P>Xnew / cos(Z) = X - Y * tan(Z)<BR>
|
| 19 |
|
|
Ynew / cos(Z) = Y + X * tan(Z)</P></DIR>
|
| 20 |
|
|
|
| 21 |
|
|
<P>It is possible to break the angle into small pieces, such that the tangents of these pieces are always a power of 2. This results in the following equations: </P><DIR>
|
| 22 |
|
|
|
| 23 |
|
|
<P>X(n+1) = P(n) * ( X(n) - Y(n) / 2^n)<BR>
|
| 24 |
|
|
Y(n+1) = P(n) * ( Y(n) + X(n) / 2^n)<BR>
|
| 25 |
|
|
Z(n) = atan(1/2^n)</P></DIR>
|
| 26 |
|
|
|
| 27 |
|
|
<P>The atan(1/2^n) has to be pre-computed, because the algorithm uses it to approximate the angle. The P(n) factor can be eliminated from the equations by pre-computing its final result. If we multiply all P(n)'s together we get the aggregate constant.</P><DIR>
|
| 28 |
|
|
|
| 29 |
|
|
<P>P = cos(atan(1/2^0)) * cos(atan(1/2^1)) * cos(atan(1/2^2))....cos(atan(1/2^n)) </P></DIR>
|
| 30 |
|
|
|
| 31 |
|
|
<P>This is a constant which reaches 0.607... Depending on the number of iterations and the number of bits used. The final equations look like this:</P><DIR>
|
| 32 |
|
|
|
| 33 |
|
|
<P>Xnew = 0.607... * sum( X(n) - Y(n) / 2^n)<BR>
|
| 34 |
|
|
Ynew = 0.607... * sum( Y(n) + X(n) / 2^n)</P></DIR>
|
| 35 |
|
|
|
| 36 |
|
|
<P>Now it is clear how we can simply implement this algorithm, it only uses shifts and adds/subs. Or in a program-like style:</P>
|
| 37 |
|
|
|
| 38 |
|
|
<DIR>
|
| 39 |
|
|
<P>For i=0 to n-1<DIR>
|
| 40 |
|
|
|
| 41 |
|
|
<P>If (Z(n) >= 0) then<DIR>
|
| 42 |
|
|
|
| 43 |
|
|
<P>X(n + 1) := X(n) – (Yn/2^n);<BR>
|
| 44 |
|
|
Y(n + 1) := Y(n) + (Xn/2^n);<BR>
|
| 45 |
|
|
Z(n + 1) := Z(n) – atan(1/2^i);</P></DIR>
|
| 46 |
|
|
|
| 47 |
|
|
<P>Else</P><DIR>
|
| 48 |
|
|
|
| 49 |
|
|
<P>X(n + 1) := X(n) + (Yn/2^n);<BR>
|
| 50 |
|
|
Y(n + 1) := Y(n) – (Xn/2^n);<BR>
|
| 51 |
|
|
Z(n + 1) := Z(n) + atan(1/2^i);</P></DIR>
|
| 52 |
|
|
|
| 53 |
|
|
<P>End if;</P></DIR>
|
| 54 |
|
|
|
| 55 |
|
|
<P>End for;</P></DIR>
|
| 56 |
|
|
</DIR>
|
| 57 |
|
|
|
| 58 |
|
|
<P>Where 'n' represents the number of iterations.</P>
|
| 59 |
|
|
<P> </P>
|
| 60 |
|
|
<B><U><FONT SIZE=4><P>Implementation:</B></U></FONT> </P><DIR>
|
| 61 |
|
|
|
| 62 |
|
|
<P>See the on-line <A HREF="cordic.pdf">documentation</A> for more information about the available CORDIC cores.</P>
|
| 63 |
|
|
<P> </P></DIR>
|
| 64 |
|
|
|
| 65 |
|
|
<B><U><FONT SIZE=4><P>Current Status:</B></U></FONT> </P>
|
| 66 |
|
|
|
| 67 |
|
|
<UL>
|
| 68 |
|
|
<LI>Design is available in VHDL from OpenCores CVS via <A HREF="http://www.opencores.org/cvsweb.shtml/">cvsweb</A> or via <A HREF="http://www.opencores.org/cvsmodule.shtml">cvsget</A> </LI>
|
| 69 |
|
|
<LI>ToDo: finish documentation</LI></UL>
|
| 70 |
|
|
|
| 71 |
|
|
<P> </P>
|
| 72 |
|
|
<B><U><FONT SIZE=4><P>Synthesis:</B></U></FONT> </P>
|
| 73 |
|
|
<P>Synthesis using Leonard Spectrum VHDL compiler and Altera Max+PlusII:<BR>
|
| 74 |
|
|
- Altera ACEX(EP1K50-1): 2190lcells@68MHz</P>
|
| 75 |
|
|
<P>Synthesis using Xilinx WebPack v3.2:<BR>
|
| 76 |
|
|
- Spartan-II (XC2S100-6): 704SLICES@93MHz </P>
|
| 77 |
|
|
<P> </P>
|
| 78 |
|
|
<B><U><FONT SIZE=4><P>Author & Maintainer(s):</B></U></FONT> </P><DIR>
|
| 79 |
|
|
|
| 80 |
|
|
<P><A HREF="mailto:rherveille@opencores.org_NOSPAM">Richard Herveille</A></P>
|
| 81 |
|
|
<P> </P></DIR>
|
| 82 |
|
|
|
| 83 |
|
|
<B><U><FONT SIZE=4><P>Mailing-list:</B></U></FONT> </P><DIR>
|
| 84 |
|
|
|
| 85 |
|
|
<P><A HREF="mailto:cores@opencores.org_NOSPAM">cores@opencores.org_NOSPAM</A></P></DIR>
|
| 86 |
|
|
|
| 87 |
|
|
<P>
|
| 88 |
|
|
</BODY>
|
| 89 |
|
|
<!--# include virtual="/ssi/ssi_end.shtml" -->
|
