previous up next SYLLABUS  Previous: 4.2 Linear equations.  Up: 4 FOURIER TRANSFORM  Next: 4.4 Non-linear equations.


4.3 Aliasing, filters and convolution.


Slide : [ Aliasing - Filters - Convolution || VIDEO login]

One of the beauties when using Fourier transforms, is the ability to work with a spectrum of modes and act on each of the components individually with a filter. By sampling the function over a period $ L$ with a finite number of values $ N=L/\Delta$ , where $ \Delta$ is the size of the sampling interval, the spectrum gets truncated at the shortest wavelength $ \lambda_c=2\Delta=2\pi/k_c$ called Nyquist critical wavelength: this corresponds to exactly 2 mesh points per wavelength, which does however not mean that shorter wavelengths $ \vert k\vert>k_c$ do not contribute to the Fourier coefficients (4.1#eq.1). Figure 4.3#fig.1 illustrates how they get aliased back into the lower components of the spectrum.

Figure 4.3#fig.1: Aliasing from Fourier components shorter than the Nyquist critical wavelength $ \vert k\vert>k_c$ .
\includegraphics[width=10cm]{figs/FFTalias.eps}
This can be important for the digital data acquisition of an experiment, where the signal has to be low-pass filtered before it is digitally sampled. Figure 4.3 shows that even with the greatest precautions, such an aliasing can sometimes not be avoided, an needs then to be correctly interpreted.

Figure 2: Experimental spectrum 0-500 kHz digitally recorded during 2 sec from the magnetic perturbations in a fusion plasma in the Joint European Torus. Apart from the Alfvén instabilities which are the subject of this research, you can see the sawteeth-like trace of an exciter antenna reaching a minimum of 200 kHz around 1.5 sec; despite heavy analogic low-pass filtering before the signal is sampled, the large dynamic range of the measurement above 80 dB is here sensitive enough to pick up (dark red line) a non-linearly induced high-frequency component which is aliased down into the frequency range of interest. Courtesy of Prof. A. Fasoli(MIT/USA).
Fusion plasma spectrum from JET

 

It is easy to design a filter in Fourier space simply by multiplying the spectrum by a suitable filter function $ \mathcal{H}(k)$ (exercise 4.2). Simply remember that

  • to keep the data real after transforming back to X-space, you must keep $ \mathcal{H}(-k)=\mathcal{H}(k)^*$ , for example by choosing $ \mathcal{H}$ real and even in $ k$ ,
  • the filter has to be defined in the entire interval $ k\in[-k_c;k_c]$ and should be smooth to avoid phase errors and dampings for wavelengths that appear with sharp edges.

Although they are present right from the beginning when the initial condition is first discretized (try to initialize and propagate an aliased cosine with ICWavelength=1.05 mesh points per wavelength using the JBONE applet above), aliases do not actually interfere with the resolution of linear equations. The story is however different for spatial non-linearities such as the quadratic term $ \partial_x f^2(x)$ that is responsible for the wave-breaking (1.3.4#eq.1). Indeed, think of the convolution theorem, which tells that the Fourier transform of a convolution $ \widehat{f*g}$ is just the product of the individual Fourier transforms  $ \hat{f}\hat{g}$ . The converse is unfortunately also true: what can be viewed as a simple product in X-space becomes a convolution in K-space

$\displaystyle \widehat{f(x) g(x)}=\hat{f}*\hat{g},\hspace{1cm} \hat{f}*\hat{g} \equiv \int \hat{f}(k^\prime)\hat{g}(k-k^\prime) dk^\prime$ (1)

or in discrete form

$\displaystyle (\hat{f}*\hat{g})_m \equiv \sum_{k=-N/2+1}^{N/2} \hat{f}_k\hat{g}_{m-k}$ (2)

For the quadratic wave-breaking non-linearity, this shows that a short wavelength component such as $ \hat{f}_{+31}$ in a sampling with 64 points, will incorrectly ``pollute'' a long wavelength channel through aliasing: $ (\hat{f}_{+31}*\hat{f}_{+31})=\widehat{f^2}_{+62}$ $ \longrightarrow\widehat{f^2}_{-2}$ . A simple cure for this, is to expand the size of the arrays by a factor two before the convolution takes place and pad them with zeros; changing the representation to calculate the multiplication of arrays twice the original size, the upper part of the spectrum is then simply discarded after the data has been transformed back. The entire procedure is illustrated in the coming section, where the non-linear Korteweg-DeVries (1.3.4#eq.3) and Burger equations (1.3.4#eq.2) are solved with a convolution in Fourier space.

SYLLABUS  Previous: 4.2 Linear equations.  Up: 4 FOURIER TRANSFORM  Next: 4.4 Non-linear equations.

      
back up next contents bibliography Copyright © Lifelong-learners at 03:14:17, October 21st, 2017