Details of a CORDIC multiplier

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:


and
However, I don't get y0 + x0 * z0 unless, according to another thread, 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.

The heart of the algorithm lies in the last line:


If z is positive, we subtract something. If it is negative we add something. This something is getting smaller and smaller as we go.
Intuitively, z should tend to zero. If we expand out the recurrence relation,


Since as i grows, z{i} \approx 0, we have


Now if we look at Y, we can clearly see that


Since x_0 does not depend on the summation index, we can bring it out of the sum and we have

Hi CCNezin,

Thanks for replying.

Your explanation seems quite reasonable but, with this explanation, we never need to set the initial value of y to zero (y0=0) neither we need to scale x0 and z0 to less than or equal to 1. I have tested a few numerical examples and apparently these are the required conditions. However, these conditions are not at all mentioned in the few references that I have studied.

Hi CCNezin,

I can add this to your explanation that the CORDIC multiplier requires a sufficiently small z0 because after n iterations we have approximated z0 with a sum of powers of two. This means that the maximum z0 is 2^0 + 2^(-1) + 2^(-2) + 2^(-3) + ..., this is about 1.5.

But what about y0 and x0?

I believe that sum is actually approximately 2, haha. However, I believe it is implicit that z0 is less than or equal to the maximum of that sum. The maximum can be increased in the algorithm by shifting the starting index, i, to some negative number. If we do iteration i = -2 : inf for instance, the maximum value would be 2^2 + 2^1 + 2^0 + ... = 8.

As for y0 and x0, I suppose the main constraint is that we don't overflow y{ i }, so assuming y0 is positive (similar analysis can include y0 negative): y0 + x0z0 < M -> x0z0 < M - y0 where M is the largest representable number. This is the equation of a hyperbola in x0 and z0, with M - y0 varying linearly in y0. This term represents how much 'room' the other parameters have. If y0 = M, this term is zero indicating we're in big trouble.

Other than overflow, I don't think there are any other constraints, as long as you carry out a large enough number of iterations.

CCNezin said:

The maximum can be increased in the algorithm by shifting the starting index, i, to some negative number. If we do iteration i = -2 : inf for instance, the maximum value would be 2^2 + 2^1 + 2^0 + ... = 8.

Click to expand...

This is interesting. Have you seen any reference using this method?

By the way, I was making a mistake in my calculations, with the CORDIC multiplier, we only need to scale z0 to the appropriate range or use a different starting index as you said. No other limitations regarding the x and y.
The overflow was not the case at least in my calculations, because I was only checking the theory not a practical implementation.

I haven't really looked at any references for linear CORDIC (only rotation and vectoring) so nope. But it shouldn't make much of a difference, a positive power of two is just shift left instead of shift right.