+ Post New Thread
Results 1 to 20 of 21

6th November 2019, 05:11 #1
 Join Date
 Apr 2019
 Posts
 48
 Helped
 0 / 0
 Points
 324
 Level
 3
Where does this equation come from?
I was referring to this article http://ww1.microchip.com/downloads/e...tes/01061a.pdf to understand cordic to implement atan function.
After a struggle, concept is just sinking into my brain. At one point I got stuck up. In Page 5, for vectoring mode, the direction di is given as 1 if yi<0 or 1 otherwise. Where does this relation come from? Is it only by observation or any logic behind this?

6th November 2019, 09:15 #2
 Join Date
 Jan 2008
 Location
 Bochum, Germany
 Posts
 45,678
 Helped
 13885 / 13885
 Points
 261,421
 Level
 100
Re: Where does this equation come from?
The explanation is in the text on top of the same page.

6th November 2019, 09:37 #3
 Join Date
 Jul 2010
 Location
 Sweden
 Posts
 1,015
 Helped
 387 / 387
 Points
 7,578
 Level
 20
Re: Where does this equation come from?
The logic is that the vector is always rotated in the direction that gets yi closer to zero.

Advertisement

6th November 2019, 10:13 #4
 Join Date
 Apr 2019
 Posts
 48
 Helped
 0 / 0
 Points
 324
 Level
 3
Re: Where does this equation come from?
hi
I do not actually get how yi becomes negative in the first quadrant? ( let us say original angle to be estimated is 30 degrees). If I do conventional calculations with cosphi and sinphi, I get all positive values for x and y for CW and CCW rotations

6th November 2019, 10:53 #5
 Join Date
 Jul 2010
 Location
 Sweden
 Posts
 1,015
 Helped
 387 / 387
 Points
 7,578
 Level
 20
Re: Where does this equation come from?
In vectoring mode (page 5), if you start with (x, y) values corresponding to 30 degress, yi will be negative after the first rotation, since the first rotation is 45 degrees. Every rotation will bring yi closer to zero.
The only purpose of di is to decide the direction for the next rotation.

6th November 2019, 11:11 #6
 Join Date
 Apr 2019
 Posts
 48
 Helped
 0 / 0
 Points
 324
 Level
 3
Re: Where does this equation come from?
thanks. I tried it and verified through sample c code. It works. I have one last clarification. Why cordic is restricted to pi/2 to pi/2.

6th November 2019, 11:55 #7
 Join Date
 Jul 2010
 Location
 Sweden
 Posts
 1,015
 Helped
 387 / 387
 Points
 7,578
 Level
 20
Re: Where does this equation come from?
That range is enough since you can always use other ranges by simple trigonometric identities.
However, it should be possible to extend the vector algorithm to +/ pi by adding new first rotations arctan(4) and arctan(2)
It gets a little more complicated since you can't get the next rotation direction by only looking at yi.
It should be possible to extend the rotational mode even more, but the efficiency will drop since the rotation angle will not increase much when you go to arctan(8), arctan(16) etc.
It is better to transform the angle into the range pi/2 to pi/2 and then use CORDIC.

Advertisement

6th November 2019, 15:53 #8
 Join Date
 Nov 2012
 Posts
 3,211
 Helped
 799 / 799
 Points
 17,611
 Level
 32
Re: Where does this equation come from?
Where does this relation come from? Is it only by observation or any logic behind this?
The standard expansion for atan(x) converges slowly. There are several devices to get the expansion converge faster. The present method is a variation of Newton Raphson method used in the polar coordinates (if I understand correctly).
I am also not aware of this method but this appears simple and elegant.

Advertisement

6th November 2019, 16:27 #9
 Join Date
 Jan 2019
 Posts
 418
 Helped
 108 / 108
 Points
 2,270
 Level
 11
Re: Where does this equation come from?
see the Wiki article:
https://en.wikipedia.org/wiki/CORDIC
there are several references at the end

7th November 2019, 10:51 #10
 Join Date
 Jul 2010
 Location
 Sweden
 Posts
 1,015
 Helped
 387 / 387
 Points
 7,578
 Level
 20
Re: Where does this equation come from?
That is probably only true if you have a hardware multiplier available with enough number of bits. One feature of the CORDIC algorithm is that there is no multiplication involved. Only shift, add, subtract and a very small table are needed.
CORDIC algorithms helped HP when they designed the revolutionary HP35 calculator, which was released in 1972. How HP35 did it's calculations with extremely limited resources is described in detail here:
http://home.citycable.ch/pierrefleur...035%20Saga.htm

7th November 2019, 11:31 #11
 Join Date
 Nov 2012
 Posts
 3,211
 Helped
 799 / 799
 Points
 17,611
 Level
 32
Re: Where does this equation come from?
One feature of the CORDIC algorithm is that there is no multiplication involved. Only shift, add, subtract and a very small table are needed.
If you recall the days multiplication was taught in high schools: this is not much different from that.
I do not have a ready reference, integer addition can be very fast, integer multiplication is bit slow and integer division is rather slow (all these are done by the CPU and no need for a hardware coprocessor).
And yes, I remember the HP35 it was priced like a computer! But I still have the Sharp calculator from those bygone days: and it still works.

8th November 2019, 13:32 #12
 Join Date
 Apr 2019
 Posts
 48
 Helped
 0 / 0
 Points
 324
 Level
 3
Re: Where does this equation come from?
Can I get sample C code for 16 bit fixed point cordic, which is understandable?

8th November 2019, 14:44 #13
 Join Date
 Jul 2010
 Location
 Sweden
 Posts
 1,015
 Helped
 387 / 387
 Points
 7,578
 Level
 20
Re: Where does this equation come from?
There is pseudo Ccode in this article:
https://www.edn.com/design/signalpr...RDICalgorithm

10th November 2019, 11:21 #14
 Join Date
 Apr 2019
 Posts
 48
 Helped
 0 / 0
 Points
 324
 Level
 3
Re: Where does this equation come from?
I tried implementing fixed point C code. I am getting wrong answer. What could be the problem. Answer is 0x4279 instead of 0x4000
int atan_cordic_atan_fixed(int x, int y);
int add(long int a , long int b);
int sub(long int a , long int b);
double test,testx,testy;
int tanLUT_fixed[16];
int p,q,pnew,qnew,acc,final_angle;
int count;
int main()
{
/*Cordic atan range pi/2 to pi/2 corresponds to to 32768 to 32767.*/
//decimal value= (65535 * angle_deg)/180
test=45; //enter angle
tanLUT_fixed[0]=0x4000; //45 degrees
tanLUT_fixed[1]=0x25c8;
tanLUT_fixed[2]=0x13f6;
tanLUT_fixed[3]=0x0a22;
tanLUT_fixed[4]=0x0516;
tanLUT_fixed[5]=0x028b;
tanLUT_fixed[6]=0x0145;
tanLUT_fixed[7]=0x00A2;
tanLUT_fixed[8]=0x0051;
tanLUT_fixed[9]=0x0029;
tanLUT_fixed[10]=0x0014;
tanLUT_fixed[11]=0x000A;
tanLUT_fixed[12]= 0x0005;
tanLUT_fixed[13]= 0x0002;
tanLUT_fixed[14]= 0x0002;
tanLUT_fixed[15]= 0x0001;
testx=cos(.01745*test);
testy=sin(.01745*test);
final_angle= atan_cordic_atan_fixed((int)(testx*32767),(int)(te sty*32767));
printf("final angle is %x\n",final_angle);
return(1);
}
int atan_cordic_atan_fixed(int x, int y)
{
unsigned int i;
p=x;
q=y;
acc=0;
pnew=0;
qnew=0;
for(i=0;i<15;i++)
{
if(q>0) // CW
{
pnew=add(p,(q>>i));
qnew=sub(q,(p>>i));
p=pnew;
q=qnew;
acc=add(acc,tanLUT_fixed[i]);
}
else //CCW
{
pnew=sub(p,(q>>i));
qnew=add(q,(p>>i));
p=pnew;
q=qnew;
acc=sub(acc,tanLUT_fixed[i]);
}
}
return (acc);
}
int add(long int a , long int b)
{
long int result;
result= a+b;
if(result>32767)
{
result=32767;
}
else if((result<32768))
{
result=32768;
}
return(result);
}
int sub(long int a , long int b)
{
long int result;
result= ab;
if(result>32767)
{
result=32767;
}
else if((result<32768))
{
result=32768;
}
return(result);
}

10th November 2019, 13:54 #15
 Join Date
 Jan 2008
 Location
 Bochum, Germany
 Posts
 45,678
 Helped
 13885 / 13885
 Points
 261,421
 Level
 100
Re: Where does this equation come from?
Check the calculation flow in debugger, pencil & paper or Excel.
You'll notice that p overflows the 16 Bit int range. Use long for p, pnew, q, qnew.
   Updated   
Or scale input values with An.

10th November 2019, 16:14 #16
 Join Date
 Apr 2019
 Posts
 48
 Helped
 0 / 0
 Points
 324
 Level
 3
Re: Where does this equation come from?
Hi FvM,
No change in the result by changing the datatype

Advertisement

10th November 2019, 16:21 #17
 Join Date
 Jan 2008
 Location
 Bochum, Germany
 Posts
 45,678
 Helped
 13885 / 13885
 Points
 261,421
 Level
 100
Re: Where does this equation come from?
You also need to put hands on your add() and sub() functions.
Perhaps you start with a simple thing, test your code with smaller X and Y values and find out when it fails.

10th November 2019, 16:33 #18
 Join Date
 Nov 2012
 Posts
 3,211
 Helped
 799 / 799
 Points
 17,611
 Level
 32
Re: Where does this equation come from?
final_angle= atan_cordic_atan_fixed((int)(testx*32767),(int)(te sty*32767));

10th November 2019, 17:01 #19
 Join Date
 Apr 2019
 Posts
 48
 Helped
 0 / 0
 Points
 324
 Level
 3
Re: Where does this equation come from?
Added the printf in for loop: printf("p,q,accumulator data %d\t%d\t%f\n",(int)p,(int)q,(double)((acc*180.0)/65535));
results are recorded below. The q value does not change sign and hence wrong result. It is strange. Initial values p=23173, q=23166 ( expected value is 45 degrees)
p,q,accumulator data 32767 7 45.000687
p,q,accumulator data 32767 16376 18.435339
p,q,accumulator data 32767 8185 32.470589
p,q,accumulator data 32767 4090 39.595329
p,q,accumulator data 32767 2043 43.171436
p,q,accumulator data 32767 1020 44.959488
p,q,accumulator data 32767 509 45.852139
p,q,accumulator data 32767 254 46.297092
p,q,accumulator data 32767 127 46.519569
p,q,accumulator data 32767 64 46.632183
p,q,accumulator data 32767 33 46.687115
p,q,accumulator data 32767 18 46.714581
p,q,accumulator data 32767 11 46.728313
p,q,accumulator data 32767 8 46.733807
p,q,accumulator data 32767 7 46.739300

10th November 2019, 17:27 #20
 Join Date
 Jan 2008
 Location
 Bochum, Germany
 Posts
 45,678
 Helped
 13885 / 13885
 Points
 261,421
 Level
 100
+ Post New Thread
Please login