1
$\begingroup$

​ Hello,

I would like to ask how to decrease (make it narrow) frequency range for calculations in FFT radix 2 - decimation in time - algorithm?

Let me explain what I exactly mean:

When you compute DFT in regular manner (I mean not FFT) you make frequency bin loop, and for each frequency bin you need next loop to use each possible sample you have. Then you can measure whole frequency range - in example for audio it would be something like from 0 Hz to 44100 Hz, of course if you have buffer size the same as sample rate 44100. But very often we don’t need to calculate whole frequency range, in example for audio very often 20 Hz to 20 kHz is perfectly enough. So in regular computation of DFT, you can just change frequency bin loop range, and then you use all possible samples but measure only those chosen frequences.

But when you compute DFT by FFT algorithm, you first divide your buffer size by half of a buffer size, so in my example you compute 22050 DFTs with two point size of each. And then you conquer results in log2(buffer size) steps. From the the first step to the one before last there is no loop that correspond to frequency range or just I can’t see it. Only the last step correspond to frequency range.

So my question is:

can I shrink the frequency range only in that last step, or can I do that in some way for whole FFT algorithm? If yes, could you give me some hint, how to do that?

$\endgroup$
0
$\begingroup$

If you studied the materials I recommended you on comments to your previous question. You would notice that FFT algorithm takes advantage of certain symmetries to make computations faster. If you don't want to work with a whole frequency range simply select the appropriate sampling frequency and concentrate all your FFT resolution points there. If you can't choose your sampling frequency take the samples and then decimate them. Alternatively you can also use the Goertzel algorithm to work only with the frequencies you select.

$\endgroup$
  • $\begingroup$ Hey, thanks for answer. You say "select the appropriate sampling frequency and concentrate all your FFT resolution points there." But that's exactly what I ask. How to do that? Ok I know I can just define other sample rate, for example 20000 Hz instead 44100. But whole algorithm still make calculations for whole range from 0 Hz to 20000 Hz. But I need not from 0 Hz, but in example from 20 Hz. I am not sure how to do that. $\endgroup$ – pajczur Mar 23 '18 at 15:47
  • $\begingroup$ And forgot to mention. Yes I studied materials you recommended, but only lessons 18, 19 and 20. It's great material thanks for that. But for me - maybe it's silly - the real key to understand how to compute FFT was understanding the butterfly chart :) Before I was trying to avoid any contact with butterfly chart, I'm not sure why. Because it looks too complicated for me? :) Or I just prefer analyzing numbers and math symbols than strange charts? But in your materials man spend lot of time to explain that so I decided "I need to understand that butterfly chart". Spent some time but it helped :) $\endgroup$ – pajczur Mar 23 '18 at 15:57
  • $\begingroup$ Yes you will have to work from 0 Hz to 20 kHz. How much will you save in computation in those first 20 Hz? Is it really worth the trouble? $\endgroup$ – VMMF Mar 23 '18 at 15:57
  • $\begingroup$ Maybe you are right here. But I imagined application where you could zoom your FFT graph just to see only some part of freq range, in example from 10 kHz to 15kHz. So below 10 kHz there is 10000 of freq bin that I don't need to calculate. And with 10000 I can save much more :) $\endgroup$ – pajczur Mar 23 '18 at 16:02
  • 1
    $\begingroup$ Ok, we have the deal :) $\endgroup$ – pajczur Mar 23 '18 at 16:42

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.