2
$\begingroup$

I'm trying to implement an FFT to understand how it works. I'm using a random sound file (so i can't control the size of the signal), with a sampling frequency of 44,1Khz. I'm using this library

https://www.nayuki.io/res/free-small-fft-in-multiple-languages/Fft.java

The objective is to apply this formula to get the frequency: F = n * Fs/N

With n number of bins. Fs sampling frequency, and N size of the FFT

1)An Fft is supposed to have a length, most of them use a power of 2 radix. But how can i know the length of the FFT if i apply it to an entire array of data ? is it the size of that array ?

2)I don't understand the bins, how is it processed ? i know that FFT works with chunks of data, but if i give a full array of data, how are the bins "created".

$\endgroup$
  • 2
    $\begingroup$ These questions can be answered with just a little bit of internet searching and reading. I also recommend that you start your coding with mathematically constructed signals of fairly short duration and apply your FFT software to those and examine the results. $\endgroup$ – Cedron Dawg Mar 30 '18 at 20:56
  • $\begingroup$ I actually did search a lot but i couldn't understand, but maybe i'm just too slow. thank you for your concern. $\endgroup$ – Bouji Mar 31 '18 at 12:40
  • 1
    $\begingroup$ Try searching on "Discrete Fourier Transform" or "how does a DFT work" instead of "how does a FFT work". A Fast Fourier Transform is a computational shortcut of a Discrete Fourier Transform. With the latter search you are more likely to find info on the computational efficiency rather than the underlying process. I don't see how you can expect somebody to explain the fundamentals better in a quick forum answer than a bunch of web sites dedicated to doing just that. The first four articles in my blog should be useful to you too. Start with dsprelated.com/showarticle/754.php. $\endgroup$ – Cedron Dawg Mar 31 '18 at 12:56
6
$\begingroup$

Question 1

If you apply it over the entire length of the array, the length of the FFT would be the length of the array. But, the FFT is more efficient if the length is a power of two, so it is common to pad 0's onto the end of the signal until its length is a power of 2.

Overly simple example...

x = [3.4, 2.56, 1.3]

x has a length of 3, the next power of 2 after 3 is 4, so we change x to be

x = [3.4, 2.56, 1.3, 0]

and apply an FFT with length 4.

Another big BUT! If your signal is long, it becomes extremely inefficient to do the whole thing at once. You would not want to try to do an FFT on an audio file the length of even a short song. In that case, we break the signal into chunks of some reasonable size, perform an FFT on each, and average the results.

Odds are good that what you actually want to do with your data is a not just a standard FFT, but rather the averaging process I described above. Google Bartlett and Welch methods for more details.

Question 2

I'm not 100% sure what you're asking about here. I'm going to interpret it as you wanting know how the width of the frequency bins are determined and run with that.

The width of each frequency bin is determines solely by the rate the signal was sampled at and the length of the FFT. The width of each bin is the sampling frequency divided by the number of samples in your FFT.

df = fs / N

Frequency bins start from -fs/2 and go up to fs/2. That means if sampled at 100Hz for 100 samples, your frequency bins will be width 1Hz. If you take 200 samples, you will now have 2x as many frequency bins and their width will be 1/2Hz each.

$\endgroup$
  • $\begingroup$ Thank you very much, it was everything i didn't understand. $\endgroup$ – Bouji Mar 31 '18 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.