Evaluating Polynomials in an FPGA

Sometimes, a polynomial will need to be evaluated at a specific value in an algorithm.  This might be used for curve fitting or interpolation.  Another case is for Galois Fields and error correction, where high-degree polynomials are common.  There is more than one way to express a polynomial, and there is more than one way to evaluate it.  Each has a different implication in terms of additions and multiplications.

There are two obvious ways to evaluate a polynomial, such as .  The first is to determine the intermediate and . The next step is to determine , , .  Finally, these intermediate terms are added up, giving the result.

The second way is to express the polynomial as .  This is a more iterative approach.  To calculate this, is evaluated, then , then , then , and then finally d is added to give the result.

Each of the above methods has advantages in different cases.  The alternate approach allows for easier evaluation when the evaluation occurs over several clock cycles.  I recently moved the syndrome computation in my Reed-Solomon decoder over to use this alternate approach.  Before, I had determined the value of first, then generated a structure that multiplied this by each cycle.  A second structure was used to multiply a coefficient by the current power of x.

Moving to the alternate form, I was able to remove the need to keep track of the current value of x.  This allowed me to remove about half of the logic in the syndrome computations.  At this time, I have not moved the same approach over to the computation of the error magnitudes, though such would be possible.

For a multi-cycle algorithm, it makes sense to use the alternate form.  It removes the need to keep track of the current value of x raised to some power.  It also removes the state machine logic to do that calculation.