+ Post New Thread
Results 1 to 16 of 16
  1. #1
    Full Member level 1
    Points: 827, Level: 6

    Join Date
    Mar 2018
    Posts
    98
    Helped
    0 / 0
    Points
    827
    Level
    6

    Implementation of sine cosine using LUT

    I was referring to link https://in.mathworks.com/help/simulink/slref/sine.html that describes the generation of sine through LUT exploiting quarter wave symmetry. I wanted to understand the concept and also how it is different from Cordic?. Matlab always recommends LUT based sine/cos over cordic for fixed point implementation. Why is so?

  2. #2
    Advanced Member level 5
    Points: 24,498, Level: 38
    barry's Avatar
    Join Date
    Mar 2005
    Location
    California, USA
    Posts
    4,703
    Helped
    1038 / 1038
    Points
    24,498
    Level
    38

    Re: Implementation of sine cosine using LUT

    CORDIC is an algorithm for performing calculations. A LUT is simply that, a look-up table: phase in, amplitude out. The CORDIC implementation takes several cycles to produce an output; a LUT produces an output in a single cycle. I suspect MATLAB recommends a LUT based approach because it’s faster.



  3. #3
    Full Member level 1
    Points: 827, Level: 6

    Join Date
    Mar 2018
    Posts
    98
    Helped
    0 / 0
    Points
    827
    Level
    6

    Re: Implementation of sine cosine using LUT

    Hi barry

    I checked matlab and they implement LUT with interpolation. Can you educate me on this?



    •   AltAdvertisement

        
       

  4. #4
    Super Moderator
    Points: 53,239, Level: 56

    Join Date
    Apr 2011
    Location
    Minneapolis, Minnesota, USA
    Posts
    13,015
    Helped
    2588 / 2588
    Points
    53,239
    Level
    56

    Re: Implementation of sine cosine using LUT

    We can generate a look-up table of sines from 0 to 45 degrees by starting with .7071 (sine of 45 deg), and taking equal proportions.

    Thus for 1 degree we take one 45th of .7071. This gives us .0157 which is 10 percent off from the true value (.017). Error increases below 1 degree.

    Values for the entire 360 degree circle are generated in like manner, by taking proportion of distance from 45 or 135 or 225 or 315.

    Doubtless Matlab and Cordic generate their LUT based on a larger number of accurate reference points.



  5. #5
    Advanced Member level 5
    Points: 24,498, Level: 38
    barry's Avatar
    Join Date
    Mar 2005
    Location
    California, USA
    Posts
    4,703
    Helped
    1038 / 1038
    Points
    24,498
    Level
    38

    Re: Implementation of sine cosine using LUT

    You’ll have to read the Matlab documentation.But, if I had to guess, I would assume they simplify take two adjacent points from the LUT and interpolate between them.



  6. #6
    Full Member level 1
    Points: 827, Level: 6

    Join Date
    Mar 2018
    Posts
    98
    Helped
    0 / 0
    Points
    827
    Level
    6

    Re: Implementation of sine cosine using LUT

    In Matlab, the number of points for LUT is 32 only. How do they get the precision?



    •   AltAdvertisement

        
       

  7. #7
    Super Moderator
    Points: 82,019, Level: 69
    Achievements:
    7 years registered
    Awards:
    2nd Helpful Member
    betwixt's Avatar
    Join Date
    Jul 2009
    Location
    Aberdyfi, West Wales, UK
    Posts
    13,453
    Helped
    4488 / 4488
    Points
    82,019
    Level
    69

    Re: Implementation of sine cosine using LUT

    Symmetry - 32 points in 45 degrees means (360/45)*32 = 256 points in total. An average of a little over 1 degree per point but also a convenient LUT size for software/hardware to use.

    Brian
    PLEASE - no friends requests or private emails, I simply don't have time to reply to them all.
    It's better to share your questions and answers on Edaboard so we can all benefit from each others experiences.



    •   AltAdvertisement

        
       

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

    Join Date
    Nov 2012
    Posts
    3,249
    Helped
    808 / 808
    Points
    17,798
    Level
    32

    Re: Implementation of sine cosine using LUT

    We can generate a look-up table of sines from 0 to 45 degrees by starting with .7071 (sine of 45 deg), and taking equal proportions.
    What you are suggesting is called linear extrapolation; look up tables may use actual values and can be more accurate.

    In good old days, we had books that had many kind of tables: log, trigonometric functions, statistical values and many had random numbers. They are the original look up tables.

    The series expansion formula for sin(x) = x - x^3/3! + x^5/5! - x^7/7! + ...

    If you take first three terms, you can get better accuracy ...



  9. #9
    Super Moderator
    Points: 79,089, Level: 68
    Achievements:
    7 years registered
    Awards:
    Most Frequent Poster 3rd Helpful Member

    Join Date
    Apr 2014
    Posts
    16,058
    Helped
    3635 / 3635
    Points
    79,089
    Level
    68

    Re: Implementation of sine cosine using LUT

    Hi,

    @Brian:
    Symmetry - 32 points in 45 degrees means (360/45)*32 = 256 points in total.
    I know the "quarter wave" LUT implementation.... but quarter wave means 4 x 90. How does the 45 table work?

    @gary36:
    How do they get the precision?
    .
    Sure you mean "precision"? Or do you ask about "resolution"?

    Klaus
    Please dont contact me via PM, because there is no time to respond to them. No friend requests. Thank you.



  10. #10
    Super Moderator
    Points: 261,960, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    45,786
    Helped
    13918 / 13918
    Points
    261,960
    Level
    100

    Re: Implementation of sine cosine using LUT

    I know the "quarter wave" LUT implementation.... but quarter wave means 4 x 90. How does the 45 table work?
    Quarter wave is 90 degree, thus 32 points per 90 degree. 45 degree table makes no sense for sine LUT.

    Interpolation error with 32 point table is already very small. There's no application mentioned in this thread, thus the requirements are unknown.

    Series expansion is another possible method, but involving higher calculation effort. LUT with or even without interpolation is most suitable for a large range of microcontroller and programmable logic applications.



  11. #11
    Super Moderator
    Points: 82,019, Level: 69
    Achievements:
    7 years registered
    Awards:
    2nd Helpful Member
    betwixt's Avatar
    Join Date
    Jul 2009
    Location
    Aberdyfi, West Wales, UK
    Posts
    13,453
    Helped
    4488 / 4488
    Points
    82,019
    Level
    69

    Re: Implementation of sine cosine using LUT

    You are quite right to correct me FvM - put my mistakes down to old age.

    They say your memory goes first ...... and I can't remember what comes second.

    Brian.
    PLEASE - no friends requests or private emails, I simply don't have time to reply to them all.
    It's better to share your questions and answers on Edaboard so we can all benefit from each others experiences.



    •   AltAdvertisement

        
       

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

    Join Date
    Nov 2012
    Posts
    3,249
    Helped
    808 / 808
    Points
    17,798
    Level
    32

    Re: Implementation of sine cosine using LUT

    How does the 45 table work?
    Using trigonometric identities.

    For 90 >x >45, we use the formula

    sin(90-x)=cos(x)=sqrt(1-sin^2(x))

    Actually the sinus and cosinus tables are the same (one table does both the work).


    1 members found this post helpful.

  13. #13
    Super Moderator
    Points: 53,239, Level: 56

    Join Date
    Apr 2011
    Location
    Minneapolis, Minnesota, USA
    Posts
    13,015
    Helped
    2588 / 2588
    Points
    53,239
    Level
    56

    Re: Implementation of sine cosine using LUT

    For angle less than 42 degrees from horizontal, multiply by ∏/180 to get sine within 10 percent error.
    Thus 30 degrees x ∏/180 = .5236. Correct value is .5.



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

    Join Date
    Nov 2012
    Posts
    3,249
    Helped
    808 / 808
    Points
    17,798
    Level
    32

    Re: Implementation of sine cosine using LUT

    For angle less than 42 degrees from horizontal, multiply by ∏/180 to get sine within 10 percent error.
    Right. A large part of the sine curve can be approximated by a straight line; see the graph below.

    Click image for larger version. 

Name:	temp.png 
Views:	4 
Size:	7.0 KB 
ID:	156667

    As sin(x) is always within +/-1, 10% accuracy means only one decimal significant digit. For most purposes, this will be insufficient.

    - - - Updated - - -

    Just two terms, you get a much better result: with three terms, you can see the significant improvement:

    Click image for larger version. 

Name:	temp1.png 
Views:	7 
Size:	9.5 KB 
ID:	156668


    1 members found this post helpful.

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

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    45,786
    Helped
    13918 / 13918
    Points
    261,960
    Level
    100

    Re: Implementation of sine cosine using LUT

    Using trigonometric identities.

    For 90 >x >45, we use the formula

    sin(90-x)=cos(x)=sqrt(1-sin^2(x))

    Actually the sinus and cosinus tables are the same (one table does both the work).
    Surely possible but rarely reasonable, neither for C nor programmable logic implementation.



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

    Join Date
    Nov 2012
    Posts
    3,249
    Helped
    808 / 808
    Points
    17,798
    Level
    32

    Re: Implementation of sine cosine using LUT

    Surely possible but rarely reasonable, neither for C nor programmable logic implementation.
    You are right; the look up table has to be computed outside. Only the table has to be stored.

    If you are using a 8-bit interger, -1 to +1 need to be mapped into 0 to 255.You will perhaps get an accuracy of 1% or better.

    If you are using quarter wave, (i.e., 0 to 90 deg), you can perhaps use a table of 16 or 32 values. With a size of 32 values, your each angle will have a resolution of 90/32 (say about 3 degree).

    For intermediate values, a simple linear interpolation will be sufficiently accurate; this is the most common practice.

    For greater accuracy, you need to have 16 bit interger calculations and have 64 or 128 size table. But that depends on the application.

    Once the table is programmed into the microprocessor, there will be no additional computational burden involved (perhaps excepting some small interpolations).

    These are essentially academic discussions because the table has to be made externally only once and there are standard routines available for these trigonometric functions.

    For non-critical work, a simple table of 16 (array of size 16 of unsigned bytes) may be more than sufficient.


    1 members found this post helpful.

--[[ ]]--