Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Details of a CORDIC multiplier

Status
Not open for further replies.

mahdi3999

Member level 2
Joined
May 10, 2013
Messages
49
Helped
13
Reputation
24
Reaction score
11
Trophy points
1,288
Activity points
1,657
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:

Code:
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
Code:
d_{i} = sign( z_{i} )

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:

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

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,

Code:
z_{i + 2} = z{i + 1} - d_{i} * 2^{-i} = (z{i} -  d_{i-1} * 2^{-i+1} ) - d_{i} * 2^{-i} = ... = z_0 - sum( d{i} * 2^{i} )

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

Code:
0 = z_0 - sum (d{i}*2^{i} ) -> z_0 \approx sum (d{i}*2^{i} ).

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

Code:
y{i + 1} = y_0 + sum ( x_0 * d_{i} * 2^{-i} ).

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

Code:
y{i + 1} = y_0 + x_0 * sum ( d_{i} * 2^{-i} ) \approx y_0 + x_0 * z_0
 

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.
 
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.

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.
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top