Learn the FFT
In this post I’d like to attempt to explain how the Fast Fourier Transform algorithm works. This post is inspired by many attempts others have made that don’t really do a good job explaining the FFT. Hopefully, I can do a better job. For explanation we’ll use the Cooley–Tukey algorithm which is the most common.
FFT Butterfly Diagram
Above is the so-called Butterfly Diagram which we will arrive at. Refer to the Example FFT Computation in C to see a program that will compute the FFT.
Table of Contents
DFT Definition
The FFT algorithm makes computation of the Discrete Fourier Transform (DFT) more efficient. Much more efficient depending on the size of the input array the computation is being performed on.
Here is the how we’ll define the DFT.
where
The input to the DFT is an array of complex valued numbers. Each element
FFT Example of size 8
In my opinion the best to way to understand the FFT is using an example of size 8 or where
Also, in matrix form for
Hopefully, I have all those constants correct! Check out the symmetry when looking down the columns of the
Why do we need to be efficient?
To do this matrix multiply we need
The reason we need to be concerned with multiplication is that computer processors are slower at multiplication than other mathematical operations such as addition. Long ago they used to be much slower at multiplication than say addition, however, they’ve gotten faster so this point isn’t as strong as it used to be.
Let’s take a realistic example of audio sampled at 48kHz. Let’s say we wanted to do an FFT every 21ms where
Take for example an ARM processor. We can swag a multiply accumulate instruction of a floating point number takes 3 clock cycles - that’s a very commendable number of instructions for a multiply. Let’s call this 3 floating point operations or FLOPS. For each second we’d have to do this roughly 48 times (
The FFT can do this computation much more efficiently. Instead of
Before the Math Starts
The Cooley-Tukey FFT algorithm breaks the DFT into smaller DFTs. Sometimes this is referred to as recursion. There are three parts to this algorithm that we should highlight before we get to the math.
- We will divide the even and odd indices of our input
as many times as it takes to get tuples - When we compute each part of
we will do this in stages where we can use computations from previous stages. - We will exploit the symmetry of the cosine and sine functions to reduce our work.
Breaking down a time series into even and odd parts is also called “Decimation in Time”. For audio say our input to the FFT is a series of samples in time.
Breaking the DFT into even and odd parts
Let’s start with an example with an input of size 8. Watch me break this down into 3 stages until we arrive with 4 pairs of tuples:
As you can see there is a logarithmic pattern here. Each time we cut the elements in each group by half.
Derive Decimation in time for the General Case
Let’s now take the DFT function and break it down into two DFTs by even and odd numbered indices:
Let us summarize this into even
As an exercise to the reader we can also drive the following.
This leaves us with the following:
Let’s stop to look at what we’ve derived.
- The DFT
we broke down to an even and odd part - The DFT is symmetric as the
and differs by only a minus sign on the odd part . - The odd part is multiped by a constant
that doesn’t depend on or the inputs .
Now we can keep breaking the even and odd parts further until we cannot do so anymore. This will leave us with groups of tuples.
Example FFT of size 8
Let’s take an example FFT of size 8. Again, size 8 is the Goldilocks example as it gives us 3 stages to work with and the math is manageable. The algorithm will break into 3 stages since
Recursive Breakdown
Let’s use 3 steps to break down the FFT. As you’ll see 3-stages is the farthest we can break it down.
For the last equation we used
Stage 1: Four sets of Tuples
For our first stage we will compute, and store in temporary locations each of the inner most expressions:
As we’ll see later the weights
Stage 2: Two parts of Four
Although we have two equations Stage 2, the weight
Stage 3: One part of Eight
For our third stage we only have one equation, however
Exploit the Symmetry of the Weights
Now we need to look at the following weights
For our example we have 3 different weights to analyze:
Around the Unit Circle in half’s
When we have
Going around the Unit Circle in two hops
Let’s break this down into 8 values as we have for our example.
This weight only takes on two values
Around the Unit circle in fourths
For the weights
Going around the unit circle in four hops
Let’s show this for each value of
This weight takes on 4 values
Around the Unit circle in eights
For the weights
Going around the unit circle in eight hops
Let’s show this for each value of
This weight takes on 8 values. However, we really only have 3 values when we look at the symmetry of the upper left quadrant and the other 3 quadrants.
Butterfly Diagram
Let’s take our fully broken down equation:
Let’s take some example values of the result from bins of the FFT,
Note, the symmetry of
Now, we can take the equations above to leap to the butterfly diagram below. For each stage we can utilize the results from previous stages to reduce computational load.
FFT Butterfly Diagram
The butterfly diagram above has the weights or twiddle factors we have represented by
Contact Me for any issues or improvements that can be made to this post.