Implementation of sine cosine using LUT

[gary36]

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?

 

[barry]

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.

 

[gary36]

Hi barry

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

 

[BradtheRad]

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.

 

[barry]

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.

 

[gary36]

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

 

[betwixt]

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

 

[c_mitra]

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

 

[KlausST]

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

 

[FvM]

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.

 

[betwixt]

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.

 

[c_mitra]

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

 

[BradtheRad]

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.

 

[c_mitra]

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.



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:

 

[FvM]

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.

 

[c_mitra]

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.