The Fourier Transform: pt. 2

Wednesday. November 13, 2024 - 4 mins

Introduction

The Fourier convolution theorem¹ is an extremely important result from the computational perspective, as with a sufficiently fast algorithm (FFT) the order of computational complexity of a convolution operation drops from $O(n^2)$ to $O(n\log n$) (read this if you have no idea what I’m talking about). This means that implementing a convolution as a multiplication in the frequency domain is significantly faster than computing it in the time-domain (for sufficiently large $n>N$). On the other hand, the modulation theorem (which is the dual of the previously mentioned convolution theorem) defined as

$$x[n]h[n]\overset{\text{FT}}{\leftrightarrow}\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{j\theta})H(e^{j(w-\theta)} d\theta),$$

seems to be less appealing from a computational perspective, and is perhaps more domain-specific (ask the telecommunications people or synthesizer geeks² about it). This post aims to disprove this notion by showing that the modulation theorem can be used constructively to prove results in DSP, via an example involving an important theoretical tool: the ideal lowpass filter.

Ideal Lowpass Filter

An ideal lowpass filter is a filter that perfectly passes all frequency components below a certain cutoff frequency $\omega_c$, while completely attenuating all frequencies above $\omega_c$. This type of filter has a brick-wall frequency response, meaning it has a sharp cutoff at the boundary between passband and stopband.

Frequency Response of the Ideal Lowpass Filter

The frequency response of an ideal lowpass filter, $H_{LP}(j\omega)$, is defined as:

$$H_{LP}(j\omega) = \begin{cases} 1, & |\omega| \leq \omega_c \\ 0, & |\omega| > \omega_c, \end{cases}$$

Where we suppose for now that the cutoff frequency is unity, meaning $\omega_c=1$.
What does the time-domain representation of this filter look like? Could we use it to implement lowpass filtering by convolution in the time-domain? In order to answer these question we will make use of another important concept in DSP: the Hilbert transformer.

Hilbert transformer

Definition

The Hilbert transformer is defined via an impulse response $h_{HT}$ as:

$$ h_{HT}(t) = \frac{1}{\pi t}, $$

with a Fourier transform of

$$ H_{HT}(j\omega)= -j\, \text{sign}(\omega), $$

We can use the Hilbert transformer to generate an analytic, or complex representation $z[n]$, such that

$$ z(t) = x(t) + j*(x(t)\circledast h_{HT}(t)) $$

where $\circledast$ is the convolution operator and j is the imaginary unit. The frequency domain representation of this signal retains the positive frequency components of x[n], while setting all negative frequency components to zero. This effectively halves the frequency bandwidth, enabling transmission over a narrower band.

Using the modulation theorem to find the Fourier transform of sinc(t)

We will use the Hilbert transformer and the Fourier modulation theorem to find the frequency-domain representation of the unnormalized sinc function, defined by

$$ sinc(t) = \frac{\sin{t}}{t} $$

. For this purpose we will multiply it by a scalar $\frac{1}{\pi}$ to obtain

$$ \frac{sinc(t)}{\pi} =\frac{\sin{t}}{\pi t} $$

Does the denominator of this function now look familiar? Let’s first find the Fourier transform of the numerator in order to use the modulation theorem.

$$ F\{\sin{t}\}= \int_{-\infty}^{\infty} sin(t)e^{-j\omega t}dt = \frac{1}{2j}\int_{-\infty}^{\infty} (e^{jt}-e^{-jt})e^{-j\omega t}dt \\ \overset{lin.}{=} \frac{1}{2j}(\int_{-\infty}^{\infty}e^{-j(\omega-1)t}dt - \int_{-\infty}^{\infty}e^{-j(\omega+1)t}dt) \overset{time-shift}{=} \frac{\pi(\delta(\omega-1) - \delta(\omega+1))}{j} \\ \overset{\omega_c=1}{=} \frac{\pi(\delta(\omega-\omega_c) - \delta(\omega+\omega_c))}{j} $$

Where $\delta(t)$ is the Dirac delta function.
Now we can finally use the modulation theorem:

$$ \frac{\sin{t}}{\pi t} = \sin{t}* \frac{1}{\pi t}\overset{F}{\leftrightarrow} \frac{\pi}{2\pi j}\int_{-\pi}^{\pi} (\delta(\theta-\omega_c) - \delta(\theta-\omega_c))H_{HT}(j(\omega-\theta))d\theta \\ = \frac{1}{2j}(H_{HT}(j(\omega-\omega_c))-H_{HT}(j(\omega+\omega_c))). $$

Let’s divide into the cases

$$ \begin{cases} 1. \, |\omega|<= \omega_c, \\ 2. \, |\omega|> \omega_c, \end{cases} $$

and respectively evaluate our intermediate result. In the first case we have

$$ H_{HT}(j(\omega-\omega_c)) = j, \, H_{HT}(j(\omega+\omega_c)) = -j \implies\\ \frac{1}{2j}(H_{HT}(j(\omega-\omega_c))-H_{HT}(j(\omega+\omega_c))) = \frac{2j}{2j} = 1. $$

Whereas in the second

$$ H_{HT}(j(\omega-\omega_c)) = j, \, H_{HT}(j(\omega+\omega_c)) = j \implies\\ \frac{1}{2j}(H_{HT}(j(\omega-\omega_c))-H_{HT}(j(\omega+\omega_c))) = \frac{0}{2j} = 0. $$

Then we can conclude

$$ \frac{1}{2j}(H_{HT}(j(\omega-\omega_c))-H_{HT}(j(\omega+\omega_c))) = \\ \begin{cases} 1, & |\omega| \leq \omega_c \\ 0, & |\omega| > \omega_c \end{cases} \\ = H_{LP} $$

Meaning we have proven that the unnormalized sinc function and ideal low-pass filter constitute a Fourier transform pair (up to a scalar $\frac{1}{\pi}$). One of the consequences of this fact is that the we are unable to implement an ideal-lowpass filter in the time domain, as the sinc function extends infinitely in each direction. This means we must find finite (and hopefully causal) approximations of the ideal low-pass for effective lowpass filtering in the time domain… That’s it for now!

Footnotes

see previous post ↩
FM-modulation actually lies behind radio technology and FM synthesis- a technique which led to the development of the best-selling Yamaha DX7 synthesizer. This synth is responsible for Lots of funky sounds you might recognize from 80’s pop. ↩