Details of a CORDIC multiplier

[Mahdi3999]

Hi,

I am looking for the details and proof of the CORDIC multiplier. I found http://www.andraka.com/files/crdcsrvy.pdf and http://web.cs.ucla.edu/digital_arithmetic/files/ch11.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 http://www.edaboard.com/thread314978.html, 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.

[stormtrooper412]

my only experience with CORDIC is complex multiplication with a sine and cosine basically doing a digital down conversion. It worked surprisingly well but in order to get a good result, you need at least 10-12 iterations. Basically your input is interpreted as a complex number Z = x + i*y and your CORDIC probably needs to do Z1=Z*e^{i*w} where you obtain w from the phase increment that you compute (or hard code) elsewhere. If your y=0 then your input is a real number and if you do the math, the outputs will be x*cos(w) and x*sin(w), which is kind of a complex digital AM signal.

Your program is (probably) working fine, it's your interpretation of the output that's off. Either way it's an iterative approximation but it's good for most applications

[Mahdi3999]

Thanks for replying.
I have tested the m-file in the thread that I mentioned previously, it works but I don't know the proof. And the proof is actually a simple geometry question:
In the attached figure which illustrates the CORDIC algorithm in the linear mode, YR must be equal to y_{R} = y_{in} + x_{in} * z_{in} but when I try to prove it I find a condition (tan(\thet)* y{in} / x_{in} << 1) which needs to be satisfied to have the above relationship.

By the way, since today's most processors have multipliers, how do you compare a CORDIC multiplier with a dedicated multiplier. I think the hardware complexity is almost the same, how much slower is CORDIC in comparison with a usual multiplier? What are the main advantages of a CORDIC multiplier?

[Vtile]

Have you looked up what en.wikipedia have to say on the subject? It does have pretty long and detailed article of CORDIC and long list of further reading and references.

[taojipeng]

In my understanding. You can not use traditional triangle function to proof the linear cordic algorithm. It is not circle cordinate. Please read Walther 1971, the angle all defined by area in the three cordinate system, A=(2S)/(R^2). Actually, in linear system, if the radius is unit, the angle is 2S, so the y cordinate of vector is 2S.