Get the latest tech news
Fast Fourier Transforms Part 1: Cooley-Tukey
I’m planning to write a series of posts about fast Fourier transform algorithms. This first post covers the Cooley-Tukey algorithm, which is the original and most well-known FFT algorithm.
\[|\mathcal{F} \{ x \}| = |x|\] \[\mathcal{F} \{ x \}[k] = \sum_{j=0}^{|x|-1} x[j] \cdot e^{-i 2 \pi jk \frac{1}{|x|}}\] Since complex exponentation is so commonly used in Fourier transforms, we’ll define a helpful term \(W_N\) as follows: In fact, the original Cooley-Tukey paper (see “related reading”) specifically described an algorithm to compute the inverse discrete Fourier transform, not the “forward” DFT. I’ve noticed an irritating and confusing tendency among many people–including published authors –when talking about discrete Fourier transforms.
Or read this on Hacker News