0

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?

Community
  • 1
  • 1
Vinay Pandey
  • 1,129
  • 3
  • 16
  • 33

4 Answers4

4

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.

sheepez
  • 986
  • 1
  • 10
  • 26
  • Also, I think the octave implementation doesn't force you to give it 2^n samples. – sheepez Dec 21 '10 at 18:29
  • unless it's a different algorithm, i'd be curious to see how they manage it. – duffymo Dec 21 '10 at 18:39
  • I want to do it in Excel, basically I am trying to develop an add-in for Excel for does this analysis. – Vinay Pandey Dec 21 '10 at 18:40
  • +1. Definitely pad with zeros. The computation increase is not noticeably larger, especially for `N` as small as, say, 2^20 or less. – Steve Tjoa Dec 21 '10 at 18:47
  • You could also truncate your data, but since you are much closer to 128 than 64 padding is probably better. I am pretty sure that zero padding will give the truest spectrum for your data. This might be worth a read http://zone.ni.com/devzone/cda/tut/p/id/4880 – sheepez Dec 21 '10 at 19:35
2

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.

Community
  • 1
  • 1
mtrw
  • 34,200
  • 7
  • 63
  • 71
1

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.

duffymo
  • 305,152
  • 44
  • 369
  • 561
  • Isn't 2^n just a "nice to have" property? I thought blocksizes of any composite number benefit from the divide and conquer approach at the heart of the FFT. – mtrw Dec 21 '10 at 19:21
  • When I last read about FFT it was a requirement; I don't know the details of the Excel implementation, so I can't swear to what it will accept and what it will not. – duffymo Dec 21 '10 at 21:58
  • 2^n aka `radix 2` just happens to be the most common implementation of the FFT, but there are plenty of other sizes possible - they generally use radices which are small primes, sometimes singly, e.g. `radix 3` or `radix 5`, sometimes in combination, aka `mixed radix` FFTs. FFTW will attempt to use mixed radix FFTs if you specify a size which is not 2^n. – Paul R Dec 22 '10 at 16:57
  • OK, so can you tell us if Excel is using an uncommon implementation? I'm guessing that they're using that common way of doing things. – duffymo Dec 23 '10 at 01:02
  • I suspect that Excel only has a radix 2 implementation, so you will need to pad with zeroes to 2^n. – Paul R Dec 23 '10 at 17:17
0

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.

AndreA
  • 295
  • 2
  • 12