# Help with a rather specific implementation of FFT Library?

So, I guess what I'm trying to do here is properly understand the FFT library posted here by Open Music Labs, done in C++. I believe I understand the Fourier transform, but the FFT has some nuance that I'm not quite familiar with. From what I understand, the FFT takes a amplitude vs. time signal and transforms it into its constituent frequencies like a normal Fourier transform, but it only does so at given points that break down the signal into the Arduino's clock speed divided by the number of bins decided on, for the sake of efficiency. Thus each bin actually accounts for a number of frequencies that is also equal to the clock speed divided by bin number. I'm correct so far, right?

So here's my question. I have a very specific application of the FFT that requires reading only frequencies at roughly 0-100 Hz. Everything else I don't need, and I want to know how to achieve such high resolution. I imagine that because the number of bins seems to be capped at around 512, that there must be some sort of way to decrease the clock speed to an exorbitantly low number in order to read these frequencies. How might I go about doing that? Or maybe there is a better way to apply the transform to the data at such low frequencies through some other method outside of FFT?

Second, I'm wondering how performing multiple FFTs simultaneously will affect performance, and if there is some way I can export this data to another program in order to do the heavy lifting regarding data storage, seeing as I imagine performing many FFTs all at once will decimate the available memory on the Arduino itself if all of those values aren't being kept on my computer.

Thanks in advance for any insight you guys might be able to provide

• You are mixing things. There is the “Fourier transform” (FT), the “discrete Fourier transform” (DFT) and the “fast Fourier transform” (FFT). DFT is a generalization of FT for finite sets of data points. FFT is an efficient algorithm for computing a DFT when the number of data points is a power of two. The binning is a feature of the DFT arising from the finite nature of your data set, it has nothing to do with efficiency. “0-100 Hz” is a frequency range, not a resolution. What resolution do you need? – Edgar Bonet Mar 4 '16 at 9:20

## 1 Answer

As Edgar has mentioned you are confusing things slightly.

First there is your sampling frequency. According to the Shannon-Nyquist theorem that is at a minimum of 2x the maximum frequency in your signal. So that is 2x100 = 200Hz. That's the number of samples per second in your sample set.

Secondly is your sample size, which is directly related to the FFT bucket size. For every two samples you can get one bucket. The more samples you have the more buckets you have, and the higher the resolution each bucket is. But for FFT to work you need a power-of-two sized sample set. That means 2, 4, 8, 16 etc samples. So 256 samples would give you 128 buckets. That would be a little under 1Hz per bucket.

To make things cleaner though you can back-apply the last calculation to the first and get them to match. 256 samples at 256 samples per second will give you 128 buckets covering 0-128Hz so 1Hz per bucket. Double that to 512 samples and you get 256 buckets at 0.5Hz per bucket. Double it again and you get double the resolution again.

The main speed issue that you will come across is not the time taken to do the FFT, but the time taken to capture your sample set. 256 samples at 256 samples per secod will, of course, take 1 second to capture. 512 samples will be 2 seconds, etc. Far longer than a decent FFT takes to calculate.

• Ok, that makes it a bit clearer. So, if I follow correctly, it seems like taking a half decent fft at such low frequencies is not a practicable option because increasing sampling rate will up the range of sampled frequencies, thus decreasing resolution, but if I leave it where it is at 256, then it would not be sampling fast enough to achieve a real-time readout. So it seems there has to be a better way to achieve the same effect of at least a 1hz resolution, because, as I understand it now, the Fourier transform is inherently limited for this application. – Scorch Mar 5 '16 at 1:44