Numeric definite integral in FPGA

Today when I looked at the comp.arch.fpga USENET feed, I saw an interesting question: how to perform integration in FPGA? Well, most of the time the answer would be, since FPGA is not handling continuous function, summation would be the approximation for integration. From the first glance, this may look like a right answer. But when we look at the purpose of integration, we find that it is too bad an approximation.

The purpose of integration is usually to find the area under a curve. If that is the case, to evaluate it numerically we have to go for adaptive quadrature algorithms, like Simpson's quadrature, Lobatto's quadrature, Gauss-Konrad quadrature, etc. If you are using MATLAB, you should be familier with the quad functions which has implemented these adaptive quadrature algorithms.

In an FPGA however, we never get input as functions, rather they are outputs of functions. For example, you would never get something like f(x) = (sin(x) + 20) for all 0<=x<=pi. Instead it would be the values of f(x) for each discrete value of x. In that case, the integration can be approximated as sum of area of triangle formed between the adjacent different values and the rectable formed by the lowest of the adjacent values with x-axis (y=0). And this has to be done for each value of x (usually comes with each CLK) and summed up. Once we get the result, we can multiply the result with the difference in x-axis between samples. Usually in an FPGA, the x-axis is CLK and so we have to use CLK period as the scale.

So at each CLK (somebody please tell me how to use LaTeX with blogger):

int(n) = int(n-1) + diff(f(n), f(n-1)) >> 1 + min(f(n), f(n-1))

The function is not as difficult to implement as it looks. The diff(f(n), f(n-1)) >> 1 gives the area of the triangle and min(f(n), f(n-1)) gives the area of the rectangle. "int" is the integration or the area under the curve at that limit. The function works if the CLK frequency is 1 Hz. For the other frequencies, the final integration function just needs to be multiplied by the CLK period.

For an ever-increasing function [f(n) >= f(n-1) for 0<=n<=N], the formula would reduce down to:

int(n) = int(n-1) + (f(n) - f(n-1)) >> 1 + f(n-1)

This works neat, but it is up to the person who implements, to determine whether they need summation or finding area.