The aim of this article is to give a self-contained and rigorous introduction to the Discrete Fourier Transform (DFT) and the Fast Fourier Transform (FFT). I will not discuss any of the numerous applications here, though you are welcome to take a look at my implementation of a Fourier epicycle drawer here.
As motivation, we consider a linear interpolation problem. That is, let be a continuous function on an open set with points for , where
and . Additionally, we will assume that is -periodic.
It is then natural to attempt to tackle this problem by considering linear combinations of elementary trigonometric functions like sine and cosine. Concretely, let and consider functions of the form
Here, we omit the final cosine term when is odd and include it when is even.
The Discrete Fourier Transform
At this point, it would be nice to transform this interpolation problem into a form that we are more familiar with. To achieve this, let's also assume that for . Using the complex definitions of sine and cosine, we can rewrite
To get rid of the negative powers, we can replace by . Note that this replacement is not valid for arbitrary , but is valid at the equidistant interpolation points we chose. For even , the two exponentials in agree at these points because , so . Thus, instead of solving the interpolation problem for , we can seek
satisfying the interpolation conditions for and suitable coefficients .
Using the substitution and , we find that the complex polynomial satisfies for . This now looks a lot more familiar, and we can deduce immediately from the fact that interpolation at distinct nodes has a unique solution among polynomials of degree at most that is uniquely determined.
Now, how do we compute the coefficients of ? Recalling some elementary properties of complex roots of unity, we first deduce that the vectors , for , form an orthogonal (not orthonormal!) basis of under the standard Hermitian inner product. With this fact, we obtain that solves the interpolation problem if and only if
Indeed, let be arbitrary. Then by our previous observations, we can write the condition as a system of equations
If we now multiply both sides by and sum over , we get
By the orthogonality of these vectors, , which yields the desired equality.
The map with is called the Discrete Fourier Transform, commonly abbreviated as DFT. Its inverse is called Fourier synthesis. Clearly, .
The Fast Fourier Transform
In the previous section, we've seen that to solve our interpolation problem, we need to calculate sums of the form
One could naively calculate these sums directly in roughly operations, which is suboptimal for large . This prompted researchers in the 60s to come up with a family of algorithms now collectively known as the Fast Fourier Transform. In this article, we will focus on the algorithm named after J. W. Cooley and John Tukey, which is arguably the most common FFT algorithm. Cooley and Tukey independently rediscovered and popularized the algorithm about 160 years after Gauß, who invented the algorithm.
Decimation in Frequency
We will focus on the case in the following treatment of the FFT, but it is straightforward to generalize to general using the same ideas. The case is immediate: . For , write (so now denotes half the transform length), and let . We distinguish between the even- and odd-indexed coefficients . In particular, the following relations hold:
and
for . These are obtained through direct computation, and I will carry them out in detail here, as I believe these calculations really capture the central idea of the algorithm.
So, let . By definition,
and an index shift yields
where . Therefore,
Now, if is even, and substituting this,
Similarly, if is odd, and thus
as desired.
If we recursively apply this process of splitting our original sums into partial sums, we obtain the relation
for and .
To untangle this sea of indices, one can think of as a counter for how many times we split the original sum (namely, at first, then after the first step, and so on) and indicates our position within the array of partial sums. At any stage, there are exactly such sums.
Some names: We call this concept of splitting partial sums into new DFTs decimation in frequency and is called a twiddle factor. With this in place, we can now rigorously define an algorithm to calculate the DFT.
Namely, define the sequence by setting
for , , and , in that order. Then
for and . After steps, namely , we then obtain
for .
Every step requires additions and multiplications, so totalling over steps, we get operations in total, which is a substantial improvement over the operations we set out with.
Storage Algorithm
It is apparent from the recursive definitions given above that to calculate , we require the previous values , which might lead one to believe that, when implementing the algorithm programmatically, we require two arrays to compute the DFT. But this is not so: A single array is sufficient to save the values for , and if we can overwrite the values and with their new counterparts and . Clearly, this can be achieved by saving at , where is a map satisfying
for the corresponding values , , and .
To find such a map , let with be a binary number with at most bits and define the bit reversal map by setting
It turns out that if we then set , this map satisfies our required conditions. In practice, one 'discovers' this definition by solving the recursion prescribed above, but for our purposes it suffices to simply prove that this is indeed the case. For instance, it follows immediately that . Moreover,
and
Since , we can write for . As bit is certainly zero, it follows that the binary representation of is exactly
Therefore,
In particular, this means that , which is precisely what we wanted to show.
Implementing the algorithm
We now have all the ingredients to actually write up the algorithm:
import cmath
import math
def bit_reverse(j: int, n: int) -> int:
result = 0
for _ in range(n):
result = (result << 1) | (j & 1)
j >>= 1
return result
def sande_tukey_fft(f):
N = len(f)
n = N.bit_length() - 1
f_tilde = [complex(x) for x in f]
# m = n, n-1, ..., 1
for m in range(n, 0, -1):
block_size = 1 << m # 2^m
half = 1 << (m - 1) # 2^(m-1)
# rho_m = exp(-2*pi*i / 2^m)
rho_m = cmath.exp(-2j * math.pi / block_size)
# r = 0, 2^m, 2*2^m, ...
for r in range(0, N, block_size):
# k = 0, ..., 2^(m-1)-1
for k in range(half):
e = rho_m ** k
x = f_tilde[r + k]
y = f_tilde[r + k + half]
# f^(m-1)_{r,k}
f_tilde[r + k] = x + y
# f^(m-1)_{r + 2^(n-m), k}
f_tilde[r + k + half] = e * (x - y)
# The values are in bit-reversed order after computing the DFT
c = [0j] * N
for j in range(N):
c[j] = f_tilde[bit_reverse(j, n)] / N
return c