# DSP for 11M element FFT

#### evilclem

Joined Dec 20, 2011
118
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?

#### MrChips

Joined Oct 2, 2009
30,442
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.

#### evilclem

Joined Dec 20, 2011
118
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.
Can I not zero pad the 11025 samples?

#### thatoneguy

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

#### MrChips

Joined Oct 2, 2009
30,442
Can I not zero pad the 11025 samples?
I got into an argument with someone else on AAC. He said you can and I said you cannot.

#### evilclem

Joined Dec 20, 2011
118
I got into an argument with someone else on AAC. He said you can and I said you cannot.
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.

#### evilclem

Joined Dec 20, 2011
118
Why not drive the wire with frequency sweeps of 10uHz steps, and measure when the amplitude is greatest?
This idea could work, we can drive the full range and then zoom the range in until we've obtained the required resolution.

#### MrChips

Joined Oct 2, 2009
30,442
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.
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.

#### Tesla23

Joined May 10, 2009
542
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?
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.

#### thatoneguy

Joined Feb 19, 2009
6,359
This idea could work, we can drive the full range and then zoom the range in until we've obtained the required resolution.
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.

#### evilclem

Joined Dec 20, 2011
118
You are looking at the problem the hard way.
That's why I came here, to help make sure I'm not leading myself too far up the garden path.

#### evilclem

Joined Dec 20, 2011
118
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.
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.

#### MrChips

Joined Oct 2, 2009
30,442
You are practically answering your own question. Shows that you are thinking.

#### thatoneguy

Joined Feb 19, 2009
6,359
You are practically answering your own question. Shows that you are thinking.
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.