9
$\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: 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. The 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 are they processed? I know that FFT works with chunks of data, but if I give a full array of data, how are the bins "created"?

Improve this question
$\endgroup$
3
  • 4
    $\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
    Commented Mar 30, 2018 at 20:56
  • 1
    $\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
    Commented Mar 31, 2018 at 12:40
  • 2
    $\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
    Commented Mar 31, 2018 at 12:56

1 Answer 1

Reset to default
12
$\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 1 Hz. If you take 200 samples, you will now have 2x as many frequency bins and their width will be 1/2Hz each.

Step further:

Say 'Dur' is the signal duration in time domain, Then the signal size would be:

N = Dur * fs

df = fs / N

df = fs / (Dur * fs)

df = 1 / Dur

This proves that frequency bin for FFT only depends on duration of the signal input. However, you can pad zeros onto/truncate the signal to make the frequency bin size you wish.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much, it was everything i didn't understand. $\endgroup$
    – Bouji
    Commented Mar 31, 2018 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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