# DSP for 11M element FFT

Discussion in 'Embedded Systems and Microcontrollers' started by evilclem, Dec 22, 2011.

1. ### evilclem Thread Starter Member

Dec 20, 2011
118
16
Hi all,

We are currently looking into spectrum analysis to find the resonant frequency of a wire.

The frequency range we are targeting is 1 kHz to 3 kHz so I will be using a sample rate of about 11025 Hz.

Since we are chasing 0.001Hz resolution I will have an array length of approximately 11.025e6 elements.

I estimate that about 22000 million cycles of the DFT loop (not calculated how many machine cycles in each loop) will be required which I estimate to be too much for many MCU's to perform in the required time frame of 1 minute. In an ideal world we would take a new sample every 1 or 2 minutes.

Does anyone know of a DSP that would do the task with such a large array length?

2. ### MrChips Moderator

Oct 2, 2009
12,635
3,454
Here is the simple math. For 0.001Hz resolution you have to sample for 1000 seconds giving 11 million samples at 11025sps. This will take 17 minutes to acquire.

3. ### evilclem Thread Starter Member

Dec 20, 2011
118
16
Can I not zero pad the 11025 samples?

4. ### thatoneguy AAC Fanatic!

Feb 19, 2009
6,357
718
Why not drive the wire with frequency sweeps of 10uHz steps, and measure when the amplitude is greatest?

5. ### MrChips Moderator

Oct 2, 2009
12,635
3,454
I got into an argument with someone else on AAC. He said you can and I said you cannot.

6. ### evilclem Thread Starter Member

Dec 20, 2011
118
16
Was there a difinitive answer/outcome to this argument?

If not then it would appear that I need to investigate it. Shouldn't be too tricky, but will need to test at lower resolution as the wire won't vibrate for 17 minutes.

7. ### evilclem Thread Starter Member

Dec 20, 2011
118
16
This idea could work, we can drive the full range and then zoom the range in until we've obtained the required resolution.

8. ### MrChips Moderator

Oct 2, 2009
12,635
3,454
Intuitively, I guess the answer is yes and no. If you pad the data set to 11025 points you will get an FFT with data points spaced every 0.001Hz.
But if you sampled for 100 seconds instead of 1000 seconds, you would essentially be smoothing your frequency plot with a 10-point filter. It would be equivalent to taking the average of every 10 points in frequency space.

9. ### Tesla23 Active Member

May 10, 2009
323
67
check out http://www.fftw.org/ for benchmarks. They suggest that for a 2^24 length complex FFT you will have 5 N log2(N) flops, or about 2e9, less if you use a real implementation. Any modern intel cpu should achieve this - check out the benchmarks on fftw - and these are several years old, and they achieve over 2GFlops, giving you one FFT per second.

Note that for a 16M FFT you can't fit all the data in the cache, so the performance is dominated by the speed of the RAM bus, and is much lower than you see for smaller FFTs.

10. ### thatoneguy AAC Fanatic!

Feb 19, 2009
6,357
718
That's the easiest method of finding the resonant frequency of a filter if it's a "black box" and you know it is a filter.

You are looking at the problem the hard way.

11. ### evilclem Thread Starter Member

Dec 20, 2011
118
16
That's why I came here, to help make sure I'm not leading myself too far up the garden path.

12. ### evilclem Thread Starter Member

Dec 20, 2011
118
16
Which brings up another question, would this be a significant obstruction to finding the one resonant frequency? The resonant frequency is still likely to have the highest amplitude peak in the fft with nearby frequencies or bins having amplitudes slowly roll down in amplitude rather than a perhaps sharper drop off that may be noticed without zero padding.

13. ### MrChips Moderator

Oct 2, 2009
12,635
3,454
You are practically answering your own question. Shows that you are thinking.

14. ### thatoneguy AAC Fanatic!

Feb 19, 2009
6,357
718
Somehow that happens a lot. Something about trying to write out what you are trying to say ends up answering your own question.

One thread was like that last week.