Engee documentation
Notebook

Fourier methods

A method such as the Fourier transform is often used for signal processing. 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 we transform the data into the frequency domain using fft(), and construct the signal spectrum using the modulus of a complex number.

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 a Complex array with the same length as the time domain data.

Since each complex number consists of two parts (real and imaginary), it seems that we have somehow doubled the information content of our signal. This is not the case: half of the frequency domain data is redundant. The fftshift() function conveniently rearranges the data in the frequency domain so that the 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 a sinc function that fits well with the numerical data in the graphs above.

Two-dimensional Fourier transform

Let's consider a similar two-dimensional problem. But this time we will go in the opposite direction, starting with the two-dimensional sinc function and taking its Fourier transform.

It is easy to build a sinc data array using a 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 about a two-dimensional function in the time domain. But the Fourier transform works with both a temporal signal and a spatial signal (or a signal in almost any other domain). So, let's assume that our two-dimensional data is in a spatial domain.

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

The generation of the Fourier transform 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 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 optimized 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().