Mark Newman Blog on DSPRelated.com

How the Cooley-Tukey FFT Algorithm Works | Part 4 - Twiddle Factors

Mark Newman — Mon, 02 Dec 2024 22:01:43 +0000

The beauty of the FFT algorithm is that it does the same thing over and over again. It treats every stage of the calculation in exactly the same way. However, this causes a problem. Not all the samples in the signal were sampled at the same time. They occupy different positions on the x-axis in relation to the cosine and sine waves the Fourier Transform tests the signal with. How can...

How the Cooley-Tukey FFT Algorithm Works | Part 3 - The Inner Butterfly

Mark Newman — Mon, 25 Nov 2024 09:42:09 +0000

At the heart of the Cooley-Tukey FFT algorithm sits a butterfly. We're not talking about a real butterfly of course, but a mathematical one. The shape of the data-flow diagram for a 2-Point Discrete Fourier Transform is strangely reminiscent of a butterfly's wings.

In Part 1 of this article, we saw how the FFT takes advantage of multiplications that repeat...

How the Cooley-Tukey FFT Algorithm Works | Part 2 - Divide & Conquer

Mark Newman — Mon, 18 Nov 2024 11:44:04 +0000

In Part 1, we saw how the Fast Fourier Transform takes advantage of calculations that repeat themselves at different frequencies in the Discrete Fourier Transform. This will happen so long as we ensure that the number of samples we are analyzing is equal to a power of 2. By remembering the result from one multiplication, it saves having to do the same calculation when it comes up again...

How the Cooley-Tukey FFT Algorithm Works | Part 1 - Repeating Calculations

Mark Newman — Mon, 11 Nov 2024 20:46:50 +0000

The Fourier Transform is everywhere. Few are the days in your life when you don’t pick up a piece of technology that implements it. However, this wouldn’t be the case if a way hadn’t been found to make it easier to calculate.

Enter James Cooley and John Tukey, two American mathematicians who published a paper in 1965 in which they proposed a recursive algorithm that vastly...