Hi,

I am looking for the details and proof of the CORDIC multiplier. I found a paper and a pdf which summarize the algorithms of the elementary functions but the linear mode of CORDIC is only briefly discussed. They mention that for multiplying x0 by z0 (actually to obtain y0 + x0 * z0) we need to perform the following:

x_{i+1} = x0

y_{i+1} = y_{i} + x_{i} * d_{i} * 2^{-i}

z_{i+1} = z_{i} - d_{i} * 2^{-i}

and d_{i} = sign( z_{i} ).

However, I don't get y0 + x0 * z0 unless, according to a thread on edaboard, the initial value of y is zero ( y0=0 ) and x0 and z0 are less than or equal to 1.

I tried to prove the above equation ( y_{n} = y0 + x0 * z0 ) but it seems to be true only under the condition 2^{-i} * y{i} / x_{i} << 1. This condition is almost satisfied when y0=0 because after a few elementary rotations 2^{-i} will become very small but I need a reliable reference to make sure that I have a good insight into this algorithm.

I would appreciate any comment or a detailed reference for the above algorithm 

Not an expert on CORDIC but maybe you are going about this the wrong way.

To my knowledge the CORDIC multiplier is not exactly an efficient way to multiply. If you already have a CORDIC infrastructure in-place for other calculations it might be useful to use it for multiplying as well.

As for the proof: I think that if you look at the general CORDIC structure and do a simple manipulation:

x_{i+1}=x_{i} - 0*y_{i}*d_{i}*2^{-i}

y_{i+1}=y{i} + x_{i}*d_{i}*2^{-i}

z_{i+1}=z{i} - d_{i}*2^{-i}

d_{i}=-1 if z_{i}<0 or +1 otherwise

From this you get to your form above and it can be used for add-multiply operations.

You might find this helpful - A survey of CORDIC algorithms for FPGA-based computers

Thanks for replying Sofer.

Actually the reference you mentioned is the one I have referred to in my question :) and I know that the equations in my post are essentially the basic equations of CORDIC algorithm but the thing I am confused about is that how keeping the x component constant and rotating a vector on a line can lead to multiplication.

In other words, this translates to a simple high-school geometry question that why the rotation shown in the following figure leads to multiplication (y_{R} = y_{in} + x_{in} * z_{in}):

I tried to prove this, but in general the above equation does not seem to be true unless tan(\thet)* y{in} / x_{in} << 1. But this condition is not mentioned in our reference.   

You are not exactly rotating here. The x remains unchanged.

I think it is misleading because you are trying to think about it like a general CORDIC while this is a mathematically manipulated one to yield the ability to multiply

I agree that this is not exactly a rotation but the figure takes the differences with the usual rotation (e.g. keeping x unchanged) into account. And I am deriving my equations from the figure.