SPTK: The Fourier Transform

An indispensable tool in CSP and all of signal processing!

This post in the Signal Processing Toolkit series deals with a key mathematical tool in CSP: The Fourier transform. Let’s try to see how the Fourier transform arises from a limiting version of the Fourier series.

The complex form of the Fourier series is used to represent an arbitrary signal on some finite interval $[-T/2, T/2]$. The idea of representation just means that the signal is equal to the sum of weighted basis functions (‘building-block functions’). The sum may have a finite or infinite number of terms, and the convergence of the sum is generally good at all points in the interval except those points corresponding to step-like discontinuities, or points that correspond to an impulse function, etc. We won’t belabor the details of the convergence and the strict mathematical properties that a signal must possess to ensure solid point-wise convergence. This is the CSP Blog, so we’re mathematical, but our focus is on building intuition so that the tools in the CSP and SPTK toolkits can be better wielded by signal-processing practitioners.

The motivation for looking for another kind of representation is that we would like to represent signals on an arbitrary interval, including an infinite interval. The essential notion of this post is that we will let the Fourier series interval approach $[-\infty, \infty]$ in a semi-careful way.

Let’s write down the complex Fourier series as our starting point. We have some complex-valued signal $s(t)$ defined on the interval $[-T/2, T/2]$ and the Fourier series represents it in terms of the sum of weighted complex-valued sine waves $\displaystyle e^{i 2 \pi (k/T) t}$, where $k$ is the index into the basis functions, and also serves as the harmonic number for the fundamental frequency $1/T$. We have the representation

$\displaystyle s(t) = \sum_{k=-\infty}^\infty c_k e^{i 2 \pi (k/T) t} \ \ \ t \in [-T/2, T/2] \hfill (1)$

where the Fourier coefficients are the $c_k$, the Fourier frequencies are $k/T$, and the coefficients are computed by

$\displaystyle c_k = \frac{1}{T} \int_{-T/2}^{T/2} s(t) e^{-i 2 \pi (k/T) t} \, dt \hfill (2)$

Now let’s substitute (2) into (1) to yield

$\displaystyle s(t) = \sum_{k=-\infty}^\infty \left[ \frac{1}{T} \int_{-T/2}^{T/2} s(u) e^{-i 2 \pi (k/T) u} \, du \right] e^{i 2 \pi (k/T) t} \hfill (3)$

where I changed the variable of integration from $t$ to $u$ in (2) to avoid confusion. Now, let’s denote the fundamental $1/T$ by $f_0$ and reexpress (3) in terms of $f_0$,

$\displaystyle s(t) = \sum_{k=-\infty}^\infty e^{i 2 \pi k f_0 t} f_0 \left[\int_{-T/2}^{T/2} s(u) e^{-i 2 \pi k f_0 u} \, du \right] \hfill (4)$

As $T$ grows, $1/T = f_0$ becomes an infinitesimal number, which we’ll call $df$. The number $kf_0 = k/T$ takes on values on an increasingly fine grid that extends to infinity, because the lower and upper limits on $k$ are infinite. The following movie illustrates the behavior of the Fourier frequencies and Fourier coefficient magnitudes for a fixed-width rectangle signal as the interval of representation gets larger and larger. Note the ever-finer spacing of the Fourier frequencies.

The sum over $k$ in (4) passes to a conventional integral, and we write it as

$\displaystyle s(t) = \int_{-\infty}^\infty e^{i 2 \pi f t} \, df \left[ \int_{-\infty}^\infty s(u) e^{-i 2 \pi f u}\, du \right] \hfill (5)$

or

$\displaystyle s(t) = \int_{-\infty}^\infty \left[ \int_{-\infty}^\infty s(u) e^{-i 2 \pi f u}\, du \right] e^{i 2 \pi f t} \, df \hfill (6)$

We call the inner integral, which is a function of frequency $f$, the Fourier transform of $s(t)$:

$\displaystyle S(f) = \int_{-\infty}^\infty s(t) e^{-i 2 \pi f t} \, dt \hfill (7)$

and we can see that the outer integral is a reverse, or inverse Fourier transform

$\displaystyle s(t) = \int_{-\infty}^\infty S(f) e^{i 2 \pi f t}\, df \hfill (8)$

In engineering, the Fourier transform of a signal is often denoted by a upper-case letter and a time function is denoted by a lower-case letter. A thick double-sided arrow is often used to denote a Fourier-transform relationship, or Fourier-transform pair:

$\displaystyle S(f) \Longleftrightarrow s(t) \hfill (9)$

Interpretation

The signal $s(t)$ is composed of an infinity of sine-wave components, each with infinitesimal strength. The strengths are given by $S(f)df$ and the frequencies are all real numbers for which $S(f) \neq 0$. So the Fourier transform represents a signal in terms of an infinite number of sine waves with infinitely small strengths (unless $S(f)$ contains an impulse!). Through the magic of calculus, these all add up to a finite number for each $t$.

Examples of the Fourier Transform

First let’s look at a simple well-behaved signal: a rectangle with height $A$ and width $T$:

Let’s just apply the definition of the transform and evaluate the integral. We have the mathematical definition of the signal

$\displaystyle s(t) = A\, \mbox{\rm rect}(t/T) \hfill (10)$

and so the Fourier transform is defined by

$\displaystyle S(f) = \int_{-\infty}^\infty A\, \mbox{\rm rect}(t/T) e^{-i 2\pi f t} \, dt \hfill (11)$

$\displaystyle = A \int_{-T/2}^{T/2} e^{-i 2 \pi f t}\, dt \hfill (12)$

$\displaystyle = A \frac{\sin(2\pi f T/2)}{\pi f} = AT\mbox{\rm sinc}(fT) \hfill (13)$

Using the double arrow notation,

$\displaystyle A\,\mbox{\rm rect}(t/T) \Longleftrightarrow AT\mbox{\rm sinc}(fT) \hfill (14)$

To obtain the Fourier transform of a constant, note that

$\displaystyle \lim_{T\rightarrow\infty} AT \mbox{\rm sinc}(fT) = A\delta(f)\hfill (15)$

and that the function $A\,\mbox{\rm rect}(t/T)$ for $T\rightarrow \infty$ is just the constant $A$. However, we can also approach this transform in a different way. Suppose we attempt to find the Fourier transform of an impulse directly

$\displaystyle x(t) = A\delta(t) \hfill (16)$

$\displaystyle X(f) = \int_{-\infty}^\infty x(t) e^{-i 2\pi f t}\, dt \hfill (17)$

$\displaystyle = \int_{-\infty}^\infty A \delta(t) e^{-i 2\pi f t} \, dt \hfill (18)$

$\displaystyle = A \int_{-\infty}^\infty \delta(t) e^0 \, dt \hfill (19)$

$\displaystyle = A (1) = A \hfill (20)$

so that the Fourier transform of an impulse is a constant. If we look at the corresponding inverse transform,

$\displaystyle x(t) = \int_{-\infty}^\infty X(f) e^{i 2 \pi f t} \, df \hfill (21)$

$\displaystyle = \int_{-\infty}^\infty A e^{i 2 \pi f t} \, df = A\delta(t) \hfill (22)$

must hold. This implies that

$\displaystyle \int_{-\infty}^\infty A e^{-i 2 \pi f t} \, dt = A \delta(-f) = A\delta(f) \hfill (23)$

We have the two Fourier transform pairs

$\displaystyle A \Longleftrightarrow A \delta(f) \hfill (24)$

and

$\displaystyle A\delta(t) \Longleftrightarrow A \hfill (25)$

The transform of a complex sine wave follows from the analysis for a constant we just looked at:

$\displaystyle x(t) = A e^{i 2 \pi f_0 t} = A\cos(2\pi f_0 t) + iA\sin(2\pi f_0 t) \hfill (26)$

$\displaystyle X(f) = \int_{-\infty}^\infty (A e^{i 2 \pi f_0 t}) e^{-i2\pi f t} \, dt \hfill (27)$

$\displaystyle = A \int_{-\infty}^\infty e^{-i2\pi(f-f_0)t} \, dt = A\delta(f-f_0)\hfill (28)$

We interpret this to mean that the ‘frequency content’ of a complex-valued sine wave is concentrated at a single frequency.

There are many mathematical properties of the Fourier transform that become useful when you do a lot of signal-processing analysis work. A particularly useful one in the context of radio-frequency communication signal modeling and analysis is the frequency-shifting property. That is, given the pair $X(f) \Longleftrightarrow x(t)$, what is the signal that corresponds to the transform $X(f-f_0)$? We could solve this using the inverse transform, but let’s guess the answer is $y(t) = x(t) e^{i 2 \pi f_0 t}$ and work through the forward transform.

$\displaystyle Y(f) = \int_{-\infty}^\infty y(t) e^{-i 2 \pi f t} \, dt \hfill (29)$

$\displaystyle = \int_{-\infty}^\infty x(t) e^{i 2 \pi f_0 t} e^{-i 2 \pi f t} \, dt \hfill (30)$

$\displaystyle = \int_{-\infty}^\infty x(t) e^{- i 2\pi(f - f_0)t} \, dt = X(f - f_0) \hfill (31)$

Discrete-Time Counterparts

Suppose we have a discrete-time signal $s(k)$ defined for integers $k = 0, 1, \ldots, T-1$. Then the discrete-time Fourier series is defined by the Fourier coefficients $d_j$,

$\displaystyle d_j = \frac{1}{T} \sum_{k=0}^{T-1} s(k) e^{-i 2 \pi (k/T) j}, \ \ \ j = 0, \pm 1, \ldots \hfill (32)$

and the representation of $s(k)$ is given by

$\displaystyle s(k) = \sum_{j=-\infty}^\infty d_j e^{i 2 \pi (k/T) j} \ \ \ k = 0, 1, \ldots, T-1 \hfill (33)$

The representation is valid for all $k$ if $s(k)$ is periodic with period $T$. Note that most of the $d_j$ are redundant because $d_{j+T} = d_j$, so that we can restrict our attention to the $T$ coefficients with indices $j = 0, 1, \ldots, T-1$.

Let’s define a discrete-time/continuous-frequency transformation by

$\displaystyle D(f) = \sum_{k=0}^{T-1} s(k) e^{-i 2 \pi f k} \hfill (34)$

where $f \in \mathbb{R}$. You can verify that

$\displaystyle d_j = \frac{1}{T} D(j/T) \hfill (35)$

In signal-processing practice, we are most often interested in the transform of a finite number of samples $T$. From our development so far, we can consider a set of equally spaced frequencies, or we can consider all frequencies. For digital signal processing applications, it is natural to focus on the former because they can be easily stored in computer memory. The sampled discrete-time Fourier transform, which is the discrete-time Fourier series, is therefore commonly called the discrete Fourier transform (DFT):

$\displaystyle S(j) = \sum_{k=0}^{T-1} s(k) e^{- i 2\pi jk/T}, \ \ \ j = 0, 1, \ldots, T-1 \hfill (36)$

and

$\displaystyle s(k) = \frac{1}{T} \sum_{j=0}^{T-1} S(j) e^{i 2\pi jk/T}, \ \ \ k = 0, 1, \ldots T-1. \hfill (37)$

This transform is most efficiently computed using an algorithm called the fast Fourier transform (FFT). From MATLAB’s help for fft.m, we see that it is identical to our definition:

Significance of the Fourier Transform in CSP

Although the Fourier transform for most mathematical models of communication signals does not exist (the DFT does though) , the transform plays a key role in the relationships between the temporal and spectral parameters. Recall our ‘golden diamond’ figure that relates all of the second-order and higher-order temporal and spectral parameters for stationary and cyclostationary signals:

We see here both Fourier series (green arrows) and Fourier transform (light purple arrows) relationships. The cyclic autocorrelation function is a Fourier coefficient of the time-varying autocorrelation function; the cyclic polyspectrum is the multi-dimensional Fourier transform of the cyclic temporal cumulant; the power spectrum and the conventional autocorrelation are a Fourier transform pair.

The discrete Fourier transform, which takes $N$ numbers in the time domain (typically) and produces $N$ numbers in the frequency domain, is the way we implement the various CSP algorithms that may be derived in continuous time and frequency, so both the continuous-time Fourier transform and the discrete-time Fourier transform are keys to CSP, the former for analysis and the latter for practice.

We’ve now developed sufficient tools and signal characterizations to begin our study of linear systems.