+ Post New Thread
Page 1 of 2 1 2 LastLast
Results 1 to 20 of 21
  1. #1
    Member level 2
    Points: 331, Level: 3

    Join Date
    Apr 2019
    Posts
    49
    Helped
    0 / 0
    Points
    331
    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?

  2. #2
    Super Moderator
    Points: 261,871, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    45,764
    Helped
    13912 / 13912
    Points
    261,871
    Level
    100

    Re: Where does this equation come from?

    The explanation is in the text on top of the same page.



  3. #3
    Advanced Member level 4
    Points: 7,597, Level: 20
    Achievements:
    7 years registered

    Join Date
    Jul 2010
    Location
    Sweden
    Posts
    1,019
    Helped
    387 / 387
    Points
    7,597
    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.



  4. #4
    Member level 2
    Points: 331, Level: 3

    Join Date
    Apr 2019
    Posts
    49
    Helped
    0 / 0
    Points
    331
    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



    •   AltAdvertisement

        
       

  5. #5
    Advanced Member level 4
    Points: 7,597, Level: 20
    Achievements:
    7 years registered

    Join Date
    Jul 2010
    Location
    Sweden
    Posts
    1,019
    Helped
    387 / 387
    Points
    7,597
    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.



  6. #6
    Member level 2
    Points: 331, Level: 3

    Join Date
    Apr 2019
    Posts
    49
    Helped
    0 / 0
    Points
    331
    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.



  7. #7
    Advanced Member level 4
    Points: 7,597, Level: 20
    Achievements:
    7 years registered

    Join Date
    Jul 2010
    Location
    Sweden
    Posts
    1,019
    Helped
    387 / 387
    Points
    7,597
    Level
    20

    Re: Where does this equation come from?

    Quote Originally Posted by curious_mind View Post
    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.
    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.



  8. #8
    Advanced Member level 5
    Points: 17,748, Level: 32
    Achievements:
    7 years registered

    Join Date
    Nov 2012
    Posts
    3,237
    Helped
    807 / 807
    Points
    17,748
    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?
    It is for good reason they are called circular trigonometric functions. You can also use them for sin and cos functions. But the Pade approximation is simpler and faster.

    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.



    •   AltAdvertisement

        
       

  9. #9
    Advanced Member level 1
    Points: 2,358, Level: 11

    Join Date
    Jan 2019
    Posts
    435
    Helped
    111 / 111
    Points
    2,358
    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



    •   AltAdvertisement

        
       

  10. #10
    Advanced Member level 4
    Points: 7,597, Level: 20
    Achievements:
    7 years registered

    Join Date
    Jul 2010
    Location
    Sweden
    Posts
    1,019
    Helped
    387 / 387
    Points
    7,597
    Level
    20

    Re: Where does this equation come from?

    Quote Originally Posted by c_mitra View Post
    It is for good reason they are called circular trigonometric functions. You can also use them for sin and cos functions. But the Pade approximation is simpler and faster.
    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



  11. #11
    Advanced Member level 5
    Points: 17,748, Level: 32
    Achievements:
    7 years registered

    Join Date
    Nov 2012
    Posts
    3,237
    Helped
    807 / 807
    Points
    17,748
    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.
    This is only "apparently" correct because "shifts" are essentially multiplications or divisions by 2. And if you think in terms of binary system, multiplications are nothing but shifts and additions (particularly integer multiplications).

    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.



  12. #12
    Member level 2
    Points: 331, Level: 3

    Join Date
    Apr 2019
    Posts
    49
    Helped
    0 / 0
    Points
    331
    Level
    3

    Re: Where does this equation come from?

    Can I get sample C code for 16 bit fixed point cordic, which is understandable?



  13. #13
    Advanced Member level 4
    Points: 7,597, Level: 20
    Achievements:
    7 years registered

    Join Date
    Jul 2010
    Location
    Sweden
    Posts
    1,019
    Helped
    387 / 387
    Points
    7,597
    Level
    20

    Re: Where does this equation come from?

    There is pseudo C-code in this article:
    https://www.edn.com/design/signal-pr...RDIC-algorithm



  14. #14
    Member level 2
    Points: 331, Level: 3

    Join Date
    Apr 2019
    Posts
    49
    Helped
    0 / 0
    Points
    331
    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= a-b;
    if(result>32767)
    {
    result=32767;
    }
    else if((result<-32768))
    {
    result=32768;
    }
    return(result);
    }



  15. #15
    Super Moderator
    Points: 261,871, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    45,764
    Helped
    13912 / 13912
    Points
    261,871
    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.



  16. #16
    Member level 2
    Points: 331, Level: 3

    Join Date
    Apr 2019
    Posts
    49
    Helped
    0 / 0
    Points
    331
    Level
    3

    Re: Where does this equation come from?

    Hi FvM,

    No change in the result by changing the datatype



  17. #17
    Super Moderator
    Points: 261,871, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    45,764
    Helped
    13912 / 13912
    Points
    261,871
    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.



  18. #18
    Advanced Member level 5
    Points: 17,748, Level: 32
    Achievements:
    7 years registered

    Join Date
    Nov 2012
    Posts
    3,237
    Helped
    807 / 807
    Points
    17,748
    Level
    32

    Re: Where does this equation come from?

    final_angle= atan_cordic_atan_fixed((int)(testx*32767),(int)(te sty*32767));
    There is a space present; remove the space and recompile. You cannot return a long int (i.e., result) as a regular int (in the two functions add and sub); the compiler may not grumble but the results will be unpredictable.



  19. #19
    Member level 2
    Points: 331, Level: 3

    Join Date
    Apr 2019
    Posts
    49
    Helped
    0 / 0
    Points
    331
    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



  20. #20
    Super Moderator
    Points: 261,871, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    45,764
    Helped
    13912 / 13912
    Points
    261,871
    Level
    100

    Re: Where does this equation come from?

    These are the intermediate result if you don't clip the values to 16 Bit int

    Click image for larger version. 

Name:	cordic.PNG 
Views:	5 
Size:	19.6 KB 
ID:	156443

    You see why the number range can't be handled in 16 bit



    •   AltAdvertisement

        
       

--[[ ]]--