Engee documentation
Notebook

Fourier methods

A method often used for signal processing is the Fourier transform. This method allows you to transform a signal between the time domain and the frequency domain. An efficient Fast Fourier Transform (FFT) algorithm is implemented in Julia using the FFTW library.

In [ ]: 
using FFTW

1D Fourier Transform

Let's start by looking at the Fourier transform in one dimension. We will create test data in the time domain using the wide rectangle function.

In [ ]: 
f = [abs(x) <= 1 ? 1 : 0 for x in -5:0.1:5];
plot(real(f))
Out[0]:

Now let's convert the data into the frequency domain using fft() and plot the spectrum of the signal using the complex number module.

In [ ]: 
FFT = fft(f);
typeof(FFT)
Out[0]:
Vector{ComplexF64} (alias for Array{Complex{Float64}, 1})
In [ ]: 
abs_FFT = sqrt.(real(FFT).^2+imag(FFT).^2)
plot(abs_FFT)
Out[0]:

The frequency domain data is an array of Complex type with the same length as the time domain data.

Since each complex number consists of two parts (real and imaginary), it would seem that we have somehow doubled the information content of our signal. This is not true: half of the frequency domain data is redundant. The fftshift() function conveniently rearranges the frequency domain data so that negative frequencies are on the left.

In [ ]: 
F = fftshift(FFT);
abs_F = sqrt.(real(F).^2+imag(F).^2)
plot(abs_F)
Out[0]:

The analytical Fourier transform of the rectangle function is the function sinc , which agrees well with the numerical data in the graphs above.

Two-dimensional Fourier transform

Let us consider an analogous two-dimensional problem. But this time we will go in the opposite direction, starting with the two-dimensional function sinc and taking its Fourier transform.

It is easy to build an array of sinc data using the list generator.

In [ ]: 
f = [(r = sqrt(x^2 + y^2); sinc(r)) for x in -6:0.125:6, y in -6:0.125:6];
plot(f)
Out[0]:

It doesn't make much sense to think of a two-dimensional function in the time domain. But the Fourier transform works with both a time signal and a spatial signal (or a signal in almost any other domain). So, suppose our two-dimensional data is in the spatial domain.

In [ ]: 
heatmap(f)
Out[0]:

Fourier transform generation for multidimensional signals is also performed using fft().

In [ ]: 
F = fft(f);
F = fftshift(F);
abs_F = sqrt.(real(F).^2+imag(F).^2)
heatmap(abs_F)
Out[0]:

Conclusion

In addition to the above, it is also convenient to apply FFT to higher dimensional data.

Most of the functionality of the FFTW library is implemented in the Julia interface.

How exactly:

  1. Generate plans for optimised FFTs using plan_fft();
  2. Use the discrete cosine transform using dct();
  3. use conjugate symmetry in real transformations using rfft();
  4. You can also run multiple threads via FFTW.set_num_threads().