Arithmetic - Signal Processing Systems - page 619

Fig. 34 Block diagram for
Horner's method used for
polynomial evaluation

b n b n −1 b 1 b 0

X

6.2 Polynomial and Piecewise Polynomial Approximations

It is possible to derive a polynomial p ( X ) that approximates a function f ( X ) by

performing a Taylor expansion for a given point a such as

∞
i = 0

f ( i ) (

)

a

i

p ( X )= ( X − a ) . (59)

i !

When the polynomial is restricted to a certain number of terms it is often better
to optimize the polynomial coefficients as there is some accuracy to be gained.
To determine the best coefficients is an approximation problems where typically
there are more constraints (number of points for the approximation) than variables
(polynomial order). This problem can be solved for a minimax solution using e.g.
Remez' exchange algorithm or linear programming. For a least square solution, the
standard methods to solve overdetermined systems can be applied. If fixed-point
coefficients are required, the problem becomes much harder.
The polynomial approximations can be efficiently and accurately evaluated using
Horner's method. This says that a polynomial

b 2 X 2 b n − 1 X n − 1 b n X n

p ( X )= b 0 + b 1 X + + ··· + + (60)

is to be evaluated as

p ( X )=(( ... (( b n X + b n − 1 ) X + b n − 1 ) X + ··· + b 2 ) X + b 1 ) X + b 0 (61)

Hence, there no need to compute any powers of x explicitly and a minimum number
of arithmetic operations is used. Polynomial evaluation using Horner's method maps
nicely to MAC-operations. The resulting scheme is illustrated in Fig. 34 .
The drawback of Horner's method is that the computation is inherently sequen-
tial. An alternative is to use Estrin's method [ 36 ] , which by explicitly computing the
terms X 2 i rearranges the computation in a tree structure, increasing the parallelism
and reducing the longest computational path. Estrin's method for polynomial
evaluation can be written as

X 2

( )=( + ) +( + )

p X b 3 X b 2 b 1 X b 0 (62)