6
$\begingroup$

I'm trying to implement a Fourier transform in an OpenGL shader. I found some literature that explains the general principles, but is a bit sparse on some details. And those details are seriously confusing me.

This paper describes the use of the Stockham FFT on the GPU. It contains the following diagram: enter image description here

I understand how to calculate the discrete fourier transform for any individual point, but I'm confused how exactly the Stockham FFT proceeds. My understanding was that the FFT in general divides the input into odd and even data points, and then recursively processes these. But the diagram I added above looks reversed to me. It starts by dividing the input into the smallest segments and then adds up to larger ones, I would have expected this to work exactly the other way around.

How exactly does the divide-and-conquer part of the Stockham FFT work?

$\endgroup$
1
$\begingroup$

Both algorithms are DIT, but the main difference is in memory access patern.
Cooley-Tukey - the most popular form of transformation from DFT to FFT comes from cache awareness, which is optimal for CPU pipeline.
Cooley-Tukey in first phase reverses bit order while Stockham changes order at each stage.
This is observable if you take look at edges - once you have half of the data it stays in place for Cooley-Tukey but moves for Stockham.

For CPU Stockham makes cache mispredictions while Cooley-Tukey makes thread serialization for GPU.

FFT - look at BFS vs DFS strategy.

FFT stage decomposition - very nice pdf showing butterfly explicitly for different FFT implementations.

$\endgroup$
0
$\begingroup$

There are two variants of FFT: Decimation in Time (DIT) and Decimation in Frequency (DIF). What you describe is DIT, whereas the diagram shows DIF. The only difference is the order in which the bits are processed – LSB to MSB in DIT, and MSB to LSB in DIF.

There are many online resources describing this – see for example these slides.

$\endgroup$
  • $\begingroup$ Hmm, the paper explicitly mentions DIT in this particular figure $\endgroup$ – Bettina Jan 11 '16 at 21:35
  • $\begingroup$ I guess one of us made a mistake. $\endgroup$ – Yuval Filmus Jan 11 '16 at 21:35

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.