1
$\begingroup$

The traditional FFT gives $N=2^k$ outputs for $N=2^k$ inputs (generally complex.) The time effort is $O(N \cdot \log(N))$. If all I want is a compact subset of $M \ll N$ output frequency points, is there some method to "depopulate" the FFT late butterflies and achieve more efficiency than the depopulation burden adds?

The question of the FFT-like algorithm for fast DTFT computation? is close, but first misses the mark being really an off-frequency question, then the Goetzel transform efficiency threshold is far too low for my case.

$\endgroup$
  • $\begingroup$ The first duplicate suggestion is not the same. That is fundimentally an off-frequency question, not a subset frequency question. The second suggestion is very close, but the Goetzl is only efficient for far too small a subset. $\endgroup$ – catraeus Mar 21 '17 at 1:56
  • $\begingroup$ I see- thanks for clarifying. Do you mean is there a way to skip the final combining stages somehow if you do not need all of the frequencies that would result? $\endgroup$ – Dan Boschen Mar 21 '17 at 1:58
  • $\begingroup$ Well, I remember tickling my brain cells from a very long time ago that the FFT butterfly propagates backward from each output in a triangle... thus if the unrolled algorithm is viewed as an N x N grid of calculation points, then there are lower-right and lower-left triangles of calculation that don't need to be done. I'm hoping someone has that knowledge handy. Otherwise, I have a great research problem. $\endgroup$ – catraeus Mar 21 '17 at 2:16
  • 4
    $\begingroup$ there is FFT pruning. $\endgroup$ – robert bristow-johnson Mar 21 '17 at 2:43
  • 1
    $\begingroup$ Possible duplicate of inverse FFT when only a few time points are needed $\endgroup$ – Jason R Mar 21 '17 at 3:30
2
$\begingroup$

Assuming your question is about bypassing the later stages of the FFT if not all samples are needed, this may give you some insight:

Knowing that the FFT alorithm is a successive decimations into even and odd samples so that smaller FFT's can be computed and thus leading to the great efficiency of the algorithm; here is a view of what the digital spectrums look like prior to combining in the final stages:

enter image description here

Everything between the pciture above showing the FFT decimation and the picture below showing the final FFT combining is covered in this post, so I won't repeat it here, but please review it if the plot below is not immediately clear: Is this signal perfect reconstructable?

enter image description here

From reading the linked post and the plots shown above, it will hopefully be clear that unless the signal is combined in the final stage, the spectrum will be superimposed with other regions of the spectrum. So if we work back one stage from the final output, as shown in the figure below, we can hopefully associate with the figure above to see that the upper N/2 pt DFT contains ALL the spectrum (folded on itself), and the lower N/2 pt DFT also contains ALL the spectrum, however separable due to the phase relationship described if combined with the appropriate phase rotations as shown.

So that said, we can see the reason for the combining (and that the signal would be irrecoverable if we did not have access to both prior DFT's). However as long as both DFT's are available for a given point of interest, we can use the mapped output from both DFT's for that point without calculating the rest of the final stage. This of course works back in the same pattern through the implementation of the smaller DFTs (since they two are made up of two DFTs, which are each made up of 2 DFT's etc.

enter image description here

We can see from this plot how the final stage works its way back through these successive DFT's to the input. This plot also gives immediate insight into the possible reduction if only a subset of the points were needed (and shows how quickly any savings if diminished- in this simple case, 1 point is touching 21 of the 48 nodes shown!). I think it is also interesting (perhaps a little mind-blowing) that if you work your way back to the first stage, each 2 pt DFT output for the same reasons described also contains ALL the spectrum, but in this case folded over itself multiple times (depending on how many stages). Hence every 2 pt DFT at the input is connected to every output in the final DFT.

enter image description here

$\endgroup$
  • $\begingroup$ Yes, the last-stage reach to the previous stage is complicated. But, I believe there might be an algorithm to ferret out the depopulation at each preceding FFT. Bit-reversal of addressing is what is happening at the LSB for each FFT so it will be very subtle, but an algorithm might fall out. $\endgroup$ – catraeus Mar 21 '17 at 2:24
  • $\begingroup$ Yes there is obviously some savings; but would be interesting if it outperforms the Goertzel algorithm for example as I do see a quick diminishing of returns. One point is the same as 1 row in the DFT. I can see a nice chart coming showing the FFT, vs Goetrzel vs Catraeus based on FFT size and number of points. I hope this was helpful! $\endgroup$ – Dan Boschen Mar 21 '17 at 2:31
  • $\begingroup$ Very helpful. I see hope for a way forward. The compact subset in the last stage stays compact in the predecessor butterfly, but occupies 2x the (relative) width. This pushes backwards to reduce the depopulation percentage at each stage. I'm on it. It seems this isn't solved, proved intractable or disproved as a line of inquiry for efficiency gain. Goetzel is horribly limiting ... 30 is the break-even point on a 65536 point FFT! $\endgroup$ – catraeus Mar 21 '17 at 2:36

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.