we usually record a set of data in time-domain. the signal or data may have some oscillation and we want to to which frequency is inside. thus, we will looking for Fourier Transform, which change from time-domain to frequency domain.

the continuous Fourier Transform is

F(k) = \frac{1}{\sqrt{2\pi}} \int_{\infty}^{\infty}{ f(x) e^{-i k x} dx}

if we see the exponential as cosine and sine function, that we understand it is finding a suitable wave-vector “k”, such that the function f(x) is “parallel” or “part-parallel” with it.

However, we cannot have infinite long data, but just some interval. Thus, the interval will bounded the available frequency.

a_n = \frac{1}{\sqrt{2\pi}} \int_{-L}^{L}{ f(x) e^{-i n \pi x / L} dx}

we can understand the reason is by invert thinking about how a signal is formed by difference frequency. say, we have a time interval of  “2L” unit (if the 2π is absorbed in the interval, the total interval is 2π larger), if a mono-frequency signal has wavelength longer then “2L” unit, or the k-vector is smaller then 1/2L, then, this signal is not going to change within the time-interval and do no contribution. Thus, the interval set the resolution of the k-vector.

when the data is discrete with m+1 data point in interval 2L, we have discrete Fourier transform. the integration becomes:

a_n = \sum_{i=0}^{m} { f(x_i) e^{-i n \pi x_i /L}} \Delta x

Set the \Delta x = 2L/m = 1 , and x_i = (i-1)2L/m , and since the data separation on the data list is defined by ourselves, so, the date does not have this information. And we want the a_n start at 1, not zero.

a_n = \sum_{i=0}^m { f(x_i) e^{-i (n-1) 2\pi (i-1) /m}}

This is the formula for Discrete Fourier Transform without a constant factor.

Remark on mathematica and FFTW user: The function “Fourier”‘s default setting is using – sign in the exponential, while FFTW is using – sign. and also, the amplitude will be divided by √n in mathematica, and FFTW will not. in this post, we use FFTW transform. For mathematica user, the “Fourier” has a setting called “FourierParameters”, by setting it to (1,-1), will get the result same as FFTW.