Dear Sir,

- The cordic algorithm is typically used to

  (a.) given (z, alfa) calculate x = z cos(alfa) and y = z sin(alfa)

  (b) given x = z cos(alfa) and y = z sin(alfa), calculate z and alfa

- During the cordic algorithm, there are 3 variables maintained:

  x1, y1, alfa1, and then there are transforms done that leave atan(y/x) + alfa constant, and result is a fixed amplitude growth during the transform. - The transformations done are rotations over a certain angle:

  x1 = x1*cos(angle1) - y1*sin(angle1)

  y1 = y1*cos(angle1) + x1*sin(angle1)

  alfa1 = alfa1 - angle1

- this is then modified into:

  x1 = cos(angle1) * (x1 -y1 *tan(angle1))

  y1 = cos(angle1) * (y1 + x1 * tan(angle1))

  alfa1 = alfa1 - angle1

- There are two forms in which this algorithms is used.

  (a) start with x1 = z, y1 = 0, alfa1 = alfa, and then iterate until alfa1 = zero

  (b) start with x1 = x , y1 = y, alfa1 = 0 and iterate until y1 = zero

- The iterations will use different angles, wherefor tan(angle1) are powers of 2.

   - 1. + or - 90 degree

     2. + or - 45 degree

     3. + or - atan(0.5)

     4. + or - atan(0.25)

- The sign is selected so that either y or alfa go to zero (convergence). The angles are selected such that the multiplication with the tangent is trivial.

- As the +/- sign has no effect on the value of the cos, and the cos only results in a fixed growth of the magnitude of the vector (which is independent of the rotation angle), it is omitted, and the algorithm is simplified to:

x1 = x1 - y1 * tan(angle1)

y1 = y1 + x1 * tan(angle1)

alfa1 = alfa1 - angle1

Now, an 'unfolded cordic' has hardware for every iteration. It has three full adders (one for X, one for Y, one for alfa) for each step of the algorithm. It can execute the algorithm in one clock (when not pipelined.)

A 'folded cordic' maps more steps of the algorithm on the same full adders, and has registers and feedback for this, and also the atan value is selected by a multiplexer as one set of full adders need to represent multiple atan values.

The drawback of the 'unfolded' cordic is the cascade of full adders. If you have eg a 10 iteration cordic, there is a cascade of 10 full adders, and their carry is slow. A 'lookahead' cordic has means to speed up the carry. (I did not find details there.)

Please note, that while the cordic looks nice on paper, the multiple carry paths in the  'unfolded' cordic are a problem. To do the transform x = z cos(alfa) and y = z sin(alfa), you should also consider alternate methods using multipliers. Using multipliers means more logic, but less carry propagation, and this may be faster than the cordic.

Cheers ,

Henri

nice description given by dr cloetens.