A self-contained introduction to the Fast Fourier Transform

· numerics, programming

Introduction

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