Discrete Fourier transform and Fourier series

This is quite silly, but the relationship between the discrete Fourier transform (DFT) and the Fourier series (FS) is clouded by annoying factors. I will try to connect both in this article. The motivation is to employ DFT techniques in a computer simulation. In the latter, one usually has a finite simulation box, which makes Fourier series the most interesting (a connection to the Fourier transform may also be made, see below).

The DFT

Let us define the DFT as having k coefficient

 \text{DFT}_{s,m}( f )  := \sum_{n=0}^{N-1} f_n \cdot e^{ s i 2 \pi m n / N} ,

here, s is a sign, either +1 or -1. In fact, s=-1 for the usual definition of DFT (but this is ok, as we will see later.)

In accordance to its computing origin, the DFT carries no physical information about the period of the signal, and just focuses on the length of the data vector, N (aka DOF, degrees of freedom).

Fourier series

The definition of a Fourier Series usually starts by introducing the inverse Fourier transform:

 f(x) := \sum_{m=0}^{N-1} \tilde{f}_{m}  e^{ i k_m x} ,

where the values of the wave vectors are given by

k_m = \frac{2\pi m}{L} ,

where L is the period of the signal (we are thinking of x as a spacial coordinate and L as the length of the system, but of course everything holds for time signals).

Now, if we sample the function f(x) at equal intervals

x_n= n \Delta x,

where the spacing \Delta x= L/N, we may write

 f(x_n) := \sum_{m=0}^{N-1} \tilde{f}_{m} e^{ i k_m x_n} ,

since k_m x_n = 2\pi m n, we find the direct correspondence

 f(x_n) := \text{DFT}_{+1,n}

The coefficients themselves (direct transform) are calculated from the integral

\ \tilde{f}_m =  \frac{1}{L} \int_0^L   f(x) e^{-i k_m x} dx

(The derivation is very simple, just by integrating upon the FS times e^{-i k_l x} and using orthogonality of the complex exponential functions.)

In the discrete world integrals have to be approximated. If we use the simple rectangle method,

\ \tilde{f}_{m}  \approx \frac{1}{L} \sum_0^{N-1}  f(x_n) e^{-i k_m x_n}  \Delta x

Recalling \Delta x= L/N,

\ \tilde{f}_{m}  \approx \frac{1}{N} \text{DFT}_{-1,m} .

Everythings together, since  \frac{1}{N} \text{DFT}_{-1}   is actually the inverse of  $\text{DFT}_{+1}  $ . (That N factor can lead to trouble if forgotten!).

Notice the signs match for the DFT and the FS, and that “the” DFT is defined with a minus sign, which corresponds to our direct FS.

Also, notice that the periodic length does not actually enter any of the equations, not even in the continuum, because the integral may change its integration variable x'=x/L, and all the L  factors drop!

Check

Let us consider a constant function f(x)=c. Its Fourier coefficients are then

\ \tilde{f}_{m} = c \delta_{m,0},

i.e. all null except for m=0. Using the Fourier series, we readilly obtain back f(x)=c.

Now, on the discrete level, the coefficients are given by

\frac{1}{N} \text{DFT}_{-1,0} = \frac{1}{N}  \sum_0^{N-1}  c = c ,  

(zero for m not equal to 0), and the DFT would be

\ \text{DFT}_{+1,n} = c .

Derivatives

A nice feature of Fourier series is the ease in treating derivatives (that, and convolution, of course). Indeed,

 f'(x) := \sum_{m=0}^{N-1} \tilde{f}_{m} i k_m  e^{ i k_m x} ,

which means that the Fourier coefficients of the derivative are

 \tilde{f'}_m :=  \tilde{f}_{m} i k_m  

Now, k_m= 2\pi m/L, and the L does not drop here. This is important, since physically the “same” sine modulation A\sin(2\pi x/L) has different derivative depending on L!

The Fourier transform

Our inverse Fourier series may be interpreted as a discretized integral simply by multiplying by the spacing in Fourier space:

 f(x) = \frac{1}{\Delta k} \Delta k \sum_{m=0}^{N-1} \tilde{f}_{m}  e^{ i k_m x} \approx\frac{1}{\Delta k} \int  \tilde{f}(k)  e^{ i k x} \, dk

Since the spacing is

\Delta k= \frac{2\pi}{L},

 f(x)  \approx\frac{L}{2\pi} \int  \tilde{f}(k)  e^{ i k x} \, dk

A quick comparison with the usual definition of the Fourier transform reveals that the Fourier transform is related to the (analytic continuation of the) fourier components thus:

 \bar{f}(k) = L \tilde{f}(k)

(We have called the Fourier transform  \bar{f}(k) to distinguish if from the coefficients.) This fact is also acknowledged in the wikipedia article.

Notice the Fourier coefficients have the same physical dimensions as the original function in real space, but that the Fourier transform has an extra multiplicative length dimension (area or volume in higher dimensions).

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s