Computing Fourier series coefficients with the FFT

The Discrete Fourier Transform (DFT) is a mathematical function, and the Fast Fourier Transform (FFT) is an algorithm for computing that function. Since the DFT is almost always computed via the FFT, the distinction between the two is sometimes lost.

It is often not necessary to distinguish between the two. In my previous post, I used the two terms interchangeably because the distinction didn’t matter in that context.

Here I will make a distinction between the DFT and the FFT; I’ll use DFT to refer to the DFT as it is defined in [1], and FFT for the DFT as computed in NumPy‘s FFT routine. The differences are due to varying conventions; this is often an issue.

Suppose we have a function f on an interval [−A/2, A/2] and we sample f at N points where N is an even integer.

Define

for n running from −N/2 + 1 to N/2.

DFT of the sequence {f_n} is defined in [1] as the sequence {F_k} where

Now suppose the function f that we sampled has a Fourier series

The Fourier coefficients c_k relate to the DFT output F_k according to the Discrete Poisson Summation Formula [1]:

This means that the c_k simply equal the F_k if f has no frequency components higher than N/2 Hz because all the terms in the infinite sum above are zero. That is, if f is band-limited and we have sampled at a frequency higher than the Nyquist frequency, then we can simply read the Fourier coefficients off the DFT.

However, when f is not band-limited, or when it is band-limited but we have not sampled it finely enough, we will have aliasing. Our Fourier coefficients will differ from our DFT output by an error term involving high-frequency Fourier series coefficients.

In application it’s usually too much to hope that your function is exactly band-limited, but it may be approximately band-limited. The Fourier coefficients of smooth functions eventually decay rapidly (see details here) and so the error in approximating Fourier series coefficients by DFT terms is small.

Computing a DFT with the FFT

We defined the DFT of the sequence {f_n} above to be the sequence {F_k} where

and k runs from −N/2 + 1 to N/2.

NumPy, on the other hand, defines the DFT of the sequence {a_n} to be the sequence {A_k} where

and k runs from 0 to N − 1.

Relative to the definition in the previous post, the NumPy definition difference in three ways:

1. The normalization factor 1/N is missing.
2. The input indices are numbered differently.
3. The output is arranged differently.

The first difference is trivial to overcome: simply divide the FFT output by N.

The second difference is easy to deal with if we think of the inputs to the FFT being samples from a periodic function, which they usually are. The f_k come from sampling a periodic function f over an interval [−A/2, A/2]. If we sample the same function over [0, A] we get the a_n. We have

If we extend the fs and the as periodically past their original ranges of definition, then they all agree. But since we start our sampling in difference places, our samples would be listed in different orders if we stored them by increasing index.

Something similar occurs with the output.

For 0 ≤ k ≤ N/2,

F_k = A_k.

But for N < k < N,

F_k = A_N−k.

Example

We’ll use a band-limited function in our example so that we find the Fourier coefficients exactly.

f(x) = 7 cos(6πx) − 5 sin(4πx)

We compute the FFT as follows.

    import numpy as np

    def f(x):
        return 7*np.sin(3*2*np.pi*x) - 5*np.cos(2*2*np.pi*x)

    N = 8
    delta = 1/N
    x = [f(n*delta) for n in range(N)]
    print( np.fft.fft(x)/N )

The output is

[0, 0, −2.5, −3.5i, 0, 3.5i, −2.5, 0]

This says F₂ and F₋₂ = −5/2, and so the coefficient of cos(2·2πx) is −5.

Also F₃ = −7/2 and F₋₃ = 7/2, so the coefficient of cos(3·2πx) is 7. These results follow from Euler’s equation

exp(iθ) = cos(θ) + i sin(θ)

[1] William L. Briggs and Van Emden Henson. The DFT: An Owner’s Manual for the Discrete Fourier Transform. SIAM 1995.