09-08-2014, 12:23 PM
Compact and Efficient Generation of Trigonometric Functions
using a CORDIC algorithm
[attachment=66797]
Introduction
Often trigonometric functions are used in embedded applications. Examples of this include motion control,
filtering and waveform synthesis. For waveforms with few output points per cycle (for example one output
point per degree) a lookup table will often suffice, and indeed this method is optimal in that it offers a
reasonable compromise between speed and the need to use the microcontroller’s memory efficiently.
For waveforms with many output points per cycle (consider a waveform with 4096 points per cycle) the
lookup table approach is often unfeasible because of the memory requirements. In the case of a waveform
with 4096 output points per cycle the lookup table alone would occupy at least 4kB of Flash, and more
often the table would take 8kB of memory. This precludes the use of such a lookup table on the lowest
cost microcontrollers with their limited Flash memory.
It would appear from the above that where many points are required on a waveform it would be more
practical to compute points on the waveform in real time when required and output them as they are
computed. This raises the question of how to compute trigonometric functions efficiently. Various methods
exist. These include Taylor Series; various curve fitting algorithms and the CORDIC (COordinate Rotation
DIgital Computer) algorithm. The CORDIC algorithm often offers the most elegant solution to the problem,
and it is astounding in its simplicity of implementation, efficiency and elegance
Pseudocode CORDIC algorithm
The algorithm is presented in its most basic form in a ‘C’ like pseudocode. We will assume a 12-step
system. This will yield 12 bits of accuracy in the final answer. Note that the Cos Θ constant for a 12 step
algorithm is 0.60725. We also assume that the 12 values of Atan (1/2I
) have been calculated before run
time and stored along with the rest of the algorithm. If true floating-point operations are used then the shift
operations must be modified to divide by 2 operations.
Establishing a Program
Examination of the above algorithm shows that several basic procedures are needed. These are:
16 bit shift: A routine to shift a 16 bit number right by I places is needed. This must be an arithmetic shift,
as it must include sign extension.
Lookup routine: A routine is needed to retrieve a 16-bit number from a 12 entry lookup table.
Negation routine: A routine to negate a number represented as a 16 bit 2’s compliment number.
Addition routine: A routine to add two 16 bit numbers.