I'm trying to perform FFT for large set of samples,
Sampling Rate : 1 MHZ
No. of Samples Captured : 1 Million (1 sec duration)
currently what I'm doing is, I've added zero padding so that it matches to 2^n, and now the total number of samples are 1048576 (2^20) and then I perform FFT. This approach seemed to take long.
I'm just wondering if there's any efficient way to do this? (Please note that at this stage, I'm not particular about the frequency resolution)
The basic physics of the Cooley-Tukey radix-2 Fast Fourier Transform are well-known.
It does log2 N "layers" of butterfly operations. Each layer does N/2 butterflies. Each butterfly does 2 multiplications and 2 additions.
For a binary million (2^20) point sample, that's 20 million multiplications and 20 million additions.
You also need a million-point (maybe half a million, I'm not absolutel certain) twiddle factor table, which you precalculate.
On a DSP, to run in real-time, that's about 40 million operations/second, which is not at all unreasonable today. A modern x86 should have no problem with this, PROVIDED OF COURSE that you are doing compiled machine code and hardware arithemtic, and that your FFT code is properly optimized for your particular hardware.
Start with the well-known Fastest FFT in the West.
If you're trying to do this on an Arduino, you are going to have some problems. It just doesn't have the horsepower.
All that is background.
The first thing to ask is this: Do you NEED frequency range up to 1 MHz AND resolution down to 1 Hz?
If you don't need 1 Hz resolution, but you are looking for high-frequency signals, keep your 1 MHz sample rate and do smaller FFTs. Halving your sample size halves your butterfly/layer count and drops your layer count by one: Instead of doing 20 layers of half a million butterflies, you do 19 layers of a quarter of a million butterflies.
If you're looking for low-frequency signals, and you don't need extreme frequency resolution, go to a slower sample rate, or downsample your 1 MHz samples. This has the same effect.
