Lecture 3: The Fourier Transform

Signal Processing for Interactive Systems

Cumhur Erkut (cer@create.aau.dk)

Aalborg University Copenhagen.

Last edited: 2025-02-25

The discrete-time Fourier transform¶

In this part, you will learn

• why it is important to look at signals in the frequency domain

• what the DTFT is

• how you can visualise noise removal in the frequency domain

🔈 Understanding the DFT and the FFT (20 minutes)

Example: analysing a trumpet signal Suppose that we record a trumpet signal $s_n$ for $n=0,1,2,\ldots,N-1$.

The discrete-time Fourier transform (DTFT)¶

Any colour can be written as a weighted combination of three atoms (red, green and blue colours).

A signal (such as the trumpet signal) can be written as a weighted combination of phasors, i.e.,

This is called the inverse discrete-time Fourier transform (inverse DTFT).

We can find the weights $S(\omega)$ by correlating our signal to the phasor $\mathrm{e}^{-j\omega n}$, i.e.,

This is called discrete-time Fourier transform (DTFT).

Note that

• the DTFT is mostly of theoretical interest since we will never encounter infinitely long signals in practice

• the practical version of the DTFT is called the discrete Fourier transform (DFT) (more on this later)

Example: analysing a trumpet signal¶

Let us now (pretend that we can actually) compute the DTFT of the trumpet signal, i.e.,

with $s_n$ being the trumpet signal. (In practice, we are computing the DFT, but we will return to that later).

Example: An EEG Signal (eyes closed)¶

Time-domain representation and frequency-domain representation (the spectrum) of anEEG signal with eyes closed. (a) The EEG signal is recorded at Oz and has a duration of 3 s and asampling rate of 160 Hz. By using bandpass filtering with difference cutoff frequencies, the signalcan be decomposed into five rhythms. (b) The spectrum of the EEG signal. After Zhang, Zhiguo. 2019. “Spectral and Time-Frequency Analysis,” in 89–116. doi:10.1007/978-981-13-9113-2_6. In “EEG Signal Processing and Feature Extraction”, edited by Li Hu and Zhiguo Zhang, 2019.

Video example FFT (Live Code)¶

We match the live script code from 16:27 to the end in the video exactly with python.

Sine Signal¶

One-sided FFT¶

Example: a noisy trumpet signal¶

Let us now assume that we record a noisy trumpet signal. We can write this as

where

• $x_n$ is the noisy trumpet signal

• $s_n$ is the clean (i.e., noise-free) trumpet signal

• $e_n$ is the noise

In the frequency-domain, the noisy trumpet signal can be written as

where

• $X(\omega)$ is the DTFT of the noisy trumpet signal

• $S(\omega)$ is the DTFT of the clean trumpet signal

• $E(\omega)$ is the DTFT of the noise

We see that the Fourier transform is additive. Thus, if we sum two signals in the time domain, we also sum them in the frequency domain. This is illustrated for the two signals $x_n$ and $y_n$ in the figure below.

Example task (SMC): removing noise from a trumpet signal¶

Note that

• the trumpet signal only has almost all of its energy concentrated in a few frequencies at (approximately) 530 Hz, 1060 Hz, 1590 Hz, 2120 Hz, 2650 Hz, etc. (These values have been estimated using a pitch estimator which we are going to discuss in lecture 12)

• the noise is spread across all frequencies

• we can remove a lot of noise by using a filter which will only allow the ‘trumpet frequencies’ to pass through

• a feedback comb filter can be designed to do exactly that!

A feedback comb filter has the difference equation

For a sampling frequency of $f_\text{s} = 44,100$ Hz and a pitch of $f_0 = 530 Hz$, the pitch period is

Since $D$ has to be an integer, we will set $D=83$ samples in the comb filter.

We will now remove the noise in the following way:

1. Filter the noisy trumpet signal $x_n$ through the feedback comb filter given by

   $$y_n = x_n + a y_{N-D}$$

   (8)

   with $D=83$ and $a$ close (but not exceeding) 1.

2. The filter output $y_n$ should now be much more similar to the clean trumpet signal $s_n$ since the filter has removed a lot of noise.

Example: transfer function and frequency response of the feedback comb filter¶

In the last lecture, we saw that the transfer function of the feedback comb filter is

We can easily obtain the frequency response as the transfer function on the unit circle. That is, we set

and obtain the frequency response of the comb filter to

Summary¶

1. The discrete-time Fourier transform (DTFT) of a signal $x_n$ is given by

   $$X(\omega) = \sum_{n=-\infty}^{\infty} x_n \mathrm{e}^{-j\omega n}\ .$$

   (12)

   You can think of the DTFT as a correlation between a signal and a phasor of frequency $\omega$.

2. The inverse DTFT of a frequency response $X(\omega)$ is given by

   $$x_n = \frac{1}{2\pi}\int_{-\pi}^{\pi} X(\omega) \mathrm{e}^{j\omega n}d\omega\ .$$

   (13)

   You can think of the inverse DTFT as writing the signal as a weighted sum of phasors.

3. Signals are often much easier to process and analyse in the frequency domain.

Active 5 minutes break¶

Recall that an impulse is given by

1. Compute the frequency response of this impulse by computing the DTFT.

Assume that you pass the impulse through a filter (i.e., set $x_n=\delta_n$) with difference equation

2. What is the impulse response $h_n$ of this filter? 3. Compute the frequency response of the filter by computing the DTFT of the impulse response.

The DTFT of a signal/impulse response $x_n$ is given by

Windowing¶

In this part, you will learn

• what a window is

• why we need them

• how windows change the frequency response of a signal

• different types of windows

The DTFT of a signal response $x_n$ is given by

Note that there are three practical problems with the DTFT

1. we will never observe a signal $x_n$ from $-\infty$ to $\infty$

2. the digital frequency $\omega$ is a continuous parameter so we cannot store $X(\omega)$ on a computer

3. the frequency content of most signals change as a function of time

We solve these problems using

1. windows to turn infinite signals into a finite number of non-zero samples (this block)

2. sample the DTFT on a uniform grid of frequencies (this is called the discrete Fourier transform (DFT)) (next block)

3. slide a window across a long signal to compute a short-time Fourier transform (STFT) (last block)

The rectangular window¶

Let us first look at the rectangular window

We can think of the rectangular window $w_n$ as a way of extracting the samples we see from an infinitely long signal $x_n$, i.e.,

Example: DTFT of a window phasor¶

Let us look at the phasor

$x_n = \mathrm{e}^{j\omega_0 n}$

which we observe for $n=0,1,\ldots,N-1$.

The DTFT of this windowed phasor is (note that subscript $N$ in $X_N(\omega)$ indicates the window length)

where the last equality follows from the geometric series.

The windowed DTFT was

Note that

1. if we set $w_0 = 0$, then $x_n=1$ and we obtain the DTFT of only the window, i.e.,

   $$W_N(\omega) = \frac{1-\mathrm{e}^{-j\omega N}}{1-\mathrm{e}^{-j\omega}}$$

   (22)

2. the DTFT $X_N(\omega)$ of the windowed phasor is simply a frequency shifted version of $W(\omega)$, i.e.,

   $$X_N(\omega) = W_N(\omega-\omega_0)\ .$$

   (23)

   This is also called the modulation property of the DTFT.

3. if we let $N\to\infty$, it can be shown that

   $$\lim_{N\to\infty}X_N(\omega) =X(\omega) = \begin{cases} \infty & \omega = \omega_0\\ 0 & \text{otherwise} \end{cases}\ .$$

   (24)

   Thus, the DTFT $X(\omega)$ of a phasor of infinite duration has an infinite peak at $\omega_0$ and is zero otherwise.

Windowing and its influence of the DTFT¶

Assume that we observe $N$ samples of a signal $x_n$ with DTFT $X(\omega)$. How is the DTFT $X_N(\omega)$ of the windowed signal related to $X(\omega)$? We know that the windowed DTFT and the inverse DTFT are given by

where we have added a $\tilde{\cdot}$ on top of $\omega$ in the last equation to indicate that it is an integration variable.

Inserting the last equation into the first results in

which is a convolution between $X(\omega)$ and the DTFT $W(\omega)$ of the rectangular window.

Note that applying a window is equivalent to low-pass filtering the DTFT $X(\omega)$. This causes frequency smearing!

Bandwidth and sidelobes of windows¶

Ideally, we would like a window with

• narrow bandwidth to minimise frequency smearing

• high sidelobe attenuation to minimise spectal leakage

Unfortunately, decreasing the bandwidth increases the sidelobes and vice versa for a fixed $N$.

As no perfect window exists, many windows have been suggested. Note that

• the windows have different trade-offs between bandwidth and sidelobe attenuation

• examples of popular windows are rectangular, sine, Hamming, Hanning, Kaiser, and Gaussian. As an example, the hanning window is given by

  $$w_n = \begin{cases} 0.5-0.5\cos(2\pi n/(N-1)) & n = 0, 1, \ldots, N-1\\ 0 & \text{otherwise}\ . \end{cases}$$

  (27)

• the rectangular window has the smallest bandwidth and the lowest sidelobe attenuation

• increasing the window length $N$ decreases the bandwidth and increases the sidelobe attenuation.

Summary¶

1. A window is used to extract a portion of a signal.

2. If we extract the $N$ samples $n=0,1,\ldots,N-1$, the windowed DTFT is

   $$X_N(\omega) = \sum_{n=-\infty}^{\infty} w_n x_n \mathrm{e}^{-j\omega n} = \sum_{n=0}^{N-1} w_n x_n \mathrm{e}^{-j\omega n}$$

   (28)

3. Windowing a signal introduces frequency smearing and leakage, and these decrease as the window length increases

4. Many differenct windows exist and they trade-off the bandwidth for the sidelobe attenuation in different ways.

The discrete Fourier transform and Spectrograms¶

In the next 20 minutes, you will learn

• how the DFT is defined

• how the DFT is related to the DTFT

• what the short-time Fourier transform (STFT) is

• what the spectrogram is

The discrete Fourier transform¶

The discrete Fourier transform (DFT) is a sampled version of the windowed DTFT, i.e.,

where the digital frequencies are evaluated on a $F$-point grid given by

with $F\geq N$.

Note that we have here assumed a rectangular window, but other windows can be used as well.

Often, the expression for $\omega_f$ is inserted directly into the DFT definition and we obtain

The inverse DFT¶

Recall that the inverse DTFT is given by

The inverse DFT is given by

where $\omega_f=2\pi f/F$.

The fast Fourier transform¶

The fast Fourier transform (FFT) computes the DFT, but is a computationally efficient way.

Note that

• computing the DFT directly from its definition costs in the order of $F^2$ floating point (flops) operations (we write this as $\mathcal{O}(F^2)$).

• computing the DFT using an FFT algorithm reduces the cost to just $\mathcal{O}(F\log_2 F)$ flops

• most FFT algorithms are working most efficiently when $\log_2(F)$ is an integer

• most FFT algorithms are slow (relatively speaking) if $F$ is prime or has large prime factors (i.e., if you factorise $F$ into a product of prime numbers and any of these are large, then most FFT algorithms will be slow)

• entire books have been written on FFT algorithms, but the most important thing to remember is that they are all just different ways of compute the DFT as fast as possible!

The short-time Fourier transform (STFT)¶

In most practical signals, the frequency content changes as a function of time.

Assume that we have a long signal $x_n$ and a much shorter window $w_n$ of length $N$ which is zero everywhere, except for $n=0,1,...,N-1$.

To analyse the signal, we slide it relative to the window. Mathematically, we can slide the signal by considering

for different $l$ where

• $l$ is the frame index

• $L$ is the hop size.

If we combine this with a window of length $N$, we obtain the STFT to

which can be computed using the DFT.

Thus,

• the STFT is simply a collection of DFTs computed at different positions of the signal

• the samples we see through the window at a given position is called a frame or a segment and is indexed by the frame index $l$

• unlike the DFT which only depends on the frequency index $f$, the STFT also depends on the frame index $l$

The spectrogram¶

The spectrogram $S_x(\omega_f,l)$ is the squared amplitude response of the STFT, i.e.,

The spectrogram is used everywhere to visualise the frequency content as a function of time!

Summary¶

1. The discrete Fourier transform (DFT) is a sampled version of the windowed DTFT, i.e.,

   $$X_N(\omega_f) = \sum_{n=0}^{N-1} x_n \mathrm{e}^{-j\omega_f n}$$

   (37)

   where $\omega_f = 2\pi f/F$ for $f=0,1,\ldots,F-1$ with $F\geq N$.

2. The DFT can be computed efficiently using an FFT algorithm.

3. The short-time Fourier transform (STFT) is the DFT of different frames of the signal, i.e.,

   $$X_N(\omega_f, l) = \sum_{n=0}^{N-1} (w_nx_{n+lL}) \mathrm{e}^{-j\omega_fn}$$

   (38)

   where $l$ is the frame index and $L$ the hop size.

4. The spectrogram is the squared amplitude response of the STFT.

Exercise SMC: Obtain the same STFT using librosa.¶

Exercise MED: Obtain a time-frewquency analysis of an EEG signal¶

https://mne.tools/stable/auto_tutorials/intro/10_overview.html#time-frequency-analysis

Epoching continuous data and time-frequency analysis¶

The Raw object and the events array are the bare minimum needed to create an Epochs object, which we create with the Epochs class constructor. Here we’ll also specify some data quality constraints: we’ll reject any epoch where peak-to-peak signal amplitude is beyond reasonable limits for that channel type. This is done with a rejection dictionary; you may include or omit thresholds for any of the channel types present in your data. The values given here are reasonable for this particular dataset, but may need to be adapted for different hardware or recording conditions. For a more automated approach, consider using the autoreject package.