Function Evaluation Algorithms
Jonathan Stein · 2000
Commercially available DSP processors are designed to implement FIR, IIR, and FFT computations efficiently, but most neglect to provide facilities for other desirable functions, such as square roots and trigonometric functions. The software libraries that come with such chips do include such functions, but one often finds these general-purpose functions to be unsuitable for the application at hand. Thus, the DSP programmer is compelled to enter the field of numerical approximation of elementary functions. This field boasts a vast literature, but only relatively little of it is directly applicable to DSP applications. As a simple but important example, consider a complex mixer of the type used to shift a signal in frequency. For every sample time tn we must generate both sin(ωtn) and cos(ωtn), which is difficult using the rather limited instruction set of a DSP processor. Lack of accuracy in the calculations will cause phase instabilities in the mixed signal, while loss of precision will cause its frequency to drift. Accurate values can be quickly retrieved from lookup tables, but such tables require large amounts of memory and the values can only be stored for specific arguments. General purpose approximations tend to be inefficient to implement on DSPs and may introduce intolerable inaccuracy. In this chapter we specifically discuss sine and cosine generation, as well as rectangular to polar conversion (needed for demodulation), and the computation of arctangent, square roots, Puthagorean addition and logarithms. In the last section we introduce the CORDIC family of algorithms, and demonstrate its applicability to a variety of computational tasks. The basic CORDIC iteration delivers a bit of accuracy, yet uses only additions and shifts and so can be implemented efficiently in hardware.