Help with EXCEL Fast Fourier Transform

I am trying to use Excel's (2007) built in FFT feature, however, it requires that I have 2^n data points - which I do not have.

I have tried two things, both give different results开发者_运维百科:

1. Pad the data values by zeros so that N (the number of data points) reach the closest power of 2
2. Use a divide-and-conquer approach i.e. if I have 112 data points, then I do a FFT for 64, then 32, then 16 (112=64+32+16)

Which is the better approach? I am comfortable writing VBA macros but I am looking for an algorithm which does not require the constraint of N being power of 2. Can anyone help?

Splitting your data into smaller bits will result in erroneous output, especially for smaller numbers of data points.

Padding with zeroes is a much better idea, and the general approach for FFTs. If you are interested in an alternative way of doing the FFT, octave will do it for you, and most of the Matlab documentation applies so you should have no trouble with it.

Padding with zeros is the right direction, but keep in mind that if you're doing the transform in order to estimate frequency content, you will need a window function, and that should be applied to the short block (i.e., if you have 2000 points, apply a 2000 point Hann window, then pad to 2048 and calculate the transform).

If you're developing an add-in, you might consider using one of the many FFT libraries out there. I'm a big fan of KISS FFT by Marc Borgerding. It offers fast transforms for many blocksizes, essentially any blocksize that can be factored into the numbers 2,3,4, and/or 5. It doesn't handle prime number sized blocks though. It's written in very plain C, so should be easy to port to C#. Or, this SO question suggests some libraries that can be used in .NET.

pad out with zeros

2^n is a requirement of the FFT algorithm.

Maybe a test of a known time series (e.g., simple sine or cosine of a single frequency). When you FFT that, you should get a single frequency (Dirac delta function). Anything else is an error. Do it with an integer power of two, padded with zeroes, etc.

You can pad with zeros, or you can use an FFT library that supports arbitrary sizes. One such library is https://github.com/altomani/XL-FFT.

It implements the FFT as a pure formula with LAMBDA functions (i.e. without any VBA code). For power of two length it uses a recursive radix-2 Cooley-Tukey algorithm and for other length a version of Bluestein's algorithm that reduces the calculation to a power of two case.